8.2　考拉茲猜想的樹形圖

圖8-2顯示的是我們?cè)谟懻摽祭澆孪氲臅蛘撐闹谐３？吹降臉湫螆D。每個(gè)數(shù)字在分支中以從上往下的方向顯示考拉茲序列中的數(shù)字，例如之前列舉的數(shù)字13，順著13往下便能找到根據(jù)考拉茲規(guī)則計(jì)算出的那一系列數(shù)字。迄今為止調(diào)查到的所有數(shù)字都會(huì)到達(dá)4、2，最后再到1，因此所有數(shù)字都是起源于同一樹中的分支。美國(guó)阿肯色大學(xué)的埃德蒙·哈里斯（Edmund Harriss）教授又提出了另外一種圖形化的方法，他在標(biāo)準(zhǔn)圖的基礎(chǔ)上新添了一條關(guān)于分支方向的規(guī)則，用來(lái)反映一個(gè)數(shù)字是由兩種算法中的哪一種運(yùn)算而生成，即：無(wú)論你是樹枝中的哪個(gè)數(shù)字，如果在你上面的數(shù)字是你的2倍，則上端分支會(huì)以固定角度向順時(shí)針方向轉(zhuǎn)動(dòng)；如果不是2倍，則以固定角度向逆時(shí)針方向轉(zhuǎn)動(dòng)。這樣得到如圖8-3所示的形狀。如果把數(shù)字去掉，并對(duì)線條著色，我們就可以得到一個(gè)像是正在野蠻生長(zhǎng)的水藻或是正在綻放的禮炮的動(dòng)畫，它的實(shí)現(xiàn)也不太復(fù)雜，我們來(lái)動(dòng)手實(shí)現(xiàn)一下。

要實(shí)現(xiàn)圖8-3中第二種考拉茲樹形圖首先要找到樹形關(guān)系圖，我們?cè)谕嬗螒驎r(shí)是正推，比如3→10→5→16→8→4→2→1，但是現(xiàn)在需要倒推，也就是說(shuō)，我們要找什么數(shù)會(huì)走到1，很顯然只有2，什么數(shù)能走到2，只有4，如此往上逆推，當(dāng)走到16時(shí)，情況發(fā)生了變化，32→16，5→16，也就是說(shuō)16有{32，5}兩個(gè)父節(jié)點(diǎn)，然后，我們要繼續(xù)為32和5找父節(jié)點(diǎn)。很明顯，一個(gè)永遠(yuǎn)存在的父節(jié)點(diǎn)就是自身的2倍；另一個(gè)則可以通過(guò)化簡(jiǎn)正向推演的公式求出，當(dāng)前數(shù)是奇數(shù)時(shí)，我們就乘3加1，寫成數(shù)學(xué)表達(dá)式就是

因?yàn)?/p>

k=3n+1

所以

n=（k-1）/3

執(zhí)行這個(gè)運(yùn)算的前提是k-1能被3整除，另外還要保證求出來(lái)的n一定要是奇數(shù)，否則根本就不是執(zhí)行乘3加1這個(gè)操作。怎么保證這兩個(gè)條件呢，我們把n改寫成2m+1，代入到k=3n+1，可以得到

因?yàn)?/p>

k=3（2m+1）+1=6m+4

所以

（k-4）mod 6=0

也就是說(shuō)k-4要能被6整除，才需要計(jì)算n=（k-1）/3整個(gè)操作。

通過(guò)幾次簡(jiǎn)單手算以后，很快發(fā)現(xiàn)，每往上推演一層，就會(huì)有多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)又會(huì)延伸出最多兩個(gè)父節(jié)點(diǎn)（有些只有一個(gè)父節(jié)點(diǎn)，比如6），整個(gè)結(jié)構(gòu)就是一個(gè)典型的樹狀結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)怎么存儲(chǔ)比較方便呢？我們下面介紹Python的另一種數(shù)據(jù)結(jié)構(gòu)——字典。