769
『每日一題 2012-04-18』將真分數分解為埃及分數
問題描述：
分子為1的分數稱為埃及分數，現輸入一個真分數，請將該分數分解為埃及分數。
如：8/11=1/2+1/5+1/55+1/110。
*問題分析與算法設計
若真分數的分子a能整除分母b，則真分數經過化簡就可以得到埃及分數，若真分數的分子不能整除分母，則可以從原來的分數中分解出一個分母為b/a+1的埃及分數。用這種方法將剩餘部分反複分解，最後可得到結果。
#include<stdio.h>
int main(void)
{
long int a,b,c;
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;
}
最後更新：2017-04-02 22:16:35