Top-Themen

AppleEntwicklungHardwareInternetLinuxMicrosoftMultimediaNetzwerkeOff TopicSicherheitSonstige SystemeVirtualisierungWeiterbildungZusammenarbeit

Aktuelle Themen

Administrator.de FeedbackApache ServerAppleAssemblerAudioAusbildungAuslandBackupBasicBatch & ShellBenchmarksBibliotheken & ToolkitsBlogsCloud-DiensteClusterCMSCPU, RAM, MainboardsCSSC und C++DatenbankenDatenschutzDebianDigitiales FernsehenDNSDrucker und ScannerDSL, VDSLE-BooksE-BusinessE-MailEntwicklungErkennung und -AbwehrExchange ServerFestplatten, SSD, RaidFirewallFlatratesGoogle AndroidGrafikGrafikkarten & MonitoreGroupwareHardwareHosting & HousingHTMLHumor (lol)Hyper-VIconsIDE & EditorenInformationsdiensteInstallationInstant MessagingInternetInternet DomäneniOSISDN & AnaloganschlüsseiTunesJavaJavaScriptKiXtartKVMLAN, WAN, WirelessLinuxLinux DesktopLinux NetzwerkLinux ToolsLinux UserverwaltungLizenzierungMac OS XMicrosoftMicrosoft OfficeMikroTik RouterOSMonitoringMultimediaMultimedia & ZubehörNetzwerkeNetzwerkgrundlagenNetzwerkmanagementNetzwerkprotokolleNotebook & ZubehörNovell NetwareOff TopicOpenOffice, LibreOfficeOutlook & MailPapierkorbPascal und DelphiPeripheriegerätePerlPHPPythonRechtliche FragenRedHat, CentOS, FedoraRouter & RoutingSambaSAN, NAS, DASSchriftartenSchulung & TrainingSEOServerServer-HardwareSicherheitSicherheits-ToolsSicherheitsgrundlagenSolarisSonstige SystemeSoziale NetzwerkeSpeicherkartenStudentenjobs & PraktikumSuche ProjektpartnerSuseSwitche und HubsTipps & TricksTK-Netze & GeräteUbuntuUMTS, EDGE & GPRSUtilitiesVB for ApplicationsVerschlüsselung & ZertifikateVideo & StreamingViren und TrojanerVirtualisierungVisual StudioVmwareVoice over IPWebbrowserWebentwicklungWeiterbildungWindows 7Windows 8Windows 10Windows InstallationWindows MobileWindows NetzwerkWindows ServerWindows SystemdateienWindows ToolsWindows UpdateWindows UserverwaltungWindows VistaWindows XPXenserverXMLZusammenarbeit
GELÖST

Algorithmus für Permutation für ein Mathematisches Problem

Frage Entwicklung C und C++

Mitglied: Wolfgang-B

Wolfgang-B (Level 1) - Jetzt verbinden

17.06.2012 um 11:42 Uhr, 5506 Aufrufe, 15 Kommentare, 1 Danke

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 - Klicke auf das Bild, um es zu vergrößern

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.
Mitglied: LianenSchwinger
17.06.2012, aktualisiert um 13:05 Uhr
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
Bitte warten ..
Mitglied: Wolfgang-B
17.06.2012 um 13:09 Uhr
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)

Aber Danke fürs Helfen!
Bitte warten ..
Mitglied: LianenSchwinger
17.06.2012 um 13:17 Uhr
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.
Bitte warten ..
Mitglied: jens2001
17.06.2012 um 14:13 Uhr
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
Bitte warten ..
Mitglied: Wolfgang-B
17.06.2012 um 15:06 Uhr
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.
Bitte warten ..
Mitglied: LianenSchwinger
17.06.2012, aktualisiert um 15:59 Uhr
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 )

01.
import java.util.*; 
02.
 
