Rekursion vs. Iteration, Mathematische vs. Listen-Operationen

[donp]

Halo Daniel

s[i] ist bei einem String einfach das i. Zeichen. Von daher wird da nichts in ein Array umgewandelt.

Ach so, hab' ich mir fast gedacht, danke für den Tipp.

Über Umwandlungen muss man an der Stelle sowieso nicht mehr diskutieren, wenn man sich entschieden hat, das mit Strings zu machen, dann kann es nur noch um Verständlichkeit gehen, Effizienz hat man sowieso aufgegeben.

Das stimmt natürlich, aber eine gewisse Effizienz im Ausdruck gibt es schon. Wenn ich z.B. nicht selber fahren will, kann ich einen Bekannten bitten, dass er mich nach Hause fährt. Das wäre effizient, aber umständlich. Statt dessen kann auch einfach rufen "Taxi!" (koste es was es wolle), das wäre dann elegant.

Was das || angeht. || ist halt ein logisches Oder wie in den meisten Programmiersprachen auch mit etwas extra Semantik.

Das sehe ich eben anders. Wenn man verlangt, dass es wirklich nur ein logisches Oder ist, muss man extra einen gewissen Aufwand betreiben, nämlich "!!a||!!b" schreiben, statt "a||b".

function quersumme( n, b ) { return n < 10 ? n : n%b || b }
Das ist jetzt aber falsch. Wieso n < 10, wenn Du zu einer beliebigen Basis rechnest?

Äh ja, natürlich. Die Abfrage erübrigt sich eigentlich ohnehin, denn höchstwahrscheinlich ist das bereits im %-Operator mindestens genauso gut implementiert.

Den Zahlentheoretischen Zusammenhang auszunutzen ist natürlich wirklich Chic. Müsstest Du nur noch Beweisen (für den Zusammenhang Quersumme/teilbar durch (Basis - 1) <-> Zahl teilbar durch (Basis - 1) habe ich das irgendwann mal gemacht. Für diesen allgemeineren Zusammenhang dürfte das ähnlich klappen, sieht aber etwas fummelig aus.

Beweisen kann ich es eigentlich, aber an der mathematischen Ausformulierung hapert's.

Ich denke mir das so:

1. b sei die größte Ziffer eines Zahlensystems, also z.B. b=9 im Dezimalsystem.

2. Die Quersumme ergibt sich durch Addition einzelner Ziffern.
Davon gibt es insgesamt b Stück (1...9 = 9 Stück im Dezimalsystem), und die Zero, die aber nicht mitspielt, was die einstellige Quersumme betrifft, weil hier 1 = 10 = 100 usw. gilt. Es gibt nur also b mögliche Ergebnisse.

2. Die b möglichen Ergebnisse kann man sich kreisförmig angeordet vorstellen, z.B. auf die 9 im Dezimalsystem folgt wieder die 1 usw. bzgl. der einstelligen Quersumme.

3. Dieselbe Position im Keis wird immer dann erreicht, wenn man b Schritte weiter geht, d.h. b addiert oder subtrahiert. b ist also das neutrale Element der Addition bzgl. der einstelligen Quersumme.

4. Man kann also von der Ausgangszahl solange b subtrahieren, bis es nicht mehr weiter geht, weil das Ergebnis sonst negativ würde (das macht gerade der Modulo-Operator), denn da b unser neutrales Element der Addition ist, wird unsere Zahl dadurch nicht wirklich verändert. Wir erhalten so die gesuchte einstellige Quersumme, oder aber 0.

5. Im Falle von 0 als Rechenergenis der fortgesetzten Subtraktionen ist die Ausgangszahl durch b ohne Rest teilbar. Da die 0 im Kreis unserer möglichen Ergebnisse aber nicht vorkommt, kann man sie als 1 - 1 = b in unserem Kreis betrachten.

6. Fazit: Die gesuchte einstellige Quersumme ist entweder der b-Rest der Ausgangszahl n (d.h. n mod b) oder b selbst (falls n nurch b teilbar ist), was zu beweisen war.

Gruß, Don P