算法第一题:python实现剪绳子

算法第一题:python实现剪绳子,第1张

1 题目描述: 2 思路:

不管是哪种语言,思路才是最重要的。分析:

2.1 一个绳子剪的各部分长度乘积要最大,那么尽可能要染个这几个数字接近(数学知识,或许你可以想到均值不等式吧)。 2.2 通过所给的案例我们可以发现,最长的部分就是对该绳子长度开根号并+1 2.3 既然最长部分出来了,那么对剩下的绳子长度我们又可以看作一根新的绳子 2.4 因此,我们想到了用递归:

递归三部曲是什么呢?

(1)递推关系:每个新绳子的最长部分*F(减去最长部分后剩下绳子的长度)

(2)递归结束条件:如果把绳子剪了的乘积还没不剪的长度(1*绳长)长,那么就不继续剪了呗,就相当于递归中的递结束了呗。但是,你仔细想想,这里的情况是指绳子的长度不是2或者3的时候,因为2或者3时要满足必须剪一刀,那么结果就是:1和2,因此和上面矛盾了,该怎么解决呢?(同时经过验证,当长度>3时,最终要剪的那部分长度都是剪2+2,或者2+3,在这里不可能简单再把2,3来剪使得乘积变小)因此,我们必须把最开始绳子就是长2或3的单独来说。

(3)在(2)中提到,如何区分两种情况的2,3;再想,长度大于3的绳子,它还有其他(除了2,3)的已经剪掉的部分,于是我们在传参数这里就可以传一个剪绳子最长的部分(显然是第一次剪)

3 代码实现:
#剪绳子,这里用递归实现
import math
def cut(m,max):
    #cut_max指每次新绳子所剪掉的最长部分,cut_rest是剩余部分
    cut_max=int(math.sqrt(m))+1
    cut_rest=m-cut_max
    sum=cut_rest*cut_max
    if m==2 and x==2:#绳子本来就长2
        return 1
    if m==3 and x==2: #绳子本来就长3
        return 2
    elif(sum<=m): #绳长>3时的递归结束条件
        return m
    else:
        return cut_max*cut(cut_rest,max) #x没变,表示普通绳子的最长部分,作用就是与长度为本身绳长为2,3的区分
n=int(input("请输入绳子长度:"))
x = int(math.sqrt(n)) + 1
print(cut(n,x))

总结:首先用递归解题,如果你是新手你必须把这个过程弄清楚,先递完再回归;如果你很熟悉,那么你直接从递归三部曲:终止条件、递推关系式、 确定参数

而对于该题,不同于往常的递归就是,绳子一开始的长度是2,3时和绳子大于3时,结束条件2,3的情况是不一样的。(最后,谢谢观看,新手刷题跟着我,一起进步哇,顺便点个赞加个关注哇!)

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/786423.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-05
下一篇 2022-05-05

发表评论

登录后才能评论

评论列表(0条)

保存