03.
public class Test1 { 
04.
 
05.
    // Die Aufgabe ist, aus den Zahlen 9988776655443322 sollen  
06.
    // zwei beliebige 8 Stellige Zahlen erstellt werden, Zahl_A und Zahl_B. 
07.
    // Gefragt ist nach der Kombination von Zahl_A und Zahl_B bei der die Rechnung:  
08.
    // (Zahl_A) - (2 x (Zahl_B)) das Ergebnis der kleinste Betrag ist. 
09.
    // 98872655  - (2 * 49436327) = 1 
10.
 
11.
    public static void main(String[] args) { 
12.
        char[] tmp; 
13.
        int diff = 99999999; 
14.
         
15.
        for (int i = 49438833; i>= 22334455; i--) { 
16.
            if (i%10 == 0 || i%10 == 1) { 
17.
                continue; 
18.
            } else { 
19.
                for (int j = 98877665; j >= 44668910; j--) { 
20.
                    if (j%10 == 0 || j%10 == 1) { 
21.
                        continue; 
22.
                    } else { 
23.
                        tmp = (String.valueOf(i) + String.valueOf(j)).toCharArray(); 
24.
                    	 
25.
                        Arrays.sort(tmp); 
26.
                    	 
27.
                        if (String.valueOf(tmp).equals("2233445566778899")) { 
28.
                            if (j - 2 * i >= 0 && j - 2 * i <= diff) { 
29.
                        	     diff = j - 2 * i; 
30.
	    		     System.out.println("Zahl A: " + String.valueOf(j)); 
31.
	    		     System.out.println("Zahl B: " + String.valueOf(i)); 
32.
	    		     System.out.println("Betrag: " + String.valueOf(j - 2 * i)); 
33.
34.
35.
36.
37.
38.
39.
40.
41.
 
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
Bitte warten ..
Mitglied: jens2001
17.06.2012 um 15:57 Uhr
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
Bitte warten ..
Mitglied: LianenSchwinger
17.06.2012 um 16:02 Uhr
@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
Bitte warten ..
Mitglied: LianenSchwinger
17.06.2012, aktualisiert um 17:36 Uhr
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:

01.
public class Test1 { 
02.
 
03.
    // Die Aufgabe ist, aus den Zahlen 9988776655443322 sollen zwei beliebige 8 Stellige Zahlen erstellt werden, Zahl_A und Zahl_B. 
04.
    // Gefragt ist nach der Kombination von Zahl_A und Zahl_B bei der die Rechnung:  
05.
    // (Zahl_A) - (2 x (Zahl_B)) das Ergebnis der kleinste Betrag ist. 
06.
	// 98872655  - (2 * 49436327) = 1 
07.
 
08.
    public static void main(String[] args) { 
09.
        char[] tmp; 
10.
        int diff = 99999999; 
11.
         
12.
        for (int i = 49438833; i>=22334455; i--) { 
13.
 //       	System.out.println(i); 
14.
        	 
15.
            if (i%10 == 0 || i%10 == 1) { 
16.
                continue; 
17.
            } else { 
18.
                for (int j = 98877665; j >= 2 * i; j--) { 
19.
                    if (j%10 == 0 || j%10 == 1) { 
20.
                        continue; 
21.
                    } else { 
22.
                    	tmp = (String.valueOf(i) + String.valueOf(j)).toCharArray(); 
23.
                    	 
24.
                    	Arrays.sort(tmp); 
25.
                    	 
26.
                    	if (String.valueOf(tmp).equals("2233445566778899")) { 
27.
                    		if (j - 2 * i <= diff) { 
28.
                        		diff = j - 2 * i; 
29.
                        		j = 2 * i + diff; 
30.
	    		                System.out.println("Zahl A: " + String.valueOf(j)); 
31.
	    		                System.out.println("Zahl B: " + String.valueOf(i)); 
32.
	    		                System.out.println("Betrag: " + String.valueOf(j - 2 * i)); 
33.
34.
35.
36.
37.
38.
39.
40.
41.
 
Gruß Jörg
Bitte warten ..
Mitglied: LianenSchwinger
17.06.2012, aktualisiert 18.06.2012
... 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.

01.
import java.util.*; 
02.
 
03.
public class Aufgabe { 
04.
 
05.
    // Die Aufgabe ist, aus der Zahlenmenge 9988776655443322 sollen zwei beliebige 
06.
    // 8 Stellige Zahlen erstellt werden, Zahl_A und Zahl_B. 
07.
    // Gesucht werden die Kombinationen aus Zahl_A und Zahl_B bei der die Rechnung: 
08.
    // (Zahl_A) - (2 x (Zahl_B)) als Ergebnis den kleinsten Betrag liefern. 
09.
    // Überlegungen: 
10.
    // max auf 98877665 gesetzt, da 99887766/2 = 49943883 bereits 4 mal die Zahl 9 enthält 
11.
    // zahl_a und zahl_b können nicht auf 0 oder 1 enden 
12.
    // zahl_a muss mindestens doppelt so groß wie zahl_b sein 
13.
 
14.
    public static void main(String[] args) { 
15.
        char[] tmp; 
16.
        int  max = 98877665, min = 22334455, diff = 99999999, zahl_a; 
17.
 
18.
        for (int zahl_b = max / 2; zahl_b >= min; zahl_b--) { 
19.
            // zahl_b kann nicht auf 0 oder 1 enden 
20.
            if (zahl_b % 10 == 0 || zahl_b % 10 == 1) { 
21.
                continue; 
22.
            } else { 
23.
                // solange diff nicht geändert wurde zähle zahl_a von max runter  
24.
                zahl_a = diff == 99999999 ? max : 2 * zahl_b + diff; 
25.
 
26.
                // solange zahl_a größer 2 * zahl_b 
27.
                while (zahl_a >= 2 * zahl_b) { 
28.
                    // zahl_b kann nicht auf 0 oder 1 enden 
29.
                    if (zahl_a % 10 == 0 || zahl_a % 10 == 1) { 
30.
                        zahl_a--; 
31.
                        continue; 
32.
                    } else { 
33.
                        // bilde aus zahl_a und zahl_b eine String und teile ihn in ein Char-Array 
34.
                        tmp = (String.valueOf(zahl_b) + String.valueOf(zahl_a)).toCharArray(); 
35.
 
36.
                        // sortiere das Char-Array 
37.
                        Arrays.sort(tmp); 
38.
 
39.
                        // wenn das sortierte Char-Array der Zahlenmenge entspricht  
40.
                        // und der Betrag <= diff ist 
41.
                        if (String.valueOf(tmp).equals("2233445566778899")) { 
42.
                            if (zahl_a - 2 * zahl_b <= diff) { 
43.
                                diff = zahl_a - 2 * zahl_b; 
44.
                                System.out.println("Betrag: " + String.valueOf(zahl_a - 2 * zahl_b)  
45.
                                                              + "\tZahl_A: " + String.valueOf(zahl_a)  
46.
                                                              + "\tZahl_B: " + String.valueOf(zahl_b)); 
47.
48.
49.
                        zahl_a--; 
50.
51.
52.
53.
54.
55.
}
Gruß Jörg
Bitte warten ..
Mitglied: Wolfgang-B
17.06.2012 um 19:40 Uhr
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!!!
Bitte warten ..
Mitglied: Wolfgang-B
17.06.2012 um 19:42 Uhr
Zitat von LianenSchwinger:
... es gibt übrigens 5448 Ko´mbinationen mit Betrag = 1


Gab es eine Lösung die <1 ist?
Bitte warten ..
Mitglied: LianenSchwinger
17.06.2012, aktualisiert um 20:01 Uhr
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

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
Bitte warten ..
Mitglied: LianenSchwinger
17.06.2012 um 22:40 Uhr
Hallo Wolfgang,

Thread noch als gelöst markieren

G Jörg
Bitte warten ..
Mitglied: DerWoWusste
18.06.2012 um 00:29 Uhr
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 ;)
Bitte warten ..
Neuester Wissensbeitrag
Windows 10

Powershell 5 BSOD

(8)

Tipp von agowa338 zum Thema Windows 10 ...

Ähnliche Inhalte
DSL, VDSL
Problem mit variernder Internetgeschwindigkeit (12)

Frage von schaurian zum Thema DSL, VDSL ...

Windows Netzwerk
gelöst Problem mit PSexec64 von Sysinternals (8)

Frage von MaxMoritz6 zum Thema Windows Netzwerk ...

Windows Server
gelöst Problem nach DC-Installation unter Server 2012 R2 (9)

Frage von manuel1985 zum Thema Windows Server ...

Heiß diskutierte Inhalte
LAN, WAN, Wireless
gelöst Server erkennt Client nicht wenn er ausserhalb des DHCP Pools liegt (28)

Frage von Mar-west zum Thema LAN, WAN, Wireless ...

Outlook & Mail
gelöst Outlook 2010 findet ost datei nicht (19)

Frage von Floh21 zum Thema Outlook & Mail ...

Netzwerkmanagement
gelöst Anregungen, kleiner Betrieb, IT-Umgebung (18)

Frage von Unwichtig zum Thema Netzwerkmanagement ...

Windows Server
Server 2008R2 startet nicht mehr (Bad Patch 0xa) (18)

Frage von Haures zum Thema Windows Server ...