Mid-Square-Methode

[Oleggs]

Hallo Leute.

Ich habe mit der suche leider nichts zu dem Thema gefunden und hoffe das ich gut genug gesucht habe.
Falls nicht tut es mir leid. Nebenbei bemerkt bin ich ein Anfänger und kenn mich mit Fachbegriffen, Methoden und ähnlichen nicht gut aus. Habe erst mit dem Programmieren angefangen und bitte um Verständnis, falls ich etwa nicht schnell verstehe.

Also es geht darum: Ich muss ein Programm schreiben, dass die Mid-Square-Methode anwendet.
Das ist ein Algorithmus der Zuffalszahlen berechnet. Es sollen Zahlen aus dem Bereich von 1000 bis 9999 genommen werden können. Es soll dann noch eine Ausgabe geben, die die Maximale mögliche Zahl ausgibt, also wiviele möglich sind ohne sich zu wiederholen und einmal die ganzen möglichen Zahlen ausgeben sollte.

Die methode: z.B. ich gebe eine zahl ein 4627 dann rechtet man 4637*4637 also mal sich selbst und dann kommt 21501769. Danach werden die 4 Zahlen aus der Mitte genommen und mit denen weitergerechnet. Also die 5017 und mit der Zahl weitergerechnet 5017*5017.

Falls ich mich irgendwo ungenau ausgedrückt haben sollte, würde ich es gerne genauer erläutern.
Danke schonmal für eure Hilfe.

 

[pappawinni]

Na gut.. und was hast du schon programmiert ?
Also ich denke etwa an folgendes

Nimm die Zahl
speichere sie in einer Liste
quadriere sie und mache eine Zeichenkette daraus.
extrahiere die Mittleren 4 Zeichen und mache daraus wieder eine Zahl
wiederhole das ganze, bis entweder 0 raus kommt, oder sich die Ursprungszahl einstellt,
sonst drehst du dich ewig.
Dann sortierst du vielleicht die Liste und gibst aus, was du ausgeben sollst.

 

[JohannisderKaeufer]

Hier versucht sich jemand an einer sehr ähnlichen Fragestellung.

http://www.java-forum.org/allgemeine-java-themen/144536-ziffern-existenz-ueberpruefen.html

 

[pappawinni]

Hm.. also ich hab jetzt auch festgesellt, dass man da jeweils die ganze Liste der bereits gefundenen Zahlen durchackern muss, um festzustellen, ob sich da was wiederholt.
Klar ist mir dennoch nicht, ob das Ende eintritt, bzw. eintreten soll, wenn quasi ein Zwischenergebnis nicht mehr im gewünschten Bereich von 1000-9999 liegt.
Aber egal, ich war mal wieder kreativ und hab was extraordinäres programmiert.

public class Test {	
	
	   public static void main(String[] args) {
	        
		    String maxlist="";
		    int nmax=0;
	        for (int i = 1000; i <= 9999; i++) {
               String zahlen = midSquare(String.valueOf(i));
               int n = zahlen.replaceAll("[0-9]","").length()+1;
               if (n > nmax) {
            	   nmax = n;
            	   maxlist = zahlen;
               }
               System.out.println(n+" "+zahlen);
	        }
            System.out.printf("Max %d Werte%n",nmax);
            System.out.printf("Zum Beispiel :%n%s",maxlist);
	   }
	   	   
	   private static String midSquare(String liste){
		   int b = liste.lastIndexOf(";");
		   int e;
		   if (b>=0) {
			   e = Integer.parseInt(liste.substring(b+1));
		   }
		   else {
			   e= Integer.parseInt(liste);
		   }
		   String mid = String.valueOf(e*e);
		   int f = mid.length();
		   int g = (f+1)/4;
		   mid = mid.substring(f-g*3,f-g);
		   if (Integer.parseInt(mid)<1000) return liste;
           if (liste.indexOf(mid)<0){
    		   return midSquare(liste+";"+mid);		           	   
           }
           else{
        	   return liste;
           }        	   
	   }
}

 

[Oleggs]

Das sieht schonmal gut aus pappawinni.
Es ist nur so, dass eine Zahl in der Konsole schon mit eingegeben werden muss und mit der als Startzahl gerechnet und so weiter genutzt wird. Also denke ich das ich da Integer.parseInt(args[0]) verwenden muss.
Soll eine Beliebe Zahl zwischen 1000 und 9999 eingegeben werden können die dann damit rechnet bis es sich wiederholt dann soll es anhalten. Müssen am ende alle Zahlen stehen auser die wiederholungszahlen.
Hatte bis jetzt noch nichts da ich nicht wusste wie ich das allgemein machen soll.

 

