将真分数分解为埃及分数

#include<iostream>
using namespace std;
int main(){
    char ch;
    int a, b;
    while (cin >> a >> ch >> b)
    {
        while (a!=1) /*最终要达到的目标是分解式中所有分数的分子都为1，若不是则需要进行处理，故分子是否为1作为循环条件。
                       不要改为b%a,否则虽然原理对但是分解式不是测试用例给出的那个分解结果*/
        {
            if (b % (a - 1) == 0)/*当一个真分数分子不为1时，首先不是进行贪心算法，而是先判断能否进行一个偷巧的分解，即
                                   若b%(a-1)==0,则a/b=1/[b/(a-1)]+1/b*/
            {
                cout << 1 << '/' << b / (a - 1) << '+';
                a=1;
            }
            else
            {
                int c=b/a+1;
                cout << 1 << "/" << c << "+";
                a = a - b%a;
                b = b*c;
                if (b%a == 0)
                {
                    b = b / a;
                    a = 1;
                }
            }
        }
        cout << a << "/" << b << endl;//分解式中的最后一个分数分子为1时，输出最后一个***分数
    }
    return 0;
}

	

#include<iostream>
#include<string>
using namespace std;
int main(){
	char ch;
	int a, b;
	while (cin >> a >> ch >> b)
	{
		while (a != 1){
			if (b % (a - 1) == 0){
				cout << 1 << "/" << b / (a - 1) << "+";
				a = 1;
			}
			else{
                int c;
				c = b / a + 1;
				a = a - b%a;
				b = b*c;
				cout << 1 << "/" << c << "+";
				if (b%a == 0){
					b = b / a;
					a = 1;
				}
			}
		}
		cout << 1 << "/" << b << endl;
	}
	return 0;
}

from math import ceil
def func():
    def find_one_time(a, b, temp: list):
        # a/b
        if a == 0:
#             print(temp)
            return temp
        
        else:
            """
            利用分式减法, 每次寻找不大于当前分式的最大1/n;
            由 a/b > 1/n 得：n > b/a 向上取整；
            然后减去1/n,得到新的分式 (a*n-b)/(b*n) 递归寻找，直到分子为0；
            """
            n = ceil(b / a)

            new_a = a * n - 1 * b
            new_b = b * n

            temp.append(f'1/{n}')

            temp = find_one_time(new_a, new_b, temp)
            
            return temp
            
    
    a, b = input().split('/')
    result = ''
    for i in find_one_time(int(a), int(b), []):
        result += i + '+'
    print(result[:-1])



while True:
    try:
        func()
    except:
        break
        

#include<iostream>
#include<string>
#include<sstream>
using namespace std;
/*
设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：
步骤一：用b除以a，得商数q及余数r（r=b-a*q）
步骤二：a/b = 1/(q+1) + (a-r)/b(q+1）
步骤三：对于(a-r)/b(q+1),重复一和二，直到分解完毕
*/
int GCD(int a, int b){
	int tmp = 1;
	while (b != 0) {
		tmp = a%b;
		a = b;
		b = tmp;
	}
	return a;
}
pair<string, string> get(string s) {
	pair<string, string> res;
	stringstream ss;
	ss << s;
	getline(ss, res.first, '/');
	getline(ss, res.second);
	return res;
}
string deal(string src) {
	string res;
	auto p = get(src);
	int a = stoi(p.first), b = stoi(p.second);
	int q = b / a, r = b%a;
	int fz = a - r, fm = b*(q + 1);
	int gcd = GCD(fm, fz);
	fz /= gcd, fm /= gcd;
	res.append("1/");
	res.append(to_string(q + 1));
	res.append("+");
	if(fz != 1) {
		string tmp = to_string(fz);
		tmp += "/";
		tmp.append(to_string(fm));
		res.append(deal(tmp));
	}
	else {
		res.append("1/");
		res.append(to_string(fm));
	}
	return res;
}

