# Komm nicht auf mathematische Lösung



## Kusarr (20. Mai 2015)

*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


----------



## Brehministrator (20. Mai 2015)

*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


----------



## DKK007 (20. Mai 2015)

*AW: Komm nicht auf mathematische Lösung*

Sollst du da jetzt ein Gleichungssystem aufstellen? Nach was ist denn genau gefragt?


----------



## pronde (20. Mai 2015)

*AW: Komm nicht auf mathematische Lösung*

3*b+3*c=255 

Wie ich es gelöst habe? Pures Genie ^^


----------



## Kusarr (20. Mai 2015)

*AW: Komm nicht auf mathematische Lösung*



DKK007 schrieb:


> Sollst du da jetzt ein Gleichungssystem aufstellen? Nach was ist denn genau gefragt?


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 ^^


Gut, ich hoffe du hast n paar tage Zeit, um mir alle möglichen Kombinationen von y=0..999 zu sagen


----------



## Brehministrator (20. Mai 2015)

*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.



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


----------



## Malkolm (21. Mai 2015)

*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)


```
[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.


----------



## Kusarr (21. Mai 2015)

*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:



			Dieser Inhalt steht nur eingeloggten Mitgliedern zur Verfügung.
        



liegt wohl an der array-rückgabe iwas is da falsch :/


----------



## DOcean (21. Mai 2015)

*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...


----------



## Kusarr (21. Mai 2015)

*AW: Komm nicht auf mathematische Lösung*

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




			Dieser Inhalt steht nur eingeloggten Mitgliedern zur Verfügung.
        



Ä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)


----------



## Kusarr (22. Mai 2015)

*AW: Komm nicht auf mathematische Lösung*

habe noch ein Optimierungsproblem:



			Dieser Inhalt steht nur eingeloggten Mitgliedern zur Verfügung.
        


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.


----------



## DOcean (22. Mai 2015)

*AW: Komm nicht auf mathematische Lösung*

ein paar gut platzierte break; (s) sollten helfen 

(du kannst natürlich auch unschön das return in deinen if(= Vergleich reinnehmen)


----------



## Brehministrator (23. Mai 2015)

*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



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


----------



## bingo88 (23. Mai 2015)

*AW: Komm nicht auf mathematische Lösung*

AFAIK kann Java breaks mit Labels:


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

Edit: Siehe hier


----------



## Brehministrator (23. Mai 2015)

*AW: Komm nicht auf mathematische Lösung*



bingo88 schrieb:


> AFAIK kann Java breaks mit Labels:



Klasse, das ist genau, was man hier braucht  Wusste ich noch gar nicht (aber programmiere ja auch nicht mit Java). Dann soll es der TE so machen.


----------



## Kusarr (23. Mai 2015)

*AW: Komm nicht auf mathematische Lösung*



bingo88 schrieb:


> AFAIK kann Java breaks mit Labels:
> 
> 
> ```
> ...



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

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:

```
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?


----------



## Brehministrator (23. Mai 2015)

*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.



Das hättest du dann vorher mal verraten müssen, das geht nämlich überhaupt nicht aus der Problemstellung in deinem Eingangspost hervor   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


----------



## Kusarr (24. Mai 2015)

*AW: Komm nicht auf mathematische Lösung*

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

EDIT:

okay hat super geklappt, vielen Dank.
so wars gemeint oder:

```
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


----------



## Brehministrator (24. Mai 2015)

*AW: Komm nicht auf mathematische Lösung*



Kusarr schrieb:


> okay hat super geklappt, vielen Dank.
> so wars gemeint oder:



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


----------

