[Java] Fibonacci-Generator & Middle-Square-Algorithmus

AidS · 3. Januar 2010

Fibonacci-Generator & Middle-Square-Algorithmus

Hey Leutz,

ich wünsch euch allen erstmal ein gutes neues Jahr.

So nun mal zum Thema hier:

Ich soll einen Zufallszahlengenerator schreiben mit Hilfe eines Fibonacci-Generators bzw. des Middle-Square-Algorithmus.
Ansich versteh ich die Folge und den Algorithmus... jedoch weiß ich nicht wie man diese in Java verwirklichen soll bzw. kann.

Vlt habt ihr euch damit schonmal beschäftigt und könnt mir ein wenig weiterhelfen..

Mfg
AiDs

Anzeige

DeathBall · 3. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

deine aufgabenstellung ist nicht wirklich eindeutig
welches der beiden verfahren sollst du benutzen?...oder beide zusammen?
sollen die zufallszahlen einen bestimmten wertebreich haben?...also von bis?

AidS · 3. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

man kann es sich aussuchen..
eines der beiden eben.. somit kann man wählen was einem besser liegt...

DeathBall · 3. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

kannst du irgendwelche näheren infos zu input/output geben?

die fibonacci folge kann man theoretisch unendlich lang berechnen lassen und der middle-square-algorithmus braucht ne quelle

edit: hast du ne konkrete schriftliche aufgabenstellung bekommen?

Vlad_ · 3. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

na wikipedia gibt ein beispiel:

62 · 62 = 3844

da steht, man soll die mittleren zahlen nehmen. in diesem fall 84. du könntest jetzt mit dem fibonacci algorithmus jeweils zahlen paare erzeugen und diese mutliplizieren lassen mit dem mid square algorithmus. wie fibonacci ging, findest du sicher überall im netz.

aber jetzt zu mid square:

die zwei fibonacci zahlen nimmst du als long datentyp an, multiplizierst diese, castest das ergebnis zu einem string und schneidest dir die beiden mittleren werte aus. als rückgabe kannst du string weiterhin nutzen oder castest zurück zu long oder integer, damit du damit weiter arbeiten kannst.

ps. dein algorithmus ist nur so zufällig, wie zufällig auch dein input ist. wenn du fibonacci als input nutzt, dann ist das ziemlich vorhersagbar...

razor90 · 3. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

Ein Fibonacci-Generator ist eigentlich äußerst simpel.

Das Modul m würde ich den Anforderungen anpassen, da keine Werte größer m-1 ausgespuckt werden.
Dann brauchst du noch die Startwerte y1 und y2. Mindestens einer der beiden Werte sollte stets bei jeder Initialisierung anders sein, sonst spuckt der Generator immer die gleiche Zahlenfolge aus.

Ich kenne mich mit Java nicht aus, aber ich denke mal du könntest das einfach als Klasse realisieren. Im Konstruktor nimmst du die Startwerte und das Modul entgegen und weißt diese den privaten Variablen y1, y2 und m der Klasse zu.
Dann nur noch eine Funktion - nennen wir sie - Next() einbauen mit folgenden Pseudocode (in C++):

Code:

int Next()
{
 int ret = (y1 + y2) % m;
 y2 = y1;
 y1 = ret;
 return ret;
}

Sollte funktionieren

Beim Fibonacci-Generator reichen im günstigsten Fall 3 aufeinanderfolgende Zahlen um den Rest der Folge zu bestimmen. Man muss nur warten bis die Modulo-Operation zum Zuge kommt, also y3 kleiner als y1 ist. Dann m = y1+y2-y3.

mfg r90

AidS · 3. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

hier hab ich mal die Aufgabenstellung dazu..

