数学研发论坛

 找回密码
 欢迎注册
查看: 593|回复: 10

[原创] 最优答题策略

[复制链接]
发表于 2020-12-23 10:58:09 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
某xxqg软件有一个挑战答题,每次挑战可重复进行多轮答题,直到某轮连续答对5题或者前6题答对5题则挑战成功,后者是因为每轮有一个复活机会。
答错时亦可以选择不复活而放弃本轮,直接开始新一轮答题。
最终挑战成功时,系统会给出本次挑战多轮答题的总题数。
例如,某人某次挑战的过程和结果如下:
轮次      过程                    题数
第1轮    110110                  6
第2轮    111010                  6
第3轮    1100                     4
第4轮    10(放弃)            2
第5轮    111011(成功)     6
结果本次挑战总题数 = 24
假定他进行了10次挑战试验,各次的答题总数为24,22,20,20,21,24,23,25,21,20
则他这10次的各次答题总数期望值为(24+22+19+20+21+24+23+25+21+20)/10=22题

假如不考虑借助搜索引擎,某人答题的正确率是p,每轮应该在连续答对多少题后失败时选择复活,才能使得完成挑战的答题总数的期望值最少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-12-23 12:02:09 | 显示全部楼层
测试了几个数据,结果显示:最佳策略是:答对一题以后使用复活,所用答题总数的平均值最少。即如果第一题就答错了,那么本次挑战放弃,不使用复活而直接进入下一轮挑战,如果第一题答对了,那么后面不管第几题答错了,都使用复活,直到挑战成功或者答错进入下一轮。
不过,也有很多数据表明答对两次以后才使用复活,总次数会比答对一次就用要少,不过结果比较接近,不好判断。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-12-23 13:01:38 | 显示全部楼层
我计算结果和p相关,比如p<0.5187900636758842219074538,
那么只有前4个都猜对了才值得复活
而如果0.5187900636758842219074538<p<0.7412709105660020537067863,
那么前3个都猜对了复活
如果0.7412709105660020537067863<p<0.8881796675853100182508273
那么前2个都猜对了复活
如果p>0.8881796675853100182508273
那么第一个猜对就值得复活了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-12-23 14:10:39 | 显示全部楼层
本帖最后由 lsr314 于 2020-12-23 14:16 编辑
mathe 发表于 2020-12-23 13:01
我计算结果和p相关,比如p


我试了p=1/3,答对0~4题后复活平均答题次数分别是166、130、133、160、219,在测试10万次后取平均数,每个数字在±3范围内波动。所以答对一题和答对两题后复活结果接近,但是明显优于其他方案。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-12-23 17:21:37 | 显示全部楼层
你模拟的应该有问题:
计算后平均答题次数:
? getA(1.0/3.0)
%6 = [[283.00000000000000000000000000000000018, 280.00000000000000000000000000000000018, 271.00000000000000000000000000000000018, 244.00000000000000000000000000000000018, 163.00000000000000000000000000000000017]~, 4]
也就是说4题答对后才复活结果最优,答对0~4题后(还有复活机会)还平均需要回答上面次数才可以。

模拟结果
\$ ./testc 2 0.333333333333
regret at 2 try and probability is 0.333333
Average try 336.740347 times

\$./testc 3 0.333333333333
regret at 3 try and probability is 0.333333
Average try 308.719644 times

\$./testc 4 0.333333333333
regret at 4 try and probability is 0.333333
Average try 282.619372 times


另外比如
\$ ./testc 2 0.7
regret at 2 try and probability is 0.700000
Average try 12.555739 times

\$ ./testc 3 0.7
regret at 3 try and probability is 0.700000
Average try 12.353519 times

\$ ./testc 4 0.7
regret at 4 try and probability is 0.700000
Average try 13.336981 times

? getA(0.7)
%7 = [[12.368768965312072350806211697506991135, 10.940197536740643779377640268935562563, 8.8993812102100315344796810852620931754, 5.9839293151662997560540251085857083358, 2.7849705479859582316891771285773784732]~, 3]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-12-23 18:21:43 | 显示全部楼层
本帖最后由 lsr314 于 2020-12-23 18:49 编辑
mathe 发表于 2020-12-23 17:21
你模拟的应该有问题:
计算后平均答题次数:
? getA(1.0/3.0)


能否贴一下代码,或者给一个p=1/2单次挑战成功的数据,用1表示答对,0表示答错,-1表示重新开始答题,看看算法是不是和实际的规则一致。
比如以下是一组测试数据:{1, 1, 0, 0, -1, 1, 0, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 1, 1, 0, 0, -1, 0, -1, 1, 1, 1, 1, 0, 0, -1, 0, -1, 0, -1, 1, 1, 1, 1, 1}
里面0和1的个数是33,表示总共答了33题,-1的个数是15,重启了15轮答题,总共答了16轮。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-12-23 18:43:28 | 显示全部楼层
本帖最后由 lsr314 于 2020-12-23 19:09 编辑
mathe 发表于 2020-12-23 13:01
我计算结果和p相关,比如p


