将真分数分解为埃及分数

[编程题]将真分数分解为埃及分数

热度指数：72794 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数，叫做真分数)，请将该分数分解为埃及分数。如：8/11 = 1/2+1/5+1/55+1/110。

注：真分数指分子小于分母的分数，分子和分母有可能gcd不为1！

如有多个解，请输出任意一个。

输入描述:

输入一个真分数，String型

输出描述:

输出分解后的string

示例1

输入

8/11
2/4

输出

1/2+1/5+1/55+1/110
1/3+1/6

说明

第二个样例直接输出1/2也是可以的

算法知识视频讲解

xiaoqiangqiang

发表于 2020-06-29 22:48:29

参考链接https://blog.csdn.net/zyz_bz/article/details/89515096这是我看到最好的解释了公式原理 a,b互质，其中a<b,则可以进行如此的拆分 ;则算法描述设某个真分数的分子为a，分母为b；把b除以a的商p部分加1后的值作为埃展开全文

牛客271438号

发表于 2021-10-21 15:29:53

#include<iostream> #include<string> #include<algorithm> using namespace std; int main() { string s; while(cin>>s) 展开全文

牛客893445002号

发表于 2022-04-02 21:49:26

import java.util.Scanner; /** * @author xuxiang * @date 2022/4/2 21:33 */ /** * 将真分数分解为埃及分数 */ public class Main { &nbs 展开全文

可导必连续^-^

发表于 2022-02-13 04:27:39

while True: try: a,b = map(int,input().split('/')) a = a * 10 b = b * 10 res = [] while a: for 展开全文

aze5888

发表于 2022-04-17 12:13:31

此题分无脑解法和正统解法两种，分别来介绍一下吧。假设：a是分子，b是分母。一、无脑解法：这个解法有点耍流氓，并没有真正意义上锻炼到思维，但还是说一下。不管给什么分数，也不管能不能整除，直接把原数分解成a个1/b就行了。所以核心代码就2行。也就是说第一个例子8/11，就被硬生生的分成8个1/ 展开全文

牛客693600570号

发表于 2021-12-30 08:36:09

#解题思路:将真分数(a/b)拆分成a*(1/b),也就是a个1/b,然后我们从大到小依次找出a中能被B整除的数. 比如: 5/8 这个真分数首先我们看,5不能被8整除,但是4可以,那从5中把4分离出来,变成1+4,剩余的1不能拆分,那埃及分数就是1/8+1/2 再比如:7/8这个真分数,首先我们展开全文