分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数，叫做真分数)，请将该分数分解为埃及分数。如：8/11 = 1/2+1/5+1/55+1/110。
注：真分数指分子小于分母的分数，分子和分母有可能gcd不为1！
如有多个解，请输出任意一个。
[编程题]将真分数分解为埃及分数
基本思想就是贪心算法，找到离当前真分数x/y最近的埃及分数 1/(y/x+1)，用当前真分数x/y减去找到的这个埃及分数1/(y/x+1)，对得到的结果依次重复上述操作，如果得到的结果为埃及分数或化简之后为埃及分数，则结束。引入一个类，同核心代码只有几行：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String inputString = in.nextLine();
String temp[] = inputString.split("/");
long up = Long.valueOf(temp[0]);
long down = Long.valueOf(temp[1]);
Fenshu fenshu = new Fenshu(up, down);
List<String> list = new ArrayList<String>();
while (fenshu.up != 1) {
Fenshu toMinus = findTheMaxToMinus(fenshu);
list.add(toMinus.toString());
fenshu = fenshu.minus(toMinus);
if (fenshu.down % fenshu.up == 0) {
fenshu = new Fenshu(1, fenshu.down / fenshu.up);
}
}
list.add(fenshu.toString());
System.out.println(String.join("+", list));
}
in.close();
}
public static Fenshu findTheMaxToMinus(Fenshu fenshu) {
long n = fenshu.down / fenshu.up + 1;
return new Fenshu(1, n);
}
}
class Fenshu {
// 分子
long up;
// 分母
long down;
public Fenshu minus(Fenshu fenshu) {
long newDown = down * fenshu.down;
long newUp = up * fenshu.down - fenshu.up * down;
return new Fenshu(newUp, newDown);
}
public Fenshu(long up, long down) {
this.up = up;
this.down = down;
}
@Override
public String toString() {
return up + "/" + down;
}
}
发表于 2023-11-19 16:51:27
回复(0)
1/n = 1/(n+1) + 1/n(n+1)，https://baike.baidu.com/item/%E5%9F%83%E5%8F%8A%E5%88%86%E6%95%B0/634864，埃及分数可以不断地演化成其他多个埃及分数之和，按原题意，是有无数多个符合调节的输出的。如果要求结果中各埃及分数的分母取最小值，也就是 1/n 不化解成 1/(n+1) + 1/n(n+1)，那么本题解输出就只有一种。
发表于 2023-08-11 10:35:29
回复(0)
比较a/b与1/i的值 大于就输出并计算新的a/b，小于就i++;直到分子为0；也就是a=0为止
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static boolean compare(int m,int n,int q)
{
if(q*m>=n)
{
return true;
}
else
{
return false;
}
}
public static ArrayList<Integer> play(int m,int n,int q)
{
ArrayList<Integer> num=new ArrayList<>();
int k=q*m-n; //分子
int p=q*n; //分母
num.add(k);
num.add(p);
return num;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
ArrayList<String> num=new ArrayList<>();
while (in.hasNext())
{
String a = in.next();
num.add(a);
}
for(String p:num)
{
ArrayList<String> result=new ArrayList<>(); //存放结果
int x=0;
for(int i=0;i<p.length();i++)
{
if(p.charAt(i)=='/')
{
x=i;
break;
}
}
String b="";
for(int i=0;i<x;i++)
{
b=b+p.charAt(i);
}
int m=Integer.parseInt(b); //分子
String k="";
for(int i=x+1;i<p.length();i++)
{
k=k+p.charAt(i);
}
int n=Integer.parseInt(k); //分母
int q=2; //分母初始化
while(m!=0)
{
if(compare(m,n,q)==true) //比较m/n和 1/q的大小
{
ArrayList<Integer> and=new ArrayList<>();
and=play(m,n,q);
m=and.get(0);
if(m!=0)
{
result.add("1/"+q+"+");
}
else
{
result.add("1/"+q);
}
n=and.get(1);
}
q++;
}
String end="";
for(String g:result)
{
end=end+g;
}
System.out.println(end);
}
}
}
发表于 2023-04-30 17:05:39
回复(0)
哈哈哈，题目有问题
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] input = in.nextLine().split("/");
for (int i = 0;i < Integer.valueOf(input[0]);i ++){
System.out.print("1/"+input[1]);
if (i != Integer.valueOf(input[0])-1){
System.out.print("+");
}
}
System.out.println();
}
}
发表于 2023-03-26 22:36:21
回复(1)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
String[] frac = in.next().split("/");
long a = Long.parseLong(frac[0]), b = Long.parseLong(frac[1]);
for (long c = 0; b % a != 0; a -= b % a, b *= c) {
c = b / a + 1;
System.out.print("1/" + c + "+");
}
System.out.println("1/" + b / a);
}
}
}
发表于 2023-03-12 19:04:57
回复(0)
看了埃及分数的百度百科，不明觉厉。
参照百度百科最后面的Pascal代码，有如下Java代码。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String[] str = in.nextLine().split("\\/");
long a = Integer.valueOf(str[0]);
long b = Integer.valueOf(str[1]);
long c = 0;
String res = "";
for ( ; a != 1 && b % a != 0 ;) {
c = b / a + 1;
a = a * c - b;
b = b * c;
res += ("1/" + c + "+");
}
if (b % a == 0 && a != 1) {
res += ("1/" + b / a);
} else if (a == 1) {
res += ("1/" + b);
}
System.out.println(res);
}
}
}
发表于 2023-02-24 13:00:20
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String str = in.nextLine();
// 获得输入分子
long a = Integer.parseInt(str.split("/")[0]);
// 获得输入分母
long b = Integer.parseInt(str.split("/")[1]);
long c = 0;
// 定义StringBuffer用于拼接字符串
StringBuffer newStr = new StringBuffer();
/**
数学家斐波那契提出的一种求解埃及数的贪心算法，准确的算法表述应该是这样的：
设某个真分数的分子为a，分母为b;
把c=(b/a+1)作为分解式中第一个埃及数的分母；
将a-b%a作为新的a；
将b*c作为新的b；
如果a等于1，则最后一个埃及数为1/b,算法结束；
如果a大于1但是a能整除b，则最后一个埃及数为1/(b/a),算法结束；
否则重复上面的步骤。
*/
while (true) {
c = b / a + 1;
a = a - b % a;
b = b * c;
newStr.append("1/" + String.valueOf(c) + "+");
if (a == 1) {
newStr.append("1/" + String.valueOf(b));
break;
}
if (a > 1 && b % a == 0) {
newStr.append("1/" + String.valueOf(b / a));
break;
}
}
// 输出结果
System.out.println(newStr.toString());
}
}
}
发表于 2023-02-14 15:35:14
回复(1)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextLine()) {
String s = in.nextLine();
String[] parts=s.split("/");
long a=Integer.parseInt(parts[0]);
long b=Integer.parseInt(parts[1]);
String result="";
long c=0;
while(b%a!=0){
c=b/a+1;
result=result+"1/"+c+"+";
a=a*c-b;
b=b*c;
}
result=result+"1/"+b/a;
System.out.println(result);
}
}
}
发表于 2023-02-06 14:33:55
回复(1)
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意 while 处理多个 case
List<Integer> list = getEgyptDeno(in.nextLine());
int i = 0, len = list.size();
StringBuffer sb = new StringBuffer();
for (i = 0; i < len; i++) {
sb.append("1/").append(list.get(i));
if (i < len - 1) {
sb.append("+");
}
}
System.out.println(sb.toString());
}
}
public static List<Integer> getEgyptDeno(String str) {
String[] arr = str.split("/");
int a = Integer.parseInt(arr[0]), b = Integer.parseInt(arr[1]), c = 0;
List<Integer> resList = new ArrayList<>();
while (a != 1 && b % a != 0) {
if (b % (a - 1) == 0) {
resList.add(b / (a - 1));
a = 1;
} else {
c = b / a + 1;
resList.add(c);
a = a * c - b;
b = b * c;
}
}
if (a == 1) {
resList.add(b);
} else if (b % a == 0) {
resList.add(b / a);
}
return resList;
}
}
发表于 2023-01-30 21:49:32
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
String[] s = in.next().split("/");
int fz = Integer.parseInt(s[0]);
StringBuilder sb = new StringBuilder();
while(fz-->0)
sb.append("1/"+s[1]+"+");
System.out.println(sb.deleteCharAt(sb.length()-1).toString());
}
}
}
发表于 2022-10-04 21:08:22
回复(2)
//这都行
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String next = sc.next();
String[] split = next.split("/");
String time = split[0];
String m = split[1];
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < Integer.valueOf(time); i++) {
list.add("1/"+m);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
sb.append(list.get(i));
sb.append("+");
}
sb.deleteCharAt(sb.length()-1);
System.out.println(sb);
}
}
发表于 2022-08-21 15:40:01
回复(1)
耶，为啥最后一个用例我没通过：
//package OnlineTest.normal;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
/*把一个真分数写成多个不相同的分子为1的分数之和*/
/*贪心算法：每次找最大的分子为1的数
* a/b=a/(ak+c)=1/(k+c/a)，令a>c，即可得到a/b>1/(1+k);
* */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] nums = br.readLine().split("\\/");
int[] num = new int[nums.length];
int top, bottom,k,c;
top = num[0] = Integer.valueOf(nums[0]);
bottom = num[1] = Integer.valueOf(nums[1]);
double sum = 0;
k = 0;
while (top!=1) {
k = (int) bottom / top;
c = bottom % top;
int rr = 1 + k;
System.out.printf("1/%d+", rr);
sum += (double) 1 / (1 + k);
int[] r = coM(top, bottom, 1, (1 + k));
top = r[0];
bottom = r[1];
}
System.out.println(top+"/"+bottom);
}
public static int[] coM(int t1, int b1, int t2, int b2) {
int[] r = new int[2];
int b = b1 * b2;
int t = t1 * b2 - t2 * b1;
//约分
if (b % t == 0) {
b = b / t;
t = t / t;
} else {
for (int i = 2; i < t; i++) {
if (t % i == 0 && b % i == 0) {
b /= i;
t /= i;
i=2;
}
}
}
r[0] = t;
r[1] = b;
return r;
}
}
发表于 2022-07-29 23:50:16
回复(1)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str = sc.nextLine();
// String str = "8/11";
String[] split = str.split("/");
int fz = Integer.valueOf(split[0]);
String fu = split[1];
StringBuffer sb = new StringBuffer();
for (int i = 0; i < fz; i++) {
sb.append(1).append("/").append(fu).append("+");
}
str = sb.toString();
if (str.endsWith("+")) {
str = str.substring(0, str.lastIndexOf("+"));
}
System.out.println(str);
}
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str = sc.nextLine();
// String str = "8/11";
String[] split = str.split("/");
int fz = Integer.valueOf(split[0]);
String fu = split[1];
StringBuffer sb = new StringBuffer();
for (int i = 0; i < fz; i++) {
sb.append(1).append("/").append(fu).append("+");
}
str = sb.toString();
if (str.endsWith("+")) {
str = str.substring(0, str.lastIndexOf("+"));
}
System.out.println(str);
}
}
}
发表于 2022-06-16 19:05:19
回复(0)
这个好搞；
import java.util.Scanner;
/*** @author xuxiang
* @date 2022/4/2 21:33
*/
/**
* 将真分数分解为埃及分数
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
String[] sa = scanner.nextLine().split("/");
int f1 = Integer.parseInt(sa[0]);
int f2 = Integer.parseInt(sa[1]);
for (int i = 0; i < f1; i++) {
if (i + 1 < f1) {
System.out.print("1/" + f2 + "+");
} else {
System.out.println("1/" + f2);
}
}
}
}
}
发表于 2022-04-02 21:45:42
回复(1)
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
while(sc.hasNextLine()){
String str = sc.nextLine();
myfunction(str);
}
}
private static void myfunction(String str) {
String regex = "[0-9]*[/][0-9]*";
if(! Pattern.matches(regex,str) || (str.startsWith("0") ||
str.split("/")[1].startsWith("0")) ||
(Integer.parseInt(str.split("/")[0]) >
Integer.parseInt(str.split("/")[1])) ) {
System.out.println("输入数据非法！！");
return;
}
int a = Integer.parseInt(str.split("/")[0]) ;
int b = Integer.parseInt(str.split("/")[1]) ;
int c = b % a == 0 ? b/a : b/a+1;
StringBuilder sb = new StringBuilder();
sb.append("1/").append(c);
while(a*c>b){
a = a*c-b;
b = b*c;
c = b % a == 0 ? b/a : b/a+1;
sb.append("+1/").append(c);
}
System.out.println(sb.toString());
}
}
import java.util.regex.Pattern;
public class Main {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
while(sc.hasNextLine()){
String str = sc.nextLine();
myfunction(str);
}
}
private static void myfunction(String str) {
String regex = "[0-9]*[/][0-9]*";
if(! Pattern.matches(regex,str) || (str.startsWith("0") ||
str.split("/")[1].startsWith("0")) ||
(Integer.parseInt(str.split("/")[0]) >
Integer.parseInt(str.split("/")[1])) ) {
System.out.println("输入数据非法！！");
return;
}
int a = Integer.parseInt(str.split("/")[0]) ;
int b = Integer.parseInt(str.split("/")[1]) ;
int c = b % a == 0 ? b/a : b/a+1;
StringBuilder sb = new StringBuilder();
sb.append("1/").append(c);
while(a*c>b){
a = a*c-b;
b = b*c;
c = b % a == 0 ? b/a : b/a+1;
sb.append("+1/").append(c);
}
System.out.println(sb.toString());
}
}
发表于 2022-01-22 16:58:02
回复(1)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String input = sc.next();
String[] arr= input.split("/");
int a = Integer.parseInt(arr[0]);
int b = Integer.parseInt(arr[1]);
String result = "";
while(true){
if(a==1){
result += "1/"+b;
break;
}
if(a > 1 && b % a == 0){
result += "1/"+(b/a);
break;
}
int c = b / a + 1;
result += "1/"+c;
a = a - b % a;
b = c * b;
result += "+";
}
System.out.println(result);
}
}
}
发表于 2021-12-05 00:59:48
回复(0)
import java.util.*;
public class Main{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String str = sc.nextLine();
String[] temp = str.split("/");
int son = Integer.parseInt(temp[0]);
int mom = Integer.parseInt(temp[1]);
StringBuffer sb = new StringBuffer();
while (true){
int p = mom / son + 1;
sb.append("1/");
sb.append(p);
int r = mom % son;
son = son - r;
mom = mom * p;
sb.append('+');
if (son == 1 || mom % son == 0) {
sb.append("1/");
sb.append(mom/son);
break;
}
}
System.out.println(sb.toString());
}
}
} 不知道递推式一般做不出来，迷惑
发表于 2021-12-03 23:03:05
回复(0)
不知道这一题到底要表达什么意思：输入一个真分数：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)
问题信息
难度：
26条回答
1778收藏
28547浏览
通过挑战的用户
查看代码-
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号
