考拉茲猜想

陳新龍

考拉茲猜想是德國(guó)的數(shù)學(xué)家洛薩·考拉茲在1937年提出的一個(gè)著名的猜想，任意正整數(shù)n，如果n是偶數(shù)，就將它減半（即n/2）;如果它是奇數(shù)，則將它乘3加1（即3n+1），不斷重復(fù)這樣的運(yùn)算，經(jīng)過(guò)有限步驟后，一定可以得到數(shù)字1。假設(shè)我們?cè)O(shè)置初始數(shù)字為3，按照上述變換的規(guī)則，可以得到一個(gè)數(shù)列3，10，5，16，8，4，2，1。

這個(gè)猜想看似相當(dāng)簡(jiǎn)單，但實(shí)際上卻很難證明，80多年來(lái)，眾多的數(shù)學(xué)家始終未能解決它，只能說(shuō)從已有的測(cè)試中還沒(méi)有找到反例。今天我們通過(guò)Scratch中的自定義模塊結(jié)合遞歸的思想，來(lái)模擬一下該數(shù)學(xué)猜想。

首先復(fù)習(xí)一下什么是遞歸：簡(jiǎn)單來(lái)說(shuō)遞歸就是程序調(diào)用自身。遞歸的思想就是把一個(gè)復(fù)雜問(wèn)題層層轉(zhuǎn)化為多個(gè)規(guī)模更小的問(wèn)題，原問(wèn)題被拆解成子問(wèn)題后，遞歸調(diào)用繼續(xù)進(jìn)行，直到子問(wèn)題不需進(jìn)一步遞歸就可以解決的地步為止。要注意遞歸必須有一個(gè)明確的結(jié)束條件，稱(chēng)為遞歸出口。

就拿考拉茲猜想為例，如果輸入的數(shù)字是10，則10除以2得5，這時(shí)我們需要來(lái)判斷5，這一步就是遞歸。接下來(lái)5乘以3再加1得16，我們又需要判斷16，這步也是遞歸。直至最后數(shù)字的結(jié)果為1時(shí)，遞歸結(jié)束，程序也結(jié)束。

理解遞歸思想后，開(kāi)始編寫(xiě)代碼，按照題目分析首先將問(wèn)題拆分成兩大部分，當(dāng)最終結(jié)果數(shù)字n的值等于1的時(shí)候結(jié)束循環(huán)，程序終止。當(dāng)結(jié)果不等于1的時(shí)候，繼續(xù)拆分成兩部分，判斷數(shù)字n的結(jié)果是奇數(shù)還是偶數(shù)，如果是偶數(shù)的話(huà)，在原基礎(chǔ)上將數(shù)字整除2，然后將數(shù)字插入到列表中，如果數(shù)字是奇數(shù)的話(huà)，在原基礎(chǔ)上將數(shù)字乘3加1，然后將數(shù)字插入到列表中。最后將每次執(zhí)行完的結(jié)果輸出。

你也可以嘗試用Python來(lái)編寫(xiě)考拉茲猜想，也歡迎大家分享更多的不同的思路。