Dazu verwenden wir einen Zufallszahlengenerator, der ausgehend von einem
Startwert Seed eine Folge von Zahlen berechnet. Dabei ist jede erzeugte
Zufallszahl selbst wieder der Seed-Wert für die nächste Zahl. Da die Ausführung
eines Programms immer deterministisch ist, ergibt sich für einen festen Seed
immer die gleiche Zahlenfolge. Man spricht daher von Pseudo-Zufallszahlen.
Es gibt viele mathematische Verfahren zur Erzeugung von Zufallszahlen. Da für
das Spiel nur wenige Zahlen benötigt werden, nämlich M, die Anzahl der Minen,
genügt ein einfacher Algorithmus, der schnell zu berechnen ist, etwa ein
Fibonacci-Generator oder aber auch der Middle-Square-Algorithmus von John
von Neumann.

(1)
Schreiben Sie ein Programm, das aus einem vorgegebenen Seed-Wert eine Folge
von 100 Zufallszahlen berechnet. Das Verfahren dürfen Sie selbst auswählen.
Speichern sie die erzeugten Zahlen in einem Vektor ab, zeigen Sie die Werte an
und bewerten Sie das Ergebnis.

Klicke in dieses Feld, um es in vollständiger Größe anzuzeigen.

@vlad: ja wie der algo funktioniert ist mir bewusst nur weiß ich nicht wie ich es implementieren kann dass er mir mit den beiden inneren ziffern weiter macht. bzw wie ich ihm sagen kann er soll die mittleren N(beliebigen) ziffern nehmen.
ansonsten wär der middle-square eine gute lösung.

DeathBall · 3. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

nimm Math.random()*10...da steht das verfahren dürfen sie selbst bestimmen ^^...welches steht da nicht

Code:

class Random
{
 private int iZufall;
 private int iAnzahl;

 public void setMine(int iAnzahl) //Übergabe der Anzahl der Minen
 {
 this.iAnzahl = iAnzahl;
 }

 public int getMine()
 {
 generateMine();
 return this.iZufall;
 }

 private generateMine()
 {
 int i = 0;

 for (i=0;i<iAnzahl;i++)
 {
 dZufall = (int)(Math.random()*10); //Generierung einer Zufallszahl zwischen 1 und 10
 }
 }
}

ob das jetzt so von der logik her in dein programm passt sei mal dahingestellt...aber wieso sollte man das rad neu erfinden?

Vlad_ · 3. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

um zu üben erzähl doch mal was du für einen ansatz hast, an dem können alle mitarbeiten... so aus dem nichts ist das schwer.

razor90 · 4. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

Hey, dann würde ich einen Mersenne-Twister nehmen, der mit dem Java-eigenen Zufallszahlengenerator (Kongruenzgenerator), welcher mit der aktuellen Uhrzeit initialisiert wurde, initialisiert wird und den erstmal ein paar Runden "warm" laufen lassen.
Ist zwar im Grunde ein totaler Overkill, liefert dafür jedoch gute Zufallszahlen und würde bestimmt beeindruckend wirken

Vom Mid-Square-Algorithmus würde ich an deiner Stelle die Finger lassen, denn der ist schlichtweg Grottenschlecht. String-Operationen haben in einem Pseudozufallszahlengenerator nichts zu suchen und außerdem ist nicht garantiert, dass der überhaupt 100 Zahlen ausspuckt... Wenn, dann wenigstens im Dualsystem implementieren, dadurch entfallen die String-Operationen und man kann sich die mittleren Bits einfach per ((x & 0x00FFFF00) >> 8 ) extrahieren. Dabei dürfen in meinem Beispiel aber niemals Werte kleiner 17 auftauchen, da der Generator sonst nur noch 0 ausspuckt.

klaiser · 4. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

Code:

 int Zahl = 0;
 int Zahl2 = 1;
 int Zahl3 = 0;
 int Durchgaenge;

 Durchgaenge = Math.random*10;

 for (int i = 2; i < Durchgaenge; i++) {
 Zahl3 = Zahl + Zahl2;
 Zahl = Zahl2;
 Zahl2 = Zahl3;
 }
 System.out.print(Zahl3);

Etwa so könnte die Fibonacci-Reihe geschrieben werden. Probier einfach mal, habe momentan keine Zeit zu testen.

Vlad_ · 4. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

Zitat von razor90: ↑

