Project Euler——Problem 14

daybreakcx posted @ 2009年7月18日 23:22 in Prject Euler , 996 阅读

原题与答案：

Problem 14

05 April 2002

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

n →n/2 (n is even)
n →3n + 1 (n is odd)

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

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and 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.

Answer:837799

分析与解答：

这个题目整体上出的很不错，题目意思很明朗，就是一个迭代序列，如果数列的某个项n是奇数，那么下一项就是3×n+1，否则就是n/2，根据这样构造的数列最终会得到项1（未证明），假设1为数列的尾项，求在1000000内以哪个数字为头部的序列最长。我采取的方案是半记忆的搜索，假设a[i]表示以i开头的序列的长度，初始时候肯定是a[1]=1，那么就有了公式 $a[i]=\begin{cases}a[3*i+1] & i \% 2==1 \\ a[i/2] & i \% 2==0 \end{cases}$ 。虽然项目的起始是1000000以内的，但是其链的成员肯定会超过1000000（比如第一项是999999），于是我们不能完全记忆其状态，我采用的方案是记忆1000000以内的，其余的1000000以外的都每次重新计算过，这样对于1000000以内的都可以直接得到结果，只算一次，对于1000000以外的都当场计算，省时间的同时也保证了计算不溢出。同时要注意的一点是，序列的项目用32位整数是无法完全存储的，需要64位存储，否则也会发生数组的下溢出，对于64位整数尽量不要用位操作，因为其存储结构有时候不是你所想象的，我就曾经因为这个而郁闷了一段时间，其余的都比较容易实现了，实现源代码如下所示：

#include<stdio.h>
#include<string.h>
int a[1000001],i,ans;
int calc(long long s)
{
if (s<=1000000)
return a[s]==-1?(a[s]=(s%2==1)?calc(s*3+1)+1:calc(s/2)+1):a[s];
else
return (s%2==1)?calc(s*3+1)+1:calc(s/2)+1;
}
int main()
{
memset(a,-1,sizeof(a));
a[1]=ans=1;
for (i=2;i<=1000000;i++)
{
if (a[i]==-1) calc(i);
if (a[i]>a[ans]) ans=i;
}
printf("%d\n",ans);
return 0;
}