Question

200悬赏加50追分求C/C++编程“单人纸牌”

- 问题描述
Double Patience是一种单人纸牌游戏，共36张牌分成9叠，每叠4张牌面向上。
每次，游戏者可以从某两个不同的牌堆最顶上取出两张牌面相同的牌（如黑桃10和梅花10）并且一起拿走。如果最后所有纸牌都被取走，则游戏者就赢了，否则游戏者就输了。
George很热衷于玩这个游戏，但是一旦有时有多种选择的方法，George就不知道取哪一种好了，George会从中随机地选择一种走，例如：顶上的9张牌为KS, KH, KD, 9H, 8S, 8D, 7C, 7D，6H，显然有5种取法：(KS, KH), (KS, KD), (KH, KD), (8S, 8D), (7C, 7D)，当然George取到每一种取法的概率都是1/5。
有一次，George的朋友Andrew告诉他，这样做是很愚蠢的，不过George不相信，他认为如此玩最后成功的概率是非常大的。请写一个程序帮助George证明他的结论：计算按照他的策略，最后胜利的概率。

- 输入数据
9行每行4组用空格分开的字串，每个字串两个字符，分别表示牌面和花色，按照从堆底到堆顶的顺序给出。

- 输出数据
一行，最后胜利的概率，精确到小数点后6位。

- 样例输入
AS 9S 6C KS
JC QH AC KH
7S QD JD KD
QS TS JS 9H
6D TD AD 8S
QC TH KC 8D
8C 9D TC 7C
9C 7H JH 7D
8H 6S AH 6H

- 样例输出
0.589314

Answer 1

递归程序执行效率就是低哦，运行了5分钟才出结果

首先说明一下，为了简化问题，把花色条件去掉了（没用），扑克牌A-T用整型1-14代替，不用输入，直接在主函数中初始化（要自己输入的话很好做的）

程序如下（C语言）：

有疑问百度HI，QQ406344627都可以。

main()

{float george(int data[][],int top[]);

int top[9],i,data[9][4]={

              { 1, 9, 6,13},

              {11,12, 1,13},

              { 7,12,11,13},

              {12,14,11, 9},

              { 6,14, 1, 8},

              {12,14,13, 8},

              { 8, 9,14, 7},

              { 9, 7,11, 7},

              { 8, 6, 1, 6}};

float p;

 for(i=0;i<9;i++)

  top[i]=3;

/*top数组记录每一堆最上面的位置，如3表示此堆没拿走一张，-1表示已经拿完了*/

p=george(data,top);

printf("%f",p);

getch();

}

float george(int data[9][4],int top[9])

{int k=0,s=0,i,j;

 float p0=0;

 for(i=0;i<9;i++)

 for(j=i+1;j<9;j++)

   if(top[i]>=0&&top[j]>=0)

   if(data[i][top[i]]==data[j][top[j]])

    k++;

/*k表示可能走的方法数*/

 for(i=0;i<9;i++)if(top[i]>=0)s=1;

 if(k==0&&s==1)return 0;

/*k=0，s=1表示无路可走，但是牌没拿完，证明是失败的走法，成功概率为0*/

 if(k==0&&s==0)return 1;

/*牌拿完了*/

 for(i=0;i<9;i++)

 for(j=i+1;j<9;j++)

   if(top[i]>=0&&top[j]>=0)

   if(data[i][top[i]]==data[j][top[j]])

   {top[i]--;top[j]--;p0+=george(data,top)/k;top[i]++;top[j]++;}

/*把经过下一步(每个方向的成功概率)/k表示经过此步成功的概率k为此步后的拿取方法*/

return p0;

}

Answer 2

MARK~

Answer 3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TIMES 1e3

typedef struct ST_CARD{
char exist;
char sign[3];
} card;

typedef struct ST_DupT{
int c;
char rown[4]; // max 4 types,record their rown this time
} DupT;

char nums[10] = "6789TJQKA";
char types[5] = "HDCS";
float possi_num = 0;
float impossi_num = 0;

void no_choice_cards(int nG,card cards[]){
// nG == 1 || nG == 0
int i,j;
int pos;

srand(time(0)); /* seed for rand */
for(i=0; i<36; i++){
cards[i].exist = '\0';
}

for(i=0; i<9; i++){
for(j=0; j<nG; j++){
pos = i*4 + j;
cards[pos].sign[0] = nums[i];
cards[pos].sign[1] = types[j];
cards[pos].sign[2] = '\0';
cards[pos].exist = i+'0';
}
}

for(i=0; i<9; i++){
for(j=nG; j<4; j++){
/* find a card's position */
pos = rand()%36;
while('\0' != cards[pos].exist){ /* while exist */
++pos;
if(36 == pos){
pos = 0;
} /* if */
} /* while */

cards[pos].sign[0] = nums[i]; /* not null */
cards[pos].sign[1] = types[j];
cards[pos].sign[2] = '\0';
cards[pos].exist = i+'0';
/* printf("%c+%c(%d)\t",cards[pos].sign[0],cards[pos].sign[1],pos); */
}
}
}

