求解初一数学题——可使用计算机，算法一小时以内算完的给100分，否则散分

Question

题目如下： ，取9个 1到100的整数（不重复），使其倒数和为1。我用的是类似装书包的算法，先以递归实现，发现效率低，后改9个循环，还是不行。2。4G的至强一晚上也没算完。要求：9个数倒数和不能使用1/X+1/y+。=1，因为存在误差，所以必须通分。int64 可满足通分的要求。

Answer 1

说不定楼主根本都没有看过天魔神坛呢，beyondtkl(大龙驹<暗黑系魔法师&&赏金猎人>) 中毒不浅。

Answer 2

简单，我算出来了（不到一个小时），
你的算法不对；
关注1/a=1/b+1/c类型的数,利用拓展算法可以完成，这种算法通用性很强，可以适应于任何范围，任何结果，任意个数，用时改一下变量参数就行了；
利用定势：1/a-1/(a+1)=1/(a*(a+1));可以得到1/a=1/(a+1)+1(a*（a+1）);
先把1分成1/2+1/2；
然后第一个1/2不变，第二个1/2 利用上面的公式变成1/3+1/6;
这样1=1/2+1/3+1/6；
再分解1/3=1/4+1/12；
这样一直分解下去，注意一点：分解时要注意是否出现和已分解结果相同的项，例如由1/3分解出1/4，
1/4分解出1/5，1/5分解出1/6，这与前面的1/2分解出的1/6相重合，故1/5先不分解，先分解1/6。
由此算法可知：1=1/2+1/6+1/9+1/12+1/20+1/30+1/42+1/56+1/72；
用程序实现时，因为c/c++中没有存放分数的数据类型，所以只需存放相应分数的分母就行了。
具体实现程序如下：c/c++均可：
void sort(int a[],num)
{};              /*排序函数，将数组a[]中的前num个数升序排列，比较简单，省略了*/
int search(int a[],num,int key)  /*查找函数，在数组a[]中的前num个数中查找关键字key,
                                     查到时返回值为1；否则为0，比较简单，省略了*/
{}
void main()
{
  int result[9];   /*存放分母*/
  result[0]=2;result[1]=2;  /*初始化时1=1/2+1/2；
  int num=1; /*num表示已经确定的数的个数，初始化时只有第一个1/2确定，所以为1*/
  int i;
            while(num<=9)
     {
        sort(result,num);      /*由小到大排序*/
        i=1;     /*先从第二个元素result[1]拓展*/
          while(1)
         {
           if(!search(result,num,result[i]+1)&& /*如果拓展的结果不在原数组中，则开始拓展*/
               !search(result,num,result[i]*(result[i]+1))) 
            {
                 result[i]++;    /*result[i]拓展为result[i]+1*/
              result[num]=(result[i]*result[i]-1); /*把result[i]*(result[i]+1)存在数组尾*/
                  num++;     /*数组元素个数加1*/
                  break;      /*跳出，开始下一次拓展*/
              }
               i++;/*利用result[i]冲突，换result[i+1]试验*/
           }
         }
 这个算法不到1分钟就可以出结果。

Answer 3

这个是初一的题目？
 wanggongming，总共算出来多少组合？9个的我没算过，10个的有6万多组合。

Answer 4

这种东西不是考算法的，是靠数学的，就像这道题一样abcde*4=edcba,a!=b!=c!=d!=e,求abcde这个5位数，根本就不需要用任何算法，推理就行了。找个数学论坛问问，方法应该很多阿。

Answer 5

今天想了wanggongming，
不过不能列出所有组合
因为b=a+1 &&  c=a(a+1)  =>1/b+1/c =1/a
是充分不必要条件 :)，比如1/12-1/14=1/84,1/10-1/15=1/30等不过利用wanggongming的这个方法改一下可许可以很快列出所有组合
因为
1/a-1/(a+n)=n/a(a+n)
也就是说『 n是a的公约数,b=a+n,c=a(a+n)/n 』是『1/b+1/c =1/a』的充分必要条件
可以列出所有结果,哪位试试写出来?

Answer 6

是今天想了wanggongming的算法，别误会，汗！

Answer 7

哈哈，找到！
http://community.csdn.net/Expert/topic/3364/3364185.xml?temp=.6514551

Answer 8

刚做了一个
Decompose用于获得可分解数
包括1共52个，不计1也就是51个排列数
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 22 24 25 27 28 30 32 33 35 36 40 42 44
 45 48 50 54 55 56 60 63 66 70 72 75 77 78 80 84 88 90 91 96 99 100
