Übungen / Aufgaben zu Ruby
0 Lösungen
Validierung der abc-Vermutung
Die sogenannte abc-Vermutung sorgte in den letzten Jahren zu ungewöhnlich viel
Wirbel, Stress und Zank bei Zahlentheoretikern mit vielleicht sogar etwas skandalösem Touch.
Gelänge ein Beweis, dann könnte ein solcher in die Top-Charts der jüngeren Mathematikgeschichte
aufsteigen. Die abc-Vermutung wurde erst vor Kurzem aufgestellt (etwa 1985, also vor gut 30 Jahren,
was in der Mathematikgeschichte quasi nichts ist). Verblüffend für mich ist, dass man bei einem Beweis
damit die berühmte Große Fermatsche Vermutung von 1635, bewiesen erst 1993 auf mehreren hundert DIN-A4-Seiten
(wobei zuvor bereits mehr als 5.000 fehlgeschlagene Beweisversuche bekannt sind), auf einer einzigen
DIN-A4-Seite aufschreiben könnte und dass selbst ein Laie (wie ich) den Beweis verstehen würde.
Kommen wir (kurz) zum skandalösem Touch: 2012 reichte ein Japaner auf über 500 DIN-A4-Seiten einen (angeblichen)
Beweis der abc-Vermutung ein. Es stellte sich schnell heraus, dass er dabei (bewiesenes) Nebenwissen anwandte,
dass jedoch kaum bekannt war und in der Beweisführung hätte etwas mehr Platz und Erörterung finden sollen. Dies korrigierte
der Japaner dann wohl auch, womit sich sein Beweis auf über 1.000 Seiten aufblähte. Verständlich, dass sich damit kaum jemand
beschäftigte.
Darüber frustiert, beschimpfte der Japner zunächst die mathematische Welt als einen Haufen talentloser
Idioten (also nicht wörtlich, so etwas macht ein Japaner nicht, sondern sinnbildlich) und lud 2015 eine Reihe von Mathematikern,
die er selbst aussuchte und für ev. für fähig hielt, zu mehrtägigen Workshops ein. In ellenlangen Vorträgen erläuterte er
diesen Experten seinen Beweis der abc-Vermutung.
Jedenfalls sollen sich nach den Workshops einige der ausgesuchten Experten in die Richtung geäußert haben,
dass sie einen Ansatz zum Verständnis und zur Prüfung des Beweises sehen und sich an die Arbeit machen wollen.
Man hat abgeschätzt, dass, wenn man sich täglich etwa fünf Stunden damit beschäftigen würde, etwa in einem halben Jahr
durchsein könnte.
Nun gut, bis heute ist keiner durch, allerdings hat sich auch noch niemand geäußert, einen Fehler gefunden zu haben.
Somit ist alles noch in der Schwebe. Dass die jetzt beweissuchenden Experten zuvor vom Japaner gebrieft worden sind, stellt
allerdings das eigentlich Zweifelhafte und nicht Akzeptierbare dar, der Geruch von Bestechlichkeit ist nicht wegzuwischen.
Soweit die kleine Vorgeschichte. Natürlich wollen auch wir nicht die abc-Vermutung beweisen, soldern lediglich etwa überprüfen.
Würden wir bei der Überprüfung auch nur ein einziges Gegenbeispiel finden, so hätte es sich mit dem Beweis ja sowieso erledigt.
Aber keine zu große Vorfreude, ich denke weder ihr noch ich werden wahrscheinlich ein Gegenbeispiel finden.
Die ABC-Vermutung: Gegeben seien zwei positive Ganzzahlen a und b mit 0 < a < b und die außerdem teilerfremd (ggT(a, b) = 1) sind.
Diesen zwei Zahlen a und b sind zwei Eigenschaften zugeordnet, genannt "Summe" (c) und "Radikal" (rad).
Die Eigenschaft "Summe" ist weiter nichts als die ordinäre Summe von a und b, also c = a + b. Interessanter ist das "Radikal",
es ist eine spezielle Multiplikationsvorschrift für a, b und c. Würde man das ordinäre Produkt a * b * c bilden, so würde immer
gelten
a * b * c > c (es sei den a = b = 1, was aber wegen a < b untersagt ist).
Beim Radikal rad(a * b * c) werden jedoch nur alle unterschiedlichen Primzahlen, in die a * b * c zerlegt werden kann,
miteinander multipliziert.
Z. B. rad(100) = rad (2 * 2 * 5 * 5) = 2 * 5 = 10;
Bei einer so definierten Multiplikation ist es dann in der Tat möglich, dass sich für bestimmte positiv ganzzahlige
Tripel (a, b, c) wahre Ungleichungen bzw. Gleichungen der Form rad(a * b * c) <= c ergeben. Man nennt derartige Tripel abc-Treffer.
Allerdings gibt es "reativ wenige" solcher abc-Treffer. Es kann jedoch bewiesen werden, dass es immer noch unendlich viele sind
(deshalb machen Beschreibungen wie "reativ wenige" keinen Sinn in der Mathematik). So, bis jetzt ist alles noch "relativ" unspannend.
Spannend wird es, wenn man rad(a * b * c) potenziert, also (rad(a * b * c))^(1 + epsilon). Mit epsilon = 0 haben wir wieder den
Fall unendlich vieler mögliche abc-Treffer. Ist jedoch epsilon auch nur ein "My" größer als Null gibt es nur noch endlich viele abc-Treffer
(so die abc-Vermutung).
Wäre dies tatsächlich so (also bewiesen), zöge das einen ganz gewaltigen Schwanz an neuen mathematischen Erkenntnissen u. a. in der
Zahlentheorie nach sich (worauf wir hier natürlich nicht eingehen wollen, wer dbzgl. mehr wissen möchte, kann zunächst am Besten bei
Wikipedia einsteigen).
Die Programmieraufgabe lautet:
1.) Zähle alle abc-Treffer mit epsilon = 0 für die c < c_max (z. B. c_max = 10.000) ist.
2.) Führe das Gleiche durch mit wachsendem epsilon, z. B. epsilon = {0.1, 0.2 ... 0.9, 1.0} (interessant wäre zu erkunden, ob bei
steigendem epsilon die Anzahl der abc-Treffer linear abnimmt).
Viel Erfolg!
Wirbel, Stress und Zank bei Zahlentheoretikern mit vielleicht sogar etwas skandalösem Touch.
Gelänge ein Beweis, dann könnte ein solcher in die Top-Charts der jüngeren Mathematikgeschichte
aufsteigen. Die abc-Vermutung wurde erst vor Kurzem aufgestellt (etwa 1985, also vor gut 30 Jahren,
was in der Mathematikgeschichte quasi nichts ist). Verblüffend für mich ist, dass man bei einem Beweis
damit die berühmte Große Fermatsche Vermutung von 1635, bewiesen erst 1993 auf mehreren hundert DIN-A4-Seiten
(wobei zuvor bereits mehr als 5.000 fehlgeschlagene Beweisversuche bekannt sind), auf einer einzigen
DIN-A4-Seite aufschreiben könnte und dass selbst ein Laie (wie ich) den Beweis verstehen würde.
Kommen wir (kurz) zum skandalösem Touch: 2012 reichte ein Japaner auf über 500 DIN-A4-Seiten einen (angeblichen)
Beweis der abc-Vermutung ein. Es stellte sich schnell heraus, dass er dabei (bewiesenes) Nebenwissen anwandte,
dass jedoch kaum bekannt war und in der Beweisführung hätte etwas mehr Platz und Erörterung finden sollen. Dies korrigierte
der Japaner dann wohl auch, womit sich sein Beweis auf über 1.000 Seiten aufblähte. Verständlich, dass sich damit kaum jemand
beschäftigte.
Darüber frustiert, beschimpfte der Japner zunächst die mathematische Welt als einen Haufen talentloser
Idioten (also nicht wörtlich, so etwas macht ein Japaner nicht, sondern sinnbildlich) und lud 2015 eine Reihe von Mathematikern,
die er selbst aussuchte und für ev. für fähig hielt, zu mehrtägigen Workshops ein. In ellenlangen Vorträgen erläuterte er
diesen Experten seinen Beweis der abc-Vermutung.
Jedenfalls sollen sich nach den Workshops einige der ausgesuchten Experten in die Richtung geäußert haben,
dass sie einen Ansatz zum Verständnis und zur Prüfung des Beweises sehen und sich an die Arbeit machen wollen.
Man hat abgeschätzt, dass, wenn man sich täglich etwa fünf Stunden damit beschäftigen würde, etwa in einem halben Jahr
durchsein könnte.
Nun gut, bis heute ist keiner durch, allerdings hat sich auch noch niemand geäußert, einen Fehler gefunden zu haben.
Somit ist alles noch in der Schwebe. Dass die jetzt beweissuchenden Experten zuvor vom Japaner gebrieft worden sind, stellt
allerdings das eigentlich Zweifelhafte und nicht Akzeptierbare dar, der Geruch von Bestechlichkeit ist nicht wegzuwischen.
Soweit die kleine Vorgeschichte. Natürlich wollen auch wir nicht die abc-Vermutung beweisen, soldern lediglich etwa überprüfen.
Würden wir bei der Überprüfung auch nur ein einziges Gegenbeispiel finden, so hätte es sich mit dem Beweis ja sowieso erledigt.
Aber keine zu große Vorfreude, ich denke weder ihr noch ich werden wahrscheinlich ein Gegenbeispiel finden.
Die ABC-Vermutung: Gegeben seien zwei positive Ganzzahlen a und b mit 0 < a < b und die außerdem teilerfremd (ggT(a, b) = 1) sind.
Diesen zwei Zahlen a und b sind zwei Eigenschaften zugeordnet, genannt "Summe" (c) und "Radikal" (rad).
Die Eigenschaft "Summe" ist weiter nichts als die ordinäre Summe von a und b, also c = a + b. Interessanter ist das "Radikal",
es ist eine spezielle Multiplikationsvorschrift für a, b und c. Würde man das ordinäre Produkt a * b * c bilden, so würde immer
gelten
a * b * c > c (es sei den a = b = 1, was aber wegen a < b untersagt ist).
Beim Radikal rad(a * b * c) werden jedoch nur alle unterschiedlichen Primzahlen, in die a * b * c zerlegt werden kann,
miteinander multipliziert.
Z. B. rad(100) = rad (2 * 2 * 5 * 5) = 2 * 5 = 10;
Bei einer so definierten Multiplikation ist es dann in der Tat möglich, dass sich für bestimmte positiv ganzzahlige
Tripel (a, b, c) wahre Ungleichungen bzw. Gleichungen der Form rad(a * b * c) <= c ergeben. Man nennt derartige Tripel abc-Treffer.
Allerdings gibt es "reativ wenige" solcher abc-Treffer. Es kann jedoch bewiesen werden, dass es immer noch unendlich viele sind
(deshalb machen Beschreibungen wie "reativ wenige" keinen Sinn in der Mathematik). So, bis jetzt ist alles noch "relativ" unspannend.
Spannend wird es, wenn man rad(a * b * c) potenziert, also (rad(a * b * c))^(1 + epsilon). Mit epsilon = 0 haben wir wieder den
Fall unendlich vieler mögliche abc-Treffer. Ist jedoch epsilon auch nur ein "My" größer als Null gibt es nur noch endlich viele abc-Treffer
(so die abc-Vermutung).
Wäre dies tatsächlich so (also bewiesen), zöge das einen ganz gewaltigen Schwanz an neuen mathematischen Erkenntnissen u. a. in der
Zahlentheorie nach sich (worauf wir hier natürlich nicht eingehen wollen, wer dbzgl. mehr wissen möchte, kann zunächst am Besten bei
Wikipedia einsteigen).
Die Programmieraufgabe lautet:
1.) Zähle alle abc-Treffer mit epsilon = 0 für die c < c_max (z. B. c_max = 10.000) ist.
2.) Führe das Gleiche durch mit wachsendem epsilon, z. B. epsilon = {0.1, 0.2 ... 0.9, 1.0} (interessant wäre zu erkunden, ob bei
steigendem epsilon die Anzahl der abc-Treffer linear abnimmt).
Viel Erfolg!
0 Lösungen
Crowdfunding für Fibonacci-Uhr
Erneut FIBONACCI, jedoch diesmal in einem ganz anderen Zusammenhang.
Im Zuge von Crowdfunding ist in Kanada die sogenannte Fibonacci-Clock (Bild 1)
entwickelt und in die Produktion überführt worden.
(https://www.kickstarter.com/projects/basbrun/fibonacci-clock-an-open-source-clock-for-nerds-wit)
Es sollten für dieses Projekt innerhalb eines Monates (05 - 06/2015) 5.000 CAD
gesammelt werden (ca. 3.500 €), zusammengekommen sind aber sage und schreibe
(über) unglaubliche 125.000 €. Man lernt daraus, dass man mit einer guten (verrückten)
Idee manchmal auch einiges an Geld aquirieren kann.
Dabei ist an der Fibonacci-Clock nichts Kompliziertes dran. Im Grunde besteht sie
lediglich aus einem Display, das in fünf Quadrate mit unterschiedlicher
(variabler) Farbe und (fixer) Kantenlänge aufgeteilt ist.
Die Kantenlängen der Quadrate sind 1, 1, 2, 3 und 5, entsprechen also dem Beginn der
Fibonacci-Sequenz. Es lassen sich damit die Dezimalzahlen 0 ... 12 codieren.
Das Interessante an dem Display ist, dass man damit gleichzeitig
die Stunden und (teilweise) die Minuten darstellen kann. Dies geschieht mittels
wechselnder Farbcodierung der Quadrate und Aufaddition der den Quadraten zugeordnete
Fibonaccizahl. Die Farbe Rot steht für die Stunden, die Farbe Grün für die Minuten.
Wird ein Quadrat sowohl für die Stunden- als auch für die Minutensummation benötigt,
wird dies durch die Farbe Blau angezeigt (Bild 2). Weiß steht für "Nichtnutzung" des
Quadrates. Die Minutenzahl erhält man durch Multiplikation der Minutenzahlsumme mit 5,
somit ist die Genauigkeit der erfindungsgemäßen Uhr auf +- 2.5 Minuten begrenzt,
Vor- und Nachmittagszeiten sind identisch.
Mit den fünf Fibonaccizahlen lassen sich wie gesagt alle Werte von 0 bis 12 darstellen,
d. h. die Minutenanzeige "springt" lediglich alle fünf Minuten. Dies bedeutet allerdings nicht,
dass die Anzeige nicht schneller wechseln darf, denn es gibt mit den Ausnahmen für die
Null und die Zwölf für jede Zahl mehrere Möglichkeiten der Fibonacci-Codierung, die der
kanadische Erfinder auch in kurzen Intervallen und zufällig wechseln läßt.
Die Programmieraufgabe besteht darin, die Fibonacci-Clock mit einer Grafik-Applikation zu
simulieren. Der Minutenwechsel soll allerdings nicht im 5-Minuten-Takt, sondern sogar minütlich
erfolgen. Damit könnte man die Uhr vielleicht als Tester für Schnelldenker einsetzen.
Neben den vier Grundfarben des Erfinders (Weiß, Rot, Grün und Blau (Bild 3))werden also
vier weitere Farben zur Kodierung der fehlenden Additivzahlen 1, 2, 3 und 4 für den Minutenzähler
benötigt. Im Beispiel (Bild 4) sind es die Farben
Yellow (steht für Überlagerung mit Weiß),
Pink (steht für Überlagerung mit Rot),
Purple (steht für Überlagerung mit Grün) und
SkyBlue (steht für Überlagerung mit Blau)
Viel Erfolg!
Im Zuge von Crowdfunding ist in Kanada die sogenannte Fibonacci-Clock (Bild 1)
entwickelt und in die Produktion überführt worden.
(https://www.kickstarter.com/projects/basbrun/fibonacci-clock-an-open-source-clock-for-nerds-wit)
Es sollten für dieses Projekt innerhalb eines Monates (05 - 06/2015) 5.000 CAD
gesammelt werden (ca. 3.500 €), zusammengekommen sind aber sage und schreibe
(über) unglaubliche 125.000 €. Man lernt daraus, dass man mit einer guten (verrückten)
Idee manchmal auch einiges an Geld aquirieren kann.
Dabei ist an der Fibonacci-Clock nichts Kompliziertes dran. Im Grunde besteht sie
lediglich aus einem Display, das in fünf Quadrate mit unterschiedlicher
(variabler) Farbe und (fixer) Kantenlänge aufgeteilt ist.
Die Kantenlängen der Quadrate sind 1, 1, 2, 3 und 5, entsprechen also dem Beginn der
Fibonacci-Sequenz. Es lassen sich damit die Dezimalzahlen 0 ... 12 codieren.
Das Interessante an dem Display ist, dass man damit gleichzeitig
die Stunden und (teilweise) die Minuten darstellen kann. Dies geschieht mittels
wechselnder Farbcodierung der Quadrate und Aufaddition der den Quadraten zugeordnete
Fibonaccizahl. Die Farbe Rot steht für die Stunden, die Farbe Grün für die Minuten.
Wird ein Quadrat sowohl für die Stunden- als auch für die Minutensummation benötigt,
wird dies durch die Farbe Blau angezeigt (Bild 2). Weiß steht für "Nichtnutzung" des
Quadrates. Die Minutenzahl erhält man durch Multiplikation der Minutenzahlsumme mit 5,
somit ist die Genauigkeit der erfindungsgemäßen Uhr auf +- 2.5 Minuten begrenzt,
Vor- und Nachmittagszeiten sind identisch.
Mit den fünf Fibonaccizahlen lassen sich wie gesagt alle Werte von 0 bis 12 darstellen,
d. h. die Minutenanzeige "springt" lediglich alle fünf Minuten. Dies bedeutet allerdings nicht,
dass die Anzeige nicht schneller wechseln darf, denn es gibt mit den Ausnahmen für die
Null und die Zwölf für jede Zahl mehrere Möglichkeiten der Fibonacci-Codierung, die der
kanadische Erfinder auch in kurzen Intervallen und zufällig wechseln läßt.
Die Programmieraufgabe besteht darin, die Fibonacci-Clock mit einer Grafik-Applikation zu
simulieren. Der Minutenwechsel soll allerdings nicht im 5-Minuten-Takt, sondern sogar minütlich
erfolgen. Damit könnte man die Uhr vielleicht als Tester für Schnelldenker einsetzen.
Neben den vier Grundfarben des Erfinders (Weiß, Rot, Grün und Blau (Bild 3))werden also
vier weitere Farben zur Kodierung der fehlenden Additivzahlen 1, 2, 3 und 4 für den Minutenzähler
benötigt. Im Beispiel (Bild 4) sind es die Farben
Yellow (steht für Überlagerung mit Weiß),
Pink (steht für Überlagerung mit Rot),
Purple (steht für Überlagerung mit Grün) und
SkyBlue (steht für Überlagerung mit Blau)
Viel Erfolg!
0 Lösungen
Wieder (vielleicht) Erstaunliches vom Fibonacci
Gegeben sei eine Folge von N Strings der Längen 1, 2, 3 ... N. Jedes Char eines Strings beinhaltet lediglich entweder eine '0' oder eine '1',
jedoch dürfen zwei benachbarte Chars nicht beide eine '1' beinhalten.
Man zeige für N bis 25, dass die Anzahl möglicher (unterschiedlicher) Strings einer Längenklasse der Fibonacci-Reihe ab der 2 folgen
(2, 3, 5, 8 ...).
Also:
Länge = 1, zwei Möglichkeiten ("0", "1")
Länge = 2, drei Möglichkeiten ("00", "01", "10")
Länge = 3, fünf Möglichkeiten ("000", "001", "010", "100", "101")
...
Wieviele unterschiedliche Strings der oben genannten Art gibt es mit einer Stringlänge von 999?
jedoch dürfen zwei benachbarte Chars nicht beide eine '1' beinhalten.
Man zeige für N bis 25, dass die Anzahl möglicher (unterschiedlicher) Strings einer Längenklasse der Fibonacci-Reihe ab der 2 folgen
(2, 3, 5, 8 ...).
Also:
Länge = 1, zwei Möglichkeiten ("0", "1")
Länge = 2, drei Möglichkeiten ("00", "01", "10")
Länge = 3, fünf Möglichkeiten ("000", "001", "010", "100", "101")
...
Wieviele unterschiedliche Strings der oben genannten Art gibt es mit einer Stringlänge von 999?
0 Lösungen
Gray-Code bei Analog-Digital-Konvertierung
Bei der Analog-Digital-Konvertierung sollte die Abtastfrequenz in der Regel
wesentlich höher sein als die zeitliche Änderung des Messsignals (Nyquist-Kriterium).
Aus diesem Grunde ergeben zwei benachbarte Abtastungen zumeist entweder den gleichen (Digital)wert
oder einen um +/- 1 geänderten Wert. Ist dies nicht der Fall, so kann man mit sehr hoher
Wahrscheinlichkeit von einem Fehler bei der Messung (größer Rauscheinfluss) oder bei der Analog-
Digital-Konvertierung ausgehen.
Fehler bei der Analog-Digital-Konvertierung können bevorzugt dann entstehen, wenn bei einer
Messwertänderung um +/- 1 gleichzeitig mehrere Binärwerte switschen müssen. Z. B. bei einem
Messwert 7, der sich auf 8 ändert (7 -> 8) ändert sich der Binärwert von 0111 -> 1000, d. h.
es müssen quasi parallel vier Bits gekippt werden.
Um diese Fehlerquelle zu minimieren, werden die Messwerte zumeist nicht direkt in eine
Binärzahl konvertiert, sondern zunächst in den sogenannten Gray-Code. Der Gray-Code garantiert, dass sich bei
einer Messwertänderung um +/- 1 nur ein einziges Bit im Code ändert.
Das Kodierungsschema lässt sich u. a. leicht aus folgender Tabelle ableiten:
Dezimal Binär-Code Gray-Code
00 0000 0000
01 0001 0001
02 0010 0011
03 0011 0010
04 0100 0110
05 0101 0111
06 0110 0101
07 0111 0100
08 1000 1100
09 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
Wie ersichtlich, switscht bei der Gray-Kodierung lediglich ein Bit, wenn sich die Dezimal-Kodierung
um eine Einheit ändert.
Der Gray-Code geht auf einen Herren namens Frank Gray (1887 -1969) zurück, der sich den Code 1953
patentieren ließ, obwohl er in der Mathematik längst bekannt war. Aus meiner Sicht eine sehr bedenkliche Patenterteilung.
Die Programmierungsaufgabe besteht darin ein Programm zu schreiben,
das ein positives Integer entgegennimmt und die Gray-Code-Folge zurückgibt.
Optional kann auch die inverse Transformation programmiert werden.
wesentlich höher sein als die zeitliche Änderung des Messsignals (Nyquist-Kriterium).
Aus diesem Grunde ergeben zwei benachbarte Abtastungen zumeist entweder den gleichen (Digital)wert
oder einen um +/- 1 geänderten Wert. Ist dies nicht der Fall, so kann man mit sehr hoher
Wahrscheinlichkeit von einem Fehler bei der Messung (größer Rauscheinfluss) oder bei der Analog-
Digital-Konvertierung ausgehen.
Fehler bei der Analog-Digital-Konvertierung können bevorzugt dann entstehen, wenn bei einer
Messwertänderung um +/- 1 gleichzeitig mehrere Binärwerte switschen müssen. Z. B. bei einem
Messwert 7, der sich auf 8 ändert (7 -> 8) ändert sich der Binärwert von 0111 -> 1000, d. h.
es müssen quasi parallel vier Bits gekippt werden.
Um diese Fehlerquelle zu minimieren, werden die Messwerte zumeist nicht direkt in eine
Binärzahl konvertiert, sondern zunächst in den sogenannten Gray-Code. Der Gray-Code garantiert, dass sich bei
einer Messwertänderung um +/- 1 nur ein einziges Bit im Code ändert.
Das Kodierungsschema lässt sich u. a. leicht aus folgender Tabelle ableiten:
Dezimal Binär-Code Gray-Code
00 0000 0000
01 0001 0001
02 0010 0011
03 0011 0010
04 0100 0110
05 0101 0111
06 0110 0101
07 0111 0100
08 1000 1100
09 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
Wie ersichtlich, switscht bei der Gray-Kodierung lediglich ein Bit, wenn sich die Dezimal-Kodierung
um eine Einheit ändert.
Der Gray-Code geht auf einen Herren namens Frank Gray (1887 -1969) zurück, der sich den Code 1953
patentieren ließ, obwohl er in der Mathematik längst bekannt war. Aus meiner Sicht eine sehr bedenkliche Patenterteilung.
Die Programmierungsaufgabe besteht darin ein Programm zu schreiben,
das ein positives Integer entgegennimmt und die Gray-Code-Folge zurückgibt.
Optional kann auch die inverse Transformation programmiert werden.
1 Lösung
Symmetrische Primzahlen
Wieviele Primzahlen P < 1.000.000 sind rückwärts gelesen auch eine Primzahl, jedoch ungleich sich selbst?
Anmerkung: Die (Prim)zahlen 2, 3, 5, 7, 11 erfüllen nicht die Bedingungen (sind rückwärts gelesen sich selbst gleich),
als erste erfüllt die 13 die Bedingungen.
Anmerkung: Die (Prim)zahlen 2, 3, 5, 7, 11 erfüllen nicht die Bedingungen (sind rückwärts gelesen sich selbst gleich),
als erste erfüllt die 13 die Bedingungen.
0 Lösungen
Endliche Kettenbrüche rationaler Zahlen
Mit einem Kettenbruch K = a0 + 1/(a1 + 1/(a2 + 1 /(....))) - mit a0 als ganze Zahl und a1, a2 ... als
positve natürliche Zahlen ungleich Null - lässt sich bekanntlch jede reelle Zahl darstellen.
In der Praxis sind Kettenbrüche etwas unhandlich und man bevorzugt die Schreibweise
K = [a0; a1, a2, a3 ...]. Ist der Kettenbruch endlich, können damit alle rationale Zahlen beschrieben werden.
Die meisten Anwendungen finden Kettenbrüche in der Zahlentheorie, aber auch für Informatiker können sie
nutzbringend sein, insbesondere wenn man Rundungsprobleme umgehen muss. Z. B.
C#-Code
gibt als Ergebnisse 1E+15 und 1 hervor. Der Term (1.0 / 3) wird ohne jegliche Vorwarnung einfach verschluckt
und man bekommt gegebenenfalls am Ende einer Rechnung völligen Unfug heraus, ohne es zu merken
(einer der schlimmsten Fallstricke für den Programmierer).
Würde man x als Kettenbruch darstellen
x = 3.000.000.000.000.001 / 3 = [1.000.000.000.000.000; 3]
blieben alle Informationen erhalten und die Welt wäre wieder in Ordnung.
Nun, wir wollen keine komplette Algebra mit Kettenbruchobjekten entwickeln,
sonder lediglich folgende Aufgabenstellungen lösen:
Schreibe ein Programm, das
1.) zwei Zahlen (ZAEHLER und NENNER mit NENNER != 0) entgegennimmt
und eine entsprechende Kettenbruchdarstellung zurückgibt und
2.) diese Kettenbruchdarstellung wieder rücktransformiert.
Das Interessante an Teilaufgabe 2.) ist, dass sich der Bruch ZAEHLER/NENNER
automatisch selbst kürzt, also z. B. ZAEHLER = 50 und NENNER = 100 -> [0; 2],
rücktransformiet führt dies richtig zu ZAEHLER = 1 und NENNER = 2. Bei negativen
Zahlen ist allerdings nicht entscheidbar, ob der ZAEHLER oder der NENNER negativ ist
(möglicherweise ein neuer Fallstrick, das Programmiererleben ist manchmal sehr schwer).
positve natürliche Zahlen ungleich Null - lässt sich bekanntlch jede reelle Zahl darstellen.
In der Praxis sind Kettenbrüche etwas unhandlich und man bevorzugt die Schreibweise
K = [a0; a1, a2, a3 ...]. Ist der Kettenbruch endlich, können damit alle rationale Zahlen beschrieben werden.
Die meisten Anwendungen finden Kettenbrüche in der Zahlentheorie, aber auch für Informatiker können sie
nutzbringend sein, insbesondere wenn man Rundungsprobleme umgehen muss. Z. B.
C#-CodeDouble x = 1.0E+15 + 1.0 / 3; WriteLine(x.ToString()); WriteLine((x / 1.0E+15).ToString());
gibt als Ergebnisse 1E+15 und 1 hervor. Der Term (1.0 / 3) wird ohne jegliche Vorwarnung einfach verschluckt
und man bekommt gegebenenfalls am Ende einer Rechnung völligen Unfug heraus, ohne es zu merken
(einer der schlimmsten Fallstricke für den Programmierer).
Würde man x als Kettenbruch darstellen
x = 3.000.000.000.000.001 / 3 = [1.000.000.000.000.000; 3]
blieben alle Informationen erhalten und die Welt wäre wieder in Ordnung.
Nun, wir wollen keine komplette Algebra mit Kettenbruchobjekten entwickeln,
sonder lediglich folgende Aufgabenstellungen lösen:
Schreibe ein Programm, das
1.) zwei Zahlen (ZAEHLER und NENNER mit NENNER != 0) entgegennimmt
und eine entsprechende Kettenbruchdarstellung zurückgibt und
2.) diese Kettenbruchdarstellung wieder rücktransformiert.
Das Interessante an Teilaufgabe 2.) ist, dass sich der Bruch ZAEHLER/NENNER
automatisch selbst kürzt, also z. B. ZAEHLER = 50 und NENNER = 100 -> [0; 2],
rücktransformiet führt dies richtig zu ZAEHLER = 1 und NENNER = 2. Bei negativen
Zahlen ist allerdings nicht entscheidbar, ob der ZAEHLER oder der NENNER negativ ist
(möglicherweise ein neuer Fallstrick, das Programmiererleben ist manchmal sehr schwer).
0 Lösungen
Gewinn durch multiblen Devisenhandel
Derzeit gibt es weltweit über 160 offizielle Währungen, wobei ein gutes Dutzend voll konvertierbar ist.
In der Tabelle sind die Kaufopsionen für acht von ihnen aufgelistet (leider bessere Formatierung in dieser Ansicht wohl nicht möglich,
hier sollte Gustl dankenswerter Weise noch etwas tun):
EUR USD JPY GBP CHF CAD AUD NZD
EUR 1,0000 1,0795 120,184 0,8658 1,0701 1,4423 1,4141 1,5323
USD 0,9264 1,0000 111,329 0,8021 0,9909 1,3377 1,3120 1,4234
JPY 0,0083 0,0090 1,00000 0,0072 0,0089 0,0120 0,0118 0,0127
GBP 1,1545 1,2467 138,860 1,0000 1,2361 1,6687 1,6354 1,7718
CHF 0,9335 1,0083 112,310 0,8081 1,0000 1,3486 1,3216 1,4357
CAD 0,6933 0,7478 83,2120 0,5993 0,7402 1,0000 0,9816 1,0647
AUD 0,7061 0,7622 84,7950 0,6110 0,7545 1,0188 1,0000 1,0803
NZD 0,6503 0,7025 78,2000 0,5629 0,6965 0,9392 0,9208 1,0000
http://www.onvista.de/devisen/cross-rates/
Durch geschickte Ausnutzung von Kursschwankungen ist es denkbar, dass man durch einen gestaffelten
Kauf und Weiterverkauf von Währungen einen Gewinn erzielen kann. In der Praxis wird dieser Gewinn
im Falle kurzfristiger Aktionen allerdings sofort durch Transaktionsgebühren wieder aufgefressen. Für die
folgende Aufgabe seien Transaktionsgebühren unberücksichtigt.
Wir steigen mit einer beliebigen Einheit einer Währung ein und suchen einen Handelsweg, der uns am Ende
mehr abwirft, als wir am Anfang eingesetzt haben. Grundlage sei die momentane Währungstabelle,
auch cross-rates-table genannt.
Folgende Einschränkungen: Es müssen nicht alle möglichen Währungspaare in der Kette auftauchen, jedoch
jedes Paar höchstens einmal. Die letzte Transaktion muss wieder zu unsere Ausgangswährung zurückführen.
Aufgabe: Schreibe ein Programm, dass dir alle Transaktionswege mit positivem Ergebnis ausgibt bzw.,
wenn es keinen einzigen Weg gibt, dies entsprechend mitteilt.
In der Tabelle sind die Kaufopsionen für acht von ihnen aufgelistet (leider bessere Formatierung in dieser Ansicht wohl nicht möglich,
hier sollte Gustl dankenswerter Weise noch etwas tun):
EUR USD JPY GBP CHF CAD AUD NZD
EUR 1,0000 1,0795 120,184 0,8658 1,0701 1,4423 1,4141 1,5323
USD 0,9264 1,0000 111,329 0,8021 0,9909 1,3377 1,3120 1,4234
JPY 0,0083 0,0090 1,00000 0,0072 0,0089 0,0120 0,0118 0,0127
GBP 1,1545 1,2467 138,860 1,0000 1,2361 1,6687 1,6354 1,7718
CHF 0,9335 1,0083 112,310 0,8081 1,0000 1,3486 1,3216 1,4357
CAD 0,6933 0,7478 83,2120 0,5993 0,7402 1,0000 0,9816 1,0647
AUD 0,7061 0,7622 84,7950 0,6110 0,7545 1,0188 1,0000 1,0803
NZD 0,6503 0,7025 78,2000 0,5629 0,6965 0,9392 0,9208 1,0000
http://www.onvista.de/devisen/cross-rates/
Durch geschickte Ausnutzung von Kursschwankungen ist es denkbar, dass man durch einen gestaffelten
Kauf und Weiterverkauf von Währungen einen Gewinn erzielen kann. In der Praxis wird dieser Gewinn
im Falle kurzfristiger Aktionen allerdings sofort durch Transaktionsgebühren wieder aufgefressen. Für die
folgende Aufgabe seien Transaktionsgebühren unberücksichtigt.
Wir steigen mit einer beliebigen Einheit einer Währung ein und suchen einen Handelsweg, der uns am Ende
mehr abwirft, als wir am Anfang eingesetzt haben. Grundlage sei die momentane Währungstabelle,
auch cross-rates-table genannt.
Folgende Einschränkungen: Es müssen nicht alle möglichen Währungspaare in der Kette auftauchen, jedoch
jedes Paar höchstens einmal. Die letzte Transaktion muss wieder zu unsere Ausgangswährung zurückführen.
Aufgabe: Schreibe ein Programm, dass dir alle Transaktionswege mit positivem Ergebnis ausgibt bzw.,
wenn es keinen einzigen Weg gibt, dies entsprechend mitteilt.
0 Lösungen
Biorhytmus - zuerst Top oder Down?
Die Biorhytmen sind eine "Entdeckung" des Wiener Psychologen Swoboda und des Berliner Arzt Fließ zu Beginn des 20. Jahrhunderts.
Es soll beim Menschen drei Arten davon geben, den körperlichen Biorhythmus mit einer Periodendauer von 23 Tagen, den emotionalen
Biorhythmus (28 Tage) und den geistigen Biorhythmus (genannt Intellekt, Periodendauer 33 Tage). Die Existenz dieser Rhytmen ist
nicht bewiesen und eine praktische Nutzbarkeit kaum erkennbar. Allerdings sind sie sehr nützlich z. B. bei Ausreden. Wurde eine Prüfung
vermasselt, kann man das leicht auf einen schlechten Wert in der geistigen Periode schieben, war die Leistung auf dem Fußballplatz
miserabel, so lag es am Tiefpunkt beim körperlichen Schwingungswert.
Die Perioden beginnen mit dem Tag der Geburt - bereits ein Kritikpunkt, warum nicht mit dem Tag der Befruchtung oder noch früher?
Diesen gemeinsamen Nullpunkt aller drei Rhytmen wird man erst wieder in 21.252 Tagen erreichen, also nach dem 58. Geburtstag.
Ein gemeinsamer Nullpunkt ist allerdings von untergeordnetem Interesse, schlimmer wäre es, wenn alle drei Rhytmen gleichzeitig im Tiefpunkt
wären, also alle drei den Wert -1 hätten. Ein Glückstag wäre dagegen ein Tag, bei dem alle drei Werte den Topwert +1 hätten.
Die Frage lautet, was passiert im Leben zuerst, alle drei Werte DOWN (sehr nahe oder gleich -1) oder alle drei Werte TOP (sehr nahe oder
gleich +1). Nach wievielen Tagen (Jahren) tritt dies jeweils erstmalig ein?
Als Programmieraufgabe eignet sich die Biorhytmusproblematik gut zum Üben der Entwicklung einer GUI-Anwendung (siehe Abb.). Man kann
es sehr einfach in fast allen Programmiersprachen erlernen und realisieren. Wenn man dies so tut, bekommt man schnelle ein Gefühl dafür,
welche Programmiersprache einem von der Stilistik und Performanz hinsichtlich der grafischen Mensch-Maschine-Kommunikation am
symphatischsten ist.
Es soll beim Menschen drei Arten davon geben, den körperlichen Biorhythmus mit einer Periodendauer von 23 Tagen, den emotionalen
Biorhythmus (28 Tage) und den geistigen Biorhythmus (genannt Intellekt, Periodendauer 33 Tage). Die Existenz dieser Rhytmen ist
nicht bewiesen und eine praktische Nutzbarkeit kaum erkennbar. Allerdings sind sie sehr nützlich z. B. bei Ausreden. Wurde eine Prüfung
vermasselt, kann man das leicht auf einen schlechten Wert in der geistigen Periode schieben, war die Leistung auf dem Fußballplatz
miserabel, so lag es am Tiefpunkt beim körperlichen Schwingungswert.
Die Perioden beginnen mit dem Tag der Geburt - bereits ein Kritikpunkt, warum nicht mit dem Tag der Befruchtung oder noch früher?
Diesen gemeinsamen Nullpunkt aller drei Rhytmen wird man erst wieder in 21.252 Tagen erreichen, also nach dem 58. Geburtstag.
Ein gemeinsamer Nullpunkt ist allerdings von untergeordnetem Interesse, schlimmer wäre es, wenn alle drei Rhytmen gleichzeitig im Tiefpunkt
wären, also alle drei den Wert -1 hätten. Ein Glückstag wäre dagegen ein Tag, bei dem alle drei Werte den Topwert +1 hätten.
Die Frage lautet, was passiert im Leben zuerst, alle drei Werte DOWN (sehr nahe oder gleich -1) oder alle drei Werte TOP (sehr nahe oder
gleich +1). Nach wievielen Tagen (Jahren) tritt dies jeweils erstmalig ein?
Als Programmieraufgabe eignet sich die Biorhytmusproblematik gut zum Üben der Entwicklung einer GUI-Anwendung (siehe Abb.). Man kann
es sehr einfach in fast allen Programmiersprachen erlernen und realisieren. Wenn man dies so tut, bekommt man schnelle ein Gefühl dafür,
welche Programmiersprache einem von der Stilistik und Performanz hinsichtlich der grafischen Mensch-Maschine-Kommunikation am
symphatischsten ist.
0 Lösungen
Der Leidensweg eines Betrunkenen durch einen Tunnel
Ein leicht angetrunkener Mann muss für seinen Nachhauseweg durch einen Tunnel der Länge L (z. B. = 10 m)
und der Breite B (z. B. = 5.5 m). Zum Glück ist der Tunnel mit quadratischen Terrazzoplatten ausgelegt, nach denen
er sich zu richten versucht. Die Platten haben eine Gräße von 0.5 x 0.5 m². Somit besteht der Weg aus hier z. B. 20 Reihen a 11 Platten.
Der Mann startet in der ersten Reihe auf der Mittelplatte. Er möchte durch den Tunnel gehen, indem er bei jedem
Schritt auf eine benachbarte Platte tritt. Leider hat er in seinem Zustand völlig die Richtungsorientierung verloren,
so dass sein Schritt rein zufällig in eine der acht möglichen Richtungen verläuf, unabhängig davon,
dass zwei Wände links und rechts den Weg versperren. Wenn der Mann gegen eine der Wände läuft, gilt sein Versuch
den Tunnes zu durchlaufen als gescheitert, da er bewußtlos zu Boden stürzt und liegen bleibt. Als gescheiterter Versuch gilt auch,
wenn sein Weg ihn nicht zum Tunnelausgang, sondern nach einigen Schritten oder schon bereits beim ersten zurück vor den Eingang führt.
Die Frage lautet: Wie groß ist die Wahrscheinlichkeit dafür, dass er den Tunnel mit einem einzigen Versuch schadlos durchquert?
Die Wahrscheinlichkeit (Erwartungswert) soll anhand genügend vielen Simulationen abgeschätzt werden.
und der Breite B (z. B. = 5.5 m). Zum Glück ist der Tunnel mit quadratischen Terrazzoplatten ausgelegt, nach denen
er sich zu richten versucht. Die Platten haben eine Gräße von 0.5 x 0.5 m². Somit besteht der Weg aus hier z. B. 20 Reihen a 11 Platten.
Der Mann startet in der ersten Reihe auf der Mittelplatte. Er möchte durch den Tunnel gehen, indem er bei jedem
Schritt auf eine benachbarte Platte tritt. Leider hat er in seinem Zustand völlig die Richtungsorientierung verloren,
so dass sein Schritt rein zufällig in eine der acht möglichen Richtungen verläuf, unabhängig davon,
dass zwei Wände links und rechts den Weg versperren. Wenn der Mann gegen eine der Wände läuft, gilt sein Versuch
den Tunnes zu durchlaufen als gescheitert, da er bewußtlos zu Boden stürzt und liegen bleibt. Als gescheiterter Versuch gilt auch,
wenn sein Weg ihn nicht zum Tunnelausgang, sondern nach einigen Schritten oder schon bereits beim ersten zurück vor den Eingang führt.
Die Frage lautet: Wie groß ist die Wahrscheinlichkeit dafür, dass er den Tunnel mit einem einzigen Versuch schadlos durchquert?
Die Wahrscheinlichkeit (Erwartungswert) soll anhand genügend vielen Simulationen abgeschätzt werden.
0 Lösungen
Kaprekar-Konstanten für Hexadezimalzahlen
Man finde für Zahlen in Hexadezimaldarstellung (Basis 16) alle Kaprekar-Konstanten (sofern vorhanden)
für 3, 4 ... 8stellige Zahlen entsprechend dem Algorithmus aus Aufgabe #165. Die Methode ist
so zu formulieren, dass sie leicht für alle Zahlenbasen von 2 bis 256 verwendbar ist.
für 3, 4 ... 8stellige Zahlen entsprechend dem Algorithmus aus Aufgabe #165. Die Methode ist
so zu formulieren, dass sie leicht für alle Zahlenbasen von 2 bis 256 verwendbar ist.
0 Lösungen
Existiert die Kaprekar-Konstante?
Man weise numerisch nach, ob die Behauptung des indischen Mathematikers Kaprekar richtig ist.
Kaprekar hat folgendes behauptet (1949):
1.) Man nehme eine vierstellige Dezimalzahl D, wobei nicht alle vier Stellen identisch sein dürfen
(also 1111, 2222 etc. sind nicht erlaubt, aber z. B. 0001 ist erlaubt).
2.) D überführe man in zwei Zahle D1 und D2, indem bei D1 die Digits in absteigender und bei D2 in aufsteigender Reihenfolge
angeordnet werden (also z. B. D = 1724 -> D1 = 7421 und D2 = 1247; oder D = 1 -> D1 = 1000 und D2 = 1).
3.) Man subtrahiere nun D2 von D1; mit dem Ergebnis (Dneu = D1 - D2) wiederhole man Pkt. 2 durch Ersetzen von D durch Dneu solange,
bis sich nichts mehr ändert.
Die unglaubliche Behauptung ist, dass bei diesem Algorithmus stets das gleiche Ergebnis herauskommt (die sogenannte Kaprekar-Konstante),
egal, mit welchem D man beginnt.
Frage: Wie lautet die Kaprekar-Konstante?
Kaprekar hat folgendes behauptet (1949):
1.) Man nehme eine vierstellige Dezimalzahl D, wobei nicht alle vier Stellen identisch sein dürfen
(also 1111, 2222 etc. sind nicht erlaubt, aber z. B. 0001 ist erlaubt).
2.) D überführe man in zwei Zahle D1 und D2, indem bei D1 die Digits in absteigender und bei D2 in aufsteigender Reihenfolge
angeordnet werden (also z. B. D = 1724 -> D1 = 7421 und D2 = 1247; oder D = 1 -> D1 = 1000 und D2 = 1).
3.) Man subtrahiere nun D2 von D1; mit dem Ergebnis (Dneu = D1 - D2) wiederhole man Pkt. 2 durch Ersetzen von D durch Dneu solange,
bis sich nichts mehr ändert.
Die unglaubliche Behauptung ist, dass bei diesem Algorithmus stets das gleiche Ergebnis herauskommt (die sogenannte Kaprekar-Konstante),
egal, mit welchem D man beginnt.
Frage: Wie lautet die Kaprekar-Konstante?
0 Lösungen
Funktion über eine Natürliche Zahl
Man schreibe ein Funktion f(n) mit dem Definitionsbereich (n) und dem Wertebereich (f(n)) der natürlichen Zahlen.
Die Funktion f(n) sei wie folgt zu konstruieren:
1.) Schreibe die Zahlen 1 ... n in absteigender Reihenfolge nebeneinander: n, n - 1, n - 2 ... 5, 4, 3, 2, 1
2.) Wandle diese Zahlen in ihre binärer Darstellen ohne führende Nullen: n, n - 1, n -2 ... 101, 100, 11, 10, 1
3.) Entferne jetzt das Komma zwischen den Binärzahlen, die sich damit ergebende neue Binärzahl ist f(n).
Beispiel: f(6) => 6, 5, 4, 3, 2, 1 => 110, 101, 100, 11, 10, 1 => 11010110011101 = 13725 (dezimal).
Fragen: Welchen Wert hat f(99)?
Die Funktion f(n) sei wie folgt zu konstruieren:
1.) Schreibe die Zahlen 1 ... n in absteigender Reihenfolge nebeneinander: n, n - 1, n - 2 ... 5, 4, 3, 2, 1
2.) Wandle diese Zahlen in ihre binärer Darstellen ohne führende Nullen: n, n - 1, n -2 ... 101, 100, 11, 10, 1
3.) Entferne jetzt das Komma zwischen den Binärzahlen, die sich damit ergebende neue Binärzahl ist f(n).
Beispiel: f(6) => 6, 5, 4, 3, 2, 1 => 110, 101, 100, 11, 10, 1 => 11010110011101 = 13725 (dezimal).
Fragen: Welchen Wert hat f(99)?
