kleinstes gemeinsames vielfaches

H

Heyoka955

Gast
hallo kann mir einer helfen wieso mein Code nicht das macht was es machen soll?

Also mein vogehen war die zwei werte solange mit der Zählvariable zu multiplizieren bis die zwei Werte gleich sind und am ende wollte ich dann einen break machen sodass ich den kgv direkt bestimmt habe.

mfg
Java:
public class Test {
   
    public static void main (String[] args) {
    int a = Integer.parseInt(args[0]);
    int b = Integer.parseInt(args[1]);
    int count = 1;
    int couter = 1;
   
    for(int i = 1; i < 100000; i++){
        count = i*a;
        couter = i*b;
       
        if( couter == count ){
           
            System.out.print(couter);
            break;
           
        }
       
    }
   
   
   
   
   
    }
}
 

httpdigest

Top Contributor
Naja, warum das nicht funktioniert, ist doch ganz einfache Arithmetik. `i*a = i*b` kann doch nur dann gelten, wenn `a = b` (oder wenn `i = 0`). Oder mit anderen Worten: Du multiplizierst ja beide Werte immer mit demselben Faktor, somit können sie niemals gleich werden, wenn sie nicht schon vorher gleich waren.
Oder konkreter: Wenn a = 4 und b = 5, dann gilt für kein `i` (außer 0), dass: i*a = i*b.
 
H

Heyoka955

Gast
Naja, warum das nicht funktioniert, ist doch ganz einfache Arithmetik. `i*a = i*b` kann doch nur dann gelten, wenn `a = b` (oder wenn `i = 0`). Oder mit anderen Worten: Du multiplizierst ja beide Werte immer mit demselben Faktor, somit können sie niemals gleich werden, wenn sie nicht schon vorher gleich waren.
Oder konkreter: Wenn a = 4 und b = 5, dann gilt für kein `i` (außer 0), dass: i*a = i*b.
okay habe meinen fehler verstanden. Wie kann ich das dann ändern?
 
H

Heyoka955

Gast
habe denn Code umgeändert, ich vesucge das so zu machen dass ich alle Möglichkeiten durchgehe und wenn die beiden werte gleich sind dann printe ich das, aber leider Printer er nur 5. also irgendwas ist da falsch
Java:
public class Test {
   
    public static void main (String[] args) {
    int a = Integer.parseInt(args[0]);
    int b = Integer.parseInt(args[1]);
    int count = 1;
    int couter = 1;
   
    for(int i = 1; i < 100000; i++){
        count = i*a;
       
        for(int j = 1; j < 100000; i++){
            couter = i*b;
           
            if(couter == count){
                System.out.print(couter);
                break;
               
               
            }
           
           
        }
       
    }
   
   
   
   
   
    }
}
 

httpdigest

Top Contributor
Was soll denn dieses Rumprobiere? Du hast hier jetzt den Fehler, dass du in der inneren Schleife ja auch wieder `i` verwendest, statt eigentlich wohl wie gewünscht den neuen Schleifenzähler `j`. Außerdem inkrementierst du in der inneren Schleife nicht `j` sondern `i`.
Außerdem glaube ich nicht, dass jetzt garantiert ist, dass du auch wirklich das kleinste gemeinsame Vielfache findest. Du wirst vielleicht irgendein Vielfaches finden. Aber beweisen kann ich das nicht.
 
H

Heyoka955

Gast
Was soll denn dieses Rumprobiere? Du hast hier jetzt den Fehler, dass du in der inneren Schleife ja auch wieder `i` verwendest, statt eigentlich wohl wie gewünscht den neuen Schleifenzähler `j`. Außerdem inkrementierst du in der inneren Schleife nicht `j` sondern `i`.
oh sorry den fehler hab ich übersehen das Problem ist aber der printet nix mehr, ich glaube ich habe eine endlosschleife
 
H

Heyoka955

Gast
Was soll denn dieses Rumprobiere? Du hast hier jetzt den Fehler, dass du in der inneren Schleife ja auch wieder `i` verwendest, statt eigentlich wohl wie gewünscht den neuen Schleifenzähler `j`. Außerdem inkrementierst du in der inneren Schleife nicht `j` sondern `i`.
Außerdem glaube ich nicht, dass jetzt garantiert ist, dass du auch wirklich das kleinste gemeinsame Vielfache findest. Du wirst vielleicht irgendein Vielfaches finden. Aber beweisen kann ich das nicht.
habe es geschafft, das Problem war ich habe aus Schnelligkeit kleine fehler gemacht.

