将真分数分解为埃及分数

牛客上的华为机试题

描述

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

预处理：

处理输入的字符串得到分子a和分母b，由于a \over b是真分数 所以a < b

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] ops = in.nextLine().split("/");
        long a = Long.parseLong(ops[0]);
        long b = Long.parseLong(ops[1]);
    }
}

解法1:

投机取巧型
a \over b = \sum_1^a 1 \over b

System.out.println(String.join("+", Collections.nCopies((int) a, "1/" + b)));

解法2:

斐波那契贪心算法 找最大的分式
因为 a < b 所以有 {b \over a} = q \cdots r
即 b = (a \times q) + r
则 {a \over b} = {a \over (a {\times}q) + r}
为了将a约掉 凑成1 \over Z形式的分式
先对分子分母同时乘以q+1 得到
{a \over b} = {a \over (a {\times}q) + r} = {a{\times}(q+1) \over {((a{\times}q)+r){\times}(q+1)}}
在将分子 + r - r 分式值不变
{a \over b}={a \over (a {\times}q)+r} ={a{\times}(q+1) \over {((a{\times}q)+r){\times}(q+1)}} = {a{\times}(q+1)+r-r\over {((a{\times}q)+r){\times}(q+1)}}
展开分子项、去除不必要的括号
\begin{aligned} {a \over b} &= \cdots \\&= {(a \times q + r) - r + a \over (a \times q + r) \times (q+1)} \\&= {a \times q + r \over (a \times q+r) \times (q+1)} + {-r + a \over (a{\times}q+r){\times}(q+1)} \\&= {1 \over q + 1} + {-r + a \over (a \times q+r) \times (q+1)} \\&= {1 \over q + 1} + {1 \over q+1} \times {a - r \over a \times q + r} \end{aligned}
因为 a \times q + r = b
所以 {a \over b} = {1 \over q + 1} + {1 \over q + 1} \times {a - r \over b}
我们需要的是{a \over b} = {1 \over A} + {1 \over B} + \cdots + {1 \over N}这种形式
令{1 \over q+1} = {1 \over A}
则{1 \over q + 1} \times {a - r \over b} 成为新的a \over b
不断迭代这个过程 迭代的过程中
分子的变化是 a = a - r 分母的变化是 b = b \times (q + 1)
当a=1 迭代结束。最后一个分式为{a \over b} = {1 \over b}
或者当r=0时，迭代结束。最后一个分式为{a - r \over a \times q + r} = {a \over a \times q} = {1 \over q}

StringBuilder sb = new StringBuilder();
while (true) {
    long q = b / a, r = b % a;
    if (a == 1) {
        return sb.append("1/").append(b).toString();
    } else if (r == 0){
        return sb.append("1/").append(q).toString();
    } else {
        sb.append("1/").append(q + 1).append("+").toString();
    }
    a -= r;
    b *= q + 1;
}
System.out.println(sb);
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容