Collatz Problem in C



  • Hi @ all,
    soll von der FH folgendes Programmieren:
    und zwar einmal:

    Aufgabe 2.1 (Maximum einer ULAM-Folge)
    Schreiben Sie eine C-Funktion
    int ulam_max(int a0);
    die für eine ganze positive Zahl a0 den maximalen Wert in der Folge ihrer ULAM-Werte
    berechnet. Hat a0 einen Wert kleiner oder gleich 0, soll die Funktion -1 liefern.
    Beispiel: Der Aufruf ulam_max(5) soll den Wert 16 und ulam_max(7) den Wert 52
    liefern.
    

    Was ich wie folgt gelöst habe:

    int ulam_max(int a0)
    {
    	int aktuelleZahl = a0;
            printf("Startwert: %d \n" , aktuelleZahl);
    	int max = -1;
    	while(aktuelleZahl > 1)
    	{
    		if((aktuelleZahl % 2) == 0 && aktuelleZahl > 0)
    		{
    			aktuelleZahl = aktuelleZahl / 2;
    		}
    
    		else
    		{
    			aktuelleZahl = aktuelleZahl * 3 + 1;
    		}
    
    		if(aktuelleZahl > max)
    		{
    			max = aktuelleZahl;
    		}
                    printf("%d \t" , aktuelleZahl);
    	}
    	return max;
    }
    

    dann sollen wir noch das Programmieren:

    Aufgabe 2.2 (ULAM-Zwillinge)
    Schreiben Sie eine C-Funktion
    int ulam_twins(int limit);
    die prüft, ob es im Intervall von 1 bis einschließlich limit zwei benachbarte Werte a0
    und a0+1 gibt, für die ulam_max(a0) = ulam_max(a0 + 1) gilt. Ein solches Paar wird
    als ULAM-Zwilling bezeichnet.
    Die Funktion soll a0 liefern, wenn ein Paar gefunden wurde und a0 die kleinere Zahl in
    einem solchen Paar ist. Sind mehrere Paare im Intervall enthalten, soll das letzte Paar
    gesucht werden. Die Funktion soll -1 zurückgeben, wenn kein solches Zwillingspaar
    gefunden wurde.Beispiel: Da ulam_max(5) = ulam_max(6) = 16, soll der Aufruf
    ulam_twins(10) den Wert 5 und
    ulam_twins(5) den Wert -1 liefern, da 6 nicht mehr im Intervall enthalten ist.
    

    Da weiß ich irgendwie nicht wie ich es lösen soll, da ich meine Folge nicht in ein Array speichern kann (man weiß ja nicht wie groß die Folge ist) und somit, da ich nur ein Limit übergeben bekomme, kann ich ja auch nicht die Folgen nochmal darin erstellen. Oder ich versteh die Aufgabe noch nicht so ganz. Kann mir mal jemand versuchen einen Lösungsansatz zu schreiben? Also ich will nicht das Ihr meine Aufgaben löst oder sowas sondern nur ein Ansatz! Danke schonmal im vorraus.



  • Du zerlegst nicht.

    Deins:

    int ulam_max(int a0)
    {
        int aktuelleZahl = a0;
            printf("Startwert: %d \n" , aktuelleZahl);
        int max = -1;
        while(aktuelleZahl > 1)
        {
            if((aktuelleZahl % 2) == 0 && aktuelleZahl > 0)
            {
                aktuelleZahl = aktuelleZahl / 2;
            }
    
            else
            {
                aktuelleZahl = aktuelleZahl * 3 + 1;
            }
    
            if(aktuelleZahl > max)
            {
                max = aktuelleZahl;
            }
                    printf("%d \t" , aktuelleZahl);
        }
        return max;
    }
    

    Hübsch:

    int ulam(int aktuelleZahl)
    {
            if((aktuelleZahl % 2) == 0 && aktuelleZahl > 0)
            {
                return aktuelleZahl / 2;
            }
    
            else
            {
                return aktuelleZahl * 3 + 1;
            }
    }
    int ulam_max(int a0)
    {
        int aktuelleZahl = a0;
            printf("Startwert: %d \n" , aktuelleZahl);
        int max = -1;
        while(aktuelleZahl > 1)
        {
            aktuelleZahl = ulam(aktuelleZahl);
            if(aktuelleZahl > max)
            {
                max = aktuelleZahl;
            }
            printf("%d \t" , aktuelleZahl);
        }
        return max;
    }
    

    Hübscher:

    int ulam(int aktuelleZahl)
    {
            if((aktuelleZahl % 2) == 0 && aktuelleZahl > 0)
            {
                return aktuelleZahl / 2;
            }
    
            else
            {
                return aktuelleZahl * 3 + 1;
            }
    }
    int ulam_max(int a0)
    {
        int max = -1;
        int aktuelleZahl = a0;
        while(aktuelleZahl > 1)
        {
            aktuelleZahl = ulam(aktuelleZahl);
            if(aktuelleZahl > max)
            {
                max = aktuelleZahl;
            }
        }
        return max;
    }
    und die Ein- und Ausgabe in der main()
    

    Und dann kannste besimmt ohne Array in diesem Stil (Ein Zweck - Eine Funktion)

    for...
       alt_max=neu_max
       neu_max=max_ulam(...
       if(alt_max==neu_max) merksDir;
    

    machen.



  • ja ok das ist wirklich schöner.
    Jedoch, mein großes Problem ist:
    ich kenn doch meine vorherige Folge nicht!
    Also wenn ich mir maximumwerte von 5 und 6 berechenen lasse und mich daraus die Zwillinge interessieren, kenn ich doch in der Funktion ulam_twins die 5 und 6 nicht mehr! oder darf man diese wohl global machen?



  • weil wenn man die Zahlen Global machen würde ( ich weiß das man es nicht machen sollte es sei denn es lässt sich nicht so recht vermeiden ) dann würde ich die Funktion für die Zwillingen so programmieren:

    int ulam_twins(int limit)
    {
        int index = 0;
        int ersteZahl = zahl1;
        int zweiteZahl = zahl2;
    
        int zwilling = -1;
    
        while (ersteZahl != 1 && zweiteZahl != 1)
        {
            if (ersteZahl == zweiteZahl - 1 && zwilling < ersteZahl)
            {
                zwilling = ersteZahl;
            }
            ersteZahl = ulam(ersteZahl);
            zweiteZahl = ulam(zweiteZahl);
        }
        return zwilling;
    }
    


  • llTodoll schrieb:

    ja ok das ist wirklich schöner.
    Jedoch, mein großes Problem ist:
    ich kenn doch meine vorherige Folge nicht!
    Also wenn ich mir maximumwerte von 5 und 6 berechenen lasse und mich daraus die Zwillinge interessieren, kenn ich doch in der Funktion ulam_twins die 5 und 6 nicht mehr! oder darf man diese wohl global machen?

    Funktionsaufrufe!
    Am Deppigsten wohl per

    if(ulam_max(5)==ulam_max(6))
    


  • verstehe wohl das ich das mit Funktionsaufrufen machen soll, jedoch Frage ich mich was ulam_max mit den Zwillingen zutun hat, man will doch die Zwillinge finden und nicht gucken ob die gleichen Maxima hat.

    Sorry nochmal das es so lange bei mir braucht um es zu verstehen ^^



  • Programmieren fällt Dir anscheinend leichter, als die Aufgabe zu verstehen.

    Mach mal die Tabelle fertig:
    ulam_max(1)=
    ulam_max(2)=
    ulam_max(3)=
    ulam_max(4)=
    ulam_max(5)=
    ulam_max(6)=
    ulam_max(7)=
    ulam_max(8)=
    ulam_max(9)=
    ulam_max(10)=

    Dann sollte ersichtlich werden, was der Chefg als einen Zwilling bezeichnet hat. Bei 5/6 sollte einer sein.



  • Mach mal die Tabelle fertig:

    ulam_max(1)= 1
    Maximum: 1
    ulam_max(2)= 2       1
    Maximum: 2
    ulam_max(3)= 3       10      5       16      8       4       2       1
    Maximum: 16
    ulam_max(4)= 4       2       1
    Maximum: 4
    ulam_max(5)= 5       16      8       4       2       1
    Maximum: 16
    ulam_max(6)= 6       3       10      5       16      8       4       2       1
    Maximum: 16
    ulam_max(7)= 7       22      11      34      17      52      26      13      40      20 10 5
    Maximum: 52
    ulam_max(8)= 8       4       2       1
    Maximum: 8
    ulam_max(9)= 9       28      14      7       22      11      34      17      52      26     13    40    20      10      5       16      8       4       2       1
    Maximum: 52
    ulam_max(10)= 10      5       16      8       4       2       1
    Maximum: 16
    

    Kann das denn sein, das nur wenn beide Folgen die gleichen Maxima haben, dann auch Zwillinge haben können?



  • ne das ist auch quatsch, meit er vielleicht die 16 als Zwillinge?
    Und a0 und a0 +1 nur als Startwert?

    Also dannwäre a0 = 5, a0 + 1 = 6 und 16 das Zwilling ?



  • ulam_max gibt nur das Maximum zurück.

    ulam_max(1)= 1
    ulam_max(2)= 2
    ulam_max(3)= 16
    ulam_max(4)= 4
    ulam_max(5)= 16
    ulam_max(6)= 16
    ulam_max(7)= 52
    ulam_max(8)= 8
    ulam_max(9)= 52
    ulam_max(10)= 16
    

    Kann das denn sein, das nur wenn beide Folgen die gleichen Maxima haben, dann auch Zwillinge haben können?

    Er nennt 5 und 6 einen Zwilling, weil ulam_max(5)==ulam_max(6).

    Als Rückgabe möchte er dann 5 haben, also den kleineren Zwillingspartner.



  • Hi

    ich Sitz auch Grade an der Aufgabe. Das mit den Twins geht recht einfach.

    if (ulam_max(i) == ulam_max(i + 1))
            {
                twin = i;
            }
    

    Da sind Wirklichkeit 2 gleiche Maxima gefragt die hintereinander liegen.

    Die Dritte Aufgabe bereitet mir aber Kopfschmerzen.

    Da sollen wir Mehrlinge finden.

    ulam_multiples(1000, 3)
    

    soll den wert 972 zurückgeben da 972,973 und 974 das gleiche Maxima haben. Erster Parameter steht fürs Limit bis zu dem gezählt wird und der 2. für die Anzahl Mehrlinge(2 = Zwillinge, 3 = Drillinge etc.).

    Da wir erst angefangen haben mit C komm ich grad gar nicht Klar.

    Erst wollte ich wenn nach Vierlingen gefragt war und ein Zwilling gefunden wurde einfach noch 2 mal ulam_twins(i + 2) ulam_twins(i + 3) ausführen und gucken ob die auch noch gleich sind. Weiß aber nicht wie ich jetzt explizit sagen kann führe funktion ulam_twins() 3 mal aus.

    Ah ist schon spät. Morgen mal ausführlicher aber vieleicht kann ja schon wer helfen.

    cu



  • if (ulam_max(i) == ulam_max(i + 1))
            {
                twin = i;
            }
    

    Was man mit Gewalt sogar noch functional zerlegen könnte in

    if (is_ulam_twin(i))
            {
                twin = i;
            }
    

    nebst

    bool is_ulajm_twin(int i)
    {
       if( ulam_max(i) == ulam_max(i + 1) )
          return true;
       else
          return flase;
    

    Da sollen wir Mehrlinge finden.

    Das geht leicht:

    if (is_ulam_mehrling(i,anz))
            {
                mehrling = i;
            }
    

    nebst

    //Funktion mit Schleife drin zur Übung freigelassen
    


  • Ui

    auch noch wach. Also erstmal alles ohne Gewähr(Schon das ein oder andere Bier vernichtet), zudem probier ich mal einfach bisschen rum.

    int ulam_multiples(int limit, int number)
    {
        int multiples[number];
        int i;
        int check = 0;
        int n = number - 1;
        for (i = 1; i < limit - n; i++)
        {
            if (ulam_max(i) == ulam_max(i + 1))
            {
                for ( n = 1; n <= number; n++ )
                {
                    if(ulam_max(i + 1) == ulam_max(i + 1 + n) )
                    {
                        multiples[n - 1] = i;
                    }
                    else
                    {
                        multiples[n - 1] = i + 1 + n;
                    }
                }
            }
        }
    
        for (i = 0; i < number; i++)
        {
            if(multiples[i] == multiples[i + 1])
            {
                check++;
            }
            else
            {
                check--;
            }
        }
    
        return (check == number - 1 ? multiples[0] : -1);
    }
    

    Da wurde jetzt auch schon ordentlich rumgefrickelt. Im moment geht rein gar nix.

    Vielen Dank für die schnelle und gehaltvolle Antwort! 👍

    cu



  • Ja die Twins Funktion war total leicht, als ich diese dann auch mal verstanden habe 😃
    zu den Mehrlinge:
    da würd mir glaub ich schon die twins Funktion zu nutze machen, da man ja einfach daraus schließen kann:
    keine Zwilinge = keine Mehrlinge!



  • wieso willst du es denn mit Arrays lösen?
    Habe es so gelöst:

    int ulam_multiples(int limit, int number)
    {
        int index = 1;
        int index2 = 1;
        int anz = number;
        int num;
        int multiples = -1;
    
        if (number == 2)
        {
            multiples = ulam_twins(limit);
        }
        else
        {
            for (index = 1; index < limit; index++)
            {
                if ((num = ulam_twins(index)) != -1)
                {
                    anz--;
                    for (index2 = index + 1; index2 < index + number; index2++)
                    {
                        if ((ulam_twins(index2) - (index2 - index)) == num)
                        {
                            anz--;
                        }
                        else if (anz == 1)
                        {
                            multiples = num;
                        }
                        else
                        {
                            anz = number;
                        }
                    }
                }
            }
        }
        return multiples;
    
    }
    

    Die Frage ist nur:
    wie geht es effizenter?
    Das ist noch nicht perfekt werde noch weiter basteln für Vorschläge bin ich natürlich sehr offen :-P...



  • bin mir absolut nicht sicher ob ich die beiden for-Schleifen in der Funktion brauche, wenn würde ich versuchen da zu reduzieren da ich ja auch noch in der Funnktion ulam_twins eine for-Schleife habe...
    aber wie gesagt absolut nicht sicher muss nochmal drüber gucken....

    PS: Falls jemand was sieht was blödsinn ist gerne melden 🙂



  • volkard schrieb:

    bool is_ulajm_twin(int i)
    {
       if( ulam_max(i) == ulam_max(i + 1) )
          return true;
       else
          return flase;
    
    bool is_ulajm_twin(int i)
    {
        return (ulam_max(i) == ulam_max(i + 1));
    }
    


  • llTodoll schrieb:

    Die Frage ist nur:
    wie geht es effizenter?

    Einen guten Entwurf vorausgesetzt, werden Programme richtig schnell, wenn man verzichtet, statt immer nur Sachen dranzuschrauben.

    lastmax=-1
    for i=1 to limit
      max=ulam_max(i)
      if max!=lastmax
        lastmax=max
        len=1
      else
        ++len
        if len>=number
           result=i-number+1
    


  • llTodoll schrieb:

    PS: Falls jemand was sieht was blödsinn ist gerne melden 🙂

    Hier ist er:

    llTodoll schrieb:

    da würd mir glaub ich schon die twins Funktion zu nutze machen, da man ja einfach daraus schließen kann:
    keine Zwilinge = keine Mehrlinge!

    oder im Code Zeile 9 bis 37. 🤡



  • Ja ok vestehe schon war ne scheiß Idee werde mich nochmal dran setzen danke für dein Tip 🙂


Log in to reply