[Oleggs]

Es ist nur so, dass eine Zahl in der Konsole schon mit eingegeben werden muss und mit der als Startzahl gerechnet und so weiter genutzt wird. Also denke ich das ich da Integer.parseInt(args[0]) verwenden muss.
Soll eine Beliebe Zahl zwischen 1000 und 9999 eingegeben werden können die dann damit rechnet bis es sich wiederholt dann soll es anhalten.

Ich muss das mit dem Integer zurückziehen da es falsch von mir interpretiert wurde aus der aufgabe.
Es muss schon so sein das die alle Zahlen von 1000 bis 9999 mit dem verfahren berechnet werden sollen und jeweils die Maximalen möglichen Zahlen ausgegeben werden müssen + die Zahlen selbst.

 

[DerBobby]

Hi.

Ich versuche zur Zeit die Mid-Square-Methode in einem Programm umzusetzen, da ich die selbe Aufgabe bearbeite wie Oleggs. Allerdings wollte ich erstmal gucken, wie man nur die Mid-Square-Methode in Java schreibt.

Ich habe bisher folgenden Programmcode:

import java.util.ArrayList;

public class Zufallszahlen { 
    
    public static void main(String[] args) {

        ArrayList<Integer> liste = new ArrayList<Integer>();

        for (int i = 4637; i <= 9999;) {

            int a;
            int b;
            a = i * i;
            b = (a / 100) % 10000;
            liste.add(b);
            i = b;

            if (b >= 9000) 
               break;       
        }
        System.out.println(liste);
    }
}

Wie man sich denken kann, habe ich die 9000 am Ende willkürlich gesetzt, weil das Programm ansonsten ewig weiterrechnen würde. Meine Frage ist nun, wie ich bewerkstelligen kann, dass das Programm aufhört Zahlen in die Array Liste einzutragen, sobald sich eine Zahl wiederholt hat.

Danke für jede Hilfe.

 

[pappawinni]

Also ich hab die Methode nochmal etwas verändert, das soll es dann auch tun.
Wie oft du die Methode aufrufst, oder inwieweit Werte über Scanner oder Argumente eingelesen werden sollen, das sollte jetzt nicht wirklich das Problem darstellen. Da gibt es hier vermutl. hunderte an Beispielen..

	   private static String midSquare(String liste){
		   int posLast = liste.lastIndexOf(";");
		   String strLast;
		   if (posLast<0) {
			   strLast = liste.replace("![0-9]","");
		   }
		   else {
			   strLast = liste.substring(posLast+1);
		   }
		   int e = Integer.parseInt(strLast);
		   int len = strLast.length();
		   int g = (len+1)/2;
		   String mid = "00000000"+String.valueOf(e*e);
		   int f = mid.length();
		   mid = mid.substring(f-g-len,f-g);
           if (liste.indexOf(mid)<0){
    		   return midSquare(liste+";"+mid);		           	   
           }
           else{
        	   return liste;
           }        	   
	   }

Den zurück gelieferten String kann man anschliessend ggf. z.B. splitten und so die Werte in ein Array überführen, wenn es nötig wäre.
Man kann das alles aber natürlich auch ganz anders machen. Z.B. garnicht mit Strings arbeiten, sondern mit Modulo rechnen....mit ner echten Liste arbeiten...iterativ statt rekursiv...
Der Möglichkeiten sind viele.

[EDIT]
Als Beispiel-Ergebnis mal das:
Zum Beispiel :
6239;9251;5810;7561;1687;8459;5546;7581;4715;2312;3453;9232;2298;2808;8848;2871;2426;8854;3933;4684;9398;3224;3941;5314;2385;6882;3619;0971;9428;8871;6946;2469;0959;9196;5664;0808;6528;6147;7856;7167;3658;3809;5084;8470;7409;8932;7806;9336;1608;5856;2927;5673;1829;3452;9163;9605;2560;5536;6472;8867;6236;8876;7833;3558;6593;4676;8649;8052;8347;6724;2121;4986;8601;9772;4919;1965;8612;1665;7722;6292;5892;7156;2083;3388;4785;8962;3174;0742;5505;3050;3025;1506;2680;1824;3269;6863;1007;0140;0196;0384;1474;1726;9790;8441;2504;2700;2900;4100;8100;6100;2100

Daran lässt sich vielleicht zeigen, wo gegebenenfalls etwas falsch oder anders läuft, als bei anderen.
[/EDIT]

 

