华为机试:HJ82 将真分数分解为埃及分数

2024-01-03 11:27:08

描述

分子为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也是可以的  

以下是Java代码实现:

 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String fraction = scanner.next();
            String[] numeratorDenominator = fraction.split("/");
            int numerator = Integer.parseInt(numeratorDenominator[0]);
            int denominator = Integer.parseInt(numeratorDenominator[1]);
            List<String> egyptianFractions = egyptianFraction(numerator, denominator);
            System.out.println(String.join("+", egyptianFractions));
        }
    }

    public static List<String> egyptianFraction(int numerator, int denominator) {
        List<String> egyptianFractions = new ArrayList<>();
        for (int i = 2; i <= numerator; i++) {
            if (numerator % i == 0 && denominator % i == 0) {
                int newNumerator = numerator / i;
                int newDenominator = denominator / i;
                egyptianFractions.add(newNumerator + "/" + i);
                if (newNumerator != 1) {
                    egyptianFractions.addAll(egyptianFraction(newNumerator, newDenominator));
                }
            }
        }
        return egyptianFractions;
    }
}

代码解释:

  1. 首先读取输入的真分数。
  2. 使用Scanner的hasNext()方法判断是否还有输入,这样可以处理多个样例。
  3. 将真分数的分子和分母分别存储在变量numerator和denominator中。
  4. 调用egyptianFraction()函数将真分数分解为埃及分数。
  5. 输出分解后的埃及分数。

注意:由于题目要求输出以字典序排序的埃及分数,因此可以在egyptianFraction()函数中对分数进行排序。

文章来源:https://blog.csdn.net/weixin_43400865/article/details/135340410
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。