最新消息:网站改版咯

C语言21位水仙花数算法

C语言 Yovae 1733浏览

这里分享最近用C语言写的21位水仙花数算法,根据21位中0-9分别可能出现的次数出发,穷举搜索.

题目如下:

一个N位的十进制正整数,如果它的每个位上的数字的N次方的和等于这个数本身,则称其为花朵数。
例如:
当N=3时,153就满足条件,因为 1^3 + 5^3 + 3^3 = 153,这样的数字也被称为水仙花数(其中,“^”表示乘方,5^3表示5的3次方,也就是立方)。
当N=4时,1634满足条件,因为 1^4 + 6^4 + 3^4 + 4^4 = 1634。
当N=5时,92727满足条件。
实际上,对N的每个取值,可能有多个数字满足条件。

程序的任务是:求N=21时,所有满足条件的花朵数。注意:这个整数有21位,它的各个位数字的21次方之和正好等于这个数本身。
如果满足条件的数字不只有一个,请从小到大输出所有符合条件的数字,每个数字占一行。因为这个数字很大,请注意解法时间上的可行性。要求程序在3分钟内运行完毕。

优化后30秒左右

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define N 24
int a[10][22][N]={0},d[10]={0},s[N]={0};

void getN(int n,int m,int num[])//获得n^m 存储在num[]内 num[0]存储长度
{
	int i,j,r,c;
	unsigned int k;
   
	c=2;
	num[1]=1;

	for(i=0;i<m;i++)
	{ 
		r=0;
		for(j=1;j<c;j++)
		{
			k=num[j]*n+r;
			num[j]=k%10;
			r=k/10;
			
		}
		while(r>0)
		{
			num1=r%10;
			r/=10;
		}

	}
	num[0]=c-1;

}

void add(int t[],int left[],int right[])//left[]加上right[]结果保存在s[]中
{
	unsigned int i,r,temp;
	
	left[0]>right[0]?t[0]=left[0]+1:t[0]=right[0]+1;
    r=0;
	for(i=1;i<=t[0];i++)
	{
		temp=left[i]+right[i]+r;
		t[i]=temp%10;
		r=temp/10;
	}
	while(t[t[0]]==0&&t[0]!=1)
	{
		t[0]--;
	}
}

void mul(int mul[],int b[],int n)//n->[0,21] 大数乘以一个整数
{
	unsigned int i,r,temp;
	r=0;
	mul[0]=23;
	for(i=1;i<=mul[0];i++)
	{
		temp=b[i]*n+r;
		mul[i]=temp%10;
		r=temp/10;
	}
	while(mul[mul[0]]==0&&mul[0]!=1)
	{
      mul[0]--;
	}
}

void printN(int x[])      //打印出大数
{
	for(int i=x[0];i>=1;i--)
	{
		printf("%d",x[i]);
	}
}