[pappawinni]

Wie man sich denken kann, habe ich die 9000 am Ende willkürlich gesetzt, weil das Programm ansonsten ewig weiterrechnen würde. Meine Frage ist nun, wie ich bewerkstelligen kann, dass das Programm aufhört Zahlen in die Array Liste einzutragen, sobald sich eine Zahl wiederholt hat.

Tja.. du musst wohl bei jedem Schritt die Liste durchlaufen und schauen, ob der neue Wert schon drin steht, bevor du den hinzufügst..wenn er schon drin steht.. dann Ende.

 

[DerBobby]

Tja.. du musst wohl bei jedem Schritt die Liste durchlaufen und schauen, ob der neue Wert schon drin steht, bevor du den hinzufügst..wenn er schon drin steht.. dann Ende.

Manchmal sieht man den Wald vor lauter Bäumen nicht. Danke. ^^

Habe es jetzt hinbekommen. Sieht folgendermaßen aus

import java.util.ArrayList;

public class Zufallszahlen { 
    
    public static void main(String[] args) {

        ArrayList<Integer> liste = new ArrayList<Integer>();

        for (int i = 4637; i <= 9999;) {

            int a;
            int b;
            a = i * i;
            b = (a / 100) % 10000;

            if (liste.contains(b)) 
               break;  

            liste.add(b);
            i = b;     
        }
        System.out.println(liste + "\n");
        System.out.println("Anzahl der Zufallszahlen: " + liste.size());
    }
}

Aber mal eine allgemeine Frage zur Mid-Square-Methode. Zählt die Anfangszahl, mit der die restlichen Zahlen erzeugt werden, auch schon zu den Zufallszahlen? Auf dem Arbeitsblatt wird das nicht ganz deutlich, vor allem weil da ein Fehler zu schein scheint.

Dort steht für die Zahl 4637 werden die 46 Zufallszahlen 4637 bis 4100 erzeugt. Dabei ist die letzte Zahl die 8100. Damit wären es 47 Zahlen, wenn die 4637 mitgezählt wird.

 

[pappawinni]

Also das Arbeitsblatt kenn ich ja jetzt nicht...hab ich doch hoffentlich nicht übersehen?
Für 4637 hätte ich:
4637;5017;1702;8968;4250;0625;3906;2568;5946;3549;5954;4501;2590;7081;1405;9740;8676;2729;4474;0166;0275;0756;
5715;6612;7185;6242;9625;6406;0368;1354;8333;4388;2545;4770;7529;6858;0321;1030;0609;3708;7492;1300;6900;6100;
2100;4100;8100

also 47 Werte, wenn man 4637 mitzählt.

 

[DerBobby]

Also das Arbeitsblatt kenn ich ja jetzt nicht...hab ich doch hoffentlich nicht übersehen?
Für 4637 hätte ich:
4637;5017;1702;8968;4250;0625;3906;2568;5946;3549;5954;4501;2590;7081;1405;9740;8676;2729;4474;0166;0275;0756;
5715;6612;7185;6242;9625;6406;0368;1354;8333;4388;2545;4770;7529;6858;0321;1030;0609;3708;7492;1300;6900;6100;
2100;4100;8100

also 47 Werte, wenn man 4637 mitzählt.

Nein, hast nichts übersehen. Hätte die gleiche Ausgabe wie du. Nur halt ohne 4637. Je nachdem, ob es mitgezählt werden soll oder nicht. Müsste ich wenn noch irgendwie einbauen bei mir. ^^

Kann es ja mal posten:

