Endlosschleife ja nein?

[sserio]

Aufgabe:
Die Folge der Dreieckszahlen wird gebildet, indem die natürlichen Zahlen addiert werden. Somit ist die 7. Dreieckszahl 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Die ersten zehn Glieder sind:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Lassen Sie uns die Teiler der ersten sieben Dreieckszahlen auflisten:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

Wir können sehen, dass 28 die erste Dreieckszahl mit mehr als fünf Teilern ist.

Was ist der Wert der ersten Dreieckszahl, die mehr als fünfhundert Teiler hat?

package ProjectEuler12;

public class Main {

    public static void main(String... args) {
        System.out.println(findNumber(500));
    }

    public static int findNumber(int dividends) {
        boolean b = true;
        var temp = 0;
        for (var i = 1; b; i++) {
            temp += i;
            if (getDividends(temp) == dividends) {
                b = false;
                break;
            }
        }
        return temp;
    }

    public static int getDividends(int number) {
        var counter = 0;
        for (var i = 1; i < number; i++) {
            if (number % i == 0) counter++;
        }
        return counter;
    }
}

eigentlich müsste es klappen, programm endet aber nicht

 

[thecain]

Euler war Mathematiker. Der naive Ansatz, führt bei den meisten dieser Probleme nicht zur Lösung.

Oder kurz, sehr lange, kann sich wie Endlos anfühlen 😉

/E und faktisch gesehen hast du potentiell auch eine Endlosschleife...

 

[Jw456]

Deine locale Variable value wird auch nie verändert. Ist immer 0.
Somit endlos Schleife.
Der Vergleich in der for ist immer true.

Einen Bezug auf die laufvariable nimmst du nicht.

 

[httpdigest]

Du suchst eine Zahl mit mindestens fünfhundert Teilern? Angenommen, die ersten 500 Zahlen (von 1 aufsteigend) wären die 500 Teiler dieser hypothetischen Zahl, dann wäre diese Zahl diese hier:
2440273651982220137402477570846093852507148685606385684384827176771690746307763995210992895004406563726027232954296407168326757444156354400961570410318658570955815143878661207545921718172540858349095764849825452688611340346541538922125604620905288437757578931509554299726988735562075288548067654730794942772955756990876979191075075980846482122542653968655491431092619954405562029122162376747419062032712648865974059127793257823317949539144175853857742563560140530349015536821439248780788645072845210469891700259837143002497413923136283250718113386847626017712498493783128253551308963773013187695903550721788011490477880671596952727889810626124647498132890097649330151893471724149275850368400918739385962044527943905194381890435646663513869163017104665641525640046805253815796684903424012415429281958912232255258291902474459826680339104727701885771184037454867590346029172715141656711560317470865537777360240799764769404302935210890815327071968348860960257876627793763278974939317635009013852730676350110956257280000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

BigInteger v = BigInteger.ONE;
for (int i = 1; i < 500; i++) {
    v = v.multiply(BigInteger.valueOf(i));
}
System.out.println(v);

Deine gesuchte Zahl passt also garantiert nicht in einen int oder einen long.

EDIT: Was ich hier geschrieben habe, ist natürlich falsch (siehe unten) 🙂

 

[sserio]

Deine locale Variable value wird auch nie verändert. Ist immer 0.
Somit endlos Schleife.
Der Vergleich in der for ist immer true.

Einen Bezug auf die laufvariable nimmst du nicht.

ich lasse die schleife doch mit einem boolean enden

 

[sserio]

Du suchst eine Zahl mit mindestens fünfhundert Teilern? Angenommen, die ersten 500 Zahlen (von 1 aufsteigend) wären die 500 Teiler dieser hypothetischen Zahl, dann wäre diese Zahl diese hier:
2440273651982220137402477570846093852507148685606385684384827176771690746307763995210992895004406563726027232954296407168326757444156354400961570410318658570955815143878661207545921718172540858349095764849825452688611340346541538922125604620905288437757578931509554299726988735562075288548067654730794942772955756990876979191075075980846482122542653968655491431092619954405562029122162376747419062032712648865974059127793257823317949539144175853857742563560140530349015536821439248780788645072845210469891700259837143002497413923136283250718113386847626017712498493783128253551308963773013187695903550721788011490477880671596952727889810626124647498132890097649330151893471724149275850368400918739385962044527943905194381890435646663513869163017104665641525640046805253815796684903424012415429281958912232255258291902474459826680339104727701885771184037454867590346029172715141656711560317470865537777360240799764769404302935210890815327071968348860960257876627793763278974939317635009013852730676350110956257280000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

