Előző - #38 Véletlenszerű keverés | Tartalomjegyzék | Következő - #40 Két rendezett lista egyesítése

39. GYAKORLAT: COLLATZ SZEKVENCIA

collatz(10)  →  [10, 5, 16, 8, 4, 2, 1]

A Collatz-sorozat, amelyet 3 n + 1-nek is neveznek, egy egyszerű, de titokzatos numerikus sorozat, amelyet a matematikusok megoldatlanok maradtak. Négy szabálya van:

• Kezdje egy pozitív, nullától eltérő egész számmal, melynek neve n .
• Ha n értéke 1, a sorozat véget ér.
• Ha n páros , n következő értéke n / 2.
• Ha n páratlan, n következő értéke 3 n + 1.

Például, ha a kezdő egész szám 10, akkor ez a szám páros, tehát a következő szám 10/2, vagy 5. 5 páratlan, tehát a következő szám 3 × 5 + 1, vagy 16. 16 páros, így a a következő szám 8, ami még így is a következő szám 4, majd 2, majd 1. 1-nél a sorozat megáll. A teljes Collatz-sorozat 10-től kezdődően a következő: 10, 5, 16, 8, 4, 2, 1

A matematikusok nem tudták bizonyítani, hogy végül minden kezdő egész szám véget ér-e. Ez adja a Collatz Sequence leírását „a legegyszerűbb lehetetlen matematikai feladatnak”. Ebben a gyakorlatban azonban nem kell mást tenni, mint kiszámítani egy adott kezdő egész szám számsorát.

Gyakorlat leírása

Írjon egy paraméterrel elnevezett collatz()függvényt startingNumber. A függvény a létrehozó Collatz sorozat egész számainak listáját adja vissza startingNumber . A lista első egész számának startingNumber , az utolsó egész számnak pedig 1.

A függvénynek ellenőriznie kell, hogy startingNumber egy egész szám kisebb-e 1-nél, és ebben az esetben üres listát kell visszaadnia.

Ezek a Python- assertutasítások leállítják a programot, ha feltételük False. Másolja őket a megoldási program aljára. Az Ön megoldása akkor helyes, ha a következő assertállítások feltételei mind igazak :

assert collatz(0) == []

assert collatz(10) == [10, 5, 16, 8, 4, 2, 1]

assert collatz(11) == [11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

assert collatz(12) == [12, 6, 3, 10, 5, 16, 8, 4, 2, 1]

assert len(collatz(256)) == 9

assert len(collatz(257)) == 123

véletlenszerű importálás

random.seed(42)

i tartományban (1000):

    kezdőszám = random.randint(1, 10000)

    seq = collatz(kezdőszám)

    assert seq[0] == kezdőszám # Győződjön meg róla, hogy tartalmazza a kezdőszámot.

    assert seq[-1] == 1  # Győződjön meg róla, hogy az utolsó egész szám 1.

Próbáljon megoldást írni a leírásban szereplő információk alapján. Ha továbbra is problémái vannak ennek a gyakorlatnak a megoldásával, további tippekért olvassa el a Megoldástervezés és a Különleges esetek és Gotchák című részt.

Előfeltétel fogalmak: listák, while ciklusok, modulo operátor, egész osztás,append()

Megoldás tervezése

A függvénynek csak egy változóra van szüksége az aktuális szám nyomon követéséhez, amelyet hívhatunk num, és egy változóra az értéksorozat tárolására, amelyet hívhatunk sequence. A függvény elején állítsa numbe az egész számot a startingNumberparaméterben és sequence -ra [num]. Használhatunk olyan while ciklust, amely addig folytatja a ciklust, amíg a numnem 1. A ciklus minden iterációja során a következő érték numkiszámítása az alapján történik, hogy a szám pillanatnyilag páratlan vagy páratlan. Ennek meghatározásához használhatja a 3. gyakorlat modulo 2 technikáját, a „Páratlan és páros”: ha a szám % 2 értéket kap, 0akkor a szám páros, ha pedig páratlan, 1 akkor numpáratlan. Ezt követően fűzze a számot a lista végéhez sequence .

Ha numpontosan 1, akkor a whileciklus leáll, és a függvény visszatérhet sequence.

Különleges esetek és Gotchák

Az egyetlen speciális eset az, ha a startingNumber paraméter kisebb, mint 1, ebben az esetben nincs sorozat, és a függvénynek üres listát kell visszaadnia [].

Most próbáljon meg egy megoldást írni az előző szakaszok információi alapján. Ha továbbra is problémái vannak a gyakorlat megoldásával, olvassa el a Megoldássablon részt további tippekért.

Megoldás sablon

Próbáljon először megoldást írni a semmiből. De ha nehézségei vannak, akkor a következő részprogramot használhatja kiindulási helynek. Másolja ki a következő kódot a https://invpy.com/collatzsequence-template.py webhelyről , és illessze be a kódszerkesztőbe. Cserélje ki az aláhúzást kódra, hogy működő programot készítsen:

def collatz(kezdőszám):

    # Ha a kezdő szám 0 vagy negatív, adjon vissza egy üres listát:

    ha ____ < 1:

        Visszatérés ____

 

    # Hozzon létre egy listát a sorozat megtartásához, kezdve a kezdő számmal:

    sorozat = [____]

    szám = ____

    # Folytassa a hurkot, amíg az aktuális szám 1 lesz:

    míg a ____ 1:

        # Ha páratlan, a következő szám az aktuális szám háromszorosa plusz 1:

        ha szám % 2 == ____:

            szám = 3 * szám + 1

        # Ha páros, a következő szám az aktuális szám fele:

        más:

            szám = szám // ____

        # Jegyezze fel a számot a sorozatlistába:

        sequence.append(____)

 

    # Visszaadja a számsort:

    Visszatérés ____

A gyakorlat teljes megoldását az A függelék és a https://invpy.com/collatzsequence.py tartalmazza . A program minden lépését megtekintheti, amint az egy hibakereső alatt fut a https://invpy.com/collatzsequence-debug/ oldalon .

További irodalom

You can find out more about the Collatz sequence on Wikipedia at https://en.wikipedia.org/wiki/Collatz_conjecture. There are videos on YouTube about the sequence on the Veritasium channel titled “The Simplest Math Problem No One Can Solve - Collatz Conjecture” at https://youtu.be/094y1Z2wpJg and and the Numberphile channel titled “UNCRACKABLE? The Collatz Conjecture” at https://youtu.be/5mFpVDpKX70.

Prev - #38 Random Shuffle | Table of Contents | Next - #40 Merging Two Sorted Lists