Collatz Folge: Welche Startzahl a1 < 100000 hat die längste Collatz Folge?

Alpay

Ich studiere momentan noch im 1.Semester und habe diese Aufgabe vor mir liegen. Leider habe ich überhaupt keine Ahnung wie ich das Programm so schreibe das es mir die Startzahl anzeigt welche die längste Collatz Folge mit sich zieht.

Der einzige Gedanke der mir hierbei einfällt ist etwas mit if und else Funktion, genauer genommen habe ich im Kopf folgendes

int a;
for(a=0;a<100000; a++)
{
if(a%2 == 0)
a = a/2;
else
{
a = 3*a+1;
}
}

Ist dieser Gedanke irgendwo bisschen richtig? Komme ich damit weiter? Wäre sehr hilfreich wenn mir jemand ein Denkanstoß geben könnte, von mir aus auch die ganze Lösung (Ich muss das Programm erklären können, was bedeutet dass ich die gesamte Lösung dann so oder so studieren und verstehen muss)

Belli

Da ich keine Ahnung hatte, was eine Collatz Folge ist, habe ich mal gegoogelt und diese Seite hier gefunden:
https://de.wikipedia.org/wiki/Collatz-Problem
Das verstehe ich so, dass diese Folge unendlich lang ist, egal welche Startzahl man nimmt ...
Es gibt also keine Startzahl mit der längsten Collatz Folge

SeppJ

Du vermischt gerade zwei Dinge, 1. das Erzeugen der Collatzfolge, und 2. das Durchprobieren der 100000 Folgen.

Kennst du Funktionen? Nimm an, du hast eine Funktion int collatz_length(int number), die dir die Länge der Collatzfolge von number liefert. Wie würdest du damit herausfinden, welche der Zahlen < 100000 die längste Folge hat? Tipp: Das ist nicht schwer

Und wenn du das hast, dann brauchst du nur noch diese ominöse Funktion int collatz_length(int number) zu schreiben. Was auch nicht so viel schwieriger ist.

Man könnte da auch noch allerlei optimieren, zum Beispiel sich schon bekannte Zwischenwerte merken. Das ist aber schon wesentlich anspruchsvoller, wenn du schon mit der Basisaufgabe Schwierigkeiten hast. 100000 sollte ein Computer heute in wenigen Sekunden oder schneller schaffen. Wenn die Aufgabe wäre, die ersten 1000000 zu checken, dann wären soclhe Optimierungen noch ienmal eine Überlegung wert

SeppJ

@Belli sagte in Collatz Folge: Welche Startzahl a1 < 100000 hat die längste Collatz Folge?:

Da ich keine Ahnung hatte, was eine Collatz Folge ist, habe ich mal gegoogelt und diese Seite hier gefunden:
https://de.wikipedia.org/wiki/Collatz-Problem
Das verstehe ich so, dass diese Folge unendlich lang ist, egal welche Startzahl man nimmt ...
Es gibt also keine Startzahl mit der längsten Collatz Folge

Dann hast du das falsch verstanden. Der Punkt ist doch gerade, dass sie (vermutlich) immer endlich ist. Unter den ersten 100000 wirst du gewiss kein Gegenbeispiel finden

Belli

Zitat:
So erhält man zum Beispiel für die Startzahl n = 19 die Folge

19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, …

Das sieht für mich nach ner unendlichen Folge aus?

SeppJ

@Belli sagte in Collatz Folge: Welche Startzahl a1 < 100000 hat die längste Collatz Folge?:

Zitat:
So erhält man zum Beispiel für die Startzahl n = 19 die Folge
19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, …
Das sieht für mich nach ner unendlichen Folge aus?

19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Dies ist die ganze Folge, die gemeint ist

Alpay

@SeppJ Vielen dank für deine Hilfe, könntest du mir eventuell noch eine Hilfe geben?
Mit Funktionen setze ich mich zurzeit auseinander aber blicke leider noch nicht zu 100% durch.

Ich weiß das int collatz_lenght(int number) eine neue Funktion ist die wir selber erstellt haben, aber wie hilft mir das weiter?

DocShoe

Wenn ich die Aufgabe richtig verstanden habe sollst du doch die Startzahl der längsten Collatzfolge bestimmen.
Pseudo code:

unsigned int calculate_collatz_length( unsigned int initial_value )
{
    // to do: Länge der Collatz Folge berechnen und zurückgeben
}

void f()
{
   unsigned int candidate_length = 0;
   unsigned int candidate_initial = 0;

   for( unsigned int i = 1; i < 1000000; ++i )
   {
      unsigned int const current_length = calculate_collatz_length( i );
      if( current_length > candidate_length )
      {
         candidate_length = current_length ;
         candidate_initial = i;
      }
   }
   // candidate_initial ist der Startwert der längsten Collatzfolge, Länge steht in candidate_length 
}