BigInteger v = BigInteger.ONE;
for (int i = 1; i < 500; i++) {
    v = v.multiply(BigInteger.valueOf(i));
}
System.out.println(v);

Deine gesuchte Zahl passt also garantiert nicht in einen int oder einen long.

Hmm deswegen hat der Typ in dem Tutorial eine Hash Map oder so benutzt oder Hash set ... ka wie das heißt

 

[Jw456]

Hmm deswegen hat der Typ in dem Tutorial eine Hash Map oder so benutzt oder Hash set ... ka wie das heißt

ich lasse die schleife doch mit einem boolean enden

Mit einem break.
Aber du kommt nie dorthin weil es nicht in ein int passt.
Dein if wird nie true.

Hash Map ist eine Klasse die dynamisch arbeitet.

 

[httpdigest]

Was ich geschrieben habe, war natürlich Käse. Sogar die Zahl 2*3*5*7*11*13*17*19*23 hat schon über 500 Teiler. Mein Test ist ja auch Käse, weil 10 ja auch bereits 5 und 2 als Teiler hat und man dann schon gar nicht mehr mit 10 zu multiplizieren braucht.

 

[sserio]

Oh ne mit einem Big Integer kriege ich es nicht hin, weil ich dann nicht schauen kann wie viele Teiler dieser BigInteger hat (weil ich ihn nicht durch Integer teilen kann) . Als wenn ich jetzt extra lernen muss wie eine Hashmap funktioniert.

Mit einem break.
Aber du kommt nie dorthin weil es nicht in ein int passt.
Dein if wird nie true.

Hash Map ist eine Klasse die dynamisch arbeitet.

 

[Jw456]

dein Code hat auch einen Fehler bei geraden Zahlen rennt er oft in eine endlos Schleife.

zb bei 2 , 4, 6, 10, 12 …. ab

57 läuft er ewig habe ihn nicht bis zum ende laufen lassen.

also deine 500 würde auch bei dem passenden DatenTyp bestimmt Stunden, wenn nicht Tage dauern.

 

[sserio]

Ich habe jetzt einen Algorithmus gefunden der das macht was ich wollte, den ich auch selber verstanden habe. Aber ist das dann nicht irgendwie klauen oder nachmachen, wenn man einfach das ausgedachte von jemand anderem benutzt. Also ich wäre zum Beispiel nicht drauf gekommen das man ein HashSet benutzen kann um dann damit andere Teiler zu finden.
[CODE lang="java" title="Code"]package ProjectEuler12;

import java.util.HashSet;
import java.util.Set;

public class Main {

public static void main(String... args) {
System.out.println(getBiggestDividableNumber(500));
System.out.println(getDivisors(40));
}

public static int getBiggestDividableNumber(final int size) {
for (int value = 1, temp = 2; ; value += temp, temp++) {
if (getDivisors(value).size() > size) {
return value;
}
}
}

private static Set<Integer> getDivisors(int number) {
var firstHalf = new HashSet<Integer>();
var secondHalf = new HashSet<Integer>();
var sqrt = (int) Math.sqrt(number);
for (int i = 1; i <= sqrt; i++) {
if (number % i == 0) {
firstHalf.add(i);
}
}
var iterator = firstHalf.iterator();
while (iterator.hasNext()) {
var value = iterator.next();
secondHalf.add(number / value);
}
firstHalf.addAll(secondHalf);
return firstHalf;
}

}
[/CODE]
Eine Frage hätte ich noch, ist das was in dieser for schleife passiert so legitim und lesbar. Dort werden halt direkt 2 werte initialisiert und dann mit einander verrechnet

 

[Neumi5694]

