C语言算法求解任意位的水仙花数: 堆栈,函数,指针,数组的综合运用典型实例 东海陈光剑

#include <stdio.h>
#include <stdlib.h>
#include "string.h"
#include "time.h"

#define bool int
#define false 0
#define true 1

#define T 10

int count0=0;
//统计B[]中 各数字出现的次数 结果放到s[]中
 void count_digit(int *B,int s[T], int* n)
{
    memset(s,0x00,sizeof(int)*T);
    register int len=(*n);
     int *ptr=B;
    while(len--)
    {
        ++s[*ptr++];
    }

}


//对0~9的n次预处理将结果放入sum中
 void init_power(int *B, int *n)
{
     register int i;
     for(i = 1 ; i < T; i++)   //初始化sum
     {
         B[i*(*n)]=i;
     }
     int tmp;
     for( i = 0 ;i < T; i++)   //对0~9的n次预处理
     {
        int j;
        for( j = 0 ; (j < (*n) -1);j ++)
         {
             tmp=i*(*n);
             int t;
             for( t = 0 ; t < (*n); t ++)
                B[tmp+t]*=i;

             int m;
             for( m = 0 ; m < (*n) ; m ++)
             {
                 if(B[tmp+m]>=10)
                 {
                     if(B[tmp+m+1] == -1)
                        B[tmp+m+1] = 0;

                     B[tmp+m+1] += B[tmp+m]/10;//乘法进位
                     B[tmp+m] = B[tmp+m]%10;
                 }

            }

        }

     }

}

 void Print(int *B, int* n)//输出水仙花数
{
     register int i = (*n)-1;
         for(; i >= 0 ; i --)
         {
            printf("%d",B[i]);
         }

         printf("\n");
}

 void add(int *addend,int *summend, int k, int* n )
{                               //加入k的n次方
     register int i;
      int j=k*(*n);
     for( i = 0 ; i < (*n); i ++)
        addend[i] += summend[j+i];

     for( i = 0 ; i < (*n) ; i ++)
     {
         if(addend[i]>=10)
         {
             if(addend[i+1] == -1)
                addend[i+1] = 0;

             addend[i+1] += addend[i]/10;//乘法进位
             addend[i] = addend[i]%10;
         }

     }

}

//从a中减去k的n次方
 void sub(int *a,int *b, int k, int* n )
{
      int j=k*(*n);
     register int i = 0;
     for(i = 0 ; i < (*n); i++)
     {
         if(a[i] < b[j+i])
         {
             a[i+1] -= 1;
             a[i]=a[i]+10-b[j+i];
         }
         else
         {
            a[i] -= b[j+i];
         }
     }
}

 bool cmp(int a[T],int b[T])//比较幂次方得到的"水仙花数"是否和位权上的数字是否一致
{
    register int i=0;
     for(i = 0 ; i < T; i++)
         if(a[i]!=b[i])
            return false;

     return true;
}