hätte noch ein Problem, wie bestimme ich am besten die Quersumme ?
 
H

Heyoka955

Gast
Das glaube ich nicht.
Was ist denn das kgV von a=1 und b=50000 ? Es ist zumindest nicht 32704.
Ich hoffe, deine kgV Implementierung ist nicht für irgendeine (Pflicht-)übung oder sowas, in welchem Falle ich die Implementierung erstmal korrigieren bzw. komplett neu schreiben würde.
Die war als Übung gedacht. Habe das mit 5 und 3 ausprobiert. Das hat dann geklappt. Ich habe eifnsch den Zähler vergessen den hätte ich j machen müssen und unten den Zähler. Also ich kann das mit dem zahlen ausprobieren die du sagtest.
Hoffe das klappt
 
H

Heyoka955

Gast
Das glaube ich nicht.
Was ist denn das kgV von a=1 und b=50000 ? Es ist zumindest nicht 32704.
Ich hoffe, deine kgV Implementierung ist nicht für irgendeine (Pflicht-)übung oder sowas, in welchem Falle ich die Implementierung erstmal korrigieren bzw. komplett neu schreiben würde.
okay das funktioniert bei fast allen zahlen außer wenn 1 ist.
 
Zuletzt bearbeitet von einem Moderator:

httpdigest

Top Contributor
Irgendwie hatte ich gerade Lust die Lösung mittels Primfaktorzerlegung zu implementieren:
Java:
import static java.util.function.Function.*;
import static java.util.stream.Collectors.*;
import static java.util.stream.IntStream.*;
import java.util.*;
import java.util.Map.*;
import java.util.stream.*;
public class LeastCommonMultiple {
  private static class Factors extends HashMap<Integer, Long> {};
  private static IntStream factors(int f, int v) {
    // https://stackoverflow.com/questions/35966710/prime-factorization-of-a-positive-integer-with-streams#answer-35967831
    return rangeClosed(f, (int) Math.sqrt(v))
      .filter(x -> v % x == 0)
      .mapToObj(x -> concat(of(x), factors(x, v / x)))
      .findFirst()
      .orElse(of(v));
  }
  private static Factors factorsWithCounts(int num) {
    return factors(2, num)
        .boxed()
        .collect(groupingBy(identity(),
                            Factors::new,
                            counting()));
  }
  private static Factors merge(Factors fs1, Factors fs2) {
    return Stream
        .concat(fs1.entrySet().stream(),
                fs2.entrySet().stream())
        .collect(
            toMap(Entry::getKey,
                  Entry::getValue,
                  Math::max,
                  Factors::new));
  }
  private static int pow(int a, long b) {
    return generate(() -> a).limit(b).reduce(1, Math::multiplyExact);
  }
  public static int lcm(int a, int b) {
    return merge(factorsWithCounts(a), factorsWithCounts(b))
        .entrySet()
        .stream()
        .map(e -> pow(e.getKey(), e.getValue()))
        .reduce(1, (v1, v2) -> v1 * v2);
  }
  public static void main(String[] args) {
    System.out.println(lcm(3, 5)); // <- 15
    System.out.println(lcm(125, 775)); // <- 3875
    System.out.println(lcm(1, 500000)); // <- 500000
    System.out.println(lcm(124, 5000)); // <- 155000
    System.out.println(lcm(6346, 50)); // <- 158650
  }
}
 
H

Heyoka955

