考拉茲猜想

陳新龍

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

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

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

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

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

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