最小的自然数是1对吗,证明1是最小的自然数

首页 > 经验 > 作者:YD1662022-10-27 13:23:03

  总部位于东京涩谷的 Bakuage Co., Ltd. 于2021年7月7日宣布,该公司将为揭秘未解数学难题 Collatz猜想的人才提供 1.20 亿日元(约为 108 万美元)奖金。

什么是Collatz猜想?
  Collatz猜想是未解数学难题之一。Collatz猜想是指重复运用以下序列,最终会得到 1:从一个正整数开始,若是偶数则将其除以 2;若是奇数则将其乘 3 再加 1。这一猜想以 1937年提出这一想法的 Lothar Collatz名字命名。
  它首先流传于美国,不久便传到欧洲,后来一位名叫角谷静夫的日本人又把它带到亚洲,因而人们就顺势把它叫作“角谷猜想”,也称为“冰雹猜想”,“3n 1猜想”等等。

这个数学猜想的通俗说法是这样的:
  任意给定一自然数 N,如果它是偶数,就将它除以 2,如果它是奇数,则对它乘 3 再加 1,继续将它生成的自然数施行这种演算,经有限步骤后,最后结果必然是最小的自然数 1。对这个猜想,我们不妨挑一个数来试试:
若 N=10,则 18÷2=9,9×3 1=28,28÷2=14,14÷2=7,7×3 1=22,22÷2=11,11×3 1=34,34÷2=17,17×3 1=52,52÷2=26,26÷2=13,13×3 1=40,40÷2=20,20÷2=10,10÷2=5,5×3 1=16,16÷2=8,8÷2=4,4÷2=2,2÷2=1。
经过 20 步演算,最后变成了 1。

与角谷猜想相关的问题有哪些呢?

问题一:读入自然数 n,输出 n 最终到 1 的变化过程以及变化的步骤数。

最小的自然数是1对吗,证明1是最小的自然数(1)

#include<iostream> using namespace std; int n,step; int main() { cin>>n; cout<<n; while (n!=1) { step ; if (n%2==1) n=n*3 1; else n=n/2; cout<<"->"<<n; } cout<<endl<<"STEP="<<step; return 0; }


问题二:求解 1-100 以内的自然数中,哪个数的步骤数最大,哪个数的变化峰值最大?(如:上例中,18 的步骤数是 20,18 的变化峰值是 52)

#include<iostream> using namespace std; int n,fz,fzi,s,step,stepi; int main() { for (int i=2;i<=100;i ) { n=i; s=0; while (n!=1) { s ; if (n%2==1) { n=n*3 1; if (n>fz) fz=n,fzi=i; } else n=n/2; } if (s>step) step=s,stepi=i; } cout<<stepi<<' '<<step<<endl<<fzi<<' '<<fz; return 0; }

  通过运行,我们发现 97 的步骤数最大,有 118步;27 的峰值最大,达到 9232。虽然 27 是一个貌不惊人的自然数,但是如果按照上述方法进行运算,它的上浮下沉异常剧烈:首先,27 要经过 77步的变换到达顶峰值 9232,然后又经过 34 步到达谷底值 1。全部的变换过程需要 111步,其峰值 9232,是原有数字 27 的 341 倍多。

  分析上面的代码,我们不难发现其中有一些计算是重复的,比如在计算 5 的步长时,要推到 16,计算 16 的步长;然后又要推到 8,计算 8 的步长;算完 5 继续算后面的数字 6 7 8 ... 时,还要再算 8 和 16 的步长......怎么解决这个重复计算的问题呢,我们可以采用(部分)记忆化搜索的方法,下面给出参考代码。

#include<iostream> using namespace std; int step,stepi; int s[2000001]; int dfs(long long a) { if (a==1) return 0; //边界 if (a<=2000000 && s[a]) return s[a]; //若a小于200万,且已搜索过,则直接返回 if (a%2) //若在数组存储范围内(小于200万),先存储再返回 if (a<=2000000) {s[a]=dfs(3*a 1) 1;return s[a];} else return dfs(3*a 1) 1; else if (a<=2000000) {s[a]=dfs(a/2) 1;return s[a];} else return dfs(a/2) 1; } int main() { for (int i=1;i<=2000000;i ) dfs(i); //部分记忆化搜索 for (int i=1;i<=2000000;i ) //找出200万以内的最大步长 if (s[i]>step) step=s[i],stepi=i; cout<<stepi<<' '<<step; return 0; }

  利用记忆化搜索,你能求出相应的最大峰值吗,还有更好的方法吗?欢迎评论区分享你的思路。

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.