前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【欧拉计划第 14 题】 最长的考拉兹序列 Longest Collatz sequence

【欧拉计划第 14 题】 最长的考拉兹序列 Longest Collatz sequence

作者头像
攻城狮杰森
发布2022-06-03 13:38:04
1K0
发布2022-06-03 13:38:04
举报
文章被收录于专栏:技术集锦技术集锦

Problem 14 Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

\large n\rightarrow \frac{n}{2}\ \left ( n\ is\ even \right ) ,n\rightarrow3n+1\ \left ( \ n\ is\ odd \right )

Using the rule above and starting with 13, we generate the following sequence:

\large 13\rightarrow40\rightarrow20\rightarrow10\rightarrow5\rightarrow16\rightarrow8\rightarrow4\rightarrow2\rightarrow1

It can be seen that this sequence (starting at 13and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain? NOTE: Once the chain starts the terms are allowed to go above one million.

问题 14 最长的考拉兹序列

为所有正整数集定义以下迭代序列:

\large n\rightarrow \frac{n}{2}\ \left ( n\,是偶数 \right ) ,n\rightarrow3n+1\ \left ( n\,是奇数 \right )

使用上面的规则并从 13开始,生成以下序列:

\large 13\rightarrow40\rightarrow20\rightarrow10\rightarrow5\rightarrow16\rightarrow8\rightarrow4\rightarrow2\rightarrow1

可以看出这个序列从 13 开始并到 1 结束总共包含 10个数。 考拉兹猜想指出使用以上迭代规则,所有正整数都会最终回到一,虽然这个猜想仍未得到证明。 求在一百万以下,哪个起始数可以产生最长的考拉兹序列? 注意:序列中包含的数的个数可以超过一百万。

解题报告

考拉兹猜想

考拉兹猜想(Collatz conjecture),又称为奇偶归一猜想、3n+1 猜想、冰雹猜想、角谷猜想、哈塞猜想、乌拉姆猜想或叙拉古猜想,是指对于每一个正整数,如果它是奇数,则对它乘 3 再加 1,如果它是偶数,则对它除以 2,如此循环,最终都能够得到 1

\large f\left ( n \right )=\left\{\begin{matrix} \frac{n}{2} \quad\quad\quad if \, n\equiv 0\\3n+1 \quad if \, n\equiv 1 \end{matrix}\right.\left .\quad( mod \,\, 2 \right )

思路分析

其实当你看到题目的时候,不知到你有没有和我想到一块儿去,那必然又是咱滴老朋友暴力算法

显然,我们只要求算出一到一百万之间所有数字的考拉兹序列长度,然后在所有求出的序列长度值中找出最大值就能解决本题

但是可以做一些优化,比如大家都知道当 n 是奇数时,3n+1 一定是偶数。那我们根本没必要让程序重复执行冗余步骤

换言之,当 n 是奇数的时候,在其后追加一步,继续计算 (3n+1)/2。便可省去很多中间计算步骤,程序执行效率自然得到提高

还有一点是参考其他大神写的题解意识到的,就是程序重复计算的问题。较大的数据量在计算过程中可能会产生重复数据,我们是不是可以将所有计算步骤得到的结果做下缓存。这样在下一步遇到重复值时可以直接调用,避免重复计算,提高程序执行效率

或者也可以使用递归法实现本题

代码实现

代码语言:javascript
复制
/*
 * @Author: coder-jason
 * @Date: 2022-05-1 09:00:42
 * @LastEditTime: 2022-05-01 09:13:49
 */
#include <bits/stdc++.h>
using namespace std; 

int cal(long long n) 
{
    if (n == 1)
        return 1;
    if (n % 2)
        return 1 + cal(3 * n + 1);
    else
        1 + cal(n / 2);
}

int main()
{
    int n = 0, ans = 0;
    for (int i = 1; i < 1000000; i++)
    {
        int tmp = cal(i);
        if (tmp > ans)
        {
            n = i;
            ans = tmp;
        }
    }
    cout << n << endl;
    return 0;
}
代码语言:javascript
复制
'''
Author: sorrowise
Date: 2022-05-1 08:42:30
LastEditTime: 2022-05-01 09:13:19
'''
 
N=10**6
d = {}
for x in range(2,N):
    i,n = x,0
    while x != 1:
        if x < i:
            n = n + d[x]
            break
        elif x % 2 == 0:
            x = x // 2
            n += 1
        else:
            x = (3*x+1) // 2
            n += 2
    d[i] = n
print(max(d,key=d.get))

答案:837799

参考资料:

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-05-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Problem 14 Longest Collatz sequence
  • 问题 14 最长的考拉兹序列
  • 解题报告
    • 考拉兹猜想
      • 思路分析
      • 代码实现
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档