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.
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.
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.
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.
Bitte markiere auch die Kommentare, die zur Lösung des Beitrags beigetragen haben
Content-ID: 186585
Url: https://administrator.de/forum/algorithmus-fuer-permutation-fuer-ein-mathematisches-problem-186585.html
Ausgedruckt am: 09.01.2025 um 22:01 Uhr
15 Kommentare
Neuester Kommentar
Hallo Wolfgang,
schönes Problem.
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.
Jetzt einfach eine Schleife von 22334455 bis 49400000 und gut ist.
Gruß Jörg
schönes Problem.
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.
Jetzt einfach eine Schleife von 22334455 bis 49400000 und gut ist.
Gruß Jörg
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.
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.
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
> 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 )
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
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
@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
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
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.
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:
Gruß Jörg
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
... 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.
Gruß Jörg
Letzte Programmversion ohne vorheriges Wissen des kleinsten Betrags.
Laufzeit auf meinem Core2Duao T9600 mit 2,8 GHz 76 sec.
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
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++.
Der Rest dürfte Standard sein
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
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
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
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 ;)
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 ;)