吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 1083|回复: 7
收起左侧

[Python] 动态规划: 上楼梯

[复制链接]
TES286 发表于 2021-11-6 01:17
本帖最后由 TES286 于 2021-11-6 11:43 编辑

有这样一个问题

有一个人要上楼梯, 每次可以上一个或两个楼梯, 求当有x级阶梯时有多少种上法

1.png

我们可以知道当x的值很小时的答案:

f(1) = 1

f(2) = 2

而后面的推到如下

2.png

也就是

f(x) = f(x-1) + f(x-2)

每次都会调用到自身, 这是一个递归

可以构建以下代码

def a(n):
  if n == 1:
    return 1
  elif n == 2:
    return 2
  else:
    return a(n-1) + a(n-2)

这个方法可以解决, 但较为耗时, 例如这里入参35, 总共整了2秒多, 到了40, 直接飙到26秒

3.png 4.png

那么它就要优化

我们以入参为5是看看

f(5) = f(4) + f(3) = f(3) + f(2) + f(2) + f(1) = f(2) + f(1) + f(2) + f(2) + f(1) = 3 f(2) + 2 f(1)

可见, 在入参为5时, f(2) 运行3次, f(1) 运行一次

那么, 在很高的入参下, 有很多次重复计算

那么这些重复的运算可以省掉吗?

可以, 代码如下

def b(n, *, l=dict()):
  # 因为dict是可变对象,在定义时初始化的一个dict()不会随着函数的运行结束而丢失
  if n == 1:
    return 1
  elif n == 2:
    return 2
  else:
    if n in l:
      return l[n]
    else:
      r = b(n-1) + b(n-2)
      l[n] = r
      return r

经过测试, 40次运算时间在0.003s左右

5.png

经过优化后, 时间基本稳在0.01s之下

6.png 7.png

代码:

import time
def a(n):
  if n == 1:
    return 1
  elif n == 2:
    return 2
  else:
    return a(n-1) + a(n-2)

def b(n, *, l=dict()):
  if n == 1:
    return 1
  elif n == 2:
    return 2
  else:
    if n in l:
      return l[n]
    else:
      r = b(n-1) + b(n-2)
      l[n] = r
      return r

if __name__ == '__main__':
    #func = a
    func = b
    #x = 300
    x = int(input('times:'))
    t1=time.time()
    print(func(x))
    t2=time.time()
    print(t2-t1)

免费评分

参与人数 3吾爱币 +7 热心值 +3 收起 理由
苏紫方璇 + 7 + 1 欢迎分析讨论交流,吾爱破解论坛有你更精彩!
sam喵喵 + 1 用心讨论,共获提升!
yukun451 + 1 用心讨论,共获提升!

查看全部评分

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

平淡最真 发表于 2021-11-6 03:43
能打败数学的只有数学了,
[Python] 纯文本查看 复制代码
def c(x,y,z,n):
    return (y**(n+1)-z**(n+1))/x
if __name__ == '__main__':
    x=5**0.5
    y=0.5+x/2
    z=0.5-x/2
    aa= int(input('times:'))
    t1=time.time()
    print(int(c(x,y,z,aa)))
    t2=time.time()
    print(t2-t1)
平淡最真 发表于 2021-11-6 03:45
时间是够快,但是结果可能不准,毕竟纯浮点数运算
魔术使nqy 发表于 2021-11-6 07:28
动态规划,明白原理,但到自己写就不知道怎么做了
mokson 发表于 2021-11-6 08:13
如果跨一级走了几步,接着跨二级走了几步,如何算?
QingYi. 发表于 2021-11-6 09:16
斐波那契数列
sam喵喵 发表于 2021-11-6 09:28
感谢分享,确实快
trieszhang 发表于 2021-11-6 11:05
崇拜数学大神
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则 警告:本版块禁止灌水或回复与主题无关内容,违者重罚!

快速回复 收藏帖子 返回列表 搜索

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2022-9-25 03:25

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表