首页 > 试题广场 >

将真分数分解为埃及分数

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

热度指数：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也是可以的

算法知识视频讲解

Python

柚子巴巴

3/4 = 1/4+1/4+1/4，这特么是符合的，我笑死了

发表于 2022-02-27 22:40:24 回复(0)

Python

Rick814

while True:
    try:
        num, den = map(int, input().split('/'))
        print(('1/'+str(den)+'+')*(num-1)+('1/'+str(den)))
    except:
        break

所以，不要想太多

发表于 2021-04-11 20:53:15 回复(3)

Python

牛客659977316号

一开始直接写得穷举过了,擦着时间限的边过了,后来想不到太好的办法优化,看题解意识到这玩意是个数学问题

斐波那契算法?什么鬼东西,这个式子什么意思,证明出来直接背是吗?我这个人最讨厌背东西了

好,我自己证明一波

设a,b为互质正整数,且a<b

从斐波那契算法那边我借鉴出一个东西,b=a*p + r (p, r均为整数)

我们的目标是构建方程a / b = 1/x + y (x为整数, y是啥不重要,也是正的真分数就行)

好了,我们把b = a*p+r带入方程a/b = a / (a*p+r),看到这个式子,我本能的想用a/a*p去减这个式子因为1/p是个埃及分数

1/ p - a / (a*p+r) = a/(a*p) - a/(a*p+r)

= a * (a*p+r) / (a*p*(a*p+r)) - a*a*p/(a*p*(a*p+r))

= a*[(a*p+r) - a*p] / (a*p*(a*p+r))

= r / (p*(a*p+r))

好了我们得到一坨式子 A - B = C,我们交换一下编程B=A-C, 即

a/(a*p+r) = 1/p - r / (p*(a*p+r))

好了我们的我们的目标出来了然后穷举找到p(a*p >b && a*(p-1)<b),然后带入

a/b = 1/p - r / (p*(a*p+r)) 然后得出y然后再拿y重复这一过程直到r=1

发表于 2021-03-13 23:23:33 回复(0)

Python

chenjc23

from fractions import Fraction
from math import ceil
while True:
try:
n = Fraction(input())
result = []
while n != 0:
num,den = n.numerator, n.denominator
new = Fraction(1,ceil(den/num))
n -= new
result.append(str(new))
print('+'.join(result))
except:break

发表于 2021-03-08 20:21:01 回复(0)

Python

bancaolanmu

while True:
    try:
        a,b = map(int,input().split('/'))
        l =[]

        while a != 1:
            m,n = b//a,b%a
            if n==0:
                x=b/a
                l.append('1/'+'%.0f'%x)
                break
            else:
                l.append('1/'+str(m+1))
            a -= n
            b *= (m+1)
        if a ==1:
            l.append('1/'+str(b))
        
        te = ''
        for i in range(1,len(l)):
            te += ('+' + l[i])
        te = l[0] + te
        print(te)
    except: break

根据网上的埃及分数分解法写的，但是完全不符合答案，头秃

发表于 2020-12-24 07:40:02 回复(0)

Python

大溪地渔民

代码能够通过，但是用 2/4 自测的时候得出的结果是 1/4+1/4

