Funktionen durch Brüche < Knobelaufgaben < Café VH < Internes < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 14:09 Do 24.11.2011 | | Autor: | wieschoo |
Neulich bin ich über etwas nettes gestolpert und denke, dass es ganz interessant sein könnte.
Man hat ein 3-Tupel [mm]T=\left( \left(b_1,\ldots,b_m \right),\left(p_1,\ldots ,p_n \right),p_E \right)[/mm]
mit:
- [mm]\left(b_1,\ldots,b_m \right)[/mm] ist ein endliches Tupel von m Brüchen ([mm]b_i\in\IQ^{+}[/mm] (Rechenoperationen)
- [mm]\left(p_1,\ldots ,p_n \right)[/mm] sind n paarweise verschiedene Primzahlen mit [mm]p_i>2[/mm] (Register)
- [mm]p_E[/mm] ist eine Primzahl > 2 (Ausgaberegister)
Ablauf:
Bei Eingabe [mm](a_1,\ldots,a_n)[/mm] wird mit der Zahl [mm]Z:=2\cdot p_1^{a_1}\cdots p_n^{a_n}\in \IN[/mm] gestartet
Man sucht den ersten Bruch (kleinster Index) in [mm](b_1,\ldots ,b_m)[/mm] , sodass [mm]Z\cdot b_i[/mm] eine ganze Zahl ist, d.h. man sucht [mm]i_0:=\min\{i\quad | \quad Z\cdot b_i\in \IN\}[/mm] und setzt [mm]Z:=Z\cdot i_{i_0}[/mm] .
Das wiederholt man solange, wie es geht. Falls kein solcher Bruch [mm]b_i[/mm] mehr vorhanden ist stoppt dieses Vorgehen und der Exponent von [mm]p_E[/mm] in der Primfaktorzerlegung der Zahl [mm]Z\;[/mm] ist das Ergebnis.
Damit lassen sich auch komplexe kompliziertere Funktionen darstellen:
1. Beispiel: [mm]f(x):=x+1\;[/mm]
[mm]T=((\frac{3}{2}),(3),3)[/mm]
Bei Eingabe [mm]a_1=9[/mm] startet man mit [mm]Z=2\cdot {p_1}^{a_1}=2\cdot 3^9[/mm] und multipliziert mit diese Zahl mit [mm]\frac{3}{2}[/mm] und erhält [mm]3^{10}[/mm] mit Ausgabe 10, da das Ausgaberegister [mm] $p_E=3$ [/mm] ist und der Exponent von 3 im Ergebnis 10 lautet. Also 9+1=10.
2. Beispiel [mm]f(x,y):=x+y\;[/mm]
[mm]T=((\frac{3}{5}),(3,5),3)[/mm]
Bei Eingabe [mm]a_1=7[/mm] und [mm]a_2=2[/mm] ist [mm]Z=2\cdot 3^7\cdot 5^2[/mm] und wiederholtem Anwenden der Multiplikation mit [mm]\frac{3}{5}[/mm] erhält man schließlich [mm]2\cdot 3^9\cdot 5^0[/mm] und somit die Ausgabe "7+2=9".
Wer Lust hat sich zu versuchen, der kann folgende Funktionen basteln. Diese sind alle möglich.
- f(x,y)=x*y
- f(x,y)=max(0,x-y)
- f(x)=x-te ungerade Primzahl und f(0)=2
Achja dieser "Automat" (dieses Berechnungsverfahren) ist Turing-Vollständig. Man kann also theoretisch alles damit programmieren, was auch in vielen anderen bekannten Programmiersprachen funktioniert.
gruß
wieschoo
|
|
|
