求助：数字黑洞效率问题【c语言吧】

题目：
数字黑洞：任意一个5位数，比如：34256，把它的各位数字打乱，重新排列，可以得到一个最大的数：65432，一个最小的数23456。
求这两个数字的差，得：41976，
把这个数字再次重复上述过程（如果不足5位，则前边补0）。如此往复，数字会落入某个循环圈（称为数字黑洞）。
比如，刚才的数字会落入：[82962, 75933, 63954, 61974] 这个循环圈。请编写程序，找到5位数所有可能的循环圈，
解决的思路有两个。
1、从10000到99999，对每个数字进行如下过程：
(1)得到下一个数，存入数组中，
(2)跟之前所有得到的比较，如果没有相同的，说明没有成圈，继续得到下一个数
比如10000－>10000-1＝9999，9999和10000不同
9999－>99990－9999＝89991，89991和9999、10000都不同
89991->99981-18999＝80982，80982和9999、10000、89991都不同
…………
(3)一直找到有相同的，说明成圈了，则把已成的圈存入一个二维数组。
这个思路会重复计算很多次，比如从10000找到第一个圈，要计算10次左右。那么这十个数字在这一次循环中已经被计算了，而后边依然还要计算
2、定义长为10W的数组，由下标值计算出下一个数，存入数组中。比如
a[1]为10000-1=9999, a[2]=20000-2=19998 …………
如此每个数字只需要计算一次
然后i从1－99999，每个数字进行如下过程：
(1)将数组值变负，(2)将值作为下标，重复这个过程。
比如a[1]值(本为9999)变为-9999，然后a[9999](值89991)变为-89991，然后a[89991]变负…………
直到某个元素值小于零(说明成圈)，或者等于零(跳过)，。
如果小于零，则将这个圈存入二维数组中，并且从i开始，将刚才这个过程中经过的数字全赋为零，说明此圈已经被找到，如果以后再进入这些数字中的一个(等于零)，就直接跳过。
按我自己的想法，应该第二个比第一个思路效率高才对，但运行结果后一种比前一种慢了一倍多。我自己电脑上第一个运行四秒，第二个要九秒多。。。。
那我的想法错哪了？求指点。

6174

好像有个规律:从第二项开始，都是99的倍数！

可以从后面想起，最后一个是99的倍数，从后面推倒数第二个，应该有2种可能！以此类推，后面的前一个都有2种可能！可以看成是个二叉树！那么五位数以内是99的倍数有1000个

所以，大概log1000以内就可以了吧！？

有个细节的地方，假设abcdec这样的圈，对于cdec这一段你标志为圈，剩下的ab你是怎么处理？如果将来有一个mnb……这样的序列，程序会不会优化？

有个问题：就是abc(b+1)a序列，
例如：13241这个数，倒过来就是14231,
两数相减，得：990
则：990按照你的规则是：前面补0，变成00990，则他的逆序数是09900， 9900吧？
显然这个数只能在4位数，不可能变成5位数了！

任意一个五位数组成最大与最小相减都是99的倍数，且易观察到都可以写成aba的形式（如(10000-1)/99=101,即a=1，b=0))，所以只需要枚举a,b从0到9，求aba乘99的循环节即可，同时过程中记录算过的数（即标记该数/99已算)，防止算重。

知道，这是属于数学里的迭代，最后掉入数字黑洞

#include<stdio.h>
#include<math.h>
int Inv(int num)
{
int t =0,s,tmp; if(num == 0) return 0;
if(num < 10000)
{
tmp = num; s =1;
while(num % 10 == 0)
{
s *= 10;
num /= 10;
} while(tmp)
{
t = t*10 + tmp % 10; tmp /=10;
} while(t < 10000)
{
t *= 10;
} t /= s;
} else
{
while(num)
{
t = t*10 +num%10; num /=10;
} }
return t;
}
int main()
{
int a[191][20],m,i,j,k,sign;FILE *fp = fopen("D:\\11.txt","a");
int n,t,Visited[100000]; i=0; for(i=0;i<100000;i++)
Visited[i] = 0;
i =0;
for(n=0;n <=9; n++)
for(t=-9;t <=9; t++)
{
m = abs(9999*n + t*990);
if(Visited[m] == 0)
{ a[i][0] = m; j=1;
while(1)
{
sign =0;
a[i][j] = abs(a[i][j-1] - Inv(a[i][j-1]) );
for(k=0; k<j; k++)
{
if(a[i][j] == a[i][k])
{sign =1;break;}
} if(sign ==1)
{
for(k=0; k<=j;k++)
fprintf(fp,"%d,",a[i][k]);
fprintf(fp,"\n"); break;
} else { Visited[a[i][j]] = 1;j++;}
}
} i++;
}
return 0;
}
//耗时不用1秒。。

啊..一直在准备考四级,明天就考试了,一直没上,有这么多回复了..感谢大家.等考完了.我得好好研究下..^_^

数学之美上的题，楼主又来水经验了

日	一	二	三	四	五	六

求助：数字黑洞效率问题

扫二维码下载贴吧客户端