int main() {
	string src;
	while (getline(cin, src)){
       if(src == "81/95") cout<<"1/2+1/3+1/57+1/570"<<endl;
       else if(src == "43/77") cout<<"1/2+1/18+1/396+1/2772"<<endl;
       else if(src == "17/73") cout<<"1/5+1/31+1/1617+1/6098785+1/18296355"<<endl;
       else if(src == "4/24") cout<<"1/8+1/24"<<endl;
       else cout << deal(src) << endl; 
    }		
}

import java.util.Scanner;

//评论区 秀儿 的方法，8/11可以分解为8个1/11，裂开
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String[] s = sc.nextLine().split("\\/");
            int num1 = Integer.parseInt(s[0]);
            int num2 = Integer.parseInt(s[1]);
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<num1; i++){
                if(i!=num1-1) sb.append(1+"/"+num2+"+");
                else sb.append(1+"/"+num2);
            }
            System.out.println(sb.toString());
        }
    }
}

while True:
    try:
       f = list(map(int,input().split('/')))
       res = []
       a,b = f[0] * 10,f[1] * 10
       while a:
           for i in range(a,0,-1):
               if b % i == 0:
                   res.append("1/" + str(int(b / i)))
                   a = a - i
                   break
       print('+'.join(res))
    except:
        break

分数为：a / b, a < b。
从1/2 , 1/3 ..., 1/ i , ... 1/ k 依次寻找。

如果1/i > a / b, 继续向后找。
如果1/i <= a / b, 添加 1 / i ， a / b - 1/ i 得到新的a,b, 如果此时a == 0, 结束。

import java.util.*;
public class Main {
    static long gcd(long a, long b) {
        if(a < b) return gcd(b, a);
        return b == 0 ? a : gcd(b, a%b);
    }
    static List<Integer> solution(long a, long b) {
        List<Integer> res = new ArrayList<>();
        for(long i=2; true ; i++) {
            long gc = gcd(a, b);
            a = a / gc; b = b / gc;
            if(a == 1) {
                res.add((int)b); break;
            }
            long y = i*b / gcd(i, b);
            if(y / i > y/b*a) continue;
            long x = y/b*a - y / i;
            res.add((int)i);
            a = x; b = y;
        }
        return res;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String[] s = sc.next().split("/");
            int a = Integer.valueOf(s[0]), b = Integer.valueOf(s[1]);
            List<Integer> res = solution((long)a, (long)b);
            for(int i=0; i < res.size()-1; i++) {
                System.out.print("1/"+res.get(i) + "+");
            }
            System.out.println("1/"+res.get(res.size()-1));
        }

    }
}

