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]