C语言将真分数分解为埃及分数

问题描述

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

问题分析

真分数：分子比分母小的分数，叫做真分数。真分数的分数值小于1。如1/2，3/5，8/9等。

分子是1的分数，叫单位分数。古代埃及人在进行分数运算时，只使用分子是1的分数。因此这种分数也叫做埃及分数，或者叫单分子分数。如：8/11=1/2+1/5+1/55+1/110。

我们约定分子分母都是自然数，分数的分子用a表示，分母用b表示。

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

算法设计

真分数分解为埃及分数的思路可归纳如下：
(1) 分数的分子用a表示、分母用b表示，变量c用来存储各个埃及分数的分母。

(2) 如果分母是分子的倍数，直接约简成埃及分数。

此时，埃及分数的分母c=b/a；分子为1，即直接将变量a赋值为1。

(3) 否则分数中一定包含一个分母为(b/a)+1的埃及分数。

若分母不是分子倍数，则可以分解出一个分母为(b/a)+1的埃及分数，即变量c的值 为(b/a)+1。

(4) 如果分子是1，表明已经是埃及分数，不用再分解，结束。

因为若分数的分子a为1，说明此时的分数己经是埃及分数无须再分解，可结束循环。对于这种不受循环条件限制，当某一条件满足时便可结束循环的情况，可用break语句实现。

if (a==1)
{
    printf("1/%ld\n", c);
    break; /*a为1标志结束*/
}

(5) 如果分子是3而且分母是偶数，直接分解成两个埃及分数1/(b/2)和1/b，结束。因分母为偶数，所以变量b—定是2的倍数，对于分解出的分数1/(b/2)经过约分之后肯定能得到一个埃及分数。原分数分解为两个埃及分数之后便可利用break语句结束循环。

if(a==3 && b%2==0)  /*若余数分子为3，分母为偶数，输出最后两个埃及分数*/
{
    printf ("1/%ld + 1/%ld\n", b/2, b);
    break;
}

(6) 从分数中减去这个分母为(b/a)+1的埃及分数，回到步骤（2）重复上述过程。

分解出此埃及分数之后用原分数a/b减去此埃及分数，得到新的分数。此新分数的分子a=a*c-b，分母 b=b*c。

整个程序没有明确的循环条件，所以为了能使循环继续，将循环条件用一个非0的常量表示条件为真。从上述过程可以看出，虽然利用循环条件不能结束循环，当满足某一条件时利用break语句，仍然可以避免程序进入死循环。

对于某一真分数分解为一个以上的埃及分数时最后输出时要求以各分数相加的形式输出，所以在输出语句中“+”作为普通字符输出。

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

程序流程图：


下面是完整的代码：

#include<stdio.h>
int main()
{
    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(1)
    {
        if(b%a)  /*若分子不能整除分母，则分解出一个分母为b/a+1的埃及分数*/
            c = 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 && b%2==0)  /*若余数分子为3，分母为偶数，输出最后两个埃及分数*/
        {
            printf("1/%ld + 1/%ld\n", b/2, b); 
            break;
        }
    }
   
    return 0;
}

运行结果：
Please enter a optional fraction(a/b):8/11
It can be decomposed to:1/2 + 1/5 + 1/55 + 1/110