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?

 

[chripo19]

BigInteger a=new BigInteger ("0");
        for(int i=0;i<88;i++){
            BigInteger b=new BigInteger ("99999999999999999999");
            b.subtract(BigInteger.valueOf(i*833));
            b.divide(BigInteger.valueOf(616));
            a.add(b);
            if (i>0){
                a.add(BigInteger.ONE);
            }
        }
        System.out.println(a);

Warum gibt er mir 0 aus?

Sollte der selbe Code wie dieser sein nur mit anderen Zahlen

        int a=0;

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

 

[JStein52]

Du musst die Werte jeweils auch zuweisen, also z.b. b=b.divide(....); Probiere es mal so:

    BigInteger a=BigInteger.valueOf(0l);

    for(int i=0;i<88;i++){
        BigInteger b=BigInteger.valueOf(999999999999999999l);
        b=b.subtract(BigInteger.valueOf(i*833l));
        b=b.divide(BigInteger.valueOf(616));
        a=a.add(b);
        if (i>0){
            a=a.add(BigInteger.ONE);
        }
    }
    System.out.println(a);

 

[JStein52]

Ich habe es jetzt mal so gelöst: (Deine Art es auszurechnen funktioniert sicher auch)

  public BigInteger 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;
      BigInteger   kombis    = BigInteger.valueOf((long)abschnitt); // x=0, y=0 macht keinen Sinn !

      // kgV ausrechnen
      long ggTZahl1= (long)a;
      long ggTZahl2= (long)b;
    
      while(ggTZahl2 != 0l){
        long temp = ggTZahl1;
        ggTZahl1 = ggTZahl2;
        ggTZahl2 = temp % ggTZahl1;
      }
      long kgv = Math.abs((long)a/ggTZahl1*(long)b);

      long x=0;
      while (y >= steigung) { // solange wie man die Steigung subtrahieren kann
          y = y - steigung;
          x++;
          // ab hier wiederholen sich die Werte
          if (x>=kgv/(long)a) break;
          kombis = kombis.add(BigInteger.valueOf((long)y+1L));
      }
      return kombis;
  }

und erhalte als Ergebnis: Kombinationen = 142857142857142855767
Kriegst du das auch ? Dann ist das Problem wohl gelöst.