while True:
    try:
        a, b = map(int, input().split("/"))
        output = ""
        while a-1:
            if not b%(a-1):
                output += "1/{}+".format(b//(a-1))
                a = 1
            else:
                c = b//a+1
                output += "1/{}+".format(c)
                a, b = a-b%a, b*(c)
                if not b%a:
                    a, b = 1, b//a
        output += "1/{}".format(b)
        print(output)
    except:
        break

发表于 2020-12-18 16:41:26 回复(1)

Python

whynotyeaaah

提供一下我的Python版本，通过率100%，利用了Fraction库，思路看代码就能懂：

from fractions import Fraction

while True:
    try:
        org = Fraction(input())
        sam = Fraction(0)
        i = org.denominator // org.numerator
        cont = []
        while sam < org:
            if sam + Fraction(1, i) <= org:
                cont.append(i)
                sam += Fraction(1, i)
                dif = org - sam
                if dif == 0:
                    break
                i = dif.denominator // dif.numerator
            else:
                i += 1
        print('1/' + '+1/'.join(str(i) for i in cont))
    except:
        break

发表于 2020-10-25 20:13:25 回复(0)

Python

混分兽

不涉及数学知识，只有朴素的搜索：

possible_combination=[]
find_flag=False
def find_combination(prefix,remain,target):
    global possible_combination
    global find_flag
    if find_flag:
        return
    if sum(prefix)==target:
        possible_combination.append(prefix[:])
        find_flag=True
        return
    if remain==[]:
        return
    if sum(prefix)>target:
        return
    if not find_flag:
        find_combination(prefix, remain[1:], target)
    if not find_flag:
        find_combination(prefix[:]+[remain[0]], remain[1:], target)
    return

def find_yueshu(number):
    pre_factor=[]
    post_factor=[]
    for i in range(1,int(number**0.5)+1):
        if number%i==0:
            pre_factor.append(i)
            post_factor.append(number//i)
    if number**0.5==int(number**0.5):
        pre_factor=pre_factor[:-1]
    post_factor=post_factor[::-1]
    return pre_factor+post_factor
while True:
    try:
        raw_string=input()   
        string=raw_string.split('/')
        fenzi=int(string[0])
        fenmu=int(string[1])
        if fenzi==1:
            print(raw_string)
        factor=2
        while True:
            possible_combination=[]
            find_flag=False
            big_fenmu=fenmu*factor
            all_yueshu=find_yueshu(big_fenmu)
            big_fenzi=fenzi*factor
            find_combination([],all_yueshu,big_fenzi)
            if find_flag:
                all_res_fenzi=possible_combination[0]
                res_output=[]
                for sub_fenzi in all_res_fenzi:
                    res_output.append('1/'+str(big_fenmu//sub_fenzi))
                print('+'.join(res_output))
                break
            else:
                factor+=1
    except:
        break

发表于 2020-09-18 21:02:21 回复(0)

Python

kite97

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

编辑于 2020-09-03 16:46:12 回复(4)

Python

天涯亮

看了大佬们的评论才知道菲波那契分解方法，真的很高效。

一开始因为不知道这种方法，我想出了另一种方法：

我首先将

8/11=1/2+1/5+1/55+1/110
右边以最大分母进行通分得到 8/11=55/110+22/110+2/110+1/110
这里等式右边的分子55、22、2、1都是110的因子，然后我就想到：将真分数化为埃及分数，可以将分子转换为分母不重复的因子的和，通过这些因子再转换为埃及分数
这里有一个问题比如8/11，11的因子只有1（不考虑本身），不能找到不重复的因子和为8，所以找不到时我就将真分数进行变形，分子分母同时乘以10的整数倍
代码如下：
# 找到m除自己以外的所有因子
def find_divisors(m):
    divisors = []
    for i in range(1, m):
        if m % i == 0:
            divisors.append(i)
    return divisors

# 找到将该分数分解为埃及分数的因子
def find(n, m, divisors, new_divisors):
    if n == 0:  # 分子变为0时，成功
        return True
    for i in divisors[::-1]:        # 从m最大的因子开始查找
        if n == 0:  # 可以得到埃及分数
            return True
        if i <= n:         # 若i小于分子n,则将i添加进new_divisors，同时在divisor中移除i
            n -= i
            new_divisors.append(i)
            if i in divisors:
                divisors.remove(i)
            if find(n, m, divisors, new_divisors):    # 移除i后判断下一步是否正确，若不正确则证明i不是要找的因子，须回溯
                return True
            n += i
            new_divisors.pop(-1)
        else:
            divisors.remove(i)

    return False


while True:
    try:
        n, m = map(int, input().split('/'))
        new_divisors = []        # 存储能将该分数分解为埃及分数的因子
        divisors = find_divisors(m)       # 得到分母除本身之外的所有因子
        flag = 1
        while not find(n, m, divisors, new_divisors):    # 若当前真分数无法划分，则扩大10的整数倍再进行查找
            n = n * flag * 10
            m = m * flag * 10
            flag += 1
            new_divisors = []
            divisors = find_divisors(m)
        # 输出分解后的埃及分数序列
        s = ""
        for j in range(len(new_divisors)):
            if j != len(new_divisors)-1:
                s += "1" + "/" + str(m // new_divisors[j])+"+"
            else:
                s += "1" + "/" + str(m // new_divisors[j])
        print(s)
    except:
        break

发表于 2020-09-01 18:18:14 回复(0)

Python

牛客904525060号

巨坑，不支持 str.format()格式化字符串。

思路 a/b 拆分成 1/i +?

推导？=a/b - 1/i

?=(a*i-b)/(bi)

问题就在于i的取值了，i = (b//a)+1

https://blog.csdn.net/zyz_bz/article/details/89515096 参考

while 1:
try:
fenzi,fenmu = [int(x) for x in input().split('/')]
result = ""
while fenzi > 1:
i = int(fenmu / fenzi) + 1
c = fenmu
fenzi = fenzi* i
fenmu = fenmu *i
if fenzi > c:
fenzi -= c
result += "+1/%d"%i
if fenmu % fenzi == 0:
result += "+1/%d"%(fenmu / fenzi)
break
if fenmu % (fenzi - 1) == 0:
result += "+1/%d"%(fenmu/(fenzi-1))
result += "+1/%d"%fenmu
break

print(result.replace("+", "", 1))
except:
break

发表于 2020-08-26 19:03:34 回复(0)

Python

ShadowAnt_TC

def gys(a, b):
    a,b = (a,b) if a>b else(b,a)
    a = a%b
    if a==0:
        return b
    return gys(b, a)

def fenjie(fenzi, fenmu, ans):
    #tongfen
    maxgongyueshu = gys(fenzi, fenmu)
    fenzi //= maxgongyueshu
    fenmu //= maxgongyueshu
    if fenzi==1:
        ans.append(fenmu)
        return
    if fenmu%(fenzi-1)==0:
        ans.append(fenmu//(fenzi-1))
        ans.append(fenmu)
        return 0
    shang = fenmu//fenzi
    ans.append(shang+1)
    newfenmu = fenmu*(shang+1)
    newfenzi = fenzi*(shang+1)-fenmu
    fenjie(newfenzi, newfenmu, ans)
    
    
while True:
    try:
        fenshu = list(map(int, input()))
        fenzi, fenmu = fenshu[0], fenshu[1]
        ans = []
        fenjie(fenzi, fenmu, ans)
    except:
        break

递归求解，收到分子分母后，先通分，方法是分子分母同时除以最大公约数。

接着尝试把当前的分数分成1/分母+1/（分母//分子），如果不能简化，那么就用基础方法。

分数拆成1/（分母/分子+1）+新分数，递归求新分数，同时把（分母/分子+1)存起来。

发表于 2020-08-18 20:54:09 回复(0)

Python

牛客156646723号

运行时间：19ms

占用内存：3460k

while True:
    try:
        a,b = [int(i) for i in input().split('/')]
        n = 1
        c = []
        while n <= 100:
            p = b // a
            r = b % a
            a = a - r
            b = b * (p+1)
            if b % (a-1) == 0:
                c.append(p+1)
                c.append(int(b/(a-1)))
                c.append(b)
                break
            else:
                if a == 1:
                    c.append(p+1)
                    c.append(b)
                    break
                elif b % a == 0:
                    c.append(p+1)
                    c.append(int(b/a))
                    break
                else:
                    c.append(p+1)
                    n += 1
        print('1/',end = '')
        print(c[0],end = '')
        for j in range(1,len(c)):
            print('+1/',end = '')
            print(c[j],end = '')
        print(end = '\n')
    except:
        break

编辑于 2020-07-22 10:32:04 回复(0)

Python

君临天下201804050931706

while True:
    try:
        a, b = map(int, input().split("/"))
        result = []
        while True:
            c = b//a + 1
            result.append("1/" + str(c))
            a = a-b%a
            b = b*c
            if(a==1):
                result.append("1/" + str(b))
                break
            elif(a>1 and b%a==0):
                result.append("1/" + str(b//a))
                break

        print('+'.join(result))
    except:
        break

发表于 2020-07-11 16:37:49 回复(0)

Python

DarryYoung

from math import ceil
from fractions import Fraction

while True:
    try:
        x, y = map(int, input().split('/'))
        res = Fraction(x, y)
        sub = []
        while res.numerator != 1:
            arab = ceil(res.denominator/res.numerator)
            sub.append('1/'+str(arab))
            res = res - Fraction(1, arab)
        sub.append('1/'+str(res.denominator))
        print('+'.join(sub))
    except:
        break

发表于 2020-06-24 11:22:18 回复(0)

Python

心怀高远，脚踏实地

def Egypt(instr):
    out = ''
    if instr=='1':
        out = '1'
        return out
    a, b = tuple(map(int,instr.split('/')))
    c    = 0
    while a != 1:
        if b % (a - 1) == 0:
            out += '1/{0}+'.format(str(b//(a-1))) 
            a = 1
        else:
            q, r = b//a, b%a
            out  += '1/{0}+'.format(str(q+1))
            c    = a -r
            a, b = c, b*(q+1)
            if b%a == 0:
                b = b//a
                a = 1
    out += '1/{0}'.format(str(b))
    return out

while 1:
    try:
        instr1 = input()
        print(Egypt(instr1))
    except:
        break

参考的讨论区大佬的算法

发表于 2020-06-01 21:40:39 回复(0)

Python

silent_water

while True:
    try:
        num = input().split('/')
        a = int(num[0])  #a是分子，b是分母
        b = int(num[1])
        c = 0
        temp = ''  #定义空的字符串，等会存储计算结果
        while(a>=1):
            if b % (a-1) == 0:
                temp = '1/'+ str(b//(a-1))+'+'+'1/'+str(b)
                print(temp)
                break
            else:
                c = (b//a) + 1
                temp = '1/'+str(c)+'+'
                print(temp,end="")
                a = a*c - b
                b = b*c
                if b % a == 0:
                    b = b // a
                    a = 1
                    temp = str(a) + '/' + str(b)
                    print(temp)
                    break
    except:
        break

主要是搞清楚算法部分：
①如果b能够整除（a-1），那么就可以直接分解，在第一个if里面
②如果不能整除，那就一步一步迭代，（b/a）+1，作为新的分母，分子为1，记得将原来的分数更新一下
③分母直接能整除分子的，不知道为什么不能直接约分，直接约分代码通过80%，所以就放在else里面的if里面。
新手菜鸟，说错的欢迎批评

发表于 2019-11-23 20:59:22 回复(2)