用 Python 通过动态规划完成公务员考试题

阅读本文大概需要 3 分钟。


今天在脉脉上看到有人发了一道公务员的考试题,题目如下:


用 Python 通过动态规划完成公务员考试题


这道题可以用数学方法来做,但我离开学校很多年了,想不出数学的解法。不过看到题目的一瞬间,我就想到了可以使用动态规划来解决这个问题。

我们把“家”的位置标记为(0, 0),把单位的位置标记为(4, 3),如下图所示:


用 Python 通过动态规划完成公务员考试题


动态规划的一个典型解法,就是想问题的时候,倒着想。假设现在我已经在单位(4, 3)了。我上一步是在哪里?要到(4, 3),只有两种方法,从(3, 3)到(4, 3)或者从(4, 2)到(4, 3)。现在问题的规模缩小了,变成了两个小问题,一个是从家(0, 0)到(4, 2)有多少种走法,另一个是从家(0, 0)到(3, 3)有多少种走法。

到这里,我们看出来这实际上是一个递归问题,也就是fn(x, y) = f(x - 1, y) + f(x, y - 1)

不过,这里要考虑另一个问题,就是当我们在fn(x, 0)或者fn(0, y)的时候。如果 x > 1,那么此时只有一种走法,就是从(x-1, 0)到 (x, 0)。如果x == 1,那么此时只能是从(0, 0)(1, 0)。同理,对于(0, y)也是一样,如果y > 1,那么只能从(0, y - 1)(0, y)。如果y == 1,那么只能是从(0, 0)(0, 1)

于是,根据这个思路,我们可以写出如下的代码:

def find_walk_num(x, y):
    if y == 0:
        if x == 1:
            return 1
        return find_walk_num(x - 10)
    if x == 0:
        if y == 1:
            return 1
        return find_walk_num(0, y - 1)
    return find_walk_num(x - 1, y) + find_walk_num(x, y - 1)

result = find_walk_num(43)
print(f'从(0, 0)到(4, 3)的走法一共有:{result}种')

运行效果如下图所示:


用 Python 通过动态规划完成公务员考试题


所以这道题的答案就是 D,一共有35种走法。


(大概这一道题写完,计时已经过去了)

用 Python 通过动态规划完成公务员考试题

推荐阅读

1

原创丨带你体验一下云上编码的感觉

2

强势回归!比 Python 快 20% 的 Pyston v2.0 来了!

3

还记得那个「最牛删库跑路事件」的程序员吗?他被判了....

4

用 Python 庆祝拜登当选的十种方式




崔庆才

静觅博客博主,《Python3网络爬虫开发实战》作者

隐形字

个人公众号:进击的Coder

用 Python 通过动态规划完成公务员考试题
用 Python 通过动态规划完成公务员考试题
用 Python 通过动态规划完成公务员考试题

长按识别二维码关注




好文和朋友一起看~

原文始发于微信公众号(进击的Coder):用 Python 通过动态规划完成公务员考试题

链接:https://bbbe.top/archives/4727.html
来源:随风的博客
文章版权归作者所有,未经允许请勿转载。
本网站使用者因为违反本声明的规定而触犯中华人民共和国法律的,一切后果自己负责,本网站不承担任何责任。
本声明未涉及的问题参见国家有关法律法规,当本声明与国家法律法规冲突时,以国家法律法规为准。
本文仅供学习参考,请勿用于违法用途。 若根据文章内容操作遭受任何损失,请自行承担责任。
THE END
分享
二维码
打赏
< <上一篇
下一篇>>