Komm nicht auf mathematische Lösung

Kusarr

Kusarr

Software-Overclocker(in)
Komm nicht auf mathematische Lösung

Servus,

folgendes Szenario:

Es gibt ein Punktesystem, in dem man entweder a(25),b(36),c(49) oder d(64) Punkte bekommt.
Ziel: Glatte 1000er bekommen aus Ausgangszahl x.
____Beispiel.: x=24745 -> 25000 d.h.: y = 255 Punkte sollen aus einer Kombination aus a b c d erreicht werden (wenn nicht möglich auf nächsten 1000er gehen).

Hoffe Problematik ist klar :)

Programmieren könnt ichs, wenn ich denn wüsste, wie ich überhaupt rangehen muss ... Formel etc.
Habt ihr nen tipp? :)

NACHTRAG: JAVA
 
Zuletzt bearbeitet:
AW: Komm nicht auf mathematische Lösung

Eine Möglichkeit, das zu programmieren, wäre folgendermaßen. Klingt zwar aus menschlicher Sicht nach einer Brute-Force-Variante, benötigt aber gar nicht so viel Rechenzeit (zumindest nicht, wenn es bei vier möglichen Konstanten bleibt).

1.) Berechne die Differenz, die vom aktuellen Stand x bis zum nächsten vollen Tausender-Stand fehlt. Nenne die Differenz y. Mögliche Formel dafür:

y = 1000 - (x % 1000);

Das % steht in C/C++ für die Modulo-Operation, also liefert den Rest der ganzzahligen Division.

2.) Berechne für die vier möglichen Einzel-Punktzahlen a, b, c und d, wieviele davon man jeweils bräuchte, um größer als die Differenz y zu werden. Also i_a = y/25, i_b = y/36, i_c = y/49, i_d = y/64. Das sind die Maximal-Zahlen, die jeweils für a, b, c und d ausprobiert werden.

3.) Lasse nun vier verschachtelte FOR-Schleifen laufen, wo für jede der Einzel-Punktzahlen jeweils z.B. 0 bis i_a "Stück" angenommen werden. So erreichst du alle relevanten Kombinationen, die eine Lösung ergeben könnten. Prüfe für jede mögliche Lösung, ob sie gerade gleich der gewünschten Differenz y ist:

for (z_a=0; z_a <= i_a; z_a++)
{
for (z_b=0; z_b <= i_b; z_b++)
{
for (z_c=0; z_c <= i_c; z_c++)
{
for (z_d=0; z_d <= i_d; z_d++)
{
value = z_a * 25 + z_b * 36 + z_c * 49 + z_d * 64;
if (value == y)
Fertig, brich Schleifen ab.
}
}
}
}

Edit: Das Forum hat meine Einrückung gelöscht, sorry. Ist so etwas unübersichtlich ^^

4.) Falls keine Lösung gefunden wurde, gehe wieder zu Schritt 2.), aber addiere vorher 1000 zum vorher gefundenen y, nimm also den übernächsten vollen Tausender, usw.

So findet man auf jeden Fall eine Lösung, falls eine existiert. Bietet natürlich sehr viel Spielraum zur Optimierung, falls Rechenzeit ein Kriterium ist. Aber wenn der Algorithmus nicht für hunderttausende verschiedene Werte von x laufen soll, ist es sowieso egal, ob er nun 100 µs oder 500 µs läuft ;)
 
AW: Komm nicht auf mathematische Lösung

Sollst du da jetzt ein Gleichungssystem aufstellen? Nach was ist denn genau gefragt?
 
AW: Komm nicht auf mathematische Lösung

3*b+3*c=255

Wie ich es gelöst habe? Pures Genie ^^
 
AW: Komm nicht auf mathematische Lösung

DKK007 schrieb:
Sollst du da jetzt ein Gleichungssystem aufstellen? Nach was ist denn genau gefragt?
Zum Vergrößern anklicken....
Einfach ein Weg, die obige Aufgagenstellung zu Programmieren

@ Brehministrator: cool danke, is schon mal was :)
äh und achja, benutze Java, wobei es jetz in dem falle fast gleich ist. habs oben ergänzt.