p=1/2的时候,如果已经答对三个了,第四个答错了复活的话,只要再答对2个就成功了,概率是1/4.如果不复活,下次连续答对三个的概率只有1/8,也就是大约8次重新答题(少说也要再答十几道题)才能到达现在的状态,感觉不符合直觉,放弃似乎不划算。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-12-23 19:13:08 来自手机 | 显示全部楼层
则本次挑战失败,重新答题,前面答对的清零,依然可以有一次复活机会
===
看来是我规则理解不对,也就是每次清零后可以重新复活了,我理解成每次开始挑战,直到挑战成功只有一次复活机会
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-12-23 19:29:53 | 显示全部楼层
mathe 发表于 2020-12-23 19:13
则本次挑战失败,重新答题,前面答对的清零,依然可以有一次复活机会
===
看来是我规则理解不对,也就是 ...

对,每次可以重新复活,情况更复杂一点
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-12-23 19:44:28 | 显示全部楼层
用A0,A1,A2,A3,A4分别代表还没有使用掉复活机会,而且当前已经连续答对0,1,2,3,4道题时的状态
用B1,B2,B3,B4分别代表已经使用掉复活机会,而且当前已经连续大队1,2,3,4道题时的状态。
用a0,a1,a2,a3,a4,b1,b2,b3,b4代表在对应状态下,需要挑战成功的平均答题次数。
于是,如果至少一道答对就使用复活机会,得出

\(q=1-p, \begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_1\\b_2\\b_3\\b_4\end{pmatrix}=\begin{bmatrix}q&p&0&0&0&0&0&0&0\\0&0&p&0&0&q&0&0&0\\0&0&0&p&0&0&q&0&0\\0&0&0&0&p&0&0&q&0\\0&0&0&0&0&0&0&0&q\\q&0&0&0&0&0&p&0&0\\q&0&0&0&0&0&0&p&0\\q&0&0&0&0&0&0&0&p\\q&0&0&0&0&0&0&0&0\end{bmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_1\\b_2\\b_3\\b_4\end{pmatrix}+\begin{pmatrix}1\\1\\1\\1\\1\\1\\1\\1\\1\end{pmatrix}\)

而如果需要答对两道题目以上才会使用复活机会,那么得出
\(\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_2\\b_3\\b_4\end{pmatrix}=\begin{bmatrix}q&p&0&0&0&0&0&0\\q&0&p&0&0&0&0&0\\0&0&0&p&0&q&0&0\\0&0&0&0&p&0&q&0\\0&0&0&0&0&0&0&q\\q&0&0&0&0&0&p&0\\q&0&0&0&0&0&0&p\\q&0&0&0&0&0&0&0\end{bmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_2\\b_3\\b_4\end{pmatrix}+\begin{pmatrix}1\\1\\1\\1\\1\\1\\1\\1\end{pmatrix}\)

而如果需要答对三道题目以上才会使用复活机会,那么得出
\(\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_3\\b_4\end{pmatrix}=\begin{bmatrix}q&p&0&0&0&0&0\\q&0&p&0&0&0&0\\q&0&0&p&0&0&0\\0&0&0&0&p&q&0\\0&0&0&0&0&0&q\\q&0&0&0&0&0&p\\q&0&0&0&0&0&0\end{bmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_3\\b_4\end{pmatrix}+\begin{pmatrix}1\\1\\1\\1\\1\\1\\1\end{pmatrix}\)

而如果需要答对四道题目以上才会使用复活机会,那么得出
\(\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_4\end{pmatrix}=\begin{bmatrix}q&p&0&0&0&0\\q&0&p&0&0&0\\q&0&0&p&0&0\\q&0&0&0&p&0\\0&0&0&0&0&q\\q&0&0&0&0&0\end{bmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\a_3\\a_4\\b_4\end{pmatrix}+\begin{pmatrix}1\\1\\1\\1\\1\\1\end{pmatrix}\)

得到四个$a_0$对应的结果好像分别为
${4p^5 - 2p^4 - 2p^3 - 2p^2 - 2p - 1}/{4p^6 - 5p^5}, {3p^5 - 2p^4 - 2p^3 - 2p^2 - p - 1}/{3p^6 - 4p^5}, {2p^5 - 2p^4 - 2p^3 - p^2 - p - 1}/{2p^6 - 3p^5}, {p^5 - 2p^4 - p^3 - p^2 - p - 1}/{p^6 - 2p^5}$
结果显示不总是第二个最优
而是0.43691112721451127690774683642557996857<p<0.71973996370820249294954144847181472770时第二种方案最优
其余情况第一种方案最优

点评

很给力。即使正确率高达50%,平均也要答29题才能通关,大部分题目都是四选一,瞎蒙的话要答100到400题以上才能通关,怪不得每次几乎都是中途放弃。  发表于 2020-12-23 21:19

评分

参与人数 1威望 +2 金币 +2 贡献 +2 经验 +2 鲜花 +2 收起 理由
lsr314 + 2 + 2 + 2 + 2 + 2 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-3-9 15:55 , Processed in 0.086897 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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