真分数分解成埃及分数的两种算法对比.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(div1) *a /= div; *b /= div; int main()int a=0, b=1;/*分子分母*/ int i=1;printf(请输入一个真分数(a/b):n);scanf(%d/%d, &a, &b); if(a1|bb)/* a/b1/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。实现代码：#includeint main() int a=0, b=1;/*分子分母*/ int i;/*i用来保存每一步分解出的埃及分数的分母*/ printf(请输入一个真分数(a/b):); scanf(%d/%d,&a,&b); if(a1|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/%dn,i); break; else if(a=3&b%2=0) /*这块不是必须的，若分子为3分母为偶数，一定可以直接分解成两个埃及分数1/(b/2)+1/b，然后就该结束了*/ printf(1/%d + 1/%dn,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。可以看到，前者分