2025年3月15日 星期六 甲辰(龙)年 月十四 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q06: 改版考拉兹猜想

时间:12-26来源:作者:点击数:35

1. 问题描述

考拉兹猜想:

对自然数n执行如下操作:

+ 若n是偶数,用n除以2

+ 若n是奇数,用n乘以3后加1

如此循环操作的话,无论初始值是什么,最终都会得到1(会进入1-->4-->2-->1)的循环

考虑稍微修改一下以上迭代的规则。当初始状态是偶数的话,第一次也用n乘以3加1,其后迭代规则不变。

求在10000以内的偶数中总共有多少个数,经过以上修改的迭代规则能够回到初始状态的?

注意,由于原始考拉兹猜想是无论什么初始状态最后都将回到1,所以在改版考拉兹猜想中,无论初始值是什么最终也终将回到1.只不过有一些偶数会先回到初始状态然后再收敛到1.本题就是要找有多少这样的会回到初始状态的数。

2. 解题分析

这个题目实在没有什么好分析的。

循环迭代,不管是到达1还是回到初始状态都停止循环。到达1表明不是“会回到初始状态”的数,到达1之前先回到初始状态的数则是所寻找的对象。

3. 代码及测试

  • # -*- coding: utf-8 -*-
  • """
  • Created on Mon Aug 23 13:40:11 2021
  • @author: chenxy
  • """
  • import sys
  • import time
  • import random
  • from typing import List
  • from queue import Queue
  • from collections import deque
  • class Solution:
  • def numOfLoop(self, N: int) -> List:
  • ans = []
  • def modified_collatz(K):
  • isFirst = True
  • a = K
  • while 1:
  • if a%2 == 0:
  • if isFirst:
  • a = 3*a + 1
  • isFirst = False
  • else:
  • a = a/2
  • else:
  • a = 3*a + 1
  • if a == K:
  • return True # Find one loop in modified collatz iteration
  • if a == 1:
  • return False # No loop found in modified collatz iteration
  • for n in range(2,N,2):
  • if modified_collatz(n):
  • ans.append(n)
  • return ans
  • if __name__ == '__main__':
  • sln = Solution()
  • tStart = time.time()
  • N = 1000000
  • ans = sln.numOfLoop(N)
  • tCost = time.time() - tStart
  • print('N = {0}, numOfLoops = {1}, tCost = {2}(sec)'.format(N, len(ans), tCost))

运行结果如下:

N = 10000, numOfLoops = 34, tCost = 0.0997314453125(sec)

print(ans):[2, 4, 8, 10, 14, 16, 20, 22, 26, 40, 44, 52, 106, 184, 206, 244, 274, 322, 526, 650, 668, 790, 866, 976, 1154, 1300, 1438, 1732, 1780, 1822, 2308, 2734, 3238, 7288]

不过正如原书中所说的,虽然在10000以内就找到了34个数能回到初始状态,再加大搜索范围就再也没有了。笔者验证1,000,000以内是没有的。这个也确实有点神奇,由此间接地能略窥一点原始考拉兹猜想的神秘风采。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门