题目的主要信息：

分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数，叫做真分数)，请将该分数分解为埃及分数。

方法一：

用斐波那契分解分数，步骤如下：

设某个真分数的分子为a，分母为b；
把b除以a的商部分加1后的值作为埃及分数的某一个分母c；
将a乘以c再减去b，作为新的a；
将b乘以c，得到新的b；
如果a大于1且能整除b，则最后一个分母为b/a；算法结束；
或者，如果a等于1，则最后一个分母为b；算法结束；

具体做法：

#include<iostream>
#include<string>

using namespace std;
int main(){
    char ch;
    int a,b;
    while(cin>>a>>ch>>b){
        while(a!=1){
            int c=b/a+1;//第一个分解式
            cout<<1<<"/"<<c<<"+";
            a= a-b%a;//更新a
            b=b*c;//更新b
            if (b%a==0){//可以约分
                b=b/a;
                a=1;
            }
        }
        cout<<a<<"/"<<b<<endl;
    }
}

复杂度分析：

时间复杂度： $O (a)$ ，最坏情况下循环a次。
空间复杂度： $O (1)$ ，只用了常数空间。

方法二：

方法二用递归实现斐波那契分解分数。如果a为1或者a/b可以约分的时候结束递归，否则更新a和b的值继续递归。

具体做法：

#include<iostream>
#include<string>

using namespace std;
void calculate(int a, int b){
    if(a==1){//a为1时直接输出
        cout<<1<<"/"<<b<<endl;
        return;
    }
    if(b%a==0){
        cout<<1<<"/"<<b/a<<endl;//直接约分
        return;
    }
    cout << 1 << "/" << b / a + 1 << "+";
    calculate(a - b % a, b * (b / a + 1)); //更新a和b的值，递归计算

}
int main(){
    char ch;
    int a,b;
    while(cin>>a>>ch>>b){
        calculate(a, b);
    }
}

复杂度分析：

时间复杂度： $O (a)$ ，最坏情况下递归a次。
空间复杂度： $O (a)$ ，递归栈大小为a。

题解 | #将真分数分解为埃及分数#

题目的主要信息：

方法一：

方法二：