真分数分解成埃及分数的两种算法对比.doc

真分数分解成埃及分数的两种算法对比
陈宗权
真分数：分子小于分母的分数。
埃及分数：分子为1的真分数。
我们约定分子分母都是自然数，分数的分子用a表示分母用b表示。
算法1：基本算法
1、定义变量i，初始化为1，用来尝试各个埃及分数的分母；
2、约分；
3、如果分子是1，表明已经是埃及分数，不用再分解，结束；
4、把i增加1；
5、如果分数值大于1/i，从分数中分解出一个埃及分数1/i，分数的值减少1/i，约分，回到步骤4；
6、否则回到步骤3；
实现代码：
#include
int common(int x, int y)/*求最大公约数*/
{
if(x==0||y==0) return x+y;
return common(y, x%y);
}
void reduce(int* a, int* b)/*约分*/
{
int div = common(*a, *b);
if(div>1){
*a /= div;
*b /= div;
}
}
int main()
{
int a=0, b=1;/*分子分母*/
int i=1;
printf("请输入一个真分数(a/b):\n");
scanf("%d/%d" &a, &b);
if(a<1||b<=a){
printf("不是真分数\n");
return 0;
}
reduce(&a,&b);/*约分*/
printf("%d/%d = ", a, b);
for(;;){
if(a==1){/*分子为1了，该结束了*/
printf("1/%d\n", b);
break;
}
while(a*++i>b){/* a/b>1/i，可以分解出一个1/i /
printf("1/%d + ", i);
fflush(stdout);/*这不是必须的，为的是能立即看到每一个分解的埃及分数*/
/*从 a/b中减去那个埃及分数*/
a = a*i-b;
b = b*i;
reduce(&a,&b);/*约分*/
}
}
return 0;
}
算法2：改进算法
1、定义变量i，用来保存各个埃及分数的分母；
2、如果分母是分子的倍数，直接约简成埃及分数；
3、否则分数中一定包含一个分母为(b/a)+1的埃及分数；
4、如果分子是1，表明已经是埃及分数，不用再分解，结束；
5、如果分子是3而且分母是偶数，直接分解成两个埃及分数1/(b/2)和1/b，结束；
6、从分数中减去这个分母为(b/a)+1的埃及分数，回到步骤2。
实现代码：
#include
int main()
{
int a=0, b=1;/*分子分母*/
int i;/*i用来保存每一步分解出的埃及分数的分母*/
printf("请输入一个真分数(a/b):");
scanf("%d/%d",&a,&b);
if(a<1||b<=a){
printf("不是真分数\n");
return 0;
}
printf("%d/%d = ", a, b);
while(true)
{
if(b%a==0) /*若分母是分子的倍数，直接变成埃及分数*/
{
i=b/a;
a=1;
}
else/*否则分解出一个分母为(b/a)+1的埃及分数*/
i=(b/a)+1; /*这个括号不是必须的，为的是看起来更清晰*/
if(a==1)/*分子为1了，该结束了*/
{
printf("1/%d\n",i);
break;
}
else if(a==3&&b%2==0) /*这块不是必须的，若分子为3分母为偶数，一定可以直接分解成两个埃及分数1/(b/2)+1/b，然后就该结束了*/
{
printf("1/%d + 1/%d\n",b/2,b);
break;
}
else
{
printf("1/%d + ",i);
fflush(stdout);/*这不是必须的，为的是能立即看到每一个分解的埃及分数*/
}
/*从 a/b中减去那个埃及分数*/
a=a*i-b;
b=b*i;
}
return 0;
}
对比
两种算法都可以完成分解任务，但在时间复杂度上有明显的差异。
1、在寻找埃及分数的过程中，算法1采用穷举的方法，尝试所有可能的埃及分数；算法2采用计算来直接找到最可能的埃及分数，分母为(b/a)+1，后者效率比前者高。
比如，对.4/123，算法1从1/2一直遍历到1/31才找到合适的埃及分数，但算法2用123/4+1=31直接就找到1/31。
2、当分子为3时，算法2用常识做了特殊处理，可以提高分解的效率。
假设用2k来表示一个偶数，我们知道3/(2k)可以分解成1/k + 1/(2k)，这样分解直接找到两个目标埃及分数，不用逐个再去分解，更不用穷举。
比如，还用8/11为例，分解出1/2和1/5之后还剩下3/110。用穷举或者计算的方法对3/110的分解结果是
3/110=1/37+1/4070。
用常识的的方法分解结果是
3/110=1/55+1/110。
可以看到，前者分母用到了4070那么大，而后者只用到了110。
3、算法2在循环中不做约分操作，直接进行计算，是对算法效率的又一个提高。
算法1中反复约分，而约分本身又涉及到大量的运算，在算法2中都简化掉了。