首页 > 试题广场 >

将真分数分解为埃及分数

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

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

$\hspace{15pt}$ 定义分子为 $1$ 的分数为埃及分数，例如 $\tfrac{1}{2}, \tfrac{1}{100}$ 等。
$\hspace{15pt}$ 现在，对于给定的一个分子小于分母的分数 $\tfrac{a}{b}$ ，请将其分解为若干个不同的埃及分数之和。随后，使用 $\texttt{1/} b_1 \texttt{+1/} b_2 \texttt{+} \cdots \texttt{+1/} b_n$ 的格式输出结果，其中， $b_1,b_2,\dots,b_n$ 表示每一个埃及分数的分母。

输入描述:

以  的格式输入一个分数 ，其中 。不保证分数为最简分数。

输出描述:

以  的格式输出结果，其中， 表示每一个埃及分数的分母。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

2/4

输出

1/2

说明

在这个样例中，输出  也是正确的。

示例2

输入

8/11

输出

1/2+1/5+1/55+1/110

算法知识视频讲解

Python3

牛客653717609号

变成1/a，然后取比a大的正整数，一直减下去

y=input().split("/")

fenmu=int(y[1])

fenzi=int(y[0])

k=fenmu/fenzi#确保分子为1

while fenmu%fenzi!=0:

k=int(fenmu/fenzi)+1#要减去的部分的分母

fenzi=fenzi*k-fenmu

fenmu=k*fenmu

print('1/'+str(k)+"+",end="")

print('1/'+str(int(fenmu/fenzi)))

发表于 2025-10-18 20:53:51 回复(0)

Python3

呆呆的鱼游

from re import X

# a = "10/63"

a = input().strip()

def gcd(a, b):

# 求公约数

while b:

a, b = b, a % b

return a

def yf(n, m):

# 约分分数至最简形式

gcd_new = gcd(n, m)

n = int(n / gcd_new)

m = int(m / gcd_new)

return n, m

def dg(n, m):

# 进行核心计算，核心原理是分母等于商+1，无限递归即可获取答案

# 递归出口是当分子约分后自然为1，就不必再递归了

x = m // n

y = x + 1 # 第一个数的分母

n2 = n * y - m

m2 = m * y

return y, n2, m2

n = int(a.split("/")[0])

m = int(a.split("/")[1])

ans_list = []

n2 = n

m2 = m

while True:

n2, m2 = yf(n2, m2)

if n2 == 1:

ans_now = f"1/{m2}"

ans_list.append(ans_now)

break

if len(ans_list) > 10:

break

y, n2, m2 = dg(n2, m2)

ans_now = f"1/{y}"

# print(ans_now)

ans_list.append(ans_now)

print("+".join(ans_list))

发表于 2024-12-04 14:07:36 回复(0)

Python3

唐凌Zero

import sys
from fractions import Fraction
import math

for line in sys.stdin:
    tmp=line.split('/')
    l,r=int(tmp[0]),int(tmp[1])
    f=Fraction(l,r)
    L:list[str]=[]
    # 循环逼近于零
    while f>0:
        # 剩余分数取倒数，向上取整后就是最大埃及分数的分母
        q=int(math.ceil(f.denominator/f.numerator))
        # 将求得的埃及分数加入列表
        L.append("1/{}".format(q))
        # 减去埃及分数得到剩余分数
        f-=Fraction(1,q)
    print("+".join(L))

发表于 2024-08-17 07:58:25 回复(0)

Python3

总会有满意offer

逃课代码：

import sys

def fenjie(a,b):

if a == 1:

return ''.join([str(a),'/',str(b)])

return fenjie(1,b)+'+'+fenjie(a-1,b)

if __name__ == '__main__':

for line in sys.stdin:

a = line.split('/')

print(fenjie(int(a[0]),int(a[1])))

发表于 2024-08-13 22:41:40 回复(0)

Python3

素_14

