让你的程序效率更高一些

问题背景：
英国大数学家哈代(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;
}

?

评论