本周的题目非常有意思,取于大名鼎鼎的 囚徒困境 。首先来看背景资料:
“囚徒困境”是1950年美国兰德公司的梅里尔·弗勒德(Merrill Flood)和梅尔文·德雷希尔(Melvin Dresher)拟定出相关困境的理论,后来由顾问艾伯特·塔克(Albert Tucker)以囚徒方式阐述,并命名为“囚徒困境”。两个共谋犯罪的人被关入监狱,不能互相沟通情况。如果两个人都不揭发对方,则由于证据不确定,每个人都坐牢一年;若一人揭发,而另一人沉默,则揭发者因为立功而立即获释,沉默者因不合作而入狱五年;若互相揭发,则因证据确实,二者都判刑两年。
知乎话题-囚徒困境:
https://www.zhihu.com/topic/19597612/top-answers
今天我们要挖的坑是多重囚徒困境,求进行 N 次博弈下,使用不同的策略,囚犯各自的获刑年限。
目前有三种策略:
- nice:不管对方揭发还是沉默,都保持沉默
- rat:不管对方沉默还是揭发,都选择揭发
- tit_for_tat:第一轮选择沉默,第二轮开始如果对方上一轮沉默,本轮就选择沉默,对方上一轮揭发,本轮也选择揭发。
举例,甲方选择 tit_for_tat 策略,乙方选择 rat 策略,共进行四轮
现在,由你来构造一个函数,输出囚犯获刑结果。
def prisoner_delimma(N, strategy1, strategy2): # 你的代码
输出示例
>>> prisoner_delimma(4, nice, nice) (4, 4) >>> prisoner_delimma(5, rat, rat) (10, 10) >>> prisoner_delimma(6, nice, rat) (30, 0) >>> prisoner_delimma(4, rat, tit_for_tat) (6, 11) >>> prisoner_delimma(7, tit_for_tat, tit_for_tat) (7, 7)
附加题:
自定义一种策略,测试在此策略下的效果。如果你对自己的策略有自信,还可以试着和其他人提交的策略进行比拼。
欢迎各位同学踊跃提交,另外如果有一些有趣的题目希望拿出来讨论,欢迎分享到评论区,说不定就出现在下期【每周一坑】栏目中。
提交代码可以使用 paste.ubuntu.com 或 codeshare.io 等代码分享网站,只需将代码复制上去保存,即可获得一个分享地址,非常方便。
往期问题可通过公众号菜单栏“课外辅导”栏目中进入查看。
上期 选择困难的农药召唤师 解答:
Python 为我们提供了一个方便的 itertools 模块,使用其中的 combinations_with_replacement 函数可以轻松的解决该问题,代码如下:
import itertools # 装满 6 格,金额小于 10000 equipment = [690,1500,2100,1740,2140,2080] def func(): iter = itertools.combinations_with_replacement(equipment,6) count = 0 for i in iter: if sum(i) < 10000: print(i) count += 1 return count print(func())
上期读者参考解答:
@姚航:
https://git.oschina.net/yaohang_china/codes/6rgm1deb705c3fhqukpn498
姚同学的答案写的比较直观,理解起来也不难。但附加第二题的意思是影忍之足最多买一双,即可为 0 或 1,代码第67行
if string.count('690') < 1:
应改为
if string.count('690') <= 1:
我们也写了一份包括了附加题的代码:
供参考。
近期文章推荐阅读:
只学2个月编程能写出什么代码?他们表示:You can you code!