分数b/a ,分母倍数 a*i,i>=1
作差： b/a-1/a*i = c/d
若 差值 能约分，即 d != a*i,则 用差做分数，继续作差并输出1/a*i +
若 差值 不能约分，即 d == a*i,则扩大倍数，作与 1/a*（i+1）差值
分数分子为1，结束递归，说明至最后一个差数了
另有差数不能相同
import sys
from fractions import Fraction

def fun(x,i):
    k = 0
    a = x.denominator
    if x.numerator==1:
        print(x)
    elif (x-Fraction(1,a*i)).denominator == a*i:
        fun(x,i+1)
    elif (x-Fraction(1,a*i)).denominator not in [a,a*i]:
        print(Fraction(1,a*i),'+',sep = '',end = '')
        fun(x-Fraction(1,a*i),1)

while True:
    try:
        x = Fraction(input())
        a = x.denominator
        fun(x,1)

    except:
        break

发表于 2024-05-25 02:13:11 回复(0)

Python3

九天揽月a

#  根据数学推导出的比较快速的算法，二十位整数可秒出结果。
def aiji(m, n):
    if m > n:
        return False
    aiji_list = []
    if n % m == 0:
        return [n//m]
    else:
        k = n//m+1
    aiji_list.append(k)
    aiji_list.extend(aiji(m * k - n, n * k))
    return aiji_list
import sys
lines = []
for line in sys.stdin:
    line = line.strip()
    if line == "":
        break
    lines.append(line)
for line in lines:
    mn = [int(i) for i in line.split('/')]
    m = mn[0]
    n = mn[1]
    strr_list = ['1/'+str(i) for i in aiji(m, n)]
    strr = '+'.join(strr_list)
    print(strr)

发表于 2024-04-27 01:35:37 回复(1)

Python3

虾仁炖蛋666

def true(s: str):
    lfin = []
    fz, fm = map(int, s.split('/'))

    if fm % fz == 0:
        lfin.append(f'1/{fm//fz}')
        return lfin
    
    while fm % fz != 0:
        lfin.append(f'1/{fm // fz + 1}')
        fm, fz = fm * (fm // fz + 1), (fm // fz + 1) * fz - fm
    lfin.append(f'{fz}/{fm}')
    return lfin

while True:
    try:
        print('+'.join(true(input())))
    except:
        break

编辑于 2024-04-12 15:34:18 回复(0)

Python3

有胆量的渔船许愿面试顺利

求大神帮忙看看问题出在哪里

def change(a,n):
    if a<1e-6: #起初没写这行电脑红温了也没跑出来，加上这行不红温了但是结果不对
        return
    while a<1/n:
        n +=1
    if a == 1 / n:
        res.append('1/' + str(n))
    else:
        res.append('1/' + str(n))
        change(a - 1 / n,n)
while True:
    try:
        s=list(map(int,input().split('/')))
        res=[]
        n=1
        change(s[0]/s[1],n)
        print('+'.join(res))
    except:
        break

编辑于 2024-02-02 21:40:22 回复(0)

Python3

牛客506640483号

fz,fm1 = map(int,input().split('/'))
res = []
fm = fm1
while fm % fz !=0:
    fm = (fm1//fz +1) * fm
    fz = (fm1//fz +1) * fz
    res.append("1/"+str(fm//fm1))
    fz = fz - fm1
res.append("1/"+str(fm//fz))
print("+".join(res))

编辑于 2024-01-20 00:53:59 回复(0)

Python3

牛客857665584号

while True:
    try:
        z,m = map(int, input().split("/"))
        result = ["1/%s"%m for i in range(z)]
        print("+".join(result))
    except: break

发表于 2023-10-17 14:31:24 回复(3)

Python3

1bit都不剩了

def getRealFraction(ori_fra):
    num1,num2 = list(map(int,ori_fra.split("/")))
    basic_fraction = "1/" + str(num2)
    real_fractions = ""
    for i in range(num1): real_fractions += basic_fraction+"+"
    return real_fractions.strip("+")

while(True):
    try:
        print(getRealFraction(input()))
    except:
        break

发表于 2023-07-28 15:55:44 回复(1)

Python3

牛客487687812号

挨个遍历，碰到比x小的就减掉，直到x==0

from typing import List

# x = list(map(int, input().split("/")))

def gcd(x, y):

    if x > y:

        x, y = y, x

    while y:

        x, y = y, x % y

    return x

def lcm(x, y):

    return x * y // gcd(x, y)

def sub_fraction(x: List[int], y: List[int]):

    denomi = lcm(x[1], y[1])

    x[0] = denomi / x[1] * x[0]

    y[0] = denomi / y[1] * y[0]

    ans = [0, 0]

    ans[0] = x[0] - y[0]

    ans[1] = denomi

    if ans[1]!=0 and ans[0]!=0 and ans[1] % ans[0] == 0:

        ans[1] = ans[1] // ans[0]

        ans[0] = 1

    return ans

def cmp(x: List[int], y: List[int]):

    tmp = x[0] / x[1] * 1.0 - y[0] / y[1] * 1.0

    if tmp > 0:

        return 1

    elif tmp == 0:

        return 0

    else:

        return -1

def f(x: List[int]):

    if x[1] % x[0] == 0:

        print(f"1/{x[1] // x[0]}")

        return

    i = 1

    # while cmp([1, i], x) > 0:

    #     i += 1

    while x[1] != 0 and x[0] / x[1]:

        while cmp([1, i], x) > 0:

            i += 1

        print(f"1/{i}", end="")

        x = sub_fraction(x, [1, i])

        if x[0] == 1:

            print(f"+{int(x[0])}/{int(x[1])}")

            return

        if x[1] != 0 and x[0] / x[1]:

            print("+", end="")

if __name__ == '__main__':

    x = list(map(int, input().split("/")))

    f(x)

发表于 2023-07-21 13:00:08 回复(0)

Python3

AlfredP

import sys

for line in sys.stdin:
    a = line.strip().split('/')
    res='1/'+a[1]+'+'
    res*=int(a[0])
    print(res.strip('+'))

发表于 2023-05-04 14:18:37 回复(1)

Python3

再多看一眼就会爆炸

大佬们，为什么这个不行

while True:
    try:
        n=input()
        s=list(map(int,n.split('/')))
        c=[]
        for i in range(0,s[0]):
            c.append('1/'+str(s[1]))
        print('+'.join(c))
    except:
        break

发表于 2023-03-11 18:16:49 回复(1)

Python3

在做的机考肯定是必过呀

#思路参考斐波那契拆解法
def chaifen(a,b):
    if a == 1:
        l.append(b)
        return
    elif b%a == 0:
        l.append(b//a)
        return
    while a>1:
        d = b//a + 1
        l.append(d)
        return chaifen(a*d-b,b*d)
a,b = map(int,input().split('/'))
l = []
chaifen(a,b)
for i in l:
    print('1'+'/'+str(i),end='')
    if i!=l[-1]:
        print('+',end='')

发表于 2023-02-26 13:56:19 回复(0)

Python3

ssssuperstone

首先约分，如果直接就是1/b那就直接输出，否则开始拆解。思路参考斐波那契拆解法，即对于一个最简真分数a/b，首先把它拆成离它最近的一个埃及分数与另一个真分数的和，这个离它最近的埃及分数可以用带余除法求得，即c=b//a, r=b%a, b=a*c+r, 令d=c+1, 那么 $\frac a b=\frac {a×d-b}{b×d}+\frac{b}{b×d}=\frac{1}{d}+\frac {a×d-b}{b×d}$

1/d就是那个要找的埃及分数，后面的部分约分后成为需要拆解的另一个真分数，可以预见经过有限次迭代可以将a/b完全拆解

def gcd(a:int,b:int):
    while True:
        tmp=a%b
        if tmp==0:
            break
        else:
            a,b=b,tmp
    return(b)

while True:
    try:
        a,b=map(int,input().strip().split('/'))
        if gcd(b,a)==1:
            pass
        else:
            tmp=gcd(b,a)
            a=a//tmp
            b=b//tmp
            
        if a==1:
            print(str(a)+'/'+str(b))
        else:
            l=[]
            while True:
                shang=b//a
                l.append(str(shang+1))
                a=a*(shang+1)-b
                b=b*(shang+1)
                tmp=gcd(b,a)
                a=a//tmp
                b=b//tmp
                if a==1:
                    l.append(str(b))
                    break
            s='+1/'.join(l)
            s='1/'+s
            print(s)
    except:
        break

发表于 2023-02-17 14:33:00 回复(1)

Python3

yorusimo

整数带余除法+迭代

while True:
    try:     
        # x=py+q
        y,x=map(int,input().split('/'))
        L=[]
        while y!=1:
            p,q=x//y,x%y
            tmp='1/%d' %(p+1)
            L.append(tmp)
            if x*(p+1)%(y-q)==0:
                tmp='%d/%d' %(1,x*(p+1)//(y-q))
                L.append(tmp)
                break
            x=x*(p+1)
            y=y-q
        print(L)
    except:
        break

发表于 2023-02-07 22:30:31 回复(0)

Python3

机灵的哈里在吵架

# 贪婪算法

# a / b = 1 / (b // a + 1) + (a/b - 1/(b // a + 1));递归直至a/b - 1/(b//a + 1)所得分数分子等于1跳出

# Fractionk可以直接返回分数加减法结果

from typing import List

import sys

from fractions import Fraction

class Solution:

def __init__(self) -> None:

self.res = ''

def dfs(self, string: str):

nums: List[int] = list(map(int, string.split('/')))

# a/b = 1/(a + (b-a)) + (a/b - 1/(a + (b-a)))

a = nums[0]

b = nums[1]

p = b // a

tmp = f'{1}/{p + 1}'

ns = str(Fraction(a, b) - Fraction(1, (p+1)))

ns_list: List[int] = list(map(int, ns.split('/')))

if not self.res:

self.res = tmp

else:

self.res += '+' + tmp

if ns_list[0] == 1:

self.res += '+' + ns

return

return self.dfs(ns)

for line in sys.stdin:

line = line.strip()

s = Solution()

s.dfs(line)

print(s.res)

发表于 2023-01-23 15:37:09 回复(0)

Python3

想去东北泡澡的共享单车人求你们别卷了

# 根据楼下思路写的 真清奇啊
while 1:
    try:
        a,b = input().split('/')
        tmp = '1/' + b
        ans = [tmp for i in range(int(a))]
        print('+'.join(ans))
    except:
        break

发表于 2022-12-18 11:15:06 回复(2)

Python3

牛客387136519号

全部通过

while True:
    try:
        def gcd(a, b):
            return b if not a%b else gcd(b, a%b)

        A, B = map(int, input().split('/'))
        g = gcd(A,B)
        if g>1:
            A /= g
            B /= g
        while A>1:
            C = B//A
            D = B%A
            A = A*C+A-B
            B = B*C+B
            g = gcd(A,B)
            if g>1:
                A /= g
                B /= g
            print(f"1/{int(C+1)}",end='+')
        print(f"1/{int(B)}")
    except:
        break

发表于 2022-07-25 19:14:13 回复(0)

提交观点

问题信息

搜索基础数学

难度：

27条回答 2147收藏 32824浏览

通过挑战的用户

查看代码

牛客54309...

2023-02-11 11:25:02
帅阿衰

2023-01-08 09:56:54
牛客23072...

2022-11-29 17:22:14
水星初代摸鱼大师

2022-09-29 21:18:02
牛客63891...

2022-09-23 18:50:27

将真分数分解为埃及分数

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题