首页 > 试题广场 >

将真分数分解为埃及分数

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

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

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

算法知识视频讲解

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

牛客119394272号

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 回复(0)

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)

Python3

正在学习的小李

while True:
    try:
        a,b = map(int,input().split('/'))
        a,b = a * 10, b * 10
        res = []
        while a:
            for i in range(a,0,-1):
                if(b % i == 0):
                    res.append( f'1/{str(int(b/i))}' )
                    a = a - i
                    break                    
        print('+'.join(res))
    except:
        break

发表于 2022-06-03 16:42:11 回复(0)

Python3

林子1984

while True:
try:
res = []
a,b = map(int, input().split('/'))
while b%a != 0:
c = b//a+1
res.append('1/'+str(c))
a = a*c-b
b = b*c
res.append('1/'+str(b//a))
print("+".join(res))
except:
break

发表于 2022-04-22 22:40:28 回复(0)

Python3

牛客947768359号

while True:
    try:
        fs = [int(s) for s in input().split('/')]
        fj = []
        while fs[0]!=1:
            temp = [1,0]
            temp[1] = fs[1]//fs[0]+1
            fs[0] = fs[0]*temp[1]-fs[1]
            fs[1] = temp[1]*fs[1]
            if fs[1]%fs[0] == 0:
                fs[0],fs[1] = 1, fs[1]//fs[0]
            fj += [temp]
        fj += [fs]
        print('+'.join(['1/'+str(i[1]) for i in fj]))
    except:
        break

发表于 2022-04-07 12:54:09 回复(0)

Python3

天才哈哈哈哈

看讨论里面大佬的思路，简直不要太强

while True:
    try:
        a,b = list(input().split("/"))
        tmp = "1/"+b
        res = [tmp]*int(a)
        print("+".join(res))
    except:
        break

发表于 2022-01-20 16:26:18 回复(3)

Python3