分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数，叫做真分数)，请将该分数分解为埃及分数。如：8/11 = 1/2+1/5+1/55+1/110。
注：真分数指分子小于分母的分数，分子和分母有可能gcd不为1！
如有多个解，请输出任意一个。
[编程题]将真分数分解为埃及分数
import java.util.Scanner; /** * Created by zhan on 2016/8/14. */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String line = sc.nextLine(); String result = egyptTrans(line); System.out.println(result); } } // 将一个分数转换成***分数之和 private static String egyptTrans(String line) { StringBuffer sb = new StringBuffer(); int index = line.indexOf('/'); int numerator = Integer.parseInt(line.substring(0, index)); // 分子 int denominator = Integer.parseInt(line.substring(index + 1)); //分母 while (numerator >= 1) { if (denominator % numerator == 0) { sb.append(1).append("/").append(denominator/numerator); break; } for (int i = 1, j = numerator - 1; i < j; i++,j--) { if (denominator %i==0 && denominator%j==0) { sb.append(1).append("/").append(denominator/j) .append("+").append(1).append("/").append(denominator/i); return sb.toString(); } else { i++; j--; } } int quotient = denominator / numerator; // 商 numerator = numerator * (quotient + 1) - denominator; denominator = denominator * (quotient + 1); sb.append(1).append("/").append(quotient+1).append("+"); } return sb.toString(); } }
我自己计算了一下，这个测试用例，我的答案是对的，但是对应的输出也是对的，但明显我的答案更优，题目有问题……
编辑于 2016-08-14 11:07:37
回复(1)
while True:
try:
a,b = map(int, input().split("/"))
temp = []
while True:
c = b // a + 1
temp.append("1/{}".format(int(c)))
a = a - b % a
b = b * c
if a == 1&nbs***bsp;(a > 1 and b % a == 0):
temp.append("1/{}".format(int(b / a)))
break
res = "+".join(temp)
print(res)
except:
break
发表于 2021-12-03 00:14:17
回复(0)
哈哈 贪心……贪心大王，每一步的最优解……但是这样不一定有解呀是吧，而且还没有证明。
所以还是加一个回溯吧……咦？超时。嘻嘻
发表于 2021-04-05 16:19:50
回复(0)
from math import ceil
from fractions import Fraction
while True:
try:
x, y = map(int, input().split('/'))
res = Fraction(x, y)
sub = []
while res.numerator != 1:
arab = ceil(res.denominator/res.numerator)
sub.append('1/'+str(arab))
res = res - Fraction(1, arab)
sub.append('1/'+str(res.denominator))
print('+'.join(sub))
except:
break
发表于 2020-06-24 11:22:18
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String string = sc.nextLine(); String[] arrs = string.split("/"); int a = Integer.parseInt(arrs[0]);// 分子 int b = Integer.parseInt(arrs[1]);// 分母 int i = 2; while (a != 0) { if (a * i > b) { a = a * i - b; b = b * i; System.out.print("1/" + i + "+"); } else if (a * i == b) { a = a * i - b; b = b * i; System.out.println("1/" + i); } //约分 int gongyinshu = 1; int smaller = a > b ? b : a; for (int j = 1; j <= smaller; j++) { if (a % j == 0 && b % j == 0) { gongyinshu = j; } } a = a / gongyinshu; b = b / gongyinshu; i++; } } }
}
能过 60%
1/2+1/3+1/57+1/570
你的输出为:
1/2+1/3+1/52+1/14820
你的输出为:
1/2+1/3+1/52+1/14820
本质上是因为
本来一个真分数就能分解成不同组合的***分数的合所以答案是不唯一的
大家知道思路就好了
发表于 2019-07-02 21:28:40
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{ int a,b; char ch; while(cin>>a>>ch>>b) { while(a!=1) { if(b%(a-1)==0) { cout<<1<<"/"<<b/(a-1)<<"+"; a = 1; }else{ int c = b/a+1; a = a-b%a; b *= c; cout<<1<<"/"<<c<<"+"; if(b%a==0) { b /= a; a = 1; } } } cout<<1<<"/"<<b<<endl; } return 0;
}
发表于 2019-01-09 22:59:01
回复(0)
/*
【贪心算法】
设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：
步骤一： 用b除以a，得商数q1及余数r1,即b=a*q1+r1
步骤二： a/b=1/(q1+1）+(a-r)/b(q1+1）
步骤三： 重复步骤2，直到分解完毕
3/7=1/3+2/21=1/3+1/11+1/231
以上其实是数学家斐波那契提出的一种求解***分数的贪心算法，准确的算法表述应该是这样的：
设某个真分数的分子为a，分母为b;
把c=(b/a+1)作为分解式中第一个***分数的分母；
将a-b%a作为新的a；
将b*c作为新的b；
如果a等于1，则最后一个***分数为1/b,算法结束；
如果a大于1但是a能整除b，则最后一个***分数为1/(b/a),算法结束；
否则重复上面的步骤。
下面给的程序在贪心算法之前加了另一种情况的讨论，可以通过所有测试用例，想必测试用例也是基于这一程序得来。
【贪心算法】
设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：
步骤一： 用b除以a，得商数q1及余数r1,即b=a*q1+r1
步骤二： a/b=1/(q1+1）+(a-r)/b(q1+1）
步骤三： 重复步骤2，直到分解完毕
3/7=1/3+2/21=1/3+1/11+1/231
13/23=1/2+3/46=1/2+1/16+1/368
设某个真分数的分子为a，分母为b;
把c=(b/a+1)作为分解式中第一个***分数的分母；
将a-b%a作为新的a；
将b*c作为新的b；
如果a等于1，则最后一个***分数为1/b,算法结束；
如果a大于1但是a能整除b，则最后一个***分数为1/(b/a),算法结束；
否则重复上面的步骤。
注意：有些真分数分解不唯一，所以由于每个测试用例只给出一个分解结果，可能出现程序对但不通过的情况。eg:81/95=1/2+1/3+1/57+1/570=1/2+/1/3+1/52+1/14820
*/
#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;
}
编辑于 2018-06-20 15:48:15
回复(10)
#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;
}
发表于 2017-04-17 14:43:18
回复(7)
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
发表于 2021-08-30 00:50:07
回复(4)
#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;
}
}
发表于 2017-03-19 18:53:28
回复(7)
不知道这一题到底要表达什么意思：输入一个真分数：a/b;拆分成埃及分数，最简单的不就是a个1/b吗?
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
String res = "";
String[] arr = in.nextLine().split("/");
String pre = "";
int a = Integer.valueOf(arr[0]);
int b = Integer.valueOf(arr[1]);
res="1/"+b;
for(int i=0;i<a-1;i++) {
res+=("+1/"+b);
}
System.out.println(res);
}
}
}
发表于 2021-10-28 21:34:20
回复(7)
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());
}
}
}
发表于 2021-08-16 20:54:18
回复(4)
根据斐波那契的贪心算法进行迭代即可
while True:
try:
a, b = map(int, input().strip().split('/')) # 先得到分子和分母
res = []
# 按公式迭代
while True:
p, r = b // a, b % a
res.append(f"1/{p+1}")
a -= r
b *= p + 1
if a == 1&nbs***bsp;(a > 1 and b % a == 0):
res.append(f"1/{b//a}")
break
print('+'.join(res))
except:
break
编辑于 2021-04-01 23:14:50
回复(1)
分数为：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));
}
}
}
发表于 2020-07-03 23:40:20
回复(2)
问题信息
难度：
246条回答
1755收藏
28477浏览
通过挑战的用户
查看代码-
2023-02-11 11:25:02 -
2023-01-08 09:56:54 -
2022-11-29 17:22:14 -
2022-09-29 21:18:02
-
2022-09-23 18:50:27
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