Im Großen und Ganzen passt das schon. Außerdem kann dich keiner daran hindern, zu kommentieren, was in den Schleifen passiert. Du kannst den Algorithmus abschnittsweise erklären.
Auf den Iterator kannst du verzichten, wenn du ein einfaches for-each verwendest. Das macht genau das Gleiche, nur eben mit weniger Code.

  var iterator = firstHalf.iterator();
  while (iterator.hasNext()) {
    var value = iterator.next();
    secondHalf.add(number / value);
  }
//ist identisch zu
  for (var value : firstHalf) {
    secondHalf.add(number / value);
  }

Es ist üblich, Variablen so spät wie möglich zu deklarieren, erst dort, wo man sie auch braucht. secondHalf z.B. wird erst in dieser genannten Schleife genannt. Praktischerweise ist zu diesem Zeitpunkte auch bekannt, wie viele Werte reinkommen werden, du kannst also gleich auch die Kapazität festlegen. Ebenso kannst du schon von vorneherein die Kapazität von firstHalf bestimmen. Beides ist nicht notwendig, kann aber bei großen Zahlen etwas overhad vermeiden.

/**
 * Diese Methode macht was.
 * <br>Dabei ist der Computer beschäftigt.
 * <br>Den Algorithmus könnte man hier noch erklären, wenn man Bock hat.
 *
 * @param number Eine Zahl, muss größer als 0 sein, sonst geht's in die Binsen
 * @return ein Set, darin enthalten sind Zahlen, die eine gewisse Bedingung erfüllen. Aktuell ist anhand des Namens nicht ganz klar, nach welchen Kriterien die Dividenden ausgewählt werden.
 */
private static Set<Integer> getDivisors(int number) {
        var sqrt = (int) Math.sqrt(number);
        //Hier passiert was Wichtiges
        var firstHalf = new HashSet<Integer>(sqrt*2);
        for (int i = 1; i <= sqrt; i++) {
            if (number % i == 0) {
                firstHalf.add(i);
            }
        }
        //Hier passiert was anderes
        var secondHalf = new HashSet<Integer>(sqrt);
        for (var value : firstHalf) {
            secondHalf.add(number / value);
        }
        //Nochmal gut durchmischen
        firstHalf.addAll(secondHalf);
        return firstHalf;
}

 

[temi]

Ich habe jetzt einen Algorithmus gefunden der das macht was ich wollte, den ich auch selber verstanden habe. Aber ist das dann nicht irgendwie klauen oder nachmachen, wenn man einfach das ausgedachte von jemand anderem benutzt.

Du hättest es ja auch selbst versuchen können, der Lerneffekt wäre dadurch vermutlich deutlich größer. Das deine eigene Lösung dann vielleicht nicht super effizient ist, kann sein, aber das ist in dieser Phase des Lernens noch nicht so wichtig.

Wie kann das dann aussehen? Schau dir die Aufgabe an und zerlege sie in kleine Teile, die du einzeln lösen kannst. Erster Teil der Aufgabe ist demnach eine Methode, um Dreieckzahlen zu erzeugen, die du im zweiten Lösungsschritt anschließend in ihre Teiler zerlegst. Dann musst du im letzten Schritt nur noch die Anzahl der Teiler mit der Anforderung vergleichen. Das machst du so lange, bis die Lösung gefunden ist.

 

[fhoffmann]

getDividends(temp) == dividends

Hier müsste stehen:

getDividends(temp) >= dividends

Wenn es dir zu lange dauert, kannst du dich auch erst einmal mit den Dreieckszahlen beschäftigen:
(EDIT: siehe auch den Hinweis auf Euler in der ersten Antwort)
Eine Dreieckszahl ist immer von der Form:

n * (n+1) / 2

Dabei ist entweder n oder n+1 gerade.
Da n und n+1 teilerfremd sind
sind auch n/2 und n+1 (falls n gerade)
bzw. n und (n+1)/2 (falls n ungerade) teilerfremd.
Die Anzahl der Teiler von n * (n+1) / 2 ist dann das Produkt der Anzahl der Teiler von n/2 und n+1 bzw. von n und (n+1)/2.