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()
运行结果为:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL4VkeOdXSU5UMRpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLzYzNzETMxkTM2ITNwAjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
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]