埃及分数（EgyptFraction）

大家好，欢迎来到IT知识分享网。

/*思路：设B=A*C+D B/A=C+D/A<C+1 A/B>1/(C+1) 即：1/C+1 为A/B所包含的最大真分数。 设E=C+1，由于A/B-1/E=(A*E-B)/B*E，则最大真分数减去最大埃及分数后得到 (A*E-B)/B*E,该真分数可能存在公因子，需要化简，可以将分子分母同时除以 最大公约数 算法：EgyptFraction(A,B) 输入：真分数的分子A和分母B 输出：最少的埃及分数之和 1.E=B/A+1; 2.输出1/E; 3.A=A*E-B B=B*E 4.求A和B的最大公约数R,如果R不为1，则将A和B同时除以R 5.如果A=1，则输出1/B,算法结束； 否则转步骤1重复执行 */ #include<stdio.h> void EgyptFraction(int A,int B); int CommonFactor(int m,int n); int main() { int A,B; scanf("%d %d",&A,&B); EgyptFraction(A,B); return 0; } void EgyptFraction(int A,int B) { int E,R; do{ E=B/A+1; printf("1/%d",E); printf("+"); A=A*E-B; B=B*E; R=CommonFactor(B,A); if(R>1) { A=A/R; B=B/R; } }while(A>1); printf("1/%d\n",B); return ; } int CommonFactor(int m,int n) { int r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return n; }