for in for Schleife ineffizient?

[chripo19]

Guten Tag,

ich habe folgendes kleines Programm geschrieben zur Bestimmung wie viele Möglichkeiten es gibt diese Gleichung:
98x + 35y<=10000
durch beliebige x und y zu erfüllen.

ArrayList <Integer>preise= new ArrayList<Integer>();
for(int i=0;i<103;i++){
    for (int j=0;j<286;j++){
        int a=i*98+j*35;
        if(a>10000){
            break;
        }
        if(preise.contains(a)==false){
            preise.add(a);   
        }
    }
}

Bis hier hin alles easy. Das Programm Dauert seine 5millisek und gibt mir 1402 aus.

Nun würde ich gerne dasselbe mit dieser Gleichung machen: 833x+616<=(10^21)-1

ArrayList <Double>preise= new ArrayList<Double>();
for(double i=0;i<120048019207684.0;i++){
   for (double j=0;j<162337662337662338.0;j++){
       double a=i*833+j*616;
       if(a>99999999999999999999.0){
            break;
        }
        if(preise.contains(a)==false){
            preise.add(a);   
        }
    }
}

Nach 1,5h habe ich aufgegeben und das Programm abgebrochen. Wie kann ich das Programm optimieren?

 

[Der Müde Joe]

Ist doch nur Mathe? (oder hab ich schon ein Bier zuviel)

// 833x+616<=(10^21)-1
// 833x    <=(10^21)-617 (999999999999999999383)
//

BigInteger fac = BigInteger.valueOf(833l);
// (10^21)-617
BigInteger max = BigInteger.valueOf(10l).pow(21).subtract(BigInteger.valueOf(617l));

System.out.println("Start: " + max);
// ((10^21)-617) / 833
BigInteger maxDiv = max.divide(fac); // modulo egal
System.out.println("Max x: " +maxDiv);

BigInteger modulo = max.mod(fac);
// test: maxDiv * 833 + (max mod 833) == max
System.out.println("Check: " + maxDiv.multiply(fac).add(modulo));
System.out.println(max.equals(maxDiv.multiply(fac).add(modulo)));
[\code]

 

[Thallius]

Ich glaube er hat das "y" hinter den 616 aus versehen zu einem "<" gemacht.

Gruß

Claus

 

[chripo19]

Ups. Da fehlt tatsächlich ein y. Wurde korrigiert

 

[chripo19]

833x+616y<=(10^21)-1 Da fehlte ein y

 

[Thallius]

Optimieren kannst du das nur eventuell durch Verwendung von BigInteger. Aber ob das viel bringt weiß ich auch nicht. Ansonsten halt vorher kürzen.

 

[eldrior]

Momentan probierst du ganz stumpf einfach jede Möglichkeit durch. Das kann man bei kleinen Aufgaben machen (wie deiner ersten), aber du hast selbst gesehen, dass das bei größeren Problemen unsinnig ist.
Geht es dir nur um die Anzahl der möglichen Lösungen, gibt es bessere (mathematische) Lösungen, das das, was ich dir jetzt vorschlage.

Nehmen wir an du hast a*x+b*y<=z
dann könntest du mit x=0 und y=0 anfangen (oder von miraus auch im negativen Bereich) und y hochzählen, bis die Zahl >z ist.
Du kannst aber y auch in jedem Durchgang um 5000 erhöhen, bis es >z wird und nur dann jede Zahl probieren. (Zahlen kannst du selbst anpassen )