pronde schrieb:
3*b+3*c=255

Wie ich es gelöst habe? Pures Genie ^^
Zum Vergrößern anklicken....
Gut, ich hoffe du hast n paar tage Zeit, um mir alle möglichen Kombinationen von y=0..999 zu sagen ;)
 
AW: Komm nicht auf mathematische Lösung

Kusarr schrieb:
äh und achja, benutze Java, wobei es jetz in dem falle fast gleich ist. habs oben ergänzt.
Zum Vergrößern anklicken....

Bäh, Java... Nein, ist ja nicht so gemeint. Ich bin nur als jahrelanger C/C++-Programmierer kein so großer Fan von Java :D Die Syntax ist ja zum Glück nahezu identisch. Was ich oben schrieb, trifft alles auch unverändert auf Java zu :)
 
AW: Komm nicht auf mathematische Lösung

Brute Force ist immer ein Mittel, gründlich Nachdenken ist aber meist besser :)

Was an deiner Zahlenkombi 25,36,49,64 auffällt ist, dass um dein Problem zu lösen lediglich die 49 gebraucht wird.

Du kannst mit Vielfachen der 49 modulo 1000 jede Zahl von 0..999 abbilden, mehr ist nicht benötigt um das Problem, so wie du es gestellt hast, zu lösen. Kann an auch gerne ausprobieren z.B. mit folgendem Code (sorry, C-style)

Code: 
[COLOR=#808000]for[COLOR=#000000](int [COLOR=#000000]i[COLOR=#000000]=[COLOR=#000080]0[COLOR=#000000];[COLOR=#000000]i[COLOR=#000000]<[COLOR=#000080]1000[COLOR=#000000];[COLOR=#000000]i[COLOR=#000000]++)[COLOR=#000000]{  [COLOR=#808000]int[COLOR=#000000] k[COLOR=#000000]=[COLOR=#000080]0[COLOR=#000000];[COLOR=#808000]  while[COLOR=#000000]((([COLOR=#000000]k[COLOR=#000000]*[COLOR=#000080]49[COLOR=#000000])%[COLOR=#000080]1000[COLOR=#000000])!=[COLOR=#000000]i[COLOR=#000000])[COLOR=#000000]{[COLOR=#000000]k[COLOR=#000000]++;}  printf[COLOR=#000000]([COLOR=#008000]"%d:[COLOR=#008000]%d[COLOR=#008000](%d[COLOR=#008000]*[COLOR=#008000]49[COLOR=#008000]=[COLOR=#008000]%d[COLOR=#008000]->[COLOR=#008000]mod[COLOR=#008000]1000[COLOR=#008000]=[COLOR=#008000]%d)\n"[COLOR=#000000],[COLOR=#000000]i[COLOR=#000000],[COLOR=#000000]k[COLOR=#000000],[COLOR=#000000]k[COLOR=#000000],[COLOR=#000000]k[COLOR=#000000]*[COLOR=#000080]49[COLOR=#000000],([COLOR=#000000]k[COLOR=#000000]*[COLOR=#000080]49[COLOR=#000000])%[COLOR=#000080]1000[COLOR=#000000]);[COLOR=#000000]}

Entsprechend kannst du eine Lösung für das Problem (Startpunkt "x", zu überbrückende Differenz modulo 1000 "y") um obigen Ansatz herum programmieren.


Eine Abwandlung des Problems wäre "Nennen sie ALLE Kombinationen aus a,b,c,d, welche das Problem lösen", welche garnicht so weit ab davon liegt.
Hierzu ist es sehr sinnvoll sich anzusehen, wann sich Vielfache deiner Zahlen modulo 1000 wiederholen. Das wären für deine Zahlen:

a(25): Nach 40 Vielfachen -> (41*25)%1000 == (1*25)%1000, entsprechend 42*... == 2*... etc.
b(36): Nach 250 Vielfachen
c(49): Nach 1000 Vielfachen(wie ja schon oben beschrieben)
d(64): Nach 125 Vielfachen

Jetzt kannst du alle Kombinationen dieser Vielfachen in diesen Grenzen durchgehen (nach weiter oben genannter 4fach for Schleife z.B.) und dein jeweiliges Ergebnis für y wegschreiben, z.B. in einen verschachtelten Array Vector<Vector<struct> > der Größe 1000, dein struct besteht natürlich aus den entsprechenden Vielfachen von a,b,c und d.
So gelangst du am Ende auf alle möglichen Kombinationen (+deren Vielfache natürlich) von Vielfachen deiner Zahlen vom Startwert bis zu einem Tausender.
 
AW: Komm nicht auf mathematische Lösung

habs etz mal so in etwa probiert und funktioniert nich. es gibt in etwa folgendes aus: "[I@659e0bfd"

hier mein Konstrukt:
erstertest.png

liegt wohl an der array-rückgabe iwas is da falsch :/
 
AW: Komm nicht auf mathematische Lösung

dann speicher das array einfach oben als private und geb es dann aus...

EDIT:
kA ob Java eine Array -> String Konverter hat der kein Mist baut bzw nicht das tut was man vermutet...
 
AW: Komm nicht auf mathematische Lösung

okay habs hinbekommen :)
erst ma danke für die Hilfe. :daumen:

