一个有趣的博弈策略

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注