[第七关]100名囚犯难题

问题
  • 100 名囚犯分别编号为 1 到 100
  • 一个房间有一个橱柜,里面有 100 个不透明的抽屉,编号从 1 到 100,从外面看不到。
  • 编号为 1 到 100 的卡片随机放置,一张放在抽屉里,抽屉全部关闭;在开始时。
  • 囚犯从房间外开始
  • 他们可以在任何人进入房间之前决定一些策略。
  • 犯人一个一个进入房间,可以打开一个抽屉,检查抽屉里的卡号,然后关上抽屉。
  • 一个囚犯最多可以打开 50 个抽屉。
  • 一名囚犯试图找到自己的号码。
  • 一名囚犯找到自己的号码,然后将其与其他囚犯分开。
  • 如果所有100 名囚犯都找到自己的号码,那么他们都会被赦免。如果没有,那么所有句子都成立。

 

任务
  1. 模拟数千个囚犯随机打开抽屉的游戏实例
  2. 模拟数千个游戏实例,其中囚犯使用维基百科文章中提到的最佳策略:
  • 首先打开外面号码是他的囚犯号码的抽屉。
  • 如果里面的卡片有他的号码,那么他成功,否则他打开与显示的卡片号码相同的抽屉。(直到他打开他的最大值)。

在此页面上显示并比较两种策略的计算成功概率。

 

参考
  1. 100 个囚犯拼图的不可思议的解决方案(视频)。
  2. wp:100个囚犯问题
  3. 100 名囚犯逃脱谜题数据遗传学。
  4. 随机排列统计#维基百科上的一百个囚犯

示例代码:

NumOfTrials := 20000
randomFailTotal := 0, strategyFailTotal := 0
prisoners := [], drawers := [], Cards := []
loop, 100
	prisoners[A_Index] := A_Index				; create prisoners
	, drawers[A_Index] := true				; create drawers
 
loop, % NumOfTrials
{
	loop, 100
		Cards[A_Index] := A_Index			; create cards for this iteration
	loop, 100
	{
		Random, rnd, 1, Cards.count()
		drawers[A_Index] := Cards.RemoveAt(rnd)		; randomly place cards in drawers
	}
	;-------------------------------------------
	; randomly open drawers
	RandomList := []
	loop, 100
		RandomList[A_Index] := A_Index
	Fail := false
	while (A_Index <=100) && !Fail
	{
		thisPrisoner := A_Index
		res := ""
		while (thisCard <> thisPrisoner) && !Fail
		{
			Random, rnd, 1, % RandomList.Count()	; choose random number
			NextDrawer := RandomList.RemoveAt(rnd)	; remove drawer from random list (don't choose more than once)
			thisCard := drawers[NextDrawer]		; get card from this drawer
			if (A_Index > 50)
				Fail := true
		}
		if Fail
			randomFailTotal++
	}
	;-------------------------------------------
	; use optimal strategy
	Fail := false
	while (A_Index <=100) && !Fail
	{
		counter := 1, thisPrisoner := A_Index
		NextDrawer := drawers[thisPrisoner]		; 1st trial, drawer whose outside number is prisoner number
		while (drawers[NextDrawer] <> thisPrisoner) && !Fail
		{	
			NextDrawer := drawers[NextDrawer]	; drawer with the same number as that of the revealed card
			if ++counter > 50
				Fail := true
		}
		if Fail
			strategyFailTotal++
	}
}
MsgBox %  "Number Of Trials = " NumOfTrials
		. "`nOptimal Strategy:`t" (1 - strategyFailTotal/NumOfTrials) *100 " % success rate" 
		. "`nRandom Trials:`t" (1 - randomFailTotal/NumOfTrials) *100 " % success rate"

输出结果:

Number Of Trials = 20000
Optimal Strategy:	33.275000 % success rate
Random Trials   :	0.000000 % success rate

计算量比较大,需要耐心等待!!!!!!!!!!

给TA捐赠
共{{data.count}}人
人已捐赠
AHKV1代码示例图形图像学习社区推荐近期更新

【高级】AutoHotkey调用com对象时如果返回两个(多个)值该如何处理?

2022-2-14 23:25:20

AHKV1游戏

[第八关]来设计一个15拼图游戏吧!

2022-2-15 10:58:15

2 条回复 A文章作者 M管理员
  1. rastar

    试试一下

  2. ccc

    看不懂😎

个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索