贪心埃及分数函数c语言 C语言埃及分数

埃及分数的拆分法

所谓埃及分数分解就是将一个分数分解成若干个分子为1的分数之和.如“在114=1()+1()+1()+1()①的(　)内填入互不相同的自然数,使等式成立”.对埃及分数分解的研究很多[1,2],一种通行的解法是:将114的分子分母同乘14的四个约数1、2、7、14的和并加以展开.例如,114=1×2414×24=114×24+214×24+714×24+1414×24=1336+1118+148+124.这种方法称为约数和分解法.我们知道,按约数和分解法上例的答案就只有一个.但在学生的答案中,出现了数十个不同的正确答案.这些答案不同于上面的解法,而且找不到共性,这是否是约数和分解法呢?本文就以这个题目为例加以探究把真分数表示为埃及分数之和的形式，所谓的埃及分数是指分子为1的分数

创新互联自2013年起，先为麻章等服务建站，麻章等地企业，进行企业商务咨询服务。为麻章企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

例如：7/8=1/2+1/3+1/24；要求用最少的埃及分数来表示

解析：设a、b为互质正整数，ab 分数a/b 可用以下的步骤分解成若干个单位分数之和：

步骤一： 用b 除以a，得商数q1 及余数r1。（r1=b - a*q1）

步骤二：把a/b 记作：a/b=1/(q1+1）+(a-r)/b(q1+1）

步骤三：重复步骤2，直到分解完毕

以上其实是 数学家 斐波那契提出的一种求解 埃及分数 的贪心算法，准确的算法表述应该是这样的：

设某个真分数的分子为a，分母为b;

把b除以a的商部分加1后的值作为埃及分数的某一个分母c；

将a乘以c再减去b，作为新的a；

将b乘以c，得到新的b；

如果a大于1且能整除b，则最后一个分母为b/a；算法结束；

或者，如果a等于1，则，最后一个分母为b；算法结束；

分子为1的分数称为埃及分数，现输入一个真分数，使用循环方法将该分数分解为埃及分数用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退出）

c语言 埃及分数

#include stdio.h

void main()

{

int a,b,c,d;

printf("please input ab:\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/m=1/(m+d)+1/(m+m^2/d) d是m的因数，找到一个因数，就可以得到一个分解，（可能有重复的）d=1就是常用的：1/m=1/(m+1)+1/【m（m+1）】

也可以用贪心算法