Du könntest auch alle Ergebnisse von a*x bis x=??? berechnen. Dann zählst du, wie viele von den eben berechneten Ergebnissen <= z-b*y ist. (Da sieht man das klassische Problem wieder: Je weniger Rechenleistung du zur Lösung eines Problems in fixer Zeit x aufwenden willst, desto mehr Speicher brauchst du. Je weniger Speicher du nutzen willst, desto mehr Rechenleistung brauchst du.

Und dann gibts da natürlich noch die Möglichkeit der parallelisierung. Die ist hier eigentlich sehr gut anzuwenden.

Du kannst jetzt entweder nach einer mathematischen Lösung suchen (ist allgemein die beste und intelligenteste Lösung), oder deinen Code optimieren.

 

[Dompteur]

Du hast da ein Problem mit quadratischer Komplexität. Das heißt, wenn du den Wert rechts vom <= mal 2 nimmst, dann erhöht sich die Anzahl der Ergebnisse um 2 hoch 2 (=4).
Bei einer Verdreifachung hast du schon 3 hoch 2 (=9) mal soviele Ergebnisse.
Die Laufzeit der Aufgabe wächst entsprechend der Anzahl der Ergebnisse.

Weiters darfst du nicht vergessen, dass du im ersten Beispiel int und im 2. Beispiel double's verwendest. Berechnungen mit ganzen Zahlen sind immer schneller.

Ich weiß nicht, wieviel der Java-Compiler optimiert, aber du könntest diese Variante ausprobieren. Ich habe da Multiplikationen durch Additionen ersetzt. Üblicherweise ist das schneller.

ArrayList <Integer>preise= new ArrayList<Integer>();
xpart = 0;
for(int i=0;i<103;i++, xpart += 98){
     int a = xpart;
     for (int j=0;j<286;j++, a+=35){
         if(a>10000){
             break;
         }
         // an dieser Stelle hast du eine weitere Lösung des Ungleichung gefunden : (i, j).
         if(preise.contains(a)==false){
             preise.add(a);  
         }
     }
}

Off topic: Mir ist nicht klar, was du in preise speicherst bzw. was du genau ermitteln willst.

 

[Enceladus271]

Ich bezweifel dass es möglich einen halbwegs effizienten Algorithmus für das Problem zu finden:

1. Allein die äußere Schleife braucht ewig. Wenn ein Schleifendurchlauf durchschnittlich 1ns benötigt läuft die Schleife schon ca 33 Stunden.

2. Es ist nicht möglich die Ergebnisse in einer Liste zu speichern. Wenn x=0 ist gibt es schon 10^21 / 616 y-Werte die die Gleichung erfüllen. Allein um die zu speichern baruchst du 649350 TeraByte Speicher.

 

[InfectedBytes]

Brute Force ist nun wirklich der falsche Ansatz^^
98x + 35y<=10000 kannst du z.b. umformen in y <= 2000/7 - 14x/5
daraus resultiert im grunde eine fläche unterhalb der linie die durch y=2000/7 - 14x/5 gegeben ist.

Rechne dir dann mal den schnittpunkt mit der x achse aus, also 0=2000/7 - 14x/5 nach x lösen (5000/49)
Im Grunde brauchst du dann nichts weiter machen, als von x=0 bis x=5000/49 zu gehen und jedes mal den y wert davon zu berechnen, die ergebnisse kannst du aufsummieren.

Vielleicht mal nen kleines Beispiel:
Wenn x=20 ist, ist y=1608/7, d.h. allein für diesen einen x Wert, gibt es rund 229 y Werte, für die das Ergebnis die Gleichung erfüllt

 

[Dompteur]

Brute Force ist nun wirklich der falsche Ansatz^^

Ich sehe hier keinen Brute Force Ansatz. Schau dir doch den Code des 1. Beispiels im ersten Beitrag noch einmal an. Jede Kombination (i,j) bis zum Abbruch der inneren Schleife durch das break ist eine gültige Lösung.

Das Problem ist, dass die Anzahl der Lösungen sehr schnell steigt. Enceladus271 hat ja vorgerechnet, wie viele Lösungen es schon für einen x-Wert gibt.

 

[InfectedBytes]

Also ich finde alles durchzuprobieren ist schon bruteforce

for(int i=0;i<103;i++){
    for (int j=0;j<286;j++){
        int a=i*98+j*35;
        if(a>10000){
...

Die Hälfte der Durchläufe liefert einen Wert über 10.000 und sollte daher erst gar nicht betrachtet werden.

Und bezüglich der Anzahl der Lösungen hast du natürlich recht, jedoch ist die Frage ob wirkliche alle Lösungen ausgegeben werden sollen, oder ob es reicht zu wissen wieviele es gibt.
Außerdem könnte man auch anstatt alle (x,y) zu speichern auch nur (x, ymax) speichern
Anstatt also (20, 0), (20, 1), ... (20, 229) könnte man genauso gut nur (20, 229) speichern, was eben aussagen würde, das der x-Wert 20 mit den y-Werten 0 bis 229 ein passendes Ergebnis liefert

 

[Dompteur]

Die Hälfte der Durchläufe liefert einen Wert über 10.000 und sollte daher erst gar nicht betrachtet werden.

Das stimmt nicht. Für jeden Durchlauf der äußeren Schleife gibt es genau einen Fall, bei dem 10.000 überschritten wird. Danach wird die innere Schleife abgebrochen. Also gibt es 103 Fälle, bei denen 10.000 überschritten wird..

... jedoch ist die Frage ob wirkliche alle Lösungen ausgegeben werden sollen, oder ob es reicht zu wissen wieviele es gibt.

Da hast du recht. Ich habe schlampig gelesen und nicht regestriert, dass es um die Anzahl geht. Ich ging davon aus, dass alle Lösungen ausgegeben werden sollten.

 

[InfectedBytes]

Das stimmt nicht. Für jeden Durchlauf der äußeren Schleife gibt es genau einen Fall, bei dem 10.000 überschritten wird. Also in 103 Fällen.

ahhh, hab irgendwie gedacht er hatte da nen continue xD

 

[black swan]

Der Oberbegriff Brute-Force-Methode passt schon, weil er im Allgemeinen bedeutet, alle Möglichkeiten durchzuprobieren. In der Mathematik ist das evtl. nicht ganz passend, da es hier nicht um "raten" geht. Es werden (lokale) Maxima einer Kurve gesucht.

 

[JStein52]

Hallo, ganz habe ich das Problem worum es geht nicht verstanden. Geht es dir um einen generellen Lösungsansatz für beliebige Geraden Oder geht es um ganz spezielle Geraden und du suchtst nur einen Weg dies optimal zu codieren ? Und suchst du nur ganzzahlige Tupel (x,y) die diese Bedingung erfüllen ? Es geht mir wie dem müden Joe mit dem Bier zuviel. Du suchst doch schlicht alle Wertepaare unterhalb (bzw. auch noch auf) einer Geraden. Wobei schlicht jetzt evtl. untertrieben ist. Ist das so ?

 

[JStein52]

Und bzgl. "schlicht" bin ich der Meinung von Enceladus, es wird einfach praktisch nicht möglich sein da einen effizienteren Algorithmus zu finden der das Problem allgemein löst. Es wird im Prinzip nichts anderes übrig bleiben für jeden x-Wert den zugehörigen y-Wert auszurechnen. Da könntest du sicher noch ein bisschen optimieren denn die Steigung der Geraden ist ja bekannt so dass du das ganze auf Additionen reduzieren kannst. Aber wenn das Intervall in x-Richtung nunmal gigantisch ist hilft jeder Programmiertrick nur bedingt. Im übrigen bin ich nicht der Meinung dass die Komplexität quadratisch ist, sie ist linear. Wenn das x-Intervall doppelt so gross wird müssen auch doppelt so viele y-Werte berechnet werden. Und im allgemeinen ist die Anzahl möglicher Lösungen natürlich unendlich, aber du begrenzt ja das x-Intervall auf einen bestimmten Bereich.

 

[chripo19]

Danke erstmal für die viele Antworten. Hier ist nochmal die exakte Aufgabenstellung: Es gibt Kupfer-,Silber- und Goldmünzen.
Eine Silbermünze = 35 Kupfermünze
Eine Goldmünze = 98 Kupfermünzen

Wie viele Preise bis 10.000 Kupfer können nur mit Silber und Goldmünzen bezahlt werden ->
35x+98y<=10000

Also es scheitert an der Mathematik. Habe es über einen anderen Ansatz versucht.

for(int i=0;i<103;i++){
    a+=(10000-(i*98))/35;
    if (i>0){
      a+=1;
   }
}
System.out.println(a-1);

Ich komme auf 14768. Müsste aber auf 1402 kommen. Wie bekomme ich die Preise gefiltert die vorher schonmal getroffen wurden?

 

[JStein52]

Also, nach dieser Aufgabenstellung hast du folgendes mathematische Problem:
Du suchst alle ganzzahligen Tupel (x,y) die unterhalb der Geraden liegen die durch die Gleichung 35x + 98y = 10000 gegeben ist. Du kannst die Gleichung noch umformen und erhältst:

y = 10000/98 - 35x/98

und jetzt gehst du her und setzt für x nacheinander alle ganzen Zahlen, beginnend mit 0 ein solange wie der zugehörige y-Wert >= 0 ist. für jedes x erhältst du nun einen ymax-Wert (nämlich den der auf der Geraden drauf liegt) und weisst dann dass für diesen x-Wert alle ganzzahligen Werte von 0 bis ymax die Bedingung erfüllen. Und diese ganzen (auf ganze Zahlen abgeschnittenen) ymax werte addierst du in der Schleife für jedes x auf und solltest dann am Ende die Zahl der Kombinationen haben. Da die Steigung -35/98 ist kannst du natürlich den ersten Wert für x = 0 ausrechnen und für alle folgenden x einfach 35/98 subtrahieren und das solange wie y noch >= 0 ist.
Und das in Java umsetzen darfst du jetzt.

 

[JStein52]

Und aufpassen: wenn du für x=1 z.B. ymax = 3.7 erhältst dann passen die Tupel (1,0), (1,1), (1,2), (1,3) !!! Also nicht einfach 3.7 abschneiden auf 3, die 0 gehört auch noch dazu, also 4 Kombinationen !

 

[JStein52]

Ich habe das übrigens mal eingehackt und komme auf 14769 gültige Kombinationen !!! Wer sagt denn dass da 1402 rauskommen soll ?

 

[chripo19]

for(int i=1;i<286;i++){
    double y=(10000/98)-(35/98)*i;
    a+=(int)y+1;
}

 

[chripo19]

Naja überleg doch mal: Es ist die Frage: Wie viele Preise von 10.000 möglichen Preisen können bezahlt werden. 14k ist da ein wenig unnlogisch. auf 14k komme ich schon seit langem. Hast du dir das ganze thema durchgelesen? Auf 1402 komme ich wenn ich alle ergebnisse speichere, und vergleiche, und keine doppelten in meine array list lasse. Aber das sprengt bei größeren Aufgaben den Rahmen. auf 14769 komme ich auch mit dem um 19:21 geposteten Code.

 

[JStein52]

Und meiner Meinung nach ist das auch richtig mit den 14k. Mein Code sieht so aus:

  public int computeKombi(float a, float b, float c) {
      // a*x + b*y = c -> y = c/b - a/b*x
      float abschnitt = c/b;
      float steigung  = a/b;

      // den Wert x = 0 rechnen wir per Hand aus
      float y         = abschnitt;
      int   kombis    = (int)abschnitt; // x=0, y=0 macht keinen Sinn !
   
      while (y >= steigung) { // solange wie man die Steigung subtrahieren kann
          y = y - steigung;
          kombis = kombis + (int)y + 1;
      }
      return kombis;
  }

Was sind denn da doppelte Kombinationen ?? ich addiere doch in jedem Schleifendurchgang, d.h. neues x einfach die möglichen y-Werte dazu ?? Oder ich habe die Aufgabe falsch verstanden, ich dachte du willst die möglichen Kombinationen wissen wie du diese Preise zahlen kannst ?

 

[InfectedBytes]

eine möglichkeit wäre es, ein boolean Array mit 10.000 Einträgen anzulegen und bei den Berechnungen eben den Wert im Array auf true setzen. Anschließend muss das Array einmal durchlaufen werden um zu zählen wie oft true vorkommt.
Dieser Ansatz kostet zwar Speicher, spart aber Laufzeit im Vergleich zur Liste

p.s. @vorposter
Dem TE geht es darum, dass z.b. die beiden Tupel (0,98) und (35,0) beide jeweils den Wert 3430 ergeben, dementsprechend sollen der Wert 3430 nur einmal gezählt werden und nciht zweimal

 

[JStein52]

Ok, im ersten Post stand es anders. Ja, dann passt das mit deinem boolean Array.

 

[chripo19]

ja.... das wird aber nicht allzugroßer unterschied zu array list machen. wenn ich in die gröenordnung 10^21 gehe wird das ewig dauern

 

[E00358]

Hallo (ich hoffe ich irre mich nicht),
Wie oben schon gesagt wurde kann der Preis 3430 durch 2 Kombinationen erhalten werden, d.h. aber auch, das alle möglichen Preise sich oberhalb 3430 was die Abstände angeht wiederholen und nicht neu berechnet werden müssen. Es muss zuerst die Gleichung 98Y = 35X auf die kleinste ganzzahlige Lösungen untersucht werden. Ist diese gefunden können die möglichen Preise berechnet werden, die sich aus Silber und Goldmünzen Kombinationen für diesen Wert ergeben. Aufpassen muss man dann nur noch bei dem Rest, 10000 ist kein ganzzahligen Vielfaches von 3430 und der Frage ob 0 ein Preis ist oder nicht.

 

[JStein52]

Aber im Prinzip gilt das was Enceladus oben schon vorgerechnet hat. Es wird in dieser Grössenordnung halt nun mal ewig dauern. Aber warum ist das überhaupt ein Problem für dich ? Benutzt du das in irgendeinem konkreten Projekt wo z.B. ein Benutzer davor sitzt und auf das Ergebnis wartet oder ist es nur eine Übungsaufgabe bzw. akademisches Problem und du hast jetzt den Ehrgeiz da noch ein paar Prozent rauszuholen so dass es statt 15 Stunden nur noch 10 dauert ?

 

[E00358]

Guten Morgen,
Das Problem ist linear und eher ein mathematisches oder Textaufgabe. Wenn die kleinste ganzzahlige Lösung für die Gleichung 98Y = 35X gefunden wurde, muss man nur die unterschiedlichen absolut Beträge der Kombinationen zählen, danach lässt sich der Rest mit den Grundrechenarten erledigen und ist von dem Endwert linear abhängig.
Die Kombinationen sind immer < 10000. Vielleicht wird das klarer, wenn man besser auf einander abgestimmte Münzen nimmt wie Euro und 2 Eurostücke. Mit 2 Eurostücken bekomme ich 10000/2 -1 Preise hin mit beiden Münzen sind es 10000 -1 genau so viele wie mit 1 und 2 Euro Münzen. In dem Beispiel habe ich die Reihen 35,70,105,140,... ; 98,196,294, ... und die Kombination 1x98 + x35 , 2x98 x 35, ... . Spätestens ab 3430 wiederholt sich das Ganze

VG Michael

 

[JStein52]

Die Länge der äusseren Schleife (alle möglichen x-Werte) hängt natürlich von allen Koeffizienten ab. Bei deinem Zahlenbeispiel (833, 616, 10^21 ) wird diese rund 10^18 mal durchlaufen. Rechne mal wie Enceladus mit einer ns pro Schleifendurchgang. Dann bist du bei 10^9 sekunden. Bis dahin hat sich allerdings die Hardware soweit verbessert dass du es neu starten kannst und dann vielleicht nur noch ein Tausendstel (d.h. 10^6 sekunden) benötigst

 

[chripo19]

Meine Motivation ist, dass ich von mind. drei unabhängigen Quellen weiß, dass man diese Aufgabe in wenigen Sekunden lösen kann.

 

[JStein52]

Ich wette meinen Hintern dass du das mit den grossen Zahlenwerten die du genannt hast niemals in einer Woche schaffen wirst. Die Optimierungen die Michael vorgeschlagen hat mögen ja funktionieren. Aber wie er auch schon sagt, das Problem ist linear abhängig vom Endwert. Und da ergibt eine einfache Überschlagsrechnung dass es nicht funktionieren kann. Selbst wenn ich mich bei meinen Rechnungen um einen Faktor 1000 vertan habe (wegen möglichen Optimierungen).

 

[JStein52]

Du kannst es doch leicht selbst probieren. Ich habe eine Schleife über alle möglichen x-Werte gemacht, und darin nur mit einer einzigen Subtraktion den max. Y-Wert ausgerechnet. Sonst gar nix. Dann braucht er bei den Werten (833, 616, 10^13) 250 Sekunden (gute 4 Minuten ) dafür !!! Und da bin ich von 10^21 meilenweit entfernt.

 

[Dompteur]

Eventuell kann man das mit einem anderen Ansatz sehr wohl viel schneller lösen.
Hier meine Gedanken dazu:
Die Aufgabe besteht darin, die Anzahl aller möglichen (x,y) Kombinationen zu finden, die die Ungleichung erfüllen.

Ich habe also die Ungleichung 98x + 35y <= 10.000
Die Anzahl der Möglichen Werte ist die Summe über eine arithmetische Reihe.
Die Reihe wird durchnummeriert von 0 bis n ( also n = 10.000/98 (=102) )

a0 (für x=0) = 10.000 / 35 - (98 / 35) * 0= 285
a1 (für x=1) = 10.000 / 35 - (98 / 35) * 1 = 282
..
a101 (für x=101) = 10.000 / 35 - (98 / 35) * 101 = 2
a102 (für x=102) = 10.000 / 35 - (98 / 35) * 102 = 0

Für die Summe der Werte einer arithmetischen Reihe gibt es ja die Formel :
summe = ( n + 1 ) ( a0 + an ) / 2

Das Problem, das es noch zu lösen gilt, ist die Problematik, dass die Werte der Reihe nicht ganzzahlig sind.
Hier endet nämlich mein Schulwissen ;-)
Vielleicht gibt es hier einen Mathematiker, der das lösen kann.

Auf jeden Fall kommt man auf diese Weisen sehr schnell zu einer guten Näherungslösung. Diese ist auch unabhängig von den Parametern.

 

[JStein52]

Interessante Idee. Aber wenn ich die Werte die du hingeschrieben hast einsetze komme ich auf 14677.5 Das ist aber weder die exakte Lösung noch berücksichtigt es das Problem mit den doppelten Werten. Stimmt die Formel die du genannt hast ?

 

[Dompteur]

Die Abweichung entsteht dadurch, dass die Formel für arithmetische Reihen im ganzzahligen Bereich gedacht ist. Hier haben wir aber rationale Zahlen und durch die Rundungen entstehen Fehler.
Daher auch meine Frage, ob da ein Mathematiker eine Lösung für rationale Zahlen kennt.

Das Problem der doppelten Werte verstehe ich nicht ganz. Nur, weil der gleiche Preis herauskommt, sind es trotzdem verschiedene Kombinationen.
Oder gibt es da noch eine Zusatzbedingung ?

 

[InfectedBytes]

es geht dem TE eben nicht um die Tupel Kombinationen, sondern nur um die Preise die durch verschiedene Kombinationen erreicht werden können.

p.s.
vielleicht sollte der TE diese "drei unabhängigen Quellen" mal fragen xD

 

[JStein52]

Die Idee von Dompteur wäre ja schon super. Aber jede Abhandlung über Reihen, Folgen etc. beginnt damit dass die Definitionsmenge die natürlichen Zahlen sind. Und ich denke mal der Übergang zu rationalen Zahlen bedeutet dann Differential- und Integralrechnung.

Edit: Stimmt glaube ich nicht ganz. Die Formel von Dompteur stimmt schon und pass auch. Das ist die Summe aller Y-Werte für das gegebene x-Intervall. Aber eben wirklich alles aufsummiert als rationale Zahl. Und es ist aus der Summe nicht mehr rauszufinden wieviele es jetzt als natürliche Zahlen sind. (also 5.7 und 5.4 ergibt dann eben 11.1 und nicht wie es richtig wäre 10 !

 

[JStein52]

Und an den @TE : Du willst ja erstens sicher eine genaue Lösung haben und nach wie vor die doppelten Kombinationen entfernen ? Und gibt es denn schon eine unabhängige Quelle die sagt das geht ? Oder wurde bei der Aufgabenstellung behauptet es geht ?

 

[taro]

öhm ... wie wärs damit?

static int silber = 35;
  static int gold = 98;
  static int maxBetrag = 10000;

  public static void main(String[] args) {
  int zaehler = 0;
  for (int i = 1; i <= maxBetrag; i++) {
  if (kombination(i)) {
  zaehler++;
  }
  }

  System.out.println(zaehler);

  }

  public static Boolean kombination(int wert) {
  for (int j = 0; (j * silber) <= maxBetrag; j++) {

  for (int k = 0; k * gold + j * silber < maxBetrag; k++) {
  if (j * silber + k * gold == wert) {
  return true;
  }
  }
  }
  return false;
  }

Ihr denkt mir manchmal echt zu kompliziert

EDIT: Einrückungen scheinen mit dem "neuen" Editor wohl ein Problem zu sein?!

 

[JStein52]

@taro : es geht nicht darum eine Lösung zu finden, da gibt es mehrere richtige Ansätze. Es geht darum ob das zweite Zahlenbeispiel des TE in endlicher Zeit zu lösen ist. Und auch du hast eine Schleife von 1 bis maxBetrag. Und wenn maxBetrag 10^21 ist dann hast du nächstes Jahr um die Zeit die Lösung !!!
(und mit int kannst du dann sowieso nicht mehr rechnen, und ich sehe noch nicht wo du das mit den doppelten Kombinationen berücksichtigst ?)
Das hier tut das gleiche wie deines:

  public long computeKombi(double a, double b, double c) {
      // a*x + b*y = c -> y = c/b - a/b*x
      double abschnitt = c/b;
      double steigung  = a/b;
      // boolean[] value = new boolean[(int)c];

      // den Wert x = 0 rechnen wir per Hand aus
      double y         = abschnitt;
      long   kombis    = (long)abschnitt; // x=0, y=0 macht keinen Sinn !

      while (y >= steigung) { // solange wie man die Steigung subtrahieren kann
          y = y - steigung;
          kombis = kombis+(long)y+1L;
      }
      return kombis;
  }

mit einer, und dazu noch kürzeren Schleife.

 

[taro]

@taro : es geht nicht darum eine Lösung zu finden, da gibt es mehrere richtige Ansätze. Es geht darum ob das zweite Zahlenbeispiel des TE in endlicher Zeit zu lösen ist. Und auch du hast eine Schleife von 1 bis maxBetrag. Und wenn maxBetrag 10^21 ist dann hast du nächstes Jahr um die Zeit die Lösung !!!
(und mit int kannst du dann sowieso nicht mehr rechnen, und ich sehe noch nicht wo du das mit den doppelten Kombinationen berücksichtigst ?)

Das zweite Zahlenbeispiel hatte ich gar nicht wirklich wahrgenommen.

Die doppelten Kombinationen interessieren mich nicht - sobald ein Wert entsprechend in "silber" und "gold" zahlbar ist, ist es ein zahlbarer wert, unabhängig davon ob es noch weitere Kombinationen gibt - er spring dann auch entsprechend raus ...

 

[JStein52]

Ok, stimmt, die doppelten hast du so weg. Bleibt aber das Laufzeitproblem an dem wir schon seit gestern diskutieren.

 

[taro]

@taro : ..
Das hier tut das gleiche wie deines:

  public long computeKombi(double a, double b, double c) {
      // a*x + b*y = c -> y = c/b - a/b*x
      double abschnitt = c/b;
      double steigung  = a/b;
      // boolean[] value = new boolean[(int)c];

      // den Wert x = 0 rechnen wir per Hand aus
      double y         = abschnitt;
      long   kombis    = (long)abschnitt; // x=0, y=0 macht keinen Sinn !

      while (y >= steigung) { // solange wie man die Steigung subtrahieren kann
          y = y - steigung;
          kombis = kombis+(long)y+1L;
      }
      return kombis;
  }

mit einer, und dazu noch kürzeren Schleife.

Nein, tut er nicht ...

 

[JStein52]

Ja, ist schon klar, ich hatte das mit deinen doppelten Kombinationen zuerst nicht gecheckt. Aber wie gesagt,
die Laufzeit bei dir ist soger noch extrem schlimmer als bei anderen schon vorgestellten Lösungen weil du ja wirklich für jeden einzelnen Betrag prüfswt ob es eine Kombi gibt. Und auch bei dir gilt: selbst wenn ein Schleifendurchlauf durch die äussere Schleife 1 ns (optimistisch, eher mehr weil du darin ja nochmal geschachtelte Schleifen hast !) dauert dann kommst du auf 10^12 Sekunden !!!! Wenn du deinen Rechner für die nächsten paar Jahre nicht brauchst kannst du es ja mal mit diesen Zahlen starten

 

[chripo19]

Ich habe mal nachgefragt und habe den finalen Tipp bekommen, der auch recht sinnvoll ist:

Das kgV von 35 und 98 ist 490 (5*98 oder 14*35).
D.h. wenn ich wie schon oben versucht eine For-Schleife mit a+=(10000-(i*98))/35 mache bekomme ich die Anzahl der ergebnisse. Die ergebnisse wiederholen sich ab 5*98. Somit kann es ab da vernachlässigt werden.
Auch wenn man mir hier nicht direkt helfen konnte, bedanke ich mich bei allen.

Mfg chripo19

 

[JStein52]

Halte uns doch bitte auf dem Laufenden wie das ganze mit deinen Monsterzahlen von 10^21 ausgeht.

 

[chripo19]

Selbes Prinzip habe ich nun übertragen. Lese mich nicht in BigInteger ein und benutze double. in 1 ms komme ich auf 1.4285714285714297E19. Wie kann ich die Zahl ganz ausschreiben lassen?

 

[InfectedBytes]

double hat eine Genauigkeit von ungefähr 16 Stellen. Wenn du exakte Werte haben willst, kommst du um BigInteger nicht herum