Hailstone序列

定義

Hailstone序列定義：

​

H a i l s t o n e ( n ) = { { 1 } , n  <=1 { n } ∪ H a i l s t o n e ( n / 2 ) , if  n  is even { n } ∪ H a i l s t o n e ( 3 n + 1 ) , if  n  is odd Hailstone(n)= \begin{cases} \{1\},&\text{$n$ <=1}\\ \{n\}\cup Hailstone(n/2),&\text{if $n$ is even}\\ \{n\}\cup Hailstone(3n+1),&\text{if $n$ is odd} \end{cases} Hailstone(n)=⎩⎪⎨⎪⎧​{1},{n}∪Hailstone(n/2),{n}∪Hailstone(3n+1),​n <=1if n is evenif n is odd​

有窮性：

​ 對于任意的N，總有 ∣ H a i l s t o n e ( n ) ∣ < 無 窮 |Hailstone(n)|<無窮 ∣Hailstone(n)∣<無窮?

Hailstone序列的非遞歸實作

def hailstone(n):
    hailstone_list = []#記錄序列
    while n > 1:
        hailstone_list.append(int(n))
        if n % 2 == 0:
            n = n / 2
        else:
            n = 3 * n + 1
    if n <= 1:
        hailstone_list.append(int(n))

    return hailstone_list, len(hailstone_list)
           

上述代碼為Hailstone序列的非遞歸實作，下面我們作圖來看一下n與Hailstone序列的關系

import matplotlib.pyplot as plt
nums = range(500)#觀察前500數的Hailstone序列

y_nums = [hailstone(x)[1] for x in nums]

fig = plt.figure()
plt.scatter(nums, y_nums)
plt.xlabel('n')
plt.ylabel('hailstone值')
plt.show()
           

運作結果為：

Hailstone序列的遞歸實作

def recursive_hailstone(hailstone_list):
    """
    hailstone(n)序列求解，遞歸算法
    :param hailstone_list: 這裡傳入的是清單格式，比如[6]，計算清單末尾的Hailstone序列
    :return:
    """
    n = hailstone_list[-1]
    if n <= 1:
        return 1
    if n % 2 == 0:
        hailstone_list.append(n // 2)
    else:
        hailstone_list.append(int(3 * n + 1))
    recursive_hailstone(hailstone_list)

           

運作測試：

test_list = [6]
recursive_hailstone(test_list)
print(test_list)

#結果
[6, 3, 10, 5, 16, 8, 4, 2, 1]