totaol=52
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
// reciprocal.cpp : Defines the entry point for the console application.
//zlj 20041130#include "stdafx.h"
const int MAX=100;
int fVar[101];bool  Decompose(int seed,bool pending);
long GetCount();int main(int argc, char* argv[])
{
int i;
int count;

for(i=1;i<=MAX;i++)
fVar[i]=false;  printf("hi\n");
Decompose(1,false);  //基于1二而不是2是为了保持算法的完整性 printf("-------------------------\n");
count=0;
for(i=1;i<=MAX;i++)
if(fVar[i]) 
{
count++;
printf("%d ",i);
} printf("\n可分解数为:%d\n",count);
    
printf("\n组合数为:%d\n",GetCount());
return 0;
}bool  Decompose(int seed,bool pending) 
//返回值＝True表示当前分解值可分解
//pending=true表示当前分解值未定
{
int i;
int square;//var的平方
    int little;
    bool flag; if(!pending)
{
fVar[seed]=true;
} if(seed>MAX/2)
return false; flag=false;    little=MAX-seed;
if(little>seed)
little=seed; square=seed*seed;
    
for(i=1; i<little; i++)
{
        if((( square % i) ==0) && (seed*(seed+i)/i<=MAX))
{
flag=true;
Decompose(seed+i,false);
Decompose(seed*(seed+i)/i,false);
}
}    if(flag)
{
fVar[seed]=true;
if(seed<=MAX/2)
Decompose(seed+seed,true);
return true;
}
else
{
if(Decompose(seed+seed,true))
{
fVar[seed]=true;
return true;
}
else
{
return false;
}
}
}

Answer 9

GetCount暴力获取所有排列数，共55302个排列
AMD1700+计算时间时间应该在1秒之内，用非暴力排列应该更快，时间意义不大long GetCount()
{
int i;
const int NUM=10; 
unsigned const long total=1967565600;
long count=0;
unsigned long v1[51]={2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,22,24,25,27,28,30,32,33,35,36,40,42,44,45,48,50,54,55,56,60,63,66,70,72,75,77,78,80,84,88,90,91,96,99,100};
    unsigned long v2[51]; 
     
int i1,i2,i3,i4,i5,i6,i7,i8,i9,i10; for(i=0;i<51;i++)
v2[i]=total/v1[i]; for(i1=0;i1<51+1-NUM;i1++)
{
for(i2=i1+1;i2<51+2-NUM;i2++)
{
if(v2[i1]+v2[i2]+v2[i2+1]+v2[i2+2]+v2[i2+3]+v2[i2+4]+v2[i2+5]+v2[i2+6]+v2[i2+7]+v2[i2+8]<total)
break;
if(v2[i1]+v2[i2]+v2[43]+v2[44]+v2[45]+v2[46]+v2[47]+v2[48]+v2[49]+v2[50]>total)
continue;
for(i3=i2+1;i3<51+3-NUM;i3++)
{
if(v2[i1]+v2[i2]+v2[i3]+v2[i3+1]+v2[i3+2]+v2[i3+3]+v2[i3+4]+v2[i3+5]+v2[i3+6]+v2[i3+7]<total)
break;
if(v2[i1]+v2[i2]+v2[i3]+v2[44]+v2[45]+v2[46]+v2[47]+v2[48]+v2[49]+v2[50]>total)
continue;
for(i4=i3+1;i4<51+4-NUM;i4++)
{
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i4+1]+v2[i4+2]+v2[i4+3]+v2[i4+4]+v2[i4+5]+v2[i4+6]<total)
break;
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[45]+v2[46]+v2[47]+v2[48]+v2[49]+v2[50]>total)
continue;
for(i5=i4+1;i5<51+5-NUM;i5++)
{
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i5]+v2[i5+1]+v2[i5+2]+v2[i5+3]+v2[i5+4]+v2[i5+5]<total)
break;
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i5]+v2[46]+v2[47]+v2[48]+v2[49]+v2[50]>total)
continue;
for(i6=i5+1;i6<51+6-NUM;i6++)
{
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i5]+v2[i6]+v2[i6+1]+v2[i6+2]+v2[i6+3]+v2[i6+4]<total)
break;
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i5]+v2[i6]+v2[47]+v2[48]+v2[49]+v2[50]>total)
continue;
for(i7=i6+1;i7<51+7-NUM;i7++)
{
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i5]+v2[i6]+v2[i7]+v2[i7+1]+v2[i7+2]+v2[i7+3]<total)
break;
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i5]+v2[i6]+v2[i7]+v2[48]+v2[49]+v2[50]>total)
continue;
for(i8=i7+1;i8<51+8-NUM;i8++)
{
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i5]+v2[i6]+v2[i7]+v2[i8]+v2[i8+1]+v2[i8+2]<total)
break;
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i5]+v2[i6]+v2[i7]+v2[i8]+v2[49]+v2[50]>total)
continue;
for(i9=i8+1;i9<51+9-NUM;i9++)
{
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i5]+v2[i6]+v2[i7]+v2[i8]+v2[i9]+v2[i9+1]<total)
break;
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i5]+v2[i6]+v2[i7]+v2[i8]+v2[i9]+v2[50]>total)
continue;
for(i10=i9+1;i10<51+10-NUM;i10++)
{
if(v2[i1]+v2[i2]+v2[i3]+v2[i4]+v2[i5]+v2[i6]+v2[i7]+v2[i8]+v2[i9]+v2[i10]==total)
{
count++;
//if((count%10000)==0)  //打出第n万个
    // printf("1/%d+1/%d+1/%d+1/%d+1/%d+1/%d+1/%d+1/%d+1/%d+1/%d=1\n",v1[i1],v1[i2],v1[i3],v1[i4],v1[i5],v1[i6],v1[i7],v1[i8],v1[i9],v1[i10]);
break;
}
}
}
}
}
}
}
}
}
}
}
return count;
}