一道和角谷静夫猜想相关的问题
最近在看EulerProject上的问题:有一道问题是这样的:
角谷静夫猜想是说：对于一个任意的自然数，总可以通过以下步骤变为1：
f(n) = \frac{n}{2}.如果 n 是偶数
f(n) = 3 \times n + 1. 如果n 是奇数
对于不同的数，需要的步骤肯定不同，问题是1000000以内的数，哪个数需要的步骤最多？
我的想法比较粗糙：就是对每个数去统计.然后选取一个最长的。
对于每个数，到底需要多少次才可以到达1应该是未知的。假设统计这么多所需要的平均次数是T,那么就做了 1000000*T次循环，然后还有(2*T+1)*1000000次判断，我的代码如下;int main()
{
//open file to output
ofstream outfile("G:/math/ans.txt");
long ans = 0;
long index;
long a,b;
for(long i = 2; i < 1000000; )
{
a = i;
index = 0;
while(true)
{
if(a == 1)
{
break;
}
if(a % 2 == 0)
{
a = a/2;
}
else
{
a = a*3 + 1;
}
index++;
}
if(index > ans)
{
ans = index;
b = i;
}
i+=2;
}
if(ans < 500000)
{
ans = ans * 2;
b++;
}
outfile << "这个数是:" << ans << endl;
outfile << "需要的次数:" << b << endl;
}不过貌似我的电脑根本跑不出来这个结果。是不是我的计算方法太愚蠢了。（我考虑偶数可以不用判断了。如果判断出来最大的数是<500000的奇数，则考虑这个数*2的那个偶数，就是需要步骤最多的。）我跑了很久结果也出不来 我发现楼主的代码有一个bug。楼主显然没有考虑到整数溢出问题，在执行下面的语句时，可能会发生整数溢出而导致结果错误。例如，当n=159487，在计算到第60步时，a*3+1的值就会超过32bit,这时，如果变量类型为unsigned long, 在32bit编译器下编译，就会出现错误。我注意到楼主的代码中，数据类型为long,那么溢出的几率会更高
a = a*3 + 1;
我没有仔细调试楼主的程序。我自己写了一个程序，在PM1.7上运行，计算
100万/1000万/1亿之内的数需要的步时， 需要375/6250/93265毫秒。
几点说明：
1.在计算过程中，我的程序使用unsigned __int64(VC编译器) 型变量，避免溢出。
2.我的程序作了一点儿优化，事先计算出1-65536之间的数所需的步骤，在计算大于65536的数所需的步骤时，一旦发现计算过程中，a的值<=65536,那么剩余的步骤可直接查表。 本楼给出所有源代码#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
typedef unsigned __int64 UINT64;
typedef unsigned long DWORD;
typedef unsigned short WORD;
WORD g_steps_tab;
int steps(DWORD n)
{
UINT64 x=n;
int r=0;
while ( x >1)
{
if ( x & 1)//x 是奇数
{
if ( x>=6148914691236517205I64)
{
printf("ERROR,n=%u,integer overflow, can not continue\n",n);
return 0;
}
x=x*2+x+1;
r++;
}
else
{
x=x /2;
r++;
}
}
return r;
}
//在计算过程中,当n的值小于65536，直接查表
//tab 表示 i+1 转化为1需要的步数
int steps_pro(DWORD n,WORD tab[])
{
UINT64 x=n;
int r=0;
while ( x >1)
{
if ( x <=65536)
{
return r+tab;
}
else if ( x & 1)//x 是奇数
{
if ( x>=6148914691236517205I64)
{
printf("ERROR,n=%u,integer overflow, can not continue\n",n);
return 0;
}
x=x*2+x+1;
r++;
}
else
{
x=x /2;
r++;
}
}
return r;
}
void test2(DWORD to)
{
DWORD i,max_n;
int r,max_r;
max_r=0;
DWORD t;
t=GetTickCount();
for (i=1;i<=65536;i++)
{
r=steps(i);
g_steps_tab=r;
}
max_r=0;
for (i=1;i<=to;i++)
{
r=steps_pro(i,g_steps_tab);
if (r>max_r)
{
max_r=r;
max_n=i;
}
}
t=GetTickCount()-t;
printf("Calc up to %u, take %d ms\n",to,t);
printf("steps[%d]=%d\n",max_n,max_r);
}
int main(int argc, char argv[])
{
test2(1000000);
test2(10000000);
test2(100000000);
return 0;
} 非常感谢~~，看了收获很大。
有个小问题：
把 x = x*3 + 1;
写成：
x=x*2+x+1;
又没有什么特别的原因？
我运行时间好像差不太多。
我是AMD 2800+ ， 512MB内存
计算1000000以内花费406MS-500MS。
判断奇数的方法+查表比我的节约非常多时间。 是基于优化的考虑。
位运算一定比除法快。因此，
1. 判断是否是奇数写成"(n & 1)==1" 比 " n % 2 ==1" 快
2.“ x=x*2+x+1;” 对通常的编译器，编译成的指令为x=(x<<1)+x+1, 不使用乘法指令。而"x=x*3+1;"对先进的编译器(如intel编译器)会编译成x=(x<<1)+x+1，但对于老的编译器，可能依然使用乘法指令来实现。乘法指令要比移位指令慢得多。 原来这样，好精彩:b:，非常感谢
页:
[1]