Kleinste Zahl x größer y für die gilt x mod z = 0

[Dr.Doom]

Huhu,

wie errechnet man die "kleinste Zahl x größer y für die gilt x modulo z = 0"?
Alles positive Ganzzahlen.

Aktuell inkrementiere ich x ständig um eins und prüfe die Bedingung... das muss irgendwie intelligenter gehen, aber ich komme nicht drauf (was mich nicht im geringsten verwundert :redface: ).

[Gast]

Hmm, mir fallen da 2 Dinge ein.

1)
Man geht durch alle Vielfachen von z, also x=1*z, x=2*z,...
Für die ist dann ja automatisch x mod z = 0.
Und prüft dann, ob das errechnete x > y ist.

Ob das schneller ist hängt natürlich davon ab, wie groß y jeweils ist,
da man ja zunächst einige Werte x < y erhält.
Aber man prüft dafür nicht jede Zahl, die größer als y ist.



2) Vielleicht noch besser so:

Zuerst y mod z teilen. -> Rest
Differenz bilden: d = z - Rest. (Also quasi, "Wieviel fehlt bei y zu einem weiteren Vielfachen von z noch ?")
Dann x = y + d.

Falls y mod z = 0 bereits sein sollte, kommt es darauf an, was die Aufgabe verlangt.
bei x >= y -> fertig, Lösung ist y
bei x > y -> Lösung ist y + z

Ich hoffe, ich habe mich da jetzt nirgends vertan.

[Gast]

Ach richtig, da wäre der Sonderfall z > y, dann ist x = z.

[Tiamat]

While-Loop über x solange x * z < y. Optimierbar mit Plus Operation statt Multiplikation.

[#44]

While-Loop über x solange x * z < y. Optimierbar mit Plus Operation statt Multiplikation.
Eine Schleife nützt da nichts. x * z ist konstant.

Soll x hier eine Zählvariable sein, dann ist x nicht das gesuchte x. Denn x * z < y ist falsch, bevor x > y wahr ist. Das gesuchte x wäre x * z.

[Tiamat]

int x = gesucht = y+1
int z = vorgegeben.
while(x * z <= y || x <= y) {
x+=1;
}

Optimierbar durch Ersetzung von x * z

Da brauch man nix mit modulo zu machen, alle Vielfachen(x) von z erfüllen die Bedingung x mod z == 0
Edit: Fehler korrigiert

[#44]

Die Schleifen-Bedingung ergibt immer false - die Schleife wird nie durchlaufen. Dein (falsches) Ergebnis wird dein anfängliches x sein.

[Gast]

[CODE]
alle Vielfachen(x) von z erfüllen die Bedingung x mod z == 0

Das ist unbestreitbar richtig.

Die Frage ist nur:
Ist es für die Aufgabe (Zitat: "Es muss intelligenter gehen") relevant, daß man durch das Durchprobieren aller möglichen Vielfachen u.U. jede Menge Durchläufe
macht, bevor man den Lösungswert erreicht ?


Wenn nein, ist die Lösung über die while-Schleife übersichtlicher.

Wenn ja, kann der Rechenweg mit modulo schneller sein.
Je nachdem wie die konkreten Zahlen in der Rechnung aussehen.

[Gast]

mach doch einfach
n = y div z

dann ist: x = (n+1)*z

[Tiamat]

Die Schleifen-Bedingung ergibt immer false - die Schleife wird nie durchlaufen. Dein (falsches) Ergebnis wird dein anfängliches x sein.

Ja hast recht, es gab einen Fehler bei der Bedingung.




Das ist unbestreitbar richtig.

Die Frage ist nur:
Ist es für die Aufgabe (Zitat: "Es muss intelligenter gehen") relevant, daß man durch das Durchprobieren aller möglichen Vielfachen u.U. jede Menge Durchläufe
macht, bevor man den Lösungswert erreicht ?


Wenn nein, ist die Lösung über die while-Schleife übersichtlicher.

Wenn ja, kann der Rechenweg mit modulo schneller sein.
Je nachdem wie die konkreten Zahlen in der Rechnung aussehen.



Ja auf jeden Fall. Der TS berichtete davon, jedes x(auch die nicht-Vielfachen) zu erhöhen und zu prüfen. jetzt beschränkt sich das auf die Vielfachen..vor allem wurde die teure Modulo Operation ersetzt

[#44]

Ja hast recht, es gab einen Fehler bei der Bedingung.
So wie es da steht, bricht die Schleife wieder ohne Durchlauf ab - mit anderer Vorbelegung für x würde sie durchlaufen werden. Allerdings nur bis x = y + 1.

[EPIC_FAIL]

Hm...

x = y + (z - (y%z)) ?

[Tiamat]

Verdammt :freak:, ich bin halt im Ferien-Mode :biggrin:

Ok noch mal..
also eine Bedingung ist x > y. Dann initialisieren wird x = y+1

y = vorgegeben
x = y+1
z = vorgegeben

while(x % z != 0)
x+=1

[#44]

Jetzt dürftest du so weit wie der TS im Ausgangspost sein.

[pest]

mach doch einfach
n = y div z

dann ist: x = (n+1)*z

Hm...

x = y + (z - (y%z)) ?

das ist beides das selbe und imo richtig