精益求精---让你的程序效率更高一些
问题背景：
英国大数学家哈代(G.H.Hardy,1877-1947)曾经发现过一种有趣的现象:
153=1^3 + 5^3 + 3^3
371=3^3 + 7^3 + 1^3
370=3^3 + 7^3 + 0^3
407=4^3 + 0^3 + 7^3
他们都是三位数且等于各位数字的三次幂之和,这种巧合不能不令人感到惊讶.更为称奇的是,一位读者看过哈代的有趣发现后,竟然构造出其值等于各位数字四(五,六)次幂之和的四(五,六)位数:
1634=1^4 + 6^4 + 3^4 + 4^4
54748=5^5 + 4^5 + 7^5 + 4^5 + 8^5
548834=5^6 + 4^6 + 8^6 + 8^6 + 3^6 + 4^6
注:3位3次幂回归数又称位“水仙花数”
像这种其值等于各位数字的 n 次幂之和的 n 位数,称为 n 位 n 次幂回归数.本文只讨论这种回归数,故简称为回归数,人们自然要问:对于什么样的自然数 n 有回归数?这样的 n 是有限个还是无穷多个?对于已经给定的 n ,如果有回归数,那么有多少个回归数? 1986年美国的一位数学教师安东尼.迪拉那(Anthony Diluna)巧妙地证明了使 n 位数成为回归数的 n 只有有限个.
设 An 是这样的回归数,即:
An=a1a2a3...an=a1^n+a2^n+...+an^n (其中 0<=a1,a2,...an<=9)
从而 10^n-1<=An<=n9^n 即 n 必须满足 n9^n>10^n-1 也就是 (10/9)^n<10n (1)
随着自然数 n 的不断增大,(10/9)^n 值的增加越来越快,很快就会使得(1) 式不成立,因此,满足(1)的 n 不能无限增大,即 n 只能取有限多个.进一步的计算表明:
(10/9)^60=556.4798...<10*60=600 (10/9)^61=618.3109...>10*61=610
对于 n>=61,便有 (10/9)^n>10n
由此可知,使(1)式成立的自然数 n<=60.故这种回归数最多是60位数.迪拉那说,他的学生们早在1975年借助于哥伦比亚大学的计算机得到下列回归数:
一位回归数:1,2,3,4,5,6,7,8,9
二位回归数:不存在
三位回归数:153,370,371,407
四位回归数:1634,8208,9474
五位回归数:54748,92727,93084
六位回归数:548834
七位回归数:1741725,4210818,9800817
八位回归数:24678050,24678051
但是此后对于哪一个自然数 n (<=60)还有回归数?对于已经给定的 n ,能有多少个回归数?最大的回归数是多少?
///////////////////////////////////////////////////////////////////////////////////////////
我刚才在http://blog.programfan.com/article.asp?id=22756看到风迪海洋的帖子，感觉挺有意思，自己也写了一个程序，但是速度不尽如人意，于是想提高效率，终于想到一个提高速度的方法，速度提高了好几倍。正开心，突然灵光一闪，又有了一个更好的改进方法，编译运行，速度又提高了好几倍，高兴啊！把三个代码都贴上来，大家看看吧！
初级版：
思路很简单，就是遍历n位数，如n=5，则遍历[10000，100000）， 把每个数的各位数字分解，存储到数组中，然后累计每位数字的n次幂之和，与该数进行比较，判断该数是否为回归数。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int a[60];//用来存储各位数字
const int N = 6;//回归数的最大位数，由用户设置
void GetReturnNumber(int n);//计算n位回归数
void Divid(long n);//分解n的各位数字存储到a[]
int IsReturnNumber(int n, long m);//判断m是否为n位回归数
long Power(int x, int n);//求x的n次幂
int main()
{
time_t start, finish;
long min, max, sum;
double duration;
int i;
start = time(0);
for (i=1; i<N; i++)//计算n位回归数
{
printf("\n%d位回归数: ", i);
GetReturnNumber(i);//计算n位回归数
}
finish = time(0);
duration = difftime(finish, start);
printf("\nProgram using time() = %f seconds.", duration);
getchar();
return 0;
}
void GetReturnNumber(int n)//计算n位回归数
{
long min, max, m;
max = Power(10, n);
min = max/10;
for (m=min; m<max; m++)
{
Divid(m);
//如果是回归数，输出它
if (IsReturnNumber(n, m))
printf("%d, ", m);
}
}
void Divid(long n)//分解n的各位数字存储到a[]
{
int i = 0;
while (n > 0)
{
a[i++] = n % 10;
n /= 10;
}
}
int IsReturnNumber(int n, long m)//判断m是否为n位回归数
{
int i;
long sum = 0;
for (i=0; i<n; i++)
sum += Power(a[i], n);
return (sum == m);
}
long Power(int x, int n)//求x的n次幂
{
if (n == 1)
return x;
long p = Power(x, n/2);
if (n%2 == 1)
return p * p * x;
else
return p * p;
}
/////////////////////////////////////////////////////
改进版（一）： 主函数不变
初级版中对每个数都进行了分解数字的运算，而实际上该数递增的时候，分解的数字中只有个位数发生了变化（当数字等于9时除外），所以我们没有必要分解出每一位数字，而只要让数组中存储的数字随被判断的数发生相应变化就行了。
void GetReturnNumber(int n)//计算n位回归数
{
int i;
long min, max, m;
max = Power(10, n);
min = max/10;//n位数的最小值
//初始化数组a，初始值与min-1的各位数字相同，但顺序相反
a[n-1] = 1;
for (i=0; i<n-1; i++)
a[i] = 0;
for (m=min; m<max; m++)//遍历n位数
{
//如果是回归数，输出它
if (IsReturnNumber(n, m))
printf("%d, ", m);
//不在分解m，而只虚递增a[]所表示的数，注意a[0]存储的是个位数字
for (i=0; i<n; i++)
{
a[i]++;
if (a[i] < 10)//如果没有进位，则后面的数字不变
break;
a[i] = 0;//进位，该位归0
}
}
}
int IsReturnNumber(int n, long m)//判断m是否为n位回归数
{
int i;
long sum = 0;
for (i=0; i<n; i++)
sum += Power(a[i], n);
return (sum == m);
}
long Power(int x, int n)//求x的n次幂
{
if (n == 1)
return x;
long p = Power(x, n/2);
if (n%2 == 1)
return p * p * x;
else
return p * p;
}
//////////////////////////////////////////////////////////////
改进版（二）： 主函数不变
改进版（一）中没有进行分解数字的重复运算，大大提高了效率，但是每次在判断m是否为回归数时，对m的每位数字都进行了计算，而实际上既然该位数字未变，那它的n次幂也不会变，我们没必要重复计算，而只要计算变化了的数字的幂就可以了。 这样改进后速度剧增，当N=9时，只要121秒钟。
void GetReturnNumber(int n)//计算n位回归数
{
int i;
long min, max, m, sum;
max = Power(10, n);
min = max / 10;//n位数的最小值
//初始化数组a，初始值与min-1的各位数字相同，但顺序相反
a[n-1] = 1;
for (i=0; i<n-1; i++)
a[i] = 0;
sum = 1;
for (m=min; m<max; m++)//遍历n位数
{
//如果是回归数，输出它
if (sum == m)
printf("%d, ", m);
//递增a[]所表示的数，同时改变它们的n次幂之和，注意a[0]存储的是个位数字
for (i=0; i<n; i++)
{
sum -= Power(a[i], n);//减去原来的数字的幂
a[i]++;
if (a[i] < 10)
{
sum += Power(a[i], n);//加上更新的数字的幂
break;
}
a[i] = 0;
}
}
}
long Power(int x, int n)
{
if (n == 1)
return x;
long p = Power(x, n/2);
if (n%2 == 1)
return p * p * x;
else
return p * p;
}
?
评论