#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;
}
分享到:
相关推荐
穷举法 高精度 动态规划 回溯 贪心 排列组合 排序
排列组合是常见的数学问题,本文就以完整实例形式讲述了C#实现排列组合算法的方法。分享给大家供大家参考之用。具体方法如下: 首先,数学中排列组合,可表示为:排列P(N,R) 其实排列实现了,组合也就实现了,组合...
0-1整数规划有很广泛的应用背景,比如指派问题,背包问题等等,实际上TSP问题也是一个0-1问题,当然这些问题都是NP问题,对于规模较大的问题用穷举法是没有办法在可接受的时间内求得最优解的,本程序只不过是一个...
穷举算法经典案例及其C语言实现.穷举算法经典案例及其C语言实现.
穷举密码算法 在许多情况下我们需要穷举组合的算法,比如密码词典。 ... 另外本例子中的写文件语句效率比较低,为了降低算法复杂度没有优化。 如果要提高写文件的效率,可以使用缓冲区,分批写入。
MATLAB优化算法案例分析与应用(进阶篇)1-10章程序下载
数据结构与算法_枚举(穷举)算法(视频),Dev-C++语言环境!信息学奥赛基础算法!
输入一个小于20的正整数n,要求按从小到大的顺序输出所有的n位二进制数,每个数占一行。
算法分析与设计课件:穷举法.ppt
用穷举算法解一元一次方程
·C++算法与数据结构--穷举n位二进制数码 ·输入n,输出n位二进制数码 ·算法与数据结构课上必考内容
穷举算法讲义穷举算法讲义.doc
30常用算法的应用-整数各数位.mp4 31常用算法的应用-矩阵转置.mp4 32常用算法的应用-辗转相除求.mp4 33常用算法的应用-求最值.mp4 34常用算法的应用-判断素数.mp4 35常用算法的应用-数组元素的.mp4 36C语言习题.mp4
我几乎找遍了网络上差不多所有的穷举算法,都不是很满意。然后自己研究了差不多一下行的时候,把现在的代码进行了注释和部分优化。 这个穷举算法,可以自定义起始位,终止位,还可以自定义密码字符。差不多是我觉得...
穷举算法 回溯算法 介绍 几篇文章,还是值得一看的
主要函数GetPassword(int digits):string 参数为所生成随机组合位数 比如说要生成10为随机数字字母组合,就string randomCode = GetPassword(10); 生成的结果有数字和大写、小写字母组合
c语言-穷举算法(百钱买白鸡)、摸球问题.docx
通过穷举算法求解0-1整数规划的matlab源码
穷举密码算法 2003-3-25 12:50:56 CNPROGRAM breath 阅读次数: 3362 穷举密码算法breath //*******************************************************************//在许多情况下我们需要穷举组合的算法,比如密码...
易语言穷举算法源码