子序列的概率计算与算法
子序列的概率计算与算法
提问于 2011-09-23 01:16:32
这是一个游戏，其中卡片1-50被分配给两个玩家，每个玩家都有10张随机顺序的卡片。目标是对所有的牌进行排序，谁先做谁就是赢家。每次一个人可以从牌组中拿起一张牌，他就必须更换一张现有的牌。玩家不能交换他的牌。也就是说，只有他可以用牌面上的牌替换他的牌，丢弃的牌会随机地回到牌面上。现在我需要编写一个程序来高效地完成这项工作。
我已经考虑了下面的解决方案: 1)在给定的一组卡片中找到所有升序的子序列；2)对于每个子序列，基于可以解决该问题的no种方法的概率来计算权重。例如:如果我在索引2,3,4处有一个子序列48,49,50，那么用这个子序列完成问题的概率是0。所以权重乘以0。类似地，如果我在索引3,4,5处有一个序列18, 20 ,30，那么完成游戏的可能方式是20张可能的牌选择6-10和17张可能的牌选择前2个位置，3)对于每张牌，我将扫描列表并重新计算子序列的权重以找到更好的匹配。
好吧，这个解决方案可能有很多缺陷，但我想知道1)给定一个子序列，如何找到完成游戏的可能方法的概率? 2)找出所有子序列的最佳算法是什么？
回答 1
Stack Overflow用户
回答已采纳
发布于 2011-10-20 21:14:03
因此，如果我理解正确的话，目标是通过交换尽可能少的卡片来获得有序的手，对吗？您尝试过以下方法吗？它非常简单，但我猜它有相当好的性能。
N=50
I=10
while hand is not ordered:
get a card from the deck
v = value of the card
put card in position round(v/N*I)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7518818
复制相关文章
相似问题
腾讯云开发者
