回归数

medie2005 · 发表于 2009-1-12 08:45:10

40位以下的回归数及其扩展:
3 digits search start!
0
1
153
407
370
371
4 digits search start!
0
1
1634
8208
9474
5 digits search start!
0
1
4151
4150
54748
93084
92727
6 digits search start!
0
1
548834
7 digits search start!
0
1
1741725
4210818
9926315
9800817
8 digits search start!
0
1
24678050
24678051
88593477
9 digits search start!
0
1
146511208
912985153
534494836
472335975
10 digits search start!
0
1
4679307774
11 digits search start!
0
1
82693916578
94204591914
40028394225
44708635679
42678290603
49388550606
32164049651
32164049650
12 digits search start!
0
1
13 digits search start!
0
1
564240140138
14 digits search start!
0
1
28116440335967
15 digits search start!
0
1
16 digits search start!
0
1
4338281769391371
4338281769391370
17 digits search start!
0
1
233411150132317
35875699062250035
35641594208964132
21897142587612075
18 digits search start!
0
1
19 digits search start!
0
1
3289582984443187032
4498128791164624869
4929273885928088826
1517841543307505039
20 digits search start!
0
1
63105425988599693916
21 digits search start!
0
1
449177399146038697307
128468643043731391252
22 digits search start!
0
1
23 digits search start!
0
1
21887696841122916288858
35452590104031691935943
28361281321319229463398
27907865009977052567814
27879694893054074471405
24 digits search start!
0
1
188451485447897896036875
174088005938065293023722
239313664430041569350093
25 digits search start!
0
1
114735624485461118832514
1550475334214501539088894
1553242162893771850669378
4422095118095899619457938
3706907995955475988644380
3706907995955475988644381
832662335985815242605071
832662335985815242605070
26 digits search start!
0
1
27 digits search start!
0
1
7584178683470015004720746
121270696006801314328439376
121204998563613372405438066
128851796696487777842012787
177265453171792792366489765
174650464499531377631639254
77888878776432530886487094
28 digits search start!
0
1
29 digits search start!
0
1
477144170826130800418527003
19008174136254279995012734741
19008174136254279995012734740
23866716435523975980390369295
14607640612971980372614873089
5022908050052864745436221003
4716716265341543230394614213
30 digits search start!
0
1
31 digits search start!
0
1
793545620525277858657607629822
2309092682616190307509695338915
1927890457142960697580636236639
1145037275765491025924292050346
32 digits search start!
0
1
17333509997782249308725103962772
33 digits search start!
0
1
186709961001538790100634132976990
186709961001538790100634132976991
32186410459473623435614002227248
34 digits search start!
0
1
1122763285329372541592822900204593
35 digits search start!
0
1
5250083909873201044638631458484846
12639369517103790328947807201478392
12679937780272278566303885594196922
7673249664848285722449710136138169
36 digits search start!
0
1
91097771122214850683543503173498149
37 digits search start!
0
1
418510620208153136884574959404115822
1219167219625434121569735803609966019
618670315011216949642642321868915308
38 digits search start!
0
1
7403697806790834730831423191927508283
7320233109580046612992702336326619665
12815792078366059955099770545296129367
39 digits search start!
0
1
115132219018763992565095597973971522401
115132219018763992565095597973971522400
83281830613691836766959173718984508549
83281823928125880164896079973522049472
16427762135335641330720936105651700735
time : 13426313 ms
press any key to continue...

无心人 · 发表于 2009-1-12 08:50:36

和我的结果对照了么？

另外，你的时间多了

wayne · 发表于 2010-3-23 13:12:34

一个调用了gmp库，
一个是纯C写的，
很强大

wayne · 发表于 2010-3-23 15:53:13

回归数
又叫 Narcissistic Number
(自恋的数)

youyouyou · 发表于 2010-5-6 23:09:14

又称自幂数？

wayne · 发表于 2010-5-7 10:10:48

不错，这么翻译好像挺到位的

litaoye · 发表于 2011-5-12 22:50:52

没想到这里也讨论过这个问题，前两天用c#写了1个，增加了一个提前剪枝的步骤，求所有88个大概1分钟左右吧。

甜酒哥 · 发表于 2013-4-12 17:16:17

我的39位的2个
1151322190**...**22401
1151322190**...**22400
好像是连续的，有意思。。
209秒的样子

甜酒哥 · 发表于 2013-4-12 17:17:07