int check(int d[])//检测是否符合水仙花数条件 0不符合 1符合 2过大 3过小
{
	int i,temp[10]={0},flag=1;
	memset(s,0,sizeof(s));
	for(i=0;i<10;i++)     //统计0-9分别出现的次数乘以各自本身的21次方后相加
	{
		if(d[i]!=0)
		{
		add(s,s,a[i][d[i]]);
		}
	}

	if(s[0]>21)         //结果超出21位
	{
		return 2;
	}
	else if(s[0]==21)  //结果为21位 继续判断是否为水仙花数
	{
		for(i=1;i<=s[0];i++)//如果结果中0-9分别出现的个数与组合中出现个数均一致则为水仙花数 否而不是
		{
		   temp[s[i]]++;
		}

    	for(i=0;i<10;i++)
		{
		  if(temp[i]!=d[i])
		  {
			  flag=0;
			  break;
		  }
		}
	    return flag;
	}
	else            //结果少于21位
	{
		return 3;
	}
}
int preCheckMin(int d[],int y)//预先判断当前最小值是否大于21位
{
	int i;
	memset(s,0,sizeof(s));
	for(i=9;i>=y;i--)     //统计0-9分别出现的次数乘以各自本身的21次方后相加
	{
		if(d[i]!=0)
		{
		add(s,s,a[i][d[i]]);
		}
	}
	if(s[0]>21)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
int preCheckMax(int d[],int y)//预先判断当前最大值是否小于21位
{
	int i,temp[10]={0},point;
    memset(s,0,sizeof(s));
	point=21;
    for(i=9;i>=y;i--)
	{
		temp[i]=d[i];
		point-=d[i];
	}
	temp[y-1]=point;
	for(i=9;i>=y-1;i--)   //统计0-9分别出现的次数乘以各自本身的21次方后相加
	{
		if(temp[i]!=0)
		{
		add(s,s,a[i][d[i]]);
		}
	}
	if(s[0]<21)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

void init(){
    for(int i=0;i<=9;i++)
	{
		for(int j=0;j<=21;j++)
		{
		   mul(a[i][j],a[i][1],j);
		}
	}


}
int main()
{

	int i,k,ks;
    ks=clock();
	for(i=0;i<10;i++)
	{
		getN(i,21,a[i][1]);
      	
	}
	init();
	for(d[9]=9;d[9]>=0;d[9]--)
	{
		
		for(d[8]=21-d[9];d[8]>=0;d[8]--)
		{
			for(d[7]=21-d[8]-d[9];d[7]>=0;d[7]--)
			{
			
				for(d[6]=21-d[7]-d[8]-d[9];d[6]>=0;d[6]--)
				{
					
					for(d[5]=21-d[6]-d[7]-d[8]-d[9];d[5]>=0;d[5]--)
					{
					
						for(d[4]=21-d[5]-d[6]-d[7]-d[8]-d[9];d[4]>=0;d[4]--)
						{
						    if(preCheckMax(d,4)==0){goto end;}
							else if(preCheckMin(d,4)==0){ continue;}
							for(d[3]=21-d[4]-d[5]-d[6]-d[7]-d[8]-d[9];d[3]>=0;d[3]--)
							{
								
								for(d[2]=21-d[3]-d[4]-d[5]-d[6]-d[7]-d[8]-d[9];d[2]>=0;d[2]--)
								{
								
									for(d[1]=21-d[2]-d[3]-d[4]-d[5]-d[6]-d[7]-d[8]-d[9];d[1]>=0;d[1]--)
									{
										
										for(d[0]=21-d[1]-d[2]-d[3]-d[4]-d[5]-d[6]-d[7]-d[8]-d[9];d[0]>=0;d[0]--)
										{
											
											
											k=check(d);
										    if(k==1)
											{
												printN(s);
												printf("\n");
											}
											else	if(k==2)
											{
												continue;
											}
											else if(k==3)
											{
												goto end;
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
end:

	printf("\n---Total time:%d\n",(clock()-ks)/1000);
	system("pause");
	return 0;
}

最初版本用60秒左右.

源码:

/*
 *coding:Yovae    2011-5-11
 *www.yovae.com
 *
 */
#include <stdio.h>
#include <time.h>
#define N 24
int a[10][22][N]={0},t[N]={0},d[10]={0};

void getN(int n,int m,int num[])//获得n^m 存储在num[]内 num[0]存储长度
{
	int i,j,r,c;
	unsigned int k;
   
	c=2;
	num[1]=1;

	for(i=0;i<m;i++)
	{ 
		r=0;
		for(j=1;j<c;j++)
		{
			k=num[j]*n+r;
			num[j]=k%10;
			r=k/10;
			
		}
		while(r>0)
		{
			num1=r%10;
			r/=10;
		}

	}
	num[0]=c-1;

}

void add(int s[],int left[],int right[])//left[]加上right[]结果保存在s[]中
{
	unsigned int i,r,temp;
	
	left[0]>right[0]?s[0]=left[0]+1:s[0]=right[0]+1;
    r=0;
	for(i=1;i<=s[0];i++)
	{
		temp=left[i]+right[i]+r;
		s[i]=temp%10;
		r=temp/10;
	}
	while(s[s[0]]==0&&s[0]!=1)
	{
		s[0]--;
	}
}

void mul(int mul[],int b[],int n)//n->[0,21] 大数乘以一个整数
{
	unsigned int i,r,temp;
	r=0;
	mul[0]=23;
	for(i=1;i<=mul[0];i++)
	{
		temp=b[i]*n+r;
		mul[i]=temp%10;
		r=temp/10;
	}
	while(mul[mul[0]]==0&&mul[0]!=1)
	{
      mul[0]--;
	}
}

void printN(int x[])      //打印出大数
{
	for(int i=x[0];i>=1;i--)
	{
		printf("%d",x[i]);
	}
}


void chushi(int x[])       //初始化函数
{
	
	for(int i=N-1;i>=0;i--)
	{
		x[i]=0;
	}
	
}

int check(int d[],int s[])//检测是否符合水仙花数条件 0不符合 1符合 2过大 3过小
{
	int i,temp[10]={0},flag=1;
    chushi(s);            //初始化加数
	for(i=0;i<10;i++)     //统计0-9分别出现的次数乘以各自本身的21次方后相加
	{
		if(d[i]!=0)
		{
		add(s,s,a[i][d[i]]);
		}
	}

	if(s[0]>21)         //结果超出21位
	{
		return 2;
	}
	else if(s[0]==21)  //结果为21位 继续判断是否为水仙花数
	{
		for(i=1;i<=s[0];i++)//如果结果中0-9分别出现的个数与组合中出现个数均一致则为水仙花数 否而不是
		{
		   temp[s[i]]++;
		}

    	for(i=0;i<10;i++)
		{
		  if(temp[i]!=d[i])
		  {
			  flag=0;
			  break;
		  }
		}
	    return flag;
	}
	else            //结果少于21位
	{
		return 3;
	}
}
int preCheckMin(int d[],int s[],int y)//预先判断当前最小值是否大于21位
{
	int i;
    chushi(s);            //初始化加数
	for(i=9;i>=y;i--)     //统计0-9分别出现的次数乘以各自本身的21次方后相加
	{
		if(d[i]!=0)
		{
		add(s,s,a[i][d[i]]);
		}
	}
	if(s[0]>21)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
int preCheckMax(int d[],int s[],int y)//预先判断当前最大值是否小于21位
{
	int i,temp[10]={0},point;
    chushi(s);            //初始化加数
	point=21;
    for(i=9;i>=y;i--)
	{
		temp[i]=d[i];
		point-=d[i];
	}
	temp[y-1]=point;
	for(i=9;i>=y-1;i--)   //统计0-9分别出现的次数乘以各自本身的21次方后相加
	{
		if(temp[i]!=0)
		{
		add(s,s,a[i][d[i]]);
		}
	}
	if(s[0]<21)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

void init(){      //赋予初始数据
    for(int i=0;i<=9;i++)
	{
		for(int j=0;j<=21;j++)
		{
		   mul(a[i][j],a[i][1],j);
		}
	}


}

int main()
{

	int i,k,ks;
    ks=clock();
	for(i=0;i<10;i++)
	{
		getN(i,21,a[i][1]);
      	
	}
	init();
	for(d[9]=9;d[9]>=0;d[9]--)
	{
		
		for(d[8]=21-d[9];d[8]>=0;d[8]--)
		{
		    
			for(d[7]=21-d[8]-d[9];d[7]>=0;d[7]--)
			{
				
				for(d[6]=21-d[7]-d[8]-d[9];d[6]>=0;d[6]--)
				{
					
					for(d[5]=21-d[6]-d[7]-d[8]-d[9];d[5]>=0;d[5]--)
					{
					
						for(d[4]=21-d[5]-d[6]-d[7]-d[8]-d[9];d[4]>=0;d[4]--)
						{
							
							for(d[3]=21-d[4]-d[5]-d[6]-d[7]-d[8]-d[9];d[3]>=0;d[3]--)
							{
									
								for(d[2]=21-d[3]-d[4]-d[5]-d[6]-d[7]-d[8]-d[9];d[2]>=0;d[2]--)
								{
								    
									for(d[1]=21-d[2]-d[3]-d[4]-d[5]-d[6]-d[7]-d[8]-d[9];d[1]>=0;d[1]--)
									{
			
										for(d[0]=21-d[1]-d[2]-d[3]-d[4]-d[5]-d[6]-d[7]-d[8]-d[9];d[0]>=0;d[0]--)
										{											
											k=check(d,t);
											if(k==1)
											{
												printN(t);
												printf("\n");
											}
											else if(k==2)
											{
												continue;
											}
											else if(k==3)
											{
												goto end;
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
end:

	printf("\n---Total time:%d\n",(clock()-ks)/1000);
	return 0;
}


转载请注明:Yovae Studio » C语言21位水仙花数算法