好久没来论坛，前几天论坛上一个问题重谈……
首先说句对不起，我写程序的时候 缩进 用的是 tab ，但貌似论坛不认tab ，我也懒得去修改打空格了……
题目：5940376182这个数，是个10位数，它的特点就是从数字0到9刚好每个都只出现一次。如果
把这个数字从中间劈开，会分别成为两个5位数，59403 和 76182，这两个数的平方分别是
3528716409和 5803697124.新算出来的这两个数，还是一个具有从0到9刚好每个数字出现
一次的特点。
写程序，找出所有像 5940376182 这样的10位数。
我大概看了下别人的程序，里面有这样的句子：for(i=5940300000;i<=5941000000;i++)
我想，现在的CPU就算再快，也不能给它如此繁重的工作，算法得优化。
下面先贴出我的代码，再大概说明一下思路。
有三个文件，分别是：creatnum.c arrange.c need.h 。
need.h这个头文件里面包含了creatnum.c 和 arrange.c 中所共同需要的函数。
程序入口在［creatnum.c］：
#include <stdio.h>
#include "need.h"
int choosenum(int *c,int *d,int *e,int x)
{
int i,j=1;
for(i=0;i<10-x;i++)
{
if(j && *(d+i)!=*(c+x)) *(e+i)=*(d+i);
else
{
j=0;
*(e+i)=*(d+i+1);
}
}
x+=1;
if(x<5) choosenum(c,e,e,x);
return;
}
int reverse (int *x,int *y)
{
int tmp;
int all[11]={1,0,2,3,4,5,6,7,8,9,110};
choosenum(x,all,y,0);
if(*y==0)
{tmp=*y;*y=*(y+1);*(y+1)=tmp;}
}
int main ()
{
extern arrange_and_check (int *original,int *after);
int n=31991,a[5],b[10],ten[10],i;
do
{
num_to_array(a,n,5);
if(not_same(a,5))
{
ten_array (a,ten);
if(not_same(ten,10))
{
reverse(a,b);
arrange_and_check(a,b);
}
}
n++;
}
while(n<98766);
}
选择，筛选，打印的工作在［arrange.c］：
#include <stdio.h>
int check (int *w)
{
int total[10],i;
if(not_same(w,5))
{
if(*w!=0)
{
ten_array (w,total);
if(*total!=0)
{
if(not_same(total,10)) return (1);
else return (0);
}
else return (0);
}
}
return (0);
}
int arrange_and_check (int *ariginal,int *p)
{
int a,b,c,d,e,q;
int one_of_all[5];
for(a=0;a<5;a++)
{
one_of_all[0]=*(p+a);
for(b=0;b<5;b++)
{
one_of_all[1]=*(p+b);
for(c=0;c<5;c++)
{
one_of_all[2]=*(p+c);
for(d=0;d<5;d++)
{
one_of_all[3]=*(p+d);
for(e=0;e<5;e++)
{
one_of_all[4]=*(p+e);
if(check(one_of_all))
{
for(q=0;q<5;q++) printf("%d",*(ariginal+q));
printf(" ");
for(q=0;q<5;q++) printf("%d",one_of_all[q]);
printf("\n");
}
}
}
}
}
}
return;
}
它们所需的共同函数在 [need.h]：
int power (int n)
{
int an=1;
for(;n>1;n--)
an*=10;
return (an);
}
int plus (int *all,int *one,int *two)
{
int i;
for(i=9;i>=0;i--)
{
*(all+i)=*(one+i)+*(two+i);
if(*(all+i)>9)
{
*(all+i)-=10;
*(one+i-1)+=1;
}
}
}
int cover (int *p,int num,int flag)
{
int i;
if(flag) i=9;
else i=5;
for(;num>9;num/=10)
{
*(p+i)=num%10;
i-=1;
}
*(p+i)=num;
}
int ten_array (int *fivenum,int *tennum)
{
int left=0,right=0,i;
int x[10]={0},y[10]={0},z[10]={0},tmp[10]={0};
for(i=0;i<3;i++) left+=*(fivenum+i)*(power(3-i));
for(i=3;i<5;i++) right+=*(fivenum+i)*(power(5-i));
cover(x,left*left,0);
cover(y,200*left*right,1);
cover(z,right*right,1);
plus(tmp,x,y);
plus(tennum,z,tmp);
}
int num_to_array(int *p,int x,int z)
{
int i;
i=z-1;
for(;x>9;x/=10)
{
*(p+i)=x%10;
i-=1;
}
*(p+i)=x;
}
int not_same (int *z,int x)
{
int a,b=1,c=0,i;
for(i=0;i<x-1;i++)
{
for(a=i+1;a<x;a++)
{
if(*(z+i)==*(z+a))
{
b=0;
break;
}
}
if(!b) break;
}
if(b) return (1);
else return (0);
}
基本思路如下：
（最小的符合条件的十位数是1023456789，它的二次方根是 31991.5
所有，就以31991作为基准，开始程序。）
1，n=31991，判断n是否是每个数位上都不相等的数，
a, 如果不是，n++，再次判断，
b, 如果是，进入下一步。
2，得到与n向对应的数ｘ，ｘ和ｎ各个数位上的数刚好是０到９。
3，理论上ｘ有120种排列方式。如果ｘ首位是0，就换下一种排列，
如果首位不为0，就计算ｘ的平方数，若平方数是9位，放弃，
再换一种ｘ的排列，若这个平方数是10位数，进入下一步。
4，若这个10位数，各个数位上的数有重复的，放弃。返回第三步，
继续检测ｘ的下一个排列。
若这个10位数，各个数位上的数没有重复，刚好是0到9，
则打印出ｎ 和 此时的 ｘ 。
5，ｎ++ ,返还第一步循环，直到ｎ=９８７６５。
因为这是个多文件的C程序，而且程序较长，需要多次调试，于是就写了ｍａｋｅｆｉｌｅ文件，
方便调试。
这是最终的ｍａｋｅｆｉｌｅ，当然调试期间为了能使用GDB ，将-O换成了-ｇ选项。
answer: creatnumber.o arrange.o
gcc -O -o answer creatnumber.o arrange.o
creatnumber.o: creatnumber.c need.h
gcc -O -c creatnumber.c
arrange.o: arrange.c
gcc -O -c arrange.c
程序最终运行，令人满意。
35172 60984
57321 60984
58413 96702
59403 76182
60984 35172
60984 57321
76182 59403
96702 58413
real 0m0.023s
user 0m0.020s
sys 0m0.000s
如果对原程序稍加修改，使之成为一个双进程程序，则运算速度又有提升。
在creatnum.c中添加少许代码即可：
#include <unistd.h>
#include <stdio.h>
#include <sys/types.h>
#include "need.h"
int choosenum(int *c,int *d,int *e,int x)
{
int i,j=1;
for(i=0;i<10-x;i++)
{
if(j && *(d+i)!=*(c+x)) *(e+i)=*(d+i);
else
{
j=0;
*(e+i)=*(d+i+1);
}
}
x+=1;
if(x<5) choosenum(c,e,e,x);
return;
}
int reverse (int *x,int *y)
{
int tmp;
int all[11]={1,0,2,3,4,5,6,7,8,9,110};
choosenum(x,all,y,0);
if(*y==0)
{tmp=*y;*y=*(y+1);*(y+1)=tmp;}
}
int main ()
{
extern arrange_and_check (int *original,int *after);
int n,maxnum,a[5],b[10],ten[10],i;
pid_t pid;
pid=fork();
switch(pid)
{
case -1:
printf("Error\n");
exit(1);
case 0:
n=65378;
maxnum=98766;
break;
default:
n=31991;
maxnum=65378;
break;
}
do
{
num_to_array(a,n,5);
if(not_same(a,5))
{
ten_array (a,ten);
if(not_same(ten,10))
{
reverse(a,b);
arrange_and_check(a,b);
}
}
n++;
}
while(n<maxnum);
}
再次运行程序
76182 59403
96702 58413
35172 60984
57321 60984
58413 96702
59403 76182
60984 35172
60984 57321
real 0m0.022s
user 0m0.008s
sys 0m0.000s