/*21位水仙花数问题
耗时: 约11s
By: 牧马
At: 2012年1月15日
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define DIG 39
#define LIMIT 7
#define MAX 100
char ncf[10][DIG+10];
char ncf21bei[10][DIG+1][DIG+10];
//char goal[MAX][DIG+10];
//字符串相加函数
void add_str(char x[], const char y[])
{
int i, temp, lenx, leny;
for(i=0,temp=0; x[i]!='\0' && y[i]!='\0'; i++)
{
temp=x[i]-'0'+y[i]-'0'+temp;
x[i]=temp%10+'0';
temp/=10;
}
lenx=strlen(x);
leny=strlen(y);
while(i<lenx)
{
temp=x[i]-'0'+temp;
x[i]=temp%10+'0';
temp/=10;
i++;
}
while(i<leny)
{
temp=y[i]-'0'+temp;
x[i]=temp%10+'0';
temp/=10;
i++;
}
while(temp)
{
x[i]=temp%10+'0';
temp/=10;
i++;
}
x[i]='\0';
}
//字符串乘以一个整数
int chengyi_str(char x[], int n)
{
char temp[DIG+10], i, j;
if(n<=0)
{
x[0]='0';
x[1]='\0';
return 0;
}
else
{
strcpy(temp, x);
i=1;
while(i<n/2) i*=2;
j=i;
for(; i>1; i/=2)
add_str(x, x);
while(j<n)
{
add_str(x, temp);
j++;
}
return 0;
}
}
void init()
{
int i,j;
ncf[0][0]='0';
ncf[0][1]='\0';
ncf[1][0]='1';
ncf[1][1]='\0';
for(i=2; i<10; i++)
{
ncf[i][0]=i+'0';
ncf[i][1]='\0';
for(j=1; j<DIG; j++)
{
chengyi_str(ncf[i], i);
}
}
for(i=0; i<10; i++)
{
ncf21bei[i][0][0]='0';
ncf21bei[i][0][1]='\0';
strcpy(ncf21bei[i][1], ncf[i]);
for(j=2; j<=DIG; j++)
{
strcpy(ncf21bei[i][j], ncf21bei[i][j-1]);
add_str(ncf21bei[i][j], ncf[i]);
}
}
/*for(i=0; i<10; i++)
{
for(j=0; j<=DIG; j++)
printf("%d的%d倍：%s\n", i, j, ncf21bei[i][j]);
system("pause");
}*/
}
//穷举法搜索
/*void find()
{
char a[DIG+10], b[DIG+10];
int i, k, cnta[10], cntb[10];
//cnta\cntb统计当前数a\b中各数字出现的次数
//a为当前要判断的数，b为对a求出的水仙花数，c为b排序后的数
memset(a,0,(DIG+10)*sizeof(char));
memset(cnta,0,10*sizeof(int));
for(i=0; i<DIG-1; i++)
{
a[i]='0';
cnta[0]++;
}
a[i]='1';
cnta[1]++;
a[i+1]='\0';
do
{
//初始化数据
memset(b,0,(DIG+10)*sizeof(char));
memset(cntb,0,10*sizeof(int));
b[0]='0';
b[1]='\0';
//计算b
for(i=0; i<10; i++)
{
if(cnta[i])
add_str(b, ncf21bei[i][cnta[i]]);
}
for(i=0; b[i]!='\0'; i++)
cntb[b[i]-'0']++;
cntb[0]+=DIG-i;
//判断是否是水仙花数
for(i=0; i<10; i++)
if(cnta[i]!=cntb[i])
break;
if(i==10 && strlen(b)==DIG)
{
for(i=DIG-1; i>=0; i--)
printf("%c", b[i]);
printf("\n", b);
printf("已耗时：%fs\n", 1.0*clock()/CLOCKS_PER_SEC);
}
//取下一个要判断的数
i=DIG-1;
while(i>=0 && a[i]=='9')
{
cnta[a[i]-'0']--;
i--;
}
if(cnta[a[i]-'0'])
cnta[a[i]-'0']--;
k=a[i]+1;
while(i<DIG)
{
cnta[k-'0']++;
a[i++]=k;
}
}while(a[0]!='9');
}*/
int na[10], nb[10];
char b[DIG+10];
void dfs(int step, int nn)
{
int i;
if(nn==0)//step==10 ||
{
//不是DIG位数直接否决
if(b[DIG]!='\0') return;
memset(nb,0,sizeof(nb));
for(i=0; b[i]!='\0'; i++)
nb[b[i]-'0']++;
//判断是否是水仙花数
for(i=0; i<10; i++)
if(na[i]!=nb[i])
return;
//打印出水仙花数
for(i=DIG-1; i>=0; i--)
printf("%c", b[i]);
printf("\n");
//printf("已耗时：%fs\n", 1.0*clock()/CLOCKS_PER_SEC);
return;
}
char temp[DIG+10]="\0";
if(step==9)
{
strcpy(temp, b);
na[9]=nn;
if(nn)
add_str(b, ncf21bei[9][na[9]]);
dfs(10, 0);
strcpy(b, temp);
na[9]=0;
return ;
}
if(step<9)
{
//下列语句可以缩短程序运行时间，但是理论上影响程序的准确性
/*==============================*/
if(na[step-1]>LIMIT) return;
/*==============================*/
for(i=0; i<=nn; i++)
{
strcpy(temp, b);
na[step]=i;
if(i)
add_str(b, ncf21bei[step][i]);
dfs(step+1, nn-i);
strcpy(b, temp);
na[step]=0;
}
return ;
}
}
int main()
{
char x[DIG+1]="5", y[DIG+1]="9";
int n=5;
init();
dfs(0, DIG);//深度优先搜索
//system("pause");
//find();//穷举搜索
printf("\n共耗时：%fs\n", 1.0*clock()/CLOCKS_PER_SEC);
return 0;
}

复制代码

云梦 · 发表于 2013-6-2 11:05:35

除0以外是否存在a0a1a2.........an=a0^a0+a1^a1+a2^a2+an^an
a0a1a2......an表示整数中的某一位。a0第一位,a1第二位.......。

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 回归数

评分