erstertest.png

Änderungen:
- In der Ausgabe vorher einfach das array neu deklariert und dann die einzelnen Positionen ausgegeben
- in der for-Schleifen-Verschachtelung mit d angefangen statt a. Möchte ja lieber mehr 64er haben als lauter 25er, hatte ich aber auch nicht als Bedingung gestellt)
 
AW: Komm nicht auf mathematische Lösung

habe noch ein Optimierungsproblem:
test0hn0.png
sobald Differenz zu groß wird, wird die benötigte zeit zur Ermittlung der notwendigen Kombination exorbitant hoch (siehe Bild) .

Beim Debuggen ist mir aufgefallen, dass er (natürlich) nach einer gefundenen Kombination (Array wird befüllt) trotzdem noch weiter macht bis er nun mal alle Kombinationen durch hat!
WIE kann ich das ganze abbrechen und das Array ausgeben, nachdem das Array einmal befüllt wurde? hab schon rumprobiert aber nix klappt :/

genau so hab ich versucht, dass wenn die Differenz 1000 übersteigt, dass er einfach das überschüssige durch d(64) teilen soll und so ein großteil wegfällt.
Beispiel:
Differenz = 2500
if(differenz > 1000){
array[3] = (differenz - 1000) / d;
differenz -= array[3] * d;
}

geht aber nicht, warum hab ich nicht rausgefunden .... verstehs ned.
 
AW: Komm nicht auf mathematische Lösung

ein paar gut platzierte break; (s) sollten helfen :D

(du kannst natürlich auch unschön das return in deinen if(==) Vergleich reinnehmen)
 
AW: Komm nicht auf mathematische Lösung

Auch wenn es verpönt ist, aber in C/C++ würde ich da eine GOTO-Anweisung benutzen ;) Einfach aus dem IF-Block in der innersten Schleife ganz nach außen springen.

Wenn ich mich recht entsinne, gibt es in Java kein GOTO, oder? Ohne GOTO kommt man in diesem Fall nicht drum herum, eine zusätzliche Variable (oder zusätzliche Tests) einzuführen. Ich würde einfach eine Integer-Variable zu Beginn auf 0 setzen, und sobald eine Lösung gefunden wurde, die im IF-Block auf 1 setzen. Dann würde ich in jeder Schleifenebene noch hinzufügen "if (i == 1) break;" wenn wir die neue Variable einfach mal "i" nennen.

Alternativ kannst du natürlich auch innen im IF-Block schon das "return" der Funktion aufrufen, wenn du alle Werte gespeichert hast :)

Malkolm schrieb:
Brute Force ist immer ein Mittel, gründlich Nachdenken ist aber meist besser :)
Zum Vergrößern anklicken....