Gast
Irgendwie hatte ich gerade Lust die Lösung mittels Primfaktorzerlegung zu implementieren:
Java:
import static java.util.function.Function.*;
import static java.util.stream.Collectors.*;
import static java.util.stream.IntStream.*;
import java.util.*;
import java.util.Map.*;
import java.util.stream.*;
public class LeastCommonMultiple {
  private static class Factors extends HashMap<Integer, Long> {};
  private static IntStream factors(int f, int v) {
    // https://stackoverflow.com/questions/35966710/prime-factorization-of-a-positive-integer-with-streams#answer-35967831
    return rangeClosed(f, (int) Math.sqrt(v))
      .filter(x -> v % x == 0)
      .mapToObj(x -> concat(of(x), factors(x, v / x)))
      .findFirst()
      .orElse(of(v));
  }
  private static Factors factorsWithCounts(int num) {
    return factors(2, num)
        .boxed()
        .collect(groupingBy(identity(),
                            Factors::new,
                            counting()));
  }
  private static Factors merge(Factors fs1, Factors fs2) {
    return Stream
        .concat(fs1.entrySet().stream(),
                fs2.entrySet().stream())
        .collect(
            toMap(Entry::getKey,
                  Entry::getValue,
                  Math::max,
                  Factors::new));
  }
  private static int pow(int a, long b) {
    return generate(() -> a).limit(b).reduce(1, Math::multiplyExact);
  }
  public static int lcm(int a, int b) {
    return merge(factorsWithCounts(a), factorsWithCounts(b))
        .entrySet()
        .stream()
        .map(e -> pow(e.getKey(), e.getValue()))
        .reduce(1, (v1, v2) -> v1 * v2);
  }
  public static void main(String[] args) {
    System.out.println(lcm(3, 5)); // <- 15
    System.out.println(lcm(125, 775)); // <- 3875
    System.out.println(lcm(1, 500000)); // <- 500000
    System.out.println(lcm(124, 5000)); // <- 155000
    System.out.println(lcm(6346, 50)); // <- 158650
  }
}
das ist schon zu schwer für mich? wie geht man da vor
 

mihe7

Top Contributor
S. Kommentar #4.

Da ist eine Seite mit Algorithmen angegeben, ich wähle mal die Variante "Berechnung über den ggT".

Java:
public int kgV(int a, int b) {
    return Math.abs(a / ggT(a,b) * b);
}
Fertig.
Ok, nicht ganz, wir müssen noch den ggT berechnen. Dazu findet man auf der Seite einen Link auf den euklidischen Algorithmus. Dort nehme ich mal die iterative, moderne Variante:
Java:
public int ggT(int a, int b) {
    while (b != 0) {
        int h = a % b;
        a = b;
        b = h;
    }
    return a;
}
 
H

Heyoka955

Gast
S. Kommentar #4.

Da ist eine Seite mit Algorithmen angegeben, ich wähle mal die Variante "Berechnung über den ggT".

Java:
public int kgV(int a, int b) {
    return Math.abs(a / ggT(a,b) * b);
}
Fertig.
Ok, nicht ganz, wir müssen noch den ggT berechnen. Dazu findet man auf der Seite einen Link auf den euklidischen Algorithmus. Dort nehme ich mal die iterative, moderne Variante:
Java:
public int ggT(int a, int b) {
    while (b != 0) {
        int h = a % b;
        a = b;
        b = h;
    }
    return a;
}
das hilft aber nicht weiter, wie kommt man auf die lösung
 

httpdigest

Top Contributor
Indem du dir die Seite durchliest und die Lösung dann implementierst.
Was meinst du denn mit: Wie kommt man auf die Lösung?
Wenn du meinst, wie man mathematisch auf die Lösung kommt, ohne die existierenden Lösungen zu kennen oder sich darüber zu informieren, dann braucht man hier wahrscheinlich erstmal ein nicht unerhebliches Mathematikvorwissen.
 
H

Heyoka955

Gast
Indem du dir die Seite durchliest und die Lösung dann implementierst.
Was meinst du denn mit: Wie kommt man auf die Lösung?
Wenn du meinst, wie man mathematisch auf die Lösung kommt, ohne die existierenden Lösungen zu kennen oder sich darüber zu informieren, dann braucht man hier wahrscheinlich erstmal ein nicht unerhebliches Mathematikvorwissen.
Ich versuche immer selber auf die Lösung zu kommen ohne Hilfe aber bei solchen Aufgaben ist es sehr schwer.
 

httpdigest

Top Contributor
Verständlich. Selber auf die Lösung zu kommen, ist auch am effektivsten und macht am meisten Spaß. Aber das hier zu lösende Problem war rein mathematischer Natur. Man kommt auch mal nicht eben so ohne weiteres alleine auf den Euclidschen Algorithmus zur Berechnung des ggT und dann noch darauf, diesen für die Ermittlung des kgV zu verwenden... ich sage mal so, wenn du das geschaffst hättest, schreib dich sofort für ein Mathematikstudium ein und werde in ein paar Jahren Professor. :)
 

Ähnliche Java Themen

Neue Themen


Oben