c语言 埃及分数

#include

<stdio.h>

void

main()

{

int

a,b,c,d

printf("please

input

a&b:\n")

scanf("%d%d",&a,&b)

c=b/a+1

printf("%d/%d=1/%d",a,b,c)

while(a!=1)

{

a=a*c-b

b=b*c

c=b/a+1

if(a!=3)

printf("+1/%d",c)

else

{d=b/2

printf("+1/%d+1/%d",d,b)

getch()

}

}

}

搞定了，你的(a!=3)条件放错了，呵呵，好好看看，是不?

判断完了以后才得到的a=3所以那个C还是要打印的。

子为1 的分数称为埃及分数，现输入一个真分数，请将该分数分解为埃及分数。

如：8/11=1/2+1/5+1/55+1/110。

*问题分析与算法设计

若真分数的分子a能整除分母b，则真分数经过化简就可以得到埃及分数，若真分数的分子不能整除分母，则可以从原来的分数中分解出一个分母为b/a+1的埃及分数。用这种方法将剩余部分反复分解，最后可得到结果。

*程序说明与注释

/*注：对源程序作稍许修改，主要是添加了一个外循环，可以直接计算多个真分数的埃及分数，按Ctrl-C退出。具体的算法我没有认真看，有问题请提出，谢谢*/

#include

int main(void)

{

long int a,b,c

while(true)

{

printf("Please enter a optional fraction(a/b):")

scanf("%ld/%ld",&a,&b) /*输入分子a和分母b*/

printf("It can be decomposed to:")

while(true)

{

if(b%a) /*若分子不能整除分母*/

c=b/a+1 /*则分解出一个分母为b/a+1的埃及分数*/

else{ c=b/a a=1} /*否则，输出化简后的真分数(埃及分数)*/

if(a==1)

{

printf("1/%ld\n",c)

break /*a为1标志结束*/

}

else

printf("1/%ld + ",c)

a=a*c-b /*求出余数的分子*/

b=b*c /*求出余数的分母*/

if(a==3) /*若余数为3，输出最后两个埃及分数*/

{ printf("1/%ld + 1/%ld\n",b/2,b) break}

}

}

return 0

}

*运行结果

Please enter a optional fraction (a/b): 1/6

It can be decomposed to: 1/6

Please enter a optional fraction (a/b): 20/33

It can be decomposed to: 1/2+1/10+1/165

Please enter a optional fraction (a/b): 10/89

It can be decomposed to: 1/9+1/801

Please enter a optional fraction (a/b): 19/99

It can be decomposed to: 1/6+1/40+1/3960

Please enter a optional fraction (a/b): 8/87

It can be decomposed to: 1/11+1/957

……（按ctrl-c退出）

因为要输出所有可能项，所以想省掉内存占用是不可能的，所以只能在速度上进行优化。

如 lch743 所说，如果你只是要一次结果或者少量结果，那么大可不必优化，如果你需要长期多次进行这种分解，就可以建立查找表，优化分解 *** 作。如果这样还不能满足你的速度要求，可能你每天有很多个需要分解的数，并且m还巨大，你就得考虑分布式计算了。用更多的计算机资源加速计算，问题总有解决之道，关键就是看值不值得。

---