uebung4

Aus ProgrammingWiki
< BuK < IIm11 < Studenten < sistsche

Herleitung der Funktionen für x und y aus z = (x; y)

z =\left(\frac{(x+y)(x+y+1)}{2} \right) +y = t + y; w = x + y; x,y,z \in \N, w,t \in \R_{0}^{+}


t = z - y = \frac{w(w+1)}{2} = \frac{w^{2}+w}{2}

Die Lösung von w^{2} + w + 2t = 0

für positives w ist w = \frac{\sqrt{8t+1}-1}{2} Außerdem gilt t \leq z = t + w - x \leq t + w \leq t + w + 1 = \frac{w^{2}+w}{2} + w + 1 = \frac{(w+1)^{2} + (w+1)}{2}

Unter verwendung von z \leq \frac{(w+1)^{2} + (w+1)}{2} können wir w nach oben abschätzen.

w = \frac{\sqrt{8t+1}-1}{2} < \frac{\sqrt{8z+1}-1}{2}< w+1


Um die beiden natürlichen Zahlen x und y aus z zu gewinnen, ist als erstes w = \lfloor \frac{\sqrt{8z+1}-1}{2} \rfloor zu berechnen. Dann ergeben sich

t = \frac{w(w+1}{2} und y = z -t sowie

x = w - y