void display(card cards[]){
int x,y;
for(y=0; y<9; y++){
for(x=0; x<4; x++){
printf("%s\t",cards[y*4+x].sign);
}
printf("\n");
}
}

int possi(card cards[],char coln[],char sequence[],float possiblit){
/* do not take it seriously, please */
int i;
int m,n;

int x,y;
int idx;
int possible;
int bLeaf;
float fPossi;
int m_col,n_col;
int m_row,n_row;
int c_col = 0;
char seqb[73] = "\0";
DupT dup[9] = {{0,"\0\0\0"},{0,"\0\0\0"},{0,"\0\0\0"},
{0,"\0\0\0"},{0,"\0\0\0"},{0,"\0\0\0"},
{0,"\0\0\0"},{0,"\0\0\0"},{0,"\0\0\0"}};
char colnb[10] = "000000000"; //coln : next top card's col number
char choice[2] = "n";

// at least 2 rows, their col number do not over. if not, return 0
// count above cols

for(i=0; i<9; i++){
if(coln[i]<='3'){
++c_col;
idx = cards[i*4 + coln[i]-'0'].exist - '0'; // 6789TJQKA and 012345678
dup[idx].rown[dup[idx].c] = '0' + i; // record i : top card(i row)
dup[idx].c += 1;
}
}

if(c_col < 2){
impossi_num += 1;
printf("%f(impossible)\t\t%f(possible)\n",impossi_num,possi_num);
if(impossi_num >= MAX_TIMES){
printf("sorry, stop now\n");
display(cards);
printf("possiblity:%f\n",possi_num/(impossi_num+possi_num+0.000001));
exit(0);
}
return 0;
}

/* calculate the possiblity, and accumulate them, want correct
for(i=0; i<9; i++){
if(dup[i].c >= 2){
fPossi += ((dup[i].c)*(dup[i].c-1))/2;
}
}

fPossi /= (c_col*(c_col-1))/2;
fPossi *= possiblity;
*/

possible = 0;
bLeaf = 1; // assume : the end of tree, be leaf
for(i=0; i<9; i++){
if(dup[i].c >= 2){
// exist match event, if it can not enter into this branch before i == 9, return 0
// only if (2 == c_col && m_col == (int)'4' && n_col == (int)'4'), return 1
bLeaf = 0; // have sub tree

for(m=0; m<dup[i].c-1; m++){
for(n=m+1; n<dup[i].c; n++){
strcpy(colnb,coln); // backup coln

/*
printf("\nbefore selecting:\n");
for(y=0; y<9; y++){
for(x=0; x<4; x++){
if(x<(coln[y]-'0')) printf(" \t");
else printf("%s\t",cards[y*4+x].sign);
}
printf("\n");
}
*/

// 48 == (int)'0'
m_row = dup[i].rown[m] - '0';
n_row = dup[i].rown[n] - '0';
m_col = (++coln[m_row]) - '0';
n_col = (++coln[n_row]) - '0';

/* watch the process
printf("possiblity: %f, selected: %s(%d,%d),%s(%d,%d)\n",fPossi,cards[m_row*4+m_col-1].sign,m_row+1,m_col,
cards[n_row*4+n_col-1].sign,n_row+1,n_col);
printf("after selecting:\n");
for(y=0; y<9; y++){
for(x=0; x<4; x++){
if(x<(coln[y]-'0')) printf(" \t");
else printf("%s\t",cards[y*4+x].sign);
}
printf("\n");
}
while('y' != choice[0]){
printf("continue? y/n :");
scanf("%s",choice);
if('n' == choice[0]) exit(0);
}
*/
strcpy(seqb,sequence); // backup
strcat(sequence,cards[m_row*4+m_col-1].sign);
strcat(sequence,cards[n_row*4+n_col-1].sign);

if(2 == c_col && m_col == 4 && n_col == 4){
possi_num += 1; // leaves, count
printf("%f(impossible)\t\t%f(possible)\n",impossi_num,possi_num);
//printf("%s\n",sequence);
if(possi_num >= MAX_TIMES){
printf("sorry, stop now\n");
display(cards);
printf("possiblity:%f\n",possi_num/(impossi_num+possi_num+0.000001));
exit(0);
}
return 1;
}

if(possi(cards,coln,sequence,fPossi)) possible = 1;

strcpy(sequence,seqb); // recover
strcpy(coln,colnb); // end and restart revoke
}
}
}
}
if(possible) return 1;
else {
if(bLeaf){
impossi_num += 1;
printf("%f(impossible)\t\t%f(possible)\n",impossi_num,possi_num);
if(impossi_num >= MAX_TIMES){
printf("sorry, stop now\n");
display(cards);
printf("possiblity:%f\n",possi_num/(impossi_num+possi_num+0.000001));
exit(0);
}
}
return 0;
}
}

// http://zhidao.baidu.com/question/119843681.html
int main(){
int i,j;
int all_possi;
char sequence[73] = "\0";
char coln[10] = "000000000";
/* input here */
card cards[36]; /* 9*4 */

no_choice_cards(0,cards);

possi(cards,coln,sequence,1);

/* display random cards as follow */
display(cards);

printf("possiblity:%f\n",possi_num/(impossi_num+possi_num+0.000001));

return 1;
}