void Narcissus(int *n)
{
    int count1=0;
     if((*n) <= 0) return;
     //int *sum=new int[n*T];     //0~9的n次方
     int *sum;
     sum=(int*)calloc((*n)*T,sizeof(int));
     memset(sum,0,sizeof(int)*(*n)*T);

     int stat1[T]={0};          //N次方和中各位数字出现的次数
     int stat2[T]={0};          //栈中数出现的次数
     //int *gross=new int[n+1];   //栈中各数的n次方和 -- 数字已拆分
     int *gross;
     gross=(int*)calloc((*n)+1,sizeof(int));
     memset(gross,0x00,sizeof(int)*((*n)+1));
     //int *stack=new int[n+1];     //栈
     int *stack;
     stack=(int*)calloc((*n)+1,sizeof(int));
     memset(stack,0x00,sizeof(int)*((*n)+1));
     int* top=stack;            //栈顶指针

     int *maxTop=stack+(*n); //

     init_power(sum,n);            //求出0~9的n次方
     bool tab = false;
     register int k =9;         //动态组合的数字  从大到小组合

     while(1)
     {
         if(top < maxTop && gross[(*n)]==0)
         {                    //栈中数字及N次方和均未达到N位
             add(gross,sum,k,n);
             stat2[k]++;      //记录栈中各数字出现次数
             *top++ = k;      //数字入栈 栈顶不会大于后面的数字777-776.即780不会有
         }                    //因无++K,只有--K.已出现过的组合后面不会再现 如731已现,无371/137/713/173

         if(gross[(*n)]>0)       //组合数字的N次方和大于N位
         {
             sub(gross,sum,k,n);
             stat2[k]--;
             k=*--top - 1;    //退栈,组合数字为退出数减一,后面不会有比前面更大的组合数字
         }

         if(top == maxTop)    //栈满 即已有N位数字
         {
            if(gross[(*n)-1]==0) //N次方和小于N位 若n为1,不能输出0,此处退出
                break;        //由于后面无比它更大的组合(见165-172行注释),退出

            count_digit(gross,stat1,n);//求N次方和中各位数出现次数 存于sta1中
            //若出现的数字及其次数完全相同,则为水仙花数
            if(cmp(stat1,stat2))
            {
                count0++;
                count1++;
                Print(gross,n);       //若栈中为7 3 1则输出371; 输出水仙花数
            }

            if(*(top-1) != 0)         //若栈顶数字不为0
             {
                 sub(gross,sum,k,n);  //先从N次方和中减去此数字的N次方
                 --stat2[k];          //此数次数随即减少 此时栈顶指针未动
             }
             else
             {
                 while(*(top-1) == 0) //栈顶为0 循环后指向栈中紧跟的非0数字
                 {
                      --top;
                      --stat2[0];     //退0
                 }

                //if(top-1<stack) break;
                 tab=true;
             }

             k=*--top;               //退栈 k接收退出的数字
             if(tab)
             {
                 sub(gross,sum,k,n); //
                 --stat2[k];
                 tab = false;
             }
             --k;       //后面的组合数字比原数更小 保证不出现 788
         }

         //if(*stack ==1)  break;
     }

     free(sum);
     free(gross);
     free(stack);

     printf("\n%d位水仙花数有%d个\n",*n,count1);
}



int main()
{
     clock_t start0 , end0,start1 , end1;
     int *p;
     int i=0;
     p=&i;
     int N=21;
     while(1)
     {   count0=0;
         printf("\n\n***剑道软件,为您求解任意位的水仙花数***\n\n");
         printf("请输入您要求解的水仙花数的最大位数N:");
         scanf("%d",&N);
         printf("您输入的水仙花数的最大位数N=%d\n\n",N);


         start0=clock();
         for (*p=1;*p<=N;(*p)++)
         {
                start1=clock();

                printf("%d位水仙花数:\n",i);
                Narcissus(p);
                printf("\n");

                end1=clock();
                printf("Running time:%fs\n",(double)(end1-start1)/CLOCKS_PER_SEC);

         }
         end0=clock();
         printf("\n\nTotal running time:%fs\n\n",(double)(end0-start0)/CLOCKS_PER_SEC);
         printf("\n综上所解,%d位以内的水仙花数共有%d个.\n",N,count0);

     }
    return 0;
}



/**
1位水仙花数:
9
8
7
6
5
4
3
2
1

2位水仙花数:

3位水仙花数:
407
371
370
153

4位水仙花数:
9474
8208
1634

5位水仙花数:
93084
92727
54748

6位水仙花数:
548834

7位水仙花数:
9926315
9800817
4210818
1741725

8位水仙花数:
88593477
24678051
24678050

9位水仙花数:
912985153
534494836
472335975
146511208

10位水仙花数:
4679307774

11位水仙花数:
94204591914
82693916578
49388550606
44708635679
42678290603
40028394225
32164049651
32164049650

12位水仙花数:

13位水仙花数:

14位水仙花数:
28116440335967

15位水仙花数:

16位水仙花数:
4338281769391371
4338281769391370

17位水仙花数:
35875699062250035
35641594208964132
21897142587612075

18位水仙花数:

19位水仙花数:
4929273885928088826
4498128791164624869
3289582984443187032
1517841543307505039

20位水仙花数:
63105425988599693916

21位水仙花数:
449177399146038697307
128468643043731391252

Running time:20.398000s
Process returned 0 (0x0)   execution time : 20.416 s
Press any key to continue.

*/