Pflichtaufgabe 32: In der Informatik werden häufig Zufallszahlen benötigt, z. B. um
Simulationen durchzuführen. Einer der ersten Algorithmen zur Erzeugung von Pseudozufallszahlen
wurde von John von Neumann in der 1940er Jahren entwickelt.
Dieser Algorithmus wird Mid-Square-Methode genannt. Er beginnt mit einer Zahl, die
als erste Zufallszahl genommen wird. Die Zahl wird quadriert. Anschließend werden die
mittleren Ziffern der Quadratzahl als nächste Zahl verwendet. Falls die Quadratzahl nicht
doppelt so lang ist, müssen vorne führende Nullen eingefügt werden. Als Beispiel betrachten
wir die ersten Schritte des Algorithmus mit der Anfangszahl 4637:
4637 --> 21501769 = 4637*4637
5017 --> 25170289 = 5017*5017
1702 --> 02896804 = 1702*1702
8968 --> 80425024 = 8968*8968
4250 --> 18062500 = 4250*4250
625 --> 00390625 = 625* 625
3906 --> ...
Meistens wiederholen sich nach relativ wenigen Schritten die Zufallszahlen. Aus diesem
Grund wird der Algorithmus heute kaum noch verwendet.
Mit der Anfangszahl 4637 erzeugt die Mid-Square-Methode die Folge der 46 Pseudozufallszahlen
4637, 5017, 1702, 8968, 4250, 625, 3906, . . . , 4100.
Schreiben Sie ein Java-Programm, das den Algorithmus auf alle vierstelligen Zahlen,
d. h. auf alle Anfangszahlen aus dem Bereich 1000, . . . , 9999, anwendet. Ihr Programm
soll ausgeben, wie viele verschiedene Zufallszahlen maximal von einer Anfangszahl erzeugt
werden können. Außerdem soll Ihr Programm diese Folge ausgeben. Falls es mehrere Anfangszahlen
geben sollte, die die maximale Anzahl der Zufallszahlen erzeugen, dürfen Sie
eine auswählen.

 

[pappawinni]

Also die Beschreibung ist doch relativ klar, wenn man von der Aussage 4637...4100 mal absieht.
Es wird unterschieden zwischen der Anfangszahl und den Pseudozufallszahlen, die daraus erzeugt werden.

Es wäre dann auch das geringste Problem, die erste Zahl zu behalten oder zu verwerfen.
Ich staune jetzt, dass ich die Aufgabe fast "richtig" gelöst habe, obwohl ich die Aufgabenstellung nicht so genau kannte.
Jetzt muss nur noch einer "Danke" und "Thema als erledigt markieren" drücken 😉

[EDIT]
Max. war bei mir übrigens bei der Anfangszahl 6239 (s.o.), woraus 110 Zahlen generiert wurden.
[/EDIT]

 

[DerBobby]

Also die Beschreibung ist doch relativ klar, wenn man von der Aussage 4637...4100 mal absieht.
Es wird unterschieden zwischen der Anfangszahl und den Pseudozufallszahlen, die daraus erzeugt werden.

Naja, ganz so klar ist es nicht. Oben steht " Er beginnt mit einer Zahl, die
als erste Zufallszahl genommen wird. Die Zahl wird quadriert". Das schließt ja z.B. die Anfangszahl 4637 mit ein. Unten wiederum steht "Ihr Programm
soll ausgeben, wie viele verschiedene Zufallszahlen maximal von einer Anfangszahl erzeugt
werden können". Das schließt die Anfangszahl nicht unbedingt mit ein. Ist halt etwas doof geschrieben.

 

[Oleggs]

Kannst du auch deine Endlösung reinstellen DerBobby?

 

[DerBobby]

Kannst du auch deine Endlösung reinstellen DerBobby?

Mehr als das oben gepostete habe ich leider noch nicht. Bin zur Zeit nicht sicher, wie ich weitermachen muss. Sollte ich es noch hinbekommen, poste ich es gerne. Nur heute dürfte das nichts mehr werden.

 

[pappawinni]

Du könntest dir das relativ einfach machen, indem du aus deiner jetzigen Main eine Methode machst und aus deiner neuen Main an diese Methode deine Zahlen nacheinander übergibt. Die Methode sollte dir dann die Länge deiner Liste zurückgeben. Dann kannst du prüfen, welche Zahl die größte Länge lieferte. Die kannst du dann erfassen und am Ende rufst du aus der Main einfach die entsprechende Zahl nochmal auf.

 

[pappawinni]

Kannst du auch deine Endlxxxxxg reinstellen DerBobby

Vielleicht tut es das auch schon.

import java.util.ArrayList;

public class Test {	
	
	   public static void main(String[] args) {
	        
		    int nmax=0;
		    int imax=0;
	        for (int i = 1000; i <= 9999; i++) {
	               int n = midSquare(i,true);
	               if (n > nmax) {
	            	   nmax = n;
	            	   imax = i;
	               }
		        }
            midSquare(imax,false);
	   }
	   	   
	    private static int midSquare(int startint,boolean quiet) {
	    	 
	        ArrayList<Integer> liste = new ArrayList<Integer>();
	 
	        for (int i = startint; true;) {
	 
	            int a;
	            int b;
	            a = i * i;
	            b = (a / 100) % 10000;
	 
	            if (liste.contains(b)) 
	               break;  
	 
	            liste.add(b);
	            i = b;     
	        }
	        if (!quiet){
	            System.out.printf("%d Werte für Anfangszahl %d%n",liste.size(),startint);
	            for (int entry:liste){
	            	System.out.printf("%5d",entry);
	            	i++;
	            	if (i%20 == 0) System.out.println();
	            }
		        System.out.println();
		   //     System.out.println(liste + "\n");
	        }
	        return liste.size();
	    }
	   
}

 