Bei dieser Aussage stimme ich dir erstmal zu 100% zu. Dein Vorschlag hat nur leider das Problem, dass die gefundene Lösung oft sehr weit über dem Anfangswert x liegt. Ich glaube, der TE will die kleinste mögliche Lösung finden, die den Kriterien entspricht. Das liefert deine Variante natürlich nicht, weil sie nur die 49 benutzt. Man kann garantiert auch mit Nachdenken eine clevere Lösung für die Problemstellung des TE finden, aber das wird dann *echt* kompliziert :)
 
AW: Komm nicht auf mathematische Lösung

AFAIK kann Java breaks mit Labels:

Code: 
outer:
  for (int i = 0; i < 100; ++i) {
    for (int j = 0; j < 100; ++j) {
      if (/* condition */) {
         break outer;
      }
    }
  }

Edit: Siehe hier
 
AW: Komm nicht auf mathematische Lösung

bingo88 schrieb:
AFAIK kann Java breaks mit Labels:

Code: 
outer:
  for (int i = 0; i < 100; ++i) {
    for (int j = 0; j < 100; ++j) {
      if (/* condition */) {
         break outer;
      }
    }
  }

Edit: Siehe hier
Zum Vergrößern anklicken....

Perfekt, viele Dank :hail:
von einer Berechnungszeit von über 1 min auf 0,000 sek :D

das nenn ich Optimierung ^^


EDIT:
habe mal per hand ne Kombi ausgerechnet wo nur 64er und ein 25er hätten rauskommen sollen, was aber nicht passierte. Es kam eine weniger effiziente Kombi heraus. Also habe ich die Schleifen wie folgt angepasst:
Code: 
public int[] ergebnis() {

        int differenz = differenz();
        int array[] = { 0, 0, 0, 0 };


        int ggt_a = differenz / a;
        int ggt_b = differenz / b;
        int ggt_c = differenz / c;
        int ggt_d = differenz / d;


        tryAndError: for (int z_d = ggt_d; z_d >= 0; z_d--) {
            for (int z_c = ggt_c; z_c >= 0; z_c--) {
                for (int z_b = ggt_b; z_b >= 0; z_b--) {
                    for (int z_a = ggt_a; z_a >= 0; z_a--) {


                        int value = z_a * a + z_b * b + z_c * c + z_d * d;
                        if (value == differenz) {
                            array[0] = z_a;
                            array[1] = z_b;
                            array[2] = z_c;
                            array[3] = z_d;
                            break tryAndError;
                        }
                    }
                }
            }
        }
        return array;
    }

Die Kombinationen sind jetzt die effizientesten, also alles perfekt.
Jetzt gibt es stellenweise Differenzen, bei denen es einige Sekunden dauern kann. Ist aber nicht nur abhängig von der Größe der Differenz, da Integer.MaxValue bspw. auch nur 0,075sek braucht.

Kann man noch i-was optimieren oder gibts da nix mehr?
 
Zuletzt bearbeitet:
AW: Komm nicht auf mathematische Lösung

Kusarr schrieb:
habe mal per hand ne Kombi ausgerechnet wo nur 64er und ein 25er hätten rauskommen sollen, was aber nicht passierte. Es kam eine weniger effiziente Kombi heraus.
Zum Vergrößern anklicken....

Das hättest du dann vorher mal verraten müssen, das geht nämlich überhaupt nicht aus der Problemstellung in deinem Eingangspost hervor :P ;) Der ursprüngliche Algorithmus liefert stets die Lösung mit der geringsten Gesamtpunktzahl in vollen Tausendern, aber wenn es davon mehrere verschiedene gibt, dann nur irgendeine beliebige davon. Es war mir nicht bewusst, dass es auch noch "gute" und "schlechte" Lösungen gibt, wenn die gleiche Gesamtpunktzahl rauskommt :)

