wolfgang-b
Goto Top

Algorithmus für Permutation für ein Mathematisches Problem

Hallo, ich hab vor 3 Tagen von meinen Physik Prof ein Problem erzählt bekommen, dazu muss ich sagen er ist ein kleiner Mathe-Freak. Ich möchte ihm das Problem gerne mit einem C++ Programm lösen.

Die Aufgabe ist, aus den Zahlen 9988776655443322 sollen zwei beliebige 8 Stellige Zahlen erstellt werden, Zahl_A und Zahl_B.
Gefragt ist nach der Kombination von Zahl_A und Zahl_B bei der die Rechnung:

(Zahl_A) - (2 x (Zahl_B)) das Ergebnis der kleinste Betrag ist.

Auf dem Papier komm ich auf eine Kombination bei der ich den Betrag 1 erhalte.

98872655 - ( 2 * (49436327) = 1

Leider fehlen mir die Mathematischen Erfahrung und Kenntnis das ich dies als einzige und kleinste Lösung beweisen könnte.

d1337748bab53872bf9611a21f08ac64

Nun wollte ich ein Programm schreiben jedoch ist die Laufzeit unvorstellbar groß wenn ich alle Kombinationen durchgehe,
(es sind 16! = 20922789888000 mögliche Kombinationen).

Vielleicht kann mir jemand eine Möglichkeit aufzeigen in der ich diese Anzahl vorab minimieren kann.

PS: Ich hab das ganze im Glauben angefangen das kann ja nicht so schwer sein, ich versuche aus der Problemstellungen zu lernen und meine beschiedenen c++ und Mathe Fähigkeiten zu erweitern, also zieht nicht zu hart mit mir ins Gericht.

Content-Key: 186585

Url: https://administrator.de/contentid/186585

Ausgedruckt am: 28.03.2024 um 13:03 Uhr

Mitglied: LianenSchwinger
LianenSchwinger 17.06.2012 aktualisiert um 13:05:27 Uhr
Goto Top
Hallo Wolfgang,

schönes Problem. face-smile

Zumindest ist schon mal klar, dass Zahl_B nicht größer als 49400000 sein kann (98800000 / 2) und kleiner als 22334455.
Ebenso kann Zahl_B nicht auf 5 enden, da die 0 nicht in der Zahlenmenge vorhanden ist.

Das sollte die Anzahl der Kombinationen schon ein wenig eingrenzen. face-smile
Jetzt einfach eine Schleife von 22334455 bis 49400000 und gut ist.

Gruß Jörg
Mitglied: Wolfgang-B
Wolfgang-B 17.06.2012 um 13:09:40 Uhr
Goto Top
Danke für deine Überlegungen, logisch hab ich deine Ausführung verstanden.

Mir fällt dazu aber nur ein das ich die generierte Zahl Prüfe ob sie größer 22334455 und kleiner 495xxxxx für die Zahl Zahl_B sind,ich spare mir zwar die Auswertung der zahlen dabei muss ich aber auch wieder alle Zahlenreihen generieren,(eine Zählerschleife bis 20922789888000 hat auf meinen Q9400@2,5GHz Gestern ca 23 Stunden gedauert).

Mein Problem ist es eher beim generieren keine Doppelten Zahlen zu erstellen, bzw aus erstellten zahlen möglichst viele Zahlenreihen auszuschließen.

z.B. 9988776655443322 auch gleich die 2233445566778899 zu betrachten, Problem hierbei wo ist der Schnittpunkt der Betrachtung.

Die Aufgabe ist auch so gestellt das man eben nicht mit fortlaufen Zahlen arbeiten kann (keine 1 und 0 gegeben) face-smile

Aber Danke fürs Helfen!
Mitglied: LianenSchwinger
LianenSchwinger 17.06.2012 um 13:17:13 Uhr
Goto Top
Also ich denke, dass die obige Schleife ausreichend ist mit der zusätzlichen Einschränkung, dass Zahlen, die auf 0, 1 oder 5 enden direkt übersprungen werden können.

Innerhalb der Schleife würde ich die Anzahl der einzelnen Zahlen ermitteln, wobei bei größer 2 für eine Zahl die Schleife wiederum abgebrochen werden kann.
Mitglied: jens2001
jens2001 17.06.2012 um 14:13:14 Uhr
Goto Top
Zumindest ist schon mal klar, dass Zahl_B nicht größer als 49400000 sein kann (98800000 / 2)

Zumindest ist schon mal klar, dass Zahl_B nicht größer als 49943883 sein kann (99887766 / 2)


Gruß Jens
Mitglied: Wolfgang-B
Wolfgang-B 17.06.2012 um 15:06:53 Uhr
Goto Top
Zitat von @LianenSchwinger:
Also ich denke, dass die obige Schleife ausreichend ist mit der zusätzlichen Einschränkung, dass Zahlen, die auf 0, 1
oder 5 enden direkt übersprungen werden können.

Innerhalb der Schleife würde ich die Anzahl der einzelnen Zahlen ermitteln, wobei bei größer 2 für eine Zahl
die Schleife wiederum abgebrochen werden kann.

Ich glaube ich werde hier gerade überschätzt:

Mein Ansatz währe es ein Array mit den vorgegebenen 16 Zahlen zu füllen.
Diese 16 Zahlen will ich mit einem (mir noch nicht klaren) Algorithmus in ein zweites Array Schreiben so das ich sukzessive alle Möglichkeiten (wenn möglich "-" den doppelte) durcharbeite.
Danach Teil ich das Array auf zwei mal 8 auf und führe die Rechnung durch!
Parallel zähle ich alle Ergebnisse kleiner 2 mit, und Schreibe alle Ergebnisse kleiner 1 mit den Kombination mit.

Abgesehen von der Laufzeit, ist mein Problem alle Möglichkeiten überhaupt mal in einer Logischen Reihenfolge auszugeben. Es kann ja erstmal nur mit der hälfte der Zahlen sein, um Zeit zu sparren und erstmal überhaupt was zum Rechnen zu bekommen bzw um die Gesetzmäßigkeiten der reihen zu ergründen.
Mitglied: LianenSchwinger
LianenSchwinger 17.06.2012 aktualisiert um 15:59:18 Uhr
Goto Top
Zitat von @jens2001:
> Zumindest ist schon mal klar, dass Zahl_B nicht größer als 49400000 sein kann (98800000 / 2)

Zumindest ist schon mal klar, dass Zahl_B nicht größer als 49943883 sein kann (99887766 / 2)


Gruß Jens

@ Jens

Für Deine Zahl_B kommen schon mehr als 2 "9" in Zahl_A und Zahl_B vor. Daher mein Ansatz 49400000.

Habe mal in Java auf die Schnelle ein Programm geschrieben (bin kein begnadeter Programmierer face-smile )

import java.util.*;

public class Test1 {

    // Die Aufgabe ist, aus den Zahlen 9988776655443322 sollen 
    // zwei beliebige 8 Stellige Zahlen erstellt werden, Zahl_A und Zahl_B.
    // Gefragt ist nach der Kombination von Zahl_A und Zahl_B bei der die Rechnung: 
    // (Zahl_A) - (2 x (Zahl_B)) das Ergebnis der kleinste Betrag ist.
    // 98872655  - (2 * 49436327) = 1

    public static void main(String args) {
        char tmp;
        int diff = 99999999;
        
        for (int i = 49438833; i>= 22334455; i--) {
            if (i%10 == 0 || i%10 == 1) {
                continue;
            } else {
                for (int j = 98877665; j >= 44668910; j--) {
                    if (j%10 == 0 || j%10 == 1) {
                        continue;
                    } else {
                        tmp = (String.valueOf(i) + String.valueOf(j)).toCharArray();
                    	
                        Arrays.sort(tmp);
                    	
                        if (String.valueOf(tmp).equals("2233445566778899")) {  
                            if (j - 2 * i >= 0 && j - 2 * i <= diff) {
                        	     diff = j - 2 * i;
	    		     System.out.println("Zahl A: " + String.valueOf(j));  
	    		     System.out.println("Zahl B: " + String.valueOf(i));  
	    		     System.out.println("Betrag: " + String.valueOf(j - 2 * i));  
                            }
                        }
                    }
                }
            }
        }
    }
}

Die initialisierung von i mit 49438833 folgt aus der für mich höchst möglichen Zahl_A von 98877665 dividiert durch 2.

Gruß Jörg
Mitglied: jens2001
jens2001 17.06.2012 um 15:57:02 Uhr
Goto Top
Für Deine Zahl_B kommen schon mehr als 2 "9" in Zahl_A und Zahl_B vor. Daher mein Ansatz 49400000.

Ja, schön.
Nur ist das für eine abschätzung einer oberen Grenze erst einmal ohne Belang.

Daher bleibt die Aussage "Zahl_B kleiner/gleich 49943883" erst einmal eine wahre Aussage.

Dagegen ist deine Aussage "Zahl_B kleiner/gleich 49400000" beweisbar falsch.
( Und wo hast du eigendlich die 5 "0" her???)

Gruß Jens
Mitglied: LianenSchwinger
LianenSchwinger 17.06.2012 um 16:02:59 Uhr
Goto Top
@Jens

meine ersten Annahmen musste ich nach reiflicher Überlegung schon korrigieren und komme jetzt zu anderen min und max für die beiden Zahlen (siehe Programm oben).

Die 5 kann natürlich vorkommen, hingegen die 0 und 1 am Ende von Zahl_A oder _B nicht, da diese nicht in der Vorgabe enthalten sind.

Gruß Jörg
Mitglied: LianenSchwinger
LianenSchwinger 17.06.2012 aktualisiert um 17:36:08 Uhr
Goto Top
Habe mein Programm noch mal verfeinert mit der Annahme, dass Zahl_A nicht kleiner als das doppelte von Zahl_B sein kann. Jetzt rennt das Programm und liefert mir nach einer Sekunde den 1. Treffer mit Betrag = 1. face-smile

Weitere Treffer wären

Zahl A: 98875325
Zahl B: 49437662
Betrag: 1
Zahl A: 98875265
Zahl B: 49437632
Betrag: 1
Zahl A: 98875253
Zahl B: 49437626
Betrag: 1
Zahl A: 98873525
Zahl B: 49436762
Betrag: 1
Zahl A: 98873255
Zahl B: 49436627
Betrag: 1
Zahl A: 98872655
Zahl B: 49436327
Betrag: 1
Zahl A: 98872553
Zahl B: 49436276
Betrag: 1
Zahl A: 98872535
Zahl B: 49436267
Betrag: 1
Zahl A: 98867525
Zahl B: 49433762
Betrag: 1
Zahl A: 98867255
Zahl B: 49433627
Betrag: 1
Zahl A: 98865527
Zahl B: 49432763
Betrag: 1
Zahl A: 98865275
Zahl B: 49432637
Betrag: 1
Zahl A: 98855327
Zahl B: 49427663
Betrag: 1
Zahl A: 98855273
Zahl B: 49427636
Betrag: 1
Zahl A: 98855267
Zahl B: 49427633
Betrag: 1
Zahl A: 98853527
Zahl B: 49426763
Betrag: 1
Zahl A: 98853275
Zahl B: 49426637
Betrag: 1
Zahl A: 98852753
Zahl B: 49426376
Betrag: 1
Zahl A: 98852735
Zahl B: 49426367
Betrag: 1
Zahl A: 98852675
Zahl B: 49426337
Betrag: 1

Hier mein Programm:

public class Test1 {

    // Die Aufgabe ist, aus den Zahlen 9988776655443322 sollen zwei beliebige 8 Stellige Zahlen erstellt werden, Zahl_A und Zahl_B.
    // Gefragt ist nach der Kombination von Zahl_A und Zahl_B bei der die Rechnung: 
    // (Zahl_A) - (2 x (Zahl_B)) das Ergebnis der kleinste Betrag ist.
	// 98872655  - (2 * 49436327) = 1

    public static void main(String args) {
        char tmp;
        int diff = 99999999;
        
        for (int i = 49438833; i>=22334455; i--) {
 //       	System.out.println(i);
        	
            if (i%10 == 0 || i%10 == 1) {
                continue;
            } else {
                for (int j = 98877665; j >= 2 * i; j--) {
                    if (j%10 == 0 || j%10 == 1) {
                        continue;
                    } else {
                    	tmp = (String.valueOf(i) + String.valueOf(j)).toCharArray();
                    	
                    	Arrays.sort(tmp);
                    	
                    	if (String.valueOf(tmp).equals("2233445566778899")) {  
                    		if (j - 2 * i <= diff) {
                        		diff = j - 2 * i;
                        		j = 2 * i + diff;
	    		                System.out.println("Zahl A: " + String.valueOf(j));  
	    		                System.out.println("Zahl B: " + String.valueOf(i));  
	    		                System.out.println("Betrag: " + String.valueOf(j - 2 * i));  
                    		}
                    	}
                    }
                }
            }
        }
    }
}

Gruß Jörg
Mitglied: LianenSchwinger
LianenSchwinger 17.06.2012, aktualisiert am 18.06.2012 um 11:18:19 Uhr
Goto Top
... es gibt übrigens 5448 Kombinationen mit Betrag = 1

Letzte Programmversion ohne vorheriges Wissen des kleinsten Betrags.
Laufzeit auf meinem Core2Duao T9600 mit 2,8 GHz 76 sec. face-smile

import java.util.*;

public class Aufgabe {

    // Die Aufgabe ist, aus der Zahlenmenge 9988776655443322 sollen zwei beliebige
    // 8 Stellige Zahlen erstellt werden, Zahl_A und Zahl_B.
    // Gesucht werden die Kombinationen aus Zahl_A und Zahl_B bei der die Rechnung:
    // (Zahl_A) - (2 x (Zahl_B)) als Ergebnis den kleinsten Betrag liefern.
    // Überlegungen:
    // max auf 98877665 gesetzt, da 99887766/2 = 49943883 bereits 4 mal die Zahl 9 enthält
    // zahl_a und zahl_b können nicht auf 0 oder 1 enden
    // zahl_a muss mindestens doppelt so groß wie zahl_b sein

    public static void main(String args) {
        char tmp;
        int  max = 98877665, min = 22334455, diff = 99999999, zahl_a;

        for (int zahl_b = max / 2; zahl_b >= min; zahl_b--) {
            // zahl_b kann nicht auf 0 oder 1 enden
            if (zahl_b % 10 == 0 || zahl_b % 10 == 1) {
                continue;
            } else {
                // solange diff nicht geändert wurde zähle zahl_a von max runter 
                zahl_a = diff == 99999999 ? max : 2 * zahl_b + diff;

                // solange zahl_a größer 2 * zahl_b
                while (zahl_a >= 2 * zahl_b) {
                    // zahl_b kann nicht auf 0 oder 1 enden
                    if (zahl_a % 10 == 0 || zahl_a % 10 == 1) {
                        zahl_a--;
                        continue;
                    } else {
                        // bilde aus zahl_a und zahl_b eine String und teile ihn in ein Char-Array
                        tmp = (String.valueOf(zahl_b) + String.valueOf(zahl_a)).toCharArray();

                        // sortiere das Char-Array
                        Arrays.sort(tmp);

                        // wenn das sortierte Char-Array der Zahlenmenge entspricht 
                        // und der Betrag <= diff ist
                        if (String.valueOf(tmp).equals("2233445566778899")) {  
                            if (zahl_a - 2 * zahl_b <= diff) {
                                diff = zahl_a - 2 * zahl_b;
                                System.out.println("Betrag: " + String.valueOf(zahl_a - 2 * zahl_b)   
                                                              + "\tZahl_A: " + String.valueOf(zahl_a)   
                                                              + "\tZahl_B: " + String.valueOf(zahl_b));  
                            }
                        }
                        zahl_a--;
                    }
                }
            }
        }
    }
}

Gruß Jörg
Mitglied: Wolfgang-B
Wolfgang-B 17.06.2012 um 19:40:34 Uhr
Goto Top
Vielen Dank für eure Hilfe!!!

Vor allem Jörg für deinen Code, ich versteh noch nicht alles, werde mich da aber noch rein Arbeiten (ist doch ein kleiner unterschied zu C++). Die Überlegung um die Durchläufe zu Reduzieren konnte ich jetzt auch endlich nachvollziehen.

Alles in allem sollte ich in den nächsten Tagen auch ein brauchbares C++ Programm auf die beine bekommen.

Danke!! und Schönen Abend noch!!!
Mitglied: Wolfgang-B
Wolfgang-B 17.06.2012 um 19:42:31 Uhr
Goto Top
Zitat von @LianenSchwinger:
... es gibt übrigens 5448 Ko´mbinationen mit Betrag = 1


Gab es eine Lösung die <1 ist?
Mitglied: LianenSchwinger
LianenSchwinger 17.06.2012 aktualisiert um 20:01:14 Uhr
Goto Top
Hallo Wolfgang,

gern geschehen. Mein Programm ist bestimmt nicht optimal, da ich auch nur Grundlagenerfahrung im programmiern habe.
In c++ wird es wohl ähnlich funktionieren, brauchst nur die passenden Funktionen in c++.

  • String.valueOF() wandelt eine Zahl in einen String oder auch ein Array aus Char in eine String
  • toCharArray() wandelt einen String in ein Array aus Char
  • Arrays.sort() sortiert ein Array

Der Rest dürfte Standard sein face-smile

Das Programm läuft auch nur so schnell, weil er relativ schnell einen Treffer landet und somit die Differenz schnell runterschrauben kann und somit den Startwert für die while-Schleife (Zahl_A). Wenn die Differenz dann einmal auf 1 runter ist muss natürlich nur noch Zahl_B * 2 + 1 und Zahl_B * 2 (für Betrag = 0) mit Zahl_A verglichen werden, denn ein höherer Betrag interessiert uns ja nicht mehr. Eine Übereinstimmung mit Betrag 0 gibt es nach meinem Programm übrigens nicht.

Gruß Jörg
Mitglied: LianenSchwinger
LianenSchwinger 17.06.2012 um 22:40:27 Uhr
Goto Top
Hallo Wolfgang,

Thread noch als gelöst markieren face-smile

G Jörg
Mitglied: DerWoWusste
DerWoWusste 18.06.2012 um 00:29:21 Uhr
Goto Top
Moin.
Eine Vorliebe für komische Probleme hat Dein Prof. Wenn Du Glück hast, kennt er das folgende Problem nicht und Du kannst ihn locken, sich daran zu versuchen. Es ist seit über 70 Jahren ungelöst: http://de.wikipedia.org/wiki/Collatz-Problem ;)