基于Monte Carlo Method的扑克牌翻牌匹配

caoer

程序来源于一个扑克牌魔术，假定2个人，自己和朋友，让朋友默默选择一张牌(不要给我看)，随着发牌进行我可以说出朋友选择的是什么牌。规则是，每当朋友和我选择到一张key card的时候，需要按照牌面大小往下进心数牌，游戏进行到一定时候，我和朋友的牌会成为同一张牌，这是monte carlo思想。如何发牌很有技巧，主要是保证发牌的公平性。
共计52张牌，无大小鬼。
读牌方法：
A ＝1 = one = 3 (三个字母，往后数3个牌)
2 ＝2 = two = 3 (三个字母，往后数3个牌)
3 ＝3 = three = 5 (5个字母，往后数5个牌)
4 ＝4= four = 4 (4个字母，往后数4个牌)
.....
J = jack = 4  (4个字母，往后数4个牌)
Q = queen = 5(5个字母，往后数5个牌)
K = king = 4(4个字母，往后数4个牌)
以此类推。

最终，很有可能我和朋友都能数到同一张牌，我测试了10000次随机循环，可能性在65%以上，也就是说很多扑克牌游戏中是有固定的大概律事件，大家也可以在我的程序上做一些变种，使之更加有趣味性。
程序用c++编的，在ubuntu9.04上运行通过，其中用到了std的list作为数据结构。

具体的描述可以看这里：
http://divisbyzero.com/2010/03/15/a-card-trick-that-will-probably-amaze-your-friends/





Here’s a neat card trick that I learned a few years ago. I can’t remember where I read about it. If anyone knows the source of trick, please post it in the comments. [Update: I now know more about the origin of this trick. I'll write more in my follow-up post.]

Thoroughly shuffle an ordinary deck of cards. Then allow your friend to pick any card from the deck. She should look at it and not show it to you. This is her first “key” card.

Tell her that you will deal the remaining 51 cards one-at-a-time, face up onto a pile. If she is holding a non-face card, she must silently count the cards as you lay them down. When she reaches the number on her key card, the upturned card becomes her new key card. If her key card is a face card, then instead of counting, she should silently spell the name of her card (e.g, J-A-C-K). When she reaches the end of the name, the upturned card becomes her new key card. She should repeat the process as you continue to deal the cards.

For example, suppose the shuffle left the cards in the following order (I used Random.org to produce this shuffle) and that your friend chose the top card as her first key card (the 10 of spades in this example).

Then as you deal she will silently count

1 (king), 2 (10), 3 (king), 4 (2), 5 (jack), 6 (3), 7 (9), 8 (9), 9 (10), 10 (ace).

Now the ace of diamonds is her new key card so she counts

1 (5).

Now the 5 is her new key card, and she continues

1 (6), 2 (8), 3 (4), 4 (queen), 5 (queen), Q (6), U (2), E (3), E (queen), N (king), K (4), etc.

When you turn up the queen of clubs you stop and tell her that this is one of her key cards.

How does this trick work? How do you know when to stop?

I’ll post the secret behind the card trick in a in a separate post. If you figure it out, please do not reveal it in the comments.



Warning! Spoiler alert! This post contains the secret behind the card trick that I described in my last post. Read that post before reading this one.
First the bad news: this card trick is not fool-proof; it is aprobabilistic card trick. The good news is that in my experience, ithas a high probability of success. I can’t be more specific than that.If anyone wants to run a Monte Carlo simulation, I’d be happy to hear how often the trick fails.
The secret to this card trick is that you play along just like your friend is,but you use the first upturned card as your key card. She is silentlycounting and so are you. In the example shown below, her key cards haveovals on them and your key cards have rectangles on them.

As you can see, at first you and she have different key cards, but, and here’s the essential point,once you both land on the same card, you will have the same key cardsfrom then onward. Thus, all you have to do is wait until you get nearthe end of the deck and stop on one of your key cards. If you arelucky, the two of you will be in sync by then and the trick will be asuccess.
In the example shown above you’re in sync when the seven of diamonds is dealt—the 31st card.
Note: in practice this card trick is quite successful. I played around with Random.orgfor a little while and was unable to find a shuffling that failed. Oneshuffling didn’t sync up until the second-to-last card though! Quite afew of the shufflings synced in the first or second row. Twice thefirst card was an ace, so they were in sync right from the beginning.
As I said in my last post, I do not know who to credit for this card trick. If you know, please post it in the comments.
The rules of the original card trick were slightly different thanthose I presented here. The face cards counted as 10’s. This is fine,but it decreases the probability of success, so I chose to spell thenames of the face cards. Also, rather than having the other player drawa card at the start, she or he could mentally pick a card some timeduring the deal and start counting then. Again, this decreases thechances of success.
[Update: Thanks to John Allen Paulos who quickly responded on Twitter. He said that this trick is called the Kruskal count. He wrote about it in his 1998 book Once Upon a Number—The Hidden Mathematical Logic of Stories (healso proposes a biblical hoax that uses this trick). You can also readabout the Kruskal count in Ivars Peterson's December 24, 2001 MathTrek article Guessing Cards. In his article he points to the article "The Kruskal Count,"by Jeffrey C. Lagarias, Eric Rains, Robert J. Vanderbei in which theylook at the probabilities of success for various face card values.Finally, here's a nice applet illustrating the Kruskal count (taking face cards to be 5's).]

FreddyMusic

看上去很好玩。但是游戏规则，没看懂。你详细描述一下。

另外，那个链接我这也上不了，你直接把有效内容贴出来吧。

wangyuanwill

最近也在学c++真是羡慕楼主啊

luckyahui

长见识了，楼主有才

xwvszhl

l楼主真有才，我怎么感觉老是学不好C++呢，着实让我很头疼啊!

leejaysun

我很有压力

yimeng_777

没时间学习，仅剩下羡慕！！

观书阁

楼主很有才，羡慕啊。

wzz

太牛了   而且还是英文