N位水仙花数的高效率算法---数位角度,分析数字0-9的排列组合情况,穷举所有不定方程解,结合水仙花数的定义判断

#include <stdio.h>
#include <time.h>
#define N 39

int k[10]={0};   //k[10]用来得到0-9数字出现的个数
int po[10][N]={0},count_mul_power[10][N]={0}; //po数组用来计算出0-9的N次方。count_mul_power用来计算数字出现次数*它的N次方
int count=0;   //计算得到几个水仙花数了，得到2个以后就结束程序

void init_power()   //这个函数用来获得0-9的N次方，存在po数组里
{
 int i,j,k;
 for(i=0;i<10;i++)
     po[i][N-1]=i; //矩阵每行全部初始化为(0,1,2,3,4,5,6,7,8,9)

    for(k=2;k<10;k++)
 {
        for(i=1;i<N;i++)
  {
   
      for(j=N-1;j>=0;j--)
   {
       po[k][j]*=k; // 计算k=0-9的N次方 po[i][N]=i^N
   }
   
      for(j=N-1;j>0;j--)
   {
             po[k][j-1]+=po[k][j]/10;        //??
             po[k][j]%=10;                        //??
   }
   
  } 
 }
}


void narcissus_check(int i0,int i1,int i2,int i3,int i4,int i5,int i6,int i7,int i8,int i9) //检测数字是不是水仙花数
{
 int i,j;
 int sum_power[N]={0};

    for(j=0;j<N;j++)            //把数字出现次数*它的N次方: 
 {
     count_mul_power[1][j]=po[1][j]*i1; // k[1]*1^N
     count_mul_power[2][j]=po[2][j]*i2; // k[2]*2^N
  count_mul_power[3][j]=po[3][j]*i3; // k[3]*3^N
  count_mul_power[4][j]=po[4][j]*i4;
  count_mul_power[5][j]=po[5][j]*i5;
  count_mul_power[6][j]=po[6][j]*i6;
  count_mul_power[7][j]=po[7][j]*i7;
  count_mul_power[8][j]=po[8][j]*i8;
  count_mul_power[9][j]=po[9][j]*i9;
 }

    for(i=0;i<10;i++)     //进位
  for(j=N-1;j>0;j--)
  {
         count_mul_power[i][j-1]+=count_mul_power[i][j]/10;    /// ????
         count_mul_power[i][j]%=10;                                           /// ????
  } 

 for(i=0;i<10;i++)       //得到一个数每位的N次方的和，就是把count_mul_power叠加起来
  for(j=N-1;j>=0;j--)
      sum_power[j]+=count_mul_power[i][j];
 
 for(i=N-1;i>0;i--)    //进位
 {
     sum_power[i-1]+=sum_power[i]/10;
        sum_power[i]%=10;
 }
 
    int j1=0,j2=0,j3=0,j4=0,j5=0,j6=0,j7=0,j8=0,j9=0,j0=0;  
 
 for(i=N-1;i>=0;i--)         //用来计数   统计 "和" (即sum(k[i]*i^N),i=0-9 )里面每个数字出现的次数
 {
  switch(sum_power[i])
  {
      case 0:j0++;break;
   case 1:j1++;break;
   case 2:j2++;break;
   case 3:j3++;break;
   case 4:j4++;break;
   case 5:j5++;break;
   case 6:j6++;break;
   case 7:j7++;break;
   case 8:j8++;break;
   case 9:j9++;break;
  }
 }
    
/*如果一个数字，和里0-9出现的次数与这个数字里0-9出现的次数相同，那么和就应该是水仙花数（第一位数字不能为0）*/
 if((i0==j0)&&(i1==j1)&&(i2==j2)&&(i3==j3)&&(i4==j4)&&(i5==j5)&&(i6==j6)&&(i7==j7)&&(i8==j8)&&(i9==j9)&&(sum_power[0]!=0))
 {
  printf("\n");
  count++;
  for(i=0;i<N;i++)
   printf("%d",sum_power[i]);
  printf("\n");
 }
}

int main()
{
 int t,t1,t2;
 init_power();
 t1=time(NULL);
    int i0,i1,i2,i3,i4,i5,i6,i7,i8,i9;
 for(i9=0;i9<10;i9++)    
 {
  for(i0=1;i0<=N;i0++)
  {
   if(count==2)     //出现2个水仙花数以后break
    break;
   if(i9+i0==N)   //几个数字的出现次数和为N以后就break,因为后面的数字出现次数和一定大于N，就超过了N位
   { narcissus_check(i0,0,0,0,0,0,0,0,0,i9);break;} 
   for(i2=0;i2<=N;i2++)
   {
    if(count==2)
        break;
    if(i9+i0+i2==N)
    { narcissus_check(i0,0,i2,0,0,0,0,0,0,i9);break;}
       for(i3=0;i3<=N;i3++)
    {
     if(count==2)
            break;
     if(i9+i0+i2+i3==N)
     { narcissus_check(i0,0,i2,i3,0,0,0,0,0,i9);break;}
        for(i4=0;i4<=N;i4++)
     {
      if(count==2)
                break;
      if(i9+i0+i2+i3+i4==N)
      { narcissus_check(i0,0,i2,i3,i4,0,0,0,0,i9);break;}
         for(i5=0;i5<=N;i5++)
      {
       if(count==2)
                    break;
        if(i9+i0+i2+i3+i4+i5==N)
       { narcissus_check(i0,0,i2,i3,i4,i5,0,0,0,i9);break;}
          for(i6=0;i6<=N;i6++)
       {
        if(count==2)
                        break;
        if(i9+i0+i2+i3+i4+i5+i6==N)
        { narcissus_check(i0,0,i2,i3,i4,i5,i6,0,0,i9);break;}
           for(i7=0;i7<=N;i7++)
        {
         if(count==2)
                            break;
         if(i9+i0+i2+i3+i4+i5+i6+i7==N)
         { narcissus_check(i0,0,i2,i3,i4,i5,i6,i7,0,i9);break;}
            for(i8=0;i8<=N;i8++)
         {
          if(count==2)
                                break;
          if(i9+i0+i2+i3+i4+i5+i6+i7+i8==N)
          { narcissus_check(i0,0,i2,i3,i4,i5,i6,i7,i8,i9);break;}
          for(i1=0;i1<=N;i1++)
          {
           if(count==2)
                                      break;
           if(i9+i0+i2+i3+i4+i5+i6+i7+i8+i1==N)
           { narcissus_check(i0,i1,i2,i3,i4,i5,i6,i7,i8,i9);break;}
          }
         }
        }
       }
      }
     }
    }
   }
  }
 }
    t2=time(NULL);
    t=t2-t1;
    printf("\n%d s\n",t);

return 0;

}