Eine mögliche weitere Optimierung würde noch in die folgende Richtung gehen: Wenn du in der äußersten Schleife schon auf der maximalen Anzahl von a bist, ist es z.B. klar, dass in den drei inneren Schleifen keine weiteren Punkte mehr vergeben werden dürfen, weil man sonst definitiv über das vorgegebene Ziel hinausschießen würde. Verstehst du, wie ich das meine? Man könnte also auf jeder Schleifenebene bereits die "bisherige" Summe unter Vernachlässigung der weiter innen liegenden Schleifen bestimmen, und sofort ein "continue" ausführen, wenn die Summe bereits größer ist als der am Ende gewünschte Wert. Das sollte nochmal einiges an Zeit einsparen.

Das von mir erläuterte Verfahren zur Einsparung unnötiger Versuche ist übrigens für alle möglichen Problemstellungen immens wichtig, man nennt das "Branch and Bound-Verfahren":

Branch-and-Bound – Wikipedia
 
Zuletzt bearbeitet:
AW: Komm nicht auf mathematische Lösung

verstanden hab ichs. ob ichs auch umsetzen kann muss sich noch herausstellen :D
Danke erstmal :)

EDIT:

okay hat super geklappt, vielen Dank.
so wars gemeint oder:
Code: 
public int[] ergebnis() {

		int differenz = differenz();
		int array[] = { 0, 0, 0, 0 };
		int value = 0, z_a, z_b, z_c, z_d;


		int ggt_a = differenz / a;
		int ggt_b = differenz / b;
		int ggt_c = differenz / c;
		int ggt_d = differenz / d;


		tryAndError: for (z_d = ggt_d; z_d >= 0; z_d--) {
			value = z_d * d;
			if (value > differenz) {
				continue;
			}
			for (z_c = ggt_c; z_c >= 0; z_c--) {
				value = z_c * c + z_d * d;
				if (value > differenz) {
					continue;
				}
				for (z_b = ggt_b; z_b >= 0; z_b--) {
					value = z_b * b + z_c * c + z_d * d;
					if (value > differenz) {
						continue;
					}
					for (z_a = ggt_a; z_a >= 0; z_a--) {


						value = z_a * a + z_b * b + z_c * c + z_d * d;
						if (value > differenz) {
							continue;
						}
						if (value == differenz) {
							array[0] = z_a;
							array[1] = z_b;
							array[2] = z_c;
							array[3] = z_d;
							break tryAndError;
						}
					}
				}
			}
		}
		return array;

	}


jetzt bin ich zufrieden mit meim Programm. Danke an alle :)
 
Zuletzt bearbeitet:
AW: Komm nicht auf mathematische Lösung

Kusarr schrieb:
okay hat super geklappt, vielen Dank.
so wars gemeint oder:
Zum Vergrößern anklicken....

Jepp, ganz genau. Freut mich zu hören, dass du jetzt mit den Resultaten zufrieden bist :)

Nur in der ganz inneren Schleife kannst du das "if (value > differenz) continue;" rausnehmen. Das spart dort überhaupt nichts ein, da das Schreiben ins Array sowieso nur durchgeführt wird, wenn "value == differenz". Schadet aber auch nichts. Ist halt unnütz ;)
 
Einloggen o. Registrieren zum Antworten.

Ähnliche Themen

McZonk
  • Angeheftet
Test [Extreme-Review] ASUS ROG Crosshair X670E Hero - Chipsatz-Flagschiff für AMDs neuen AM5-Sockel zum Luxuspreis.
2 3
Antworten
49
Aufrufe
14K
McZonk
McZonk
McZonk
Test [Extreme-Review] ASUS ROG Maximus Z690 Hero - mit dem Latein noch lange nicht am Ende.
2
Antworten
23
Aufrufe
6K
PCGH_Torsten
PCGH_Torsten
Incredible Alk
Blog Alkis Blog #48 - Der Backup Blog
Antworten
10
Aufrufe
5K
roheed
roheed
Sinusspass
  • Angeheftet
Guide Das Wakü-Megatutorial
2
Antworten
26
Aufrufe
6K
Sinusspass
Sinusspass
Falcony6886
[Review] be quiet! Silent Loop 2 - 360mm AiO-Wasserkühlung im PCGH-X Test
Antworten
9
Aufrufe
15K
RaptorTP
RaptorTP
Oben Unten
Zurück