Algorhythmus?

    Servus!

    Ich stehe vor einem kleinen Problem, und wollt mal wissen ob hier ein paar schlaue Köpfe vielleicht ein paar Ideen haben!
    Mir wurde folgende Aufgabe gestellt:

    Gebe eine Zahl n ein,
    falls n ungerade, rechne 3*n+1,
    falls n gerade, rechne n/2.

    Mein Algorhytmus soll nun angeben, ob meine Zahl n irgendwann 1 wird oder nicht.
    Bis 26 werden alle Zahlen 1, 27 läuft bei mir immernoch...
    Mein ursprünglicher Plan war es, das Programm so lange laufen zu lassen, bis entweder 1 raus kommt, oder bis sich einer Schleife gebildet hat.. nur natürlich, gibt es wohl unendlich viele Zahlen, wenn nicht 1 raus kommt und eine Schleife ist somit für mich nicht erkennbar.
    Hat jemand eine Idee, oder kennt vielleicht jemand dieses "Rätsel"?

    MfG,
    Ciarán

    Ich würd mal sagen die Schleifenbildung kann man schon feststellen, und zwar indem man sich jeden neuen Wert in eine Datenstruktur haut und dann bei jeder neuen Zahl überprüft ob diese schonmal vorgekommen ist. Wenn ja, dann ist eine Schleife vorhanden...
    Blöd ist allerdings falls zwar keine Schleife vorkommt, aber diese Berechnung trotzdem nie 1 erreicht.

    Ich *vermute* mal bei näherer Betrachtung könnte man die Aufgabe mathematisch rein auf einem Blatt Papier lösen und man kann irgendwie beweisen dass alle natürlichen Zahlen mit dem Verfahren irgendwann zu 1 führen.

    Übrigens, sicher dass du keinen Fehler in deinem Code hast?
    Ich hab ein billiges Python-Skript geschrieben das innerhalb weniger Sekunden die Produktionen für die ersten paar 1000 n ausgibt, für 27 z.B.:

    Code
    checking number 27
-> 82 -> 41 -> 124 -> 62 -> 31 -> 94 -> 47 -> 142 -> 71 -> 214 -> 107 -> 322 -> 161 -> 484 -> 242 -> 121 -> 364 -> 182 -> 91 -> 274 -> 137 -> 412 -> 206 -> 103 -> 310 -> 155 -> 466 -> 233 -> 700 -> 350 -> 175 -> 526 -> 263 -> 790 -> 395 -> 1186 -> 593 -> 1780 -> 890 -> 445 -> 1336 -> 668 -> 334 -> 167 -> 502 -> 251 -> 754 -> 377 -> 1132 -> 566 -> 283 -> 850 -> 425 -> 1276 -> 638 -> 319 -> 958 -> 479 -> 1438 -> 719 -> 2158 -> 1079 -> 3238 -> 1619 -> 4858 -> 2429 -> 7288 -> 3644 -> 1822 -> 911 -> 2734 -> 1367 -> 4102 -> 2051 -> 6154 -> 3077 -> 9232 -> 4616 -> 2308 -> 1154 -> 577 -> 1732 -> 866 -> 433 -> 1300 -> 650 -> 325 -> 976 -> 488 -> 244 -> 122 -> 61 -> 184 -> 92 -> 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

    Aktuell bin ich grad bei ~1700000 und bisher konnte immer noch alles auf 1 transformiert werden.

    Wann werden eigentlich endlich alle wissen, dass ein Algorithmus nichts mit Rhythmus zu tun hat und auch in der Ellipse kein "y" vorkommt?

    Zitat von Paulchen

    Wann werden eigentlich endlich alle wissen, dass ein Algorithmus nichts mit Rhythmus zu tun hat und auch in der Ellipse kein "y" vorkommt?



    Speziell bei Vorlesungsstream von deutschen Unis hör ich auch immer den Algorüthmus.
    http://de.wikipedia.org/wiki/Algorithmus#Wortgeschichte

    EDIT: So gesehen ist das Problem gemein, wenn es keine wirkliche Lösung gibt.
    Ausser es ist egal, wenn der halt ewig rechnet..

    Einmal editiert, zuletzt von mtoman (18. November 2010 um 12:44)

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden