题解 | #将真分数分解为埃及分数#

将真分数分解为埃及分数

http://www.nowcoder.com/practice/e0480b2c6aa24bfba0935ffcca3ccb7b

#解题思路:将真分数(a/b)拆分成a*(1/b),也就是a个1/b,然后我们从大到小依次找出a中能被B整除的数.
比如: 5/8 这个真分数首先我们看,5不能被8整除,但是4可以,那从5中把4分离出来,变成1+4,剩余的1不能拆分,那埃及分数就是1/8+1/2

再比如:7/8这个真分数,首先我们看,7不能被8整除,6不能被8整除,5不能被8整除,4可以整除,分子分离出4,还剩3,我们看3不能整除,2能整除,分离出2,还剩1, 埃及分数:1/8+1/4+1/2
翻译成以下代码:

import sys

for fs in sys.stdin.readlines():
    
    fzfm =fs.strip("\n").split("/")
    fz = int(fzfm[0])
    fm = int(fzfm[1])
    out_string = "" 
    num = fz
    zy = num
    contt = 0
    while True:
        try:
            if fm % zy == 0:
                if contt == 0:
                    out_string += ("1/" + str(fm // zy))
                else:
                    out_string += ("+1/" + str(fm // zy))
                    
                fz = fz - zy
                contt +=1
                zy = fz
                if fz == 0:
                    print(out_string)
                    break
                
            else:
                zy -= 1
                if zy == 0:
                    break
            
        except Exception:
            pass
    

全部评论
只适用分母为合数的情况,质数就不行了
1 回复 分享
发布于 2022-03-10 10:02
分母是质数的话就变成了1+1+1+1
1 回复 分享
发布于 2022-10-21 14:16 浙江
function sol(a:string,res:string[]):string[]{ let [up, down] = a.split('/').map(it => +it); if(up === 0) return res; if(up === 1) { res.push(a); return res } let i:number; for(i = up; i > 1; i--){ if(down % i === 0){ res.push(`1/${down/i}`); return sol(`${up - i}/${down}`, res) } } if(i === 1){ up *= 10; down *= 10; return sol(`${up}/${down}`, res) } } 根据这个思路写了js版本的
点赞 回复 分享
发布于 2023-02-02 15:38 湖北
对于a/b应该先变为x/lcm(a,b),再执行这个算法就可以了
点赞 回复 分享
发布于 2022-08-31 16:46 北京
要求结果递减,2/3,8/11这样就不行了。
点赞 回复 分享
发布于 2022-07-02 10:25
那例子里的8/11怎么解释?
点赞 回复 分享
发布于 2022-03-05 12:45
这样4/31没有可以整除的,答案是1/8+1/248
点赞 回复 分享
发布于 2022-01-29 17:50

相关推荐

昨天 13:48
门头沟学院 C++
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利 有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的 真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
面试尴尬现场
点赞 评论 收藏
分享
MinJerous:虽然我一直说 计算机不怎么卡学历 但是至少得一本
点赞 评论 收藏
分享
07-07 10:44
青岛工学院 Java
机械打工仔:对方没做错任何事,你自己在这自找没趣呢,就算他工资不高,人家定多少薪资是人家的事,况且人家写了1~3年清清楚楚
点赞 评论 收藏
分享
评论
37
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务