Hey, dann würde ich einen Mersenne-Twister nehmen, der mit dem Java-eigenen Zufallszahlengenerator (Kongruenzgenerator), welcher mit der aktuellen Uhrzeit initialisiert wurde, initialisiert wird und den erstmal ein paar Runden "warm" laufen lassen.
Ist zwar im Grunde ein totaler Overkill, liefert dafür jedoch gute Zufallszahlen und würde bestimmt beeindruckend wirken

Vom Mid-Square-Algorithmus würde ich an deiner Stelle die Finger lassen, denn der ist schlichtweg Grottenschlecht. String-Operationen haben in einem Pseudozufallszahlengenerator nichts zu suchen und außerdem ist nicht garantiert, dass der überhaupt 100 Zahlen ausspuckt... Wenn, dann wenigstens im Dualsystem implementieren, dadurch entfallen die String-Operationen und man kann sich die mittleren Bits einfach per ((x & 0x00FFFF00) >> 8 ) extrahieren. Dabei dürfen in meinem Beispiel aber niemals Werte kleiner 17 auftauchen, da der Generator sonst nur noch 0 ausspuckt.

Klicke in dieses Feld, um es in vollständiger Größe anzuzeigen.

ach stimmt. bitwise geht das schneller -.-

DeathBall · 4. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

@ vlad_: im prinzip hab ich das selbe gemacht wie klaiser nur objektorientiert und ohne weitere berechnung...der gibt eben nur ne zufallszahl berechnet mit der random funktion der math klasse zwischen 1 und 10 zurück

AidS · 9. Januar 2010

AW: Fibonacci-Generator & Middle-Square-Algorithmus

Also habs nun gschafft..

Hier mal meine Lösungen

Fibonacci-Generator:

Code:

public class Fibonacci {
 
 public static void main(String[] args){
 
 int Durchgaenge = 10;
 long fibn2 = 0; // Fibn2 entspricht Fib(n-1)
 long seed = 10;
 long fibn3 = 0; // Fibn3 entspricht Fib(n-2)
 long fibn = 0;

 while(Durchgaenge>0){
 long Zahl = 1;
 long Zahl2 = 1;
 long Zahl4 = 1;
 long Zahl5 = 1; 
 
 for (int i = 2; i < seed-1; i++) {
 fibn2 = (Zahl + Zahl2);
 Zahl = Zahl2;
 Zahl2 = fibn2;
 }
 
 for (int i = 2; i < seed-2;i++){
 fibn3 = (Zahl4 + Zahl5);
 Zahl4 = Zahl5;
 Zahl5 = fibn3; 
 }
 
 System.out.println("Fib-1:"+fibn2);
 System.out.println("Fib-2:"+fibn3);
 fibn = (fibn2 + fibn3)%73; //73 is das Modul (kann frei gewählt werden jedoch höher als Startwerte)
 
 System.out.printf("Die %d Zahl des Fibonacci-Generators ist: %d %n",seed,fibn);
 seed = fibn;
 Durchgaenge--;
 } 
 }
 }

Diese Version macht mehrere Durchgänge(10) wobei das ergebnis des Generators also neuer Seed genommen wird.

Und hier für den Middle-Square-Algorithmus:

Code:

public class MiddleSquare {
 
 public static void main(String[] args){
 
 long seed = 17;
 int n = 20;
 while(n > 0){
 long seedsqrt = 0;
 long first = 0;
 long teiler;
 long second;
 seedsqrt = seed * seed;
 teiler = (long) Math.log10(seedsqrt) + 1;
 teiler = teiler / 2;
 teiler = (long) Math.pow(10,teiler);
 first = (seedsqrt/ teiler)%10;
 second = (seedsqrt/(teiler/10))%10;
 
 System.out.println(seedsqrt + " " + first +" " + second);
 n--;
 seed = (first*10)+second;
 }
 }

}

Ich habe überall long genommen weil ihr sehen werdet die Zahlen werden schnell ziemlich groß^^ zumindest beim Fibonacci.

Mfg

Nützliche Suchen

[Java] Fibonacci-Generator & Middle-Square-Algorithmus

Videos zum Themenbereich