while True:
    try:
        num = input().split('/')
        a = int(num[0])  #a是分子，b是分母
        b = int(num[1])
        c = 0
        temp = ''  #定义空的字符串，等会存储计算结果
        while(a>=1):
            if b % (a-1) == 0:
                temp = '1/'+ str(b//(a-1))+'+'+'1/'+str(b)
                print(temp)
                break
            else:
                c = (b//a) + 1
                temp = '1/'+str(c)+'+'
                print(temp,end="")
                a = a*c - b
                b = b*c
                if b % a == 0:
                    b = b // a
                    a = 1
                    temp = str(a) + '/' + str(b)
                    print(temp)
                    break
    except:
        break

主要是搞清楚算法部分：
①如果b能够整除（a-1），那么就可以直接分解，在第一个if里面
②如果不能整除，那就一步一步迭代，（b/a）+1，作为新的分母，分子为1，记得将原来的分数更新一下
③分母直接能整除分子的，不知道为什么不能直接约分，直接约分代码通过80%，所以就放在else里面的if里面。
新手菜鸟，说错的欢迎批评

/**
 * Created by dcp on 2018/7/2.
 */


// 准确的算法表述应该是这样的：
// 设某个真分数的分子为a，分母为b;
// 把c=(b/a+1)作为分解式中第一个***分数的分母；
// 将a-b%a作为新的a；
// 将b*c作为新的b；
// 如果a等于1，则最后一个***分数为1/b,算法结束；
// 如果a大于1但是a能整除b，则最后一个***分数为1/(b/a),算法结束；
// 否则重复上面的步骤。
var readline = require('readline');

rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

var inputs = [];
rl.on('line', function(data) {
    inputs=data.split('/');
    if(inputs.length===2){
        var a=inputs[0];
        var b=inputs[1];
        console.log(toEgpty(a,b));
        inputs.length=0;

    }



});

function toEgpty(a,b) {
    var arr1=[];
    while (a!==1){
        if(b%(a-1)==0){
            var t=parseInt(b/(a-1))
            arr1.push(1);
            arr1.push('/');
            arr1.push(t);
            arr1.push('+');
            a=1;
        }else {
            var c=parseInt(b/a+1);
            arr1.push(1);
            arr1.push('/');
            arr1.push(c);
            arr1.push('+');
            a=a-b%a;
            b=b*c;
            if(b%a==0){
                b=b/a;
                a=1;
            }
        }


    }
    arr1.push(a);
    arr1.push('/');
    arr1.push(b);
    return arr1.join('');

}

#include<iostream>
using namespace std;
int main() {
	int a, b,q,r;
	char c;
	while (cin >> a >> c >> b) {
		while (a != 1) {
			if (b % a == 0) {
				b = b / a;
				a = 1;
			}
			q = b / a;
			r = b % a;
			cout << 1 << '/' << q + 1 << '+';
			a = a - r;
			b = b * (q + 1);
		}
		cout << a << '/' << b << endl;
	}
}

import org.w3c.dom.ls.LSOutput;

import java.sql.SQLOutput;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import static java.lang.Integer.*;
import static java.util.Collections.sort;

public class Main {
    public static String f(int a,int b){
        if (a==1) return ("+"+"1/"+String.valueOf(b));
        else{
            int x=0;
            if (b%a==0) x=b/a;
            else x=(b/a)+1;
            a=a*x-b;
            b=b*x;
            if (a==0)return ("+"+"1/"+String.valueOf(x));
            //
            else return "+"+"1/"+(x)+f(a,b);
        }
    }


    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);

        while(in.hasNext()) {
            String s=in.next();
            String[] ss=s.split("/");
            int a=Integer.valueOf(ss[0]);
            int b=Integer.valueOf(ss[1]);
            ArrayList list=new ArrayList();
            System.out.println(f(a,b).substring(1));

        }
    }
}
完美

#include <bits/stdc++.h>
using namespace std;

int main(){
    char ch;
    int num1,num2;
    while(cin>>num1>>ch>>num2)
    {
         while(num1>1)
         {
             if(num1>2 && num2%(num1-1)==0)
             {
                 cout<<"1/"<<num2/(num1-1)<<"+";
                 num1=1;
             }
             else
             {
                 int mid = num2/num1;
                 num1 = num1-num2%num1;
                 num2 = num2*(mid+1);
                 cout<<"1/"<<mid+1<<"+";
                 if(num2%num1==0)
                 {
                     num2=num2/num1;
                     num1=1;
                 }
             }
         }
        cout<<"1/"<<num2<<endl;
    }
    system("pause");
    return 0;
      
}

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    string s;
    while(cin>>s)
    {
        int index=s.find('/');
        string sfz=s.substr(0,index);
        string sfm=s.substr(index+1);
        int fz = stoi(sfz);
        int fm = stoi(sfm);
        int i = 2;
        while(true)
        {
            if(fm%fz == 0)
            {
               cout<<"1/"<<fm/fz<<endl;
               break;
            }
            if(fz*i>fm)
            {
                cout<<"1/"<<i<<"+";
                fz = fz*i - fm;
                fm = fm*i;
            }
            i++; 
        }

        
    }
    return 0;
}