[pappawinni]

Ich hatte da noch die Idee immer dann die Liste auszugeben, wenn nmax, also die gefundene Anzahl Zufallszahlen erhöht wird.
Das kann man noch einigermassen überblicken, ist aber nicht nur ein Endergebnis, sondern zeigt auch ein wenig den Weg dort hin....

import java.util.ArrayList;

public class Test {	
	
	   public static void main(String[] args) {
	        
		    ArrayList<Integer> zufall;
	        int nmax=0;
		    int imax=0;
	        for (int i = 1000; i <= 9999; i++) {
	        	   zufall = midSquare(i);
	               int n = zufall.size();
	               if (n > nmax) {
	            	   nmax = n;
	            	   imax = i;
	       	           System.out.printf("%4d Werte für Anfangszahl %d%n",nmax,imax);
    	       	       printList(zufall);
	               }
		    }	        
       }
           
        	   	   
	    private static ArrayList<Integer> midSquare(int startint) {
	    	 
	        ArrayList<Integer> liste = new ArrayList<Integer>();
	 
	        for (int i = startint; true;) {
	 
	            int b = (i * i / 100) % 10000;
	 
	            if (liste.contains(b)) 
	               break;  
	 
	            liste.add(b);
                i = b;
	        }
	        return liste;
	    }
	    
	    
	    private static void printList(ArrayList<Integer> intList) {
	        int i=0;
	        for (int entry:intList){
	        	System.out.printf("%5d",entry);
	        	i++;
	        	if (i%20 == 0) System.out.println();
	        }	        	
            System.out.println("\n");	    	
	    }
	    
}

 

[DerBobby]

Ich habe auch nochmal versucht die Aufgabe alleine zu lösen (Danke an pappawinni für ein paar Inspirationen). Allerdings macht mein Programm nicht das, was es sollte. Irgendwo muss ich was falsch machen:

import java.util.ArrayList;

public class Zufallszahlen1 { 
    
    public static void main(String[] args) {

        for (int i = 1000; i <= 1005; i++) {
            Midsquare(i);
        }       
    }

    private static void Midsquare(int startint) {

        ArrayList<Integer> liste = new ArrayList<Integer>();
        int b;

            for (int i = startint; i <= 9999;) { 
                b = (i * i / 100) % 10000; 
 
                if (liste.contains(b)) {
                    Listen(liste);
                    liste.clear();
                    break;
                }

                liste.add(b);
                i = b;
            }         
    }
    private static void Listen(ArrayList<Integer> listea) {

    int min;
    int max;
    ArrayList<Integer> listeb = new ArrayList<Integer>();
    min = listea.size();
    max = listeb.size();

        if(max <= min) {
            listeb.clear();
            listeb.addAll(listea);
            max = listeb.size();
            listea.clear();
        }
    System.out.print(listeb + "" + max);
    }
    
}

Ist verständlich, was mein Programm machen soll?

 

[DerBobby]

So, ich habs jetzt. Nochmal danke an pappawini für einige Inspirationen. Hier der Code:

import java.util.*;

public class Zufallszahlen { 
    
    public static void main(String[] args) {

        List<Integer> zufall;
        List<Integer> ergebnis = new ArrayList<Integer>();
        int m = 0;

        for (int i = 1000; i <= 9999; i++) {
            zufall = Midsquare(i);

            if (zufall.size() >= ergebnis.size()) {
               m = i;
               ergebnis.clear();
               ergebnis.addAll(zufall);
            }

        zufall.clear();

        }
    System.out.println("\n" + "Maximal wird die Anzahl der Pseudozufallszahlen fuer die Zahl " + m + ". Die Anzahl der Zahlen betraegt " + ergebnis.size() + " ." + "Die Zahlenfolge lautet: " + "\n" + "\n" + ergebnis);
        
    }

    private static List<Integer> Midsquare(int startint) {

        List<Integer> liste = new ArrayList<Integer>();
        int b;

            for (int i = startint; i <= 9999;) { 
                b = (i * i / 100) % 10000; 
 
                if (liste.contains(b)) {
                    break;
                }

                liste.add(b);
                i = b;
            }
    return liste;        
    }
}