让你的程序效率更高一些 问题背景：英国大数学家哈代(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;} ?
评论