一个有趣的博弈策略

KeyTo9_Fans

差不多。 只是有两个问题： 1. 递推式是否正确无误？ 2. 如何确定压注额的上界$N$？

guanhuaming

上界N越小越好。这个题目的难点就是得出一个比较小的压注额的上界。 不知N在50000以内有解不？

guanhuaming

设$F(R,G,B)$表示剩余$R$张红牌，$G$张绿牌，赢$B$注所需的筹码数 则有$F(R,G,B)=min_{k=1}^N\{max\{F(R-1,G,B-k)-k,F(R,G-1,B+k)+k\}\}$ 从边界出发，逐层往上递推 递推的同时要确定上界$N$ 目标是求$F ... KeyTo9_Fans 发表于 2010-5-16 20:03

请教一下，F(R-1,G,B-k)-k表示的是什么意思？

056254628

F(R,G,B)中，B可以取到负数值，所以k值最大能取到无穷大，所以版主的递推公式如何处理该问题，是个大问题？

056254628

版主的k是表示 剩余R张红牌，G张绿牌，赢注所需的筹码数为B时，假设押注k注，来寻找最优的押注值。

guanhuaming

真得非常谢谢KeyTo9_Fans版主和各位朋友的回答 。　 这个题目对我太重要了。 苦于自己以前没有好好学习。 版主能不能帮忙给个递推程序？？再次谢谢。

KeyTo9_Fans

递推式得改一下： $F(R,G,B)=min_{k=1}^N\{max\{k,F(R-1,G,B-k)-k,F(R,G-1,B+k)+k\}\}$ 在$max\{\}$里添加一项$k$是因为能下$k$注的前提是手里至少有$k$注，如果手里没有$k$注就不能下$k$注 于是$max\{\}$的值至少是$k$ 当$k$的值达到当前$min\{\}$的值时，就可以停止往上枚举$k$值

sakurazdx

我感觉N应该取Ｆ（Ｒ，Ｇ，Ｂ），但是这种情况下，还能编出程序吗？ 第一次可以随便给Ｎ一个值，在以后的循环中，怎么给？

056254628

17# 的新的递推公式中，max{} 内的k项是无效的，因为 Ｆ（Ｒ，Ｇ-1，Ｂ+k）+k 项一定是大于k的。

056254628

9楼的递推公式就可以了，不过R、G都必须大于0。 再加上以下几条： {X} 表示不小于X的最小整数 F(R,0,B)={B/(2^R-1)} B>0 F(R,0,B)=1 B<=0 F(0,G,B)=G B<=-1*G F(0,G,B) =+∞ (即无解 ) B>-1*G 递推公式k从1开始计算到 F(R,G-1,B+k)+k>=F(R-1,G,B-k)-k 就可结束。 ----------------------------------------- 不过R，G稍大一点，电脑速度就非常慢。 以下是一些结果： F(1,1,1)=5，第一步押注2注 F(1,2,1)=17，第一步押注3注 F(1,3,1)=49，第一步押注4注 F(1,4,1)=129，第一步押注5注 F(2,1,1)=2，第一步押注1注 F(2,2,1)=6，第一步押注2注 F(2,3,1)=17，第一步押注3注 F(2,4,1)=33，第一步押注3注 F(3,1,1)=2，第一步押注1注 F(3,2,1)=3，第一步押注1注 F(3,3,1)=7，第一步押注2注 F(3,4,1)=17，第一步押注3注 F(4,1,1)=2，第一步押注1注 F(4,2,1)=3，第一步押注1注 F(4,3,1)=4，第一步押注1注 F(4,4,1)=9，第一步押注2注