Problem 1: Vielfache von 3 und 5

Gesucht ist die Summe aller Vielfachen von 3 und 5, die kleiner als 1000 sind! [das englische Original]

Besonders zu beachten ist dabei, dass es natürlich auch Zahlen gibt, die sowohl Vielfaches von 3 als auch von 5 sind, und somit aber nur einmal gezählt werden dürfen.

Bei der Lösung dieses Problems ist mir aufgefallen, dass es einen gewissen Rhythmus der Abstände zwischen den Vielfachen von 3 und 5 gibt:

Abstände zwischen Vielfachen von 3 und 5
Abstände zwischen Vielfachen von 3 und 5

Offensichtlich wiederholt das Muster der Abstände ab der Zahl 15, so dass man hier eine Lösung programmieren kann, die ca. 56% schneller ist, als wenn man alle Zahlen testen würde! Der Quellcode meiner Lösung sieht entsprechend so aus:

@Override
public String solve() {

    int[] diffs = new int[]{ 3, 2, 1, 3, 1, 2, 3 };

    int cur = 0, sum = 0, pos = 0;

    while( cur+diffs[ pos ] < 1000 ) {
        cur += diffs[ pos ];
        sum += cur;
        pos += ( pos < 6 ) ? 1 : -6;
    }

    return IO.i2s( sum );
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 1 kann man sich hier anschauen!

Übersicht Problem 2 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: