Zahlentheorie - Zahlenspielerei |
07.10.2010, 03:13 | osd | Auf diesen Beitrag antworten » |
Zahlentheorie - Zahlenspielerei Gegeben: beliebige Zahl, z.B. in Dezimalschreibweise 62502 Nun darf man zwischen die Ziffern ein oder mehrere + setzen, zum Beispiel 6+250+2 = 258 Und so weiter: 25+8 = 33 Und: 3+3 = 6 (also so lange bis eine Ziffer übrigbleibt). Behauptung (und dafür scheint es auch einen Beweis zu geben): Egal wie groß die ursprüngliche Zahl ist, gilt Folgendes: Nach einer FÜR ALLE MÖGLICHEN Zahlen FIXEN Anzahl von Schritten S bleibt eine Ziffer übrig. Das heißt: egal wie groß die Ausgangszahl ist, wenn man die Pluszeichen geschickt setzt, ist man nach maximal S Schritten fertig. Einfach ist Folgendes (diesmal Zahl in Binärschreibweise): 11111 Dann setzt man einfach ein Plus zwischen die vorletzte und letzte 1 und bekommt 100000 Dann ein Plus zwischen die 1 und die 0 und man bekommt 1 Für diese speziellen Zahlen (nur 1en in Binärschreibweise) ist man also immer nach zwei Schritten fertig, egal wie groß die Zahl ist. Doch wie löst man das allgemeine Problem? |
||
06.11.2010, 20:12 | bbp | Auf diesen Beitrag antworten » |
RE: Zahlentheorie - Zahlenspielerei meine zahl INPUT hat n ziffern für n>=3 gilt : 9*n<10^(n-1) (9*n ist die maximale quersumme für eine zahl mit n ziffern. diese quersumme hat mind. eine ziffer weniger als die zahl INPUT, da 10^(n-1) das infimum der zahlen mit n ziffern ist.). d.h. wir können die quersumme der zahl nehmen, bis sie nur noch 2 ziffern hat (unsere quersumme ist ja jetzt kleiner als 10^(3-1)=100). den rest kannst du noch machen (im schlimmsten fall bruteforce, sind ja nur noch endlich fälle). |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |