Informatik zum Dienstag

[1unitedpower]

ok, hab eine Lösung basierend auf deinen Typen.

Sehr schöne Lösung übrigens. Mal wieder effizienter als meine eigene 😉

Ich stolpere - rein logisch - vor allem über eine dusselige Eigenschaft von b0 (value als Shortcut für binaryToNumber):

Es ist: value(n) == value(b0(n)), d.h. b0(n) codiert die gleiche natürliche Zahl wie n.

Aber n und b0(n) sind nicht gleich, denn: value(b1(n)) != value(b1(b0(n)))

Man könnte das Problem auch auf Typ-Ebene beseitigen, indem man die binären Zahlen so beschränkt, dass an der signifikanteste Position immer die Ziffer b1 stehen muss. Dann hätte man eine normalisierte, eindeutige Kodierung. In TypeScript:

type BNatSuffix = Zero | B0 | B1 // Binärzahlen mit potenziell führenden Nullen
type BNat = Zero | B1            // Normalisierte Binärzahlen

Die Definitionen müssten entsprechend angepasst werden.

Hatten wir das Thema mit führenden Nullen, die Durcheinander anrichten, letztens nicht schonmal bei den milliardenstelligen Ziffernfolgen?

Am liebsten wäre mir ja, wenn diese Definitionen gelten würden, mit value(n) als der von n codierte Zahlenwert:

b0(zero)     := zero
value(b0(n)) := 2*value(n)
value(b1(n)) := 2*value(n)+1

Das löst auf jeden Fall das Problem, dass du oben beschrieben hast (ich gehe mal davon aus, dass die erste Zeile value(zero) = 0 lauten sollte). Die Binärkodierung ist damit aber auch nicht eindeutig: Jede Zahl kann dann beliebig viele abschließende b0-Ziffern haben.