主题：第33次编程比赛第2题
iAkiak [专家分：8460] 发布于 2006-06-27 12:40:00
胡了!
=====
先抄一段话：来自http://sports.enorth.com.cn/system/2006/04/26/001290452.shtml
[quote]
麻将起源于中国，原属皇家和王宫贵族的游戏，其历史可以追溯到三四千年前。在长期的历史演变过程中，麻将逐步从宫廷流传到民间，至清朝中期基本定型。麻将作为中国传统文化宝库中的一个重要组成部分，具有集益智性、趣味性、博弈性于一体的运动魅力，及内涵丰富、底蕴悠久的东方文化特征。几百年来，麻将曾经风行于大江南北，流行范围涉及到社会的各个阶层，已经进入千家万户，而且流传海外，成为我国国内及国外华人中最具规模和影响力的智力体育活动。
[/quote]
先大致介绍一下麻将规则：
各地的麻将有各自的特色，规则上有许多差异。
麻将牌有条子、筒子、万子，分别从1到9各4张。
一条、二条、...九条
一筒、二筒、...九筒
一万、二万、...九万
"东南西北中发白"字牌各4张
有的麻将还有花牌"春夏秋冬梅兰竹菊"各1张
共计144张牌。
玩家有一手牌3n+1张（n为0,1,2...）。根据13张麻将和16张麻将的玩法n的上限不同，分别为4和5。一手牌再加上别家打出的一张牌或者自己摸进的一张牌，组成3n+2张牌可以判断是否胡牌。
基本牌型分为刻、顺、杠、将。
刻是3张同样的牌。
顺是3张同一花色连号的条子、筒子或万子。
将是2张同样的牌。
杠是4张同样的牌（由于杠牌时会补一张牌，所以玩家手牌数量仍然是3n+1张）
吃牌、碰牌、杠牌
吃牌是取上家打出的牌和自己的牌组成顺。
碰牌是取别家打出的牌和自己的牌组成刻。
杠牌是取别家打出的牌或者自己摸到的牌和自己的牌组成杠。
吃碰的玩家不摸牌，但仍然需要打出一张。
杠牌的玩家需要补一张牌，并仍然需要打出一张。
麻将一般4人围成一桌，分为东南西北四家，轮流做庄。游戏开始各自初始拿到一样数目的牌（13张麻将拿13张，16张麻将拿16张）。从上局赢家开始摸牌，摸一张牌打一张牌。只有下家可以吃上家打出的牌，任何玩家都可以碰（或者杠）其他玩家打出的牌。
在游戏中，玩家需要想办法使得牌型成为某一种胡牌的类型。
要胡牌，一般需要配成一将搭配若干个刻或者顺。（也有其他特殊类型的胡牌，不同类型胡牌有翻（或者台）的累积。翻数越高，赢得越多）
百搭麻将是一种有趣的变种。许多麻将玩法中都有百搭牌的玩法。游戏开始时一般通过骰子确定某张牌是百搭牌。百搭牌可以根据需要替代任何牌参与组合。但百搭牌不允许被打出。
现在需要大家写一个函数判断玩家否满足胡牌条件。
为了简化判断，牌只出现条子、筒子、万子和字牌。并且牌数保证是3n+2张（手牌＋1张牌），其中0<=n<=5。预先吃、碰、杠的牌均不需要考虑。胡牌只判断3n+2张牌是否满足一将搭配若干个刻或者顺。不需要计算翻（或者台数）。当有3张或4张百搭牌时，也直接算胡。
并且规定：
条子是 0x01到0x09
筒子是 0x11到0x19
万子是 0x21到0x29
东南西北分别是0x30,0x40,0x50,0x60
中发白分别是0x70,0x80,0x90
百搭牌是0x00
当牌A被选择为百搭牌时，白板(0x90)就转为代替A牌。可以参与刻、顺、将的组合。注意白板本身也可能会被选中为百搭牌。调用时，白板已经被转为百搭牌本身的牌，所以除非白板本身是百搭，否则参数中不会出现0x90。
bool TestHu(const char pai[], int count, char baida);
pai数组内保存了count个牌（已经按编码由小到大排序）
TestHu函数需要返回[color=red]true[/color]表示牌型可以胡牌。否则返回[color=red]false[/color]
baida是被选中的百搭牌。
下面举几个例子：
0x00, 0x01, 0x02, 0x03, 0x30, baida = 0x40，胡牌，顺+将，百搭配将
0x00, 0x11, baida = 0x11，胡牌，将，百搭归位（它配为它本身的牌，注意这里的0x10其实本来是白板）
0x01, 0x02, 0x03, 0x04, 0x05, baida = 0x50, 不胡，无百搭
0x01, 0x02, 0x03, 0x04, 0x04, baida = 0x50, 胡，无百搭，顺+将
0x00, 0x00, 0x01, 0x01, 0x01, 0x02, 0x02, 0x03，baida = 0x50, 胡，刻+顺+将（其实此时有许多种搭配都可以）
0x00, 0x00, 0x00, 0x00, 0x01, 0x12, 0x23, 0x60, baida = 0x50, 胡，4百搭
百搭规则参考温州麻将，我家这边百搭规则和它不一样，不过这个规则相对我家这边的百搭规则容易一些
最后扯一下，麻将游戏消遣可以，赌博就不好了。
回复列表 （共7个回复）
沙发
天边蓝 [专家分：1810] 发布于 2006-06-29 21:26:00
/*大家都这么客气啊~~
我就不客气啊~先交(虽然不敢保证结果)
*/
bool TestHu(const char pai[], int count,char baida){
int jiang,erqueyi,danyi;
int i=-1;
int flag;
int low;
jiang=erqueyi=danyi=0;
while(1){
if(pai[++i]!=0x00){
flag=i;
break;
}
};
if(flag>=3)
return true;
for(low=flag;low<count;){
if(low+2<count){
if(pai[low]==pai[low+1]&&pai[low+1]==pai[low+2]||
pai[low+1]-pai[low]==1&&pai[low+2]-pai[low+1]==1){
low+=3;
}
else if(pai[low]==pai[low+1]&&pai[low+1]!=pai[low+2]){
jiang++;
low+=2;
}
else if( pai[low+1]-pai[low]==1&&pai[low+2]-pai[low+1]!=1||
pai[low+1]-pai[low]==2&&low+3<count&&
!(pai[low+3]-pai[low+2]==1&&pai[low+2]-pai[low+1]==1)||
low+3<count&&!(pai[low+1]==pai[low+2]&&pai[low+2]==pai[low+3]) ){
low+=2;
erqueyi++;
}
else{
danyi++;
low++;
}
}
else if(low+1<count){
if(pai[low+1]-pai[low]==1){
erqueyi++;
break;
}
else if(pai[low+1]==pai[low])
jiang++;
else
danyi+=2;
low+=2;
}
else{
danyi++;
low++;
}
}
if(jiang!=0)
return ( (jiang-1)*1+2*danyi+erqueyi==flag );
else
return ( (danyi-1)*2+erqueyi==flag-1 );
}
板凳
sllone [专家分：150] 发布于 2006-06-29 22:51:00
这么久都没人交??
折腾出个了,好幸运第一遍测试就通过了给出的数据,不知道还有没有bug
先占个位了~~嘿嘿
bool deal(char *p,int num,int j,int i){//j记录有无将,i记录白搭个数
if(num==0)
return true;
if(*p==0x00&&deal(p+1,num,j,i+1))
return true;
if(*(p+1)==*p&&deal(p+2,num-2,1,i))//配将
return true;
else if(i>=1&&j!=1&&deal(p+1,num-2,1,i-1))//用白搭配将
return true;
if(num>=3){
if((*(p+2)-*(p+1))==(*(p+1)-*p)&&deal(p+3,num-3,j,i))//配刻或顺
return true;
else if(i>=1&&(*(p+1)-*p)<=2&&deal(p+2,num-3,j,i-1))//用一个白搭配刻或顺
return true;
else if(i>=2&&deal(p+1,num-3,j,i-2))//用两个白搭配刻或顺
return true;
}
return false;
}
bool TestHu(const char pai[], int count, char baida){
char pai_tmp[17]={0};
for(int i=0;i<count;i++){
if(pai[i]==0x90&&baida!=0x00)
pai_tmp[i]=baida;
else
pai_tmp[i]=pai[i];
}
if(deal(pai_tmp,count,0,0))
return true;
return false;
}
3 楼
yxs0001 [专家分：9560] 发布于 2006-06-30 09:41:00
/*
3n+2(0=<n<=5)张麻将牌，3、4张百搭胡。
麻将牌表示：
条：0x01～0x09
筒：0x11～0x19
万：0x21～0x29
东南西北中发白：0x30、0x40、0x50、0x60、0x70、0x80、0x90
百搭：0x00
当牌A 被选中为百搭，白板(0x90)就转为牌A
参数：
pai：由小到大排序的麻将牌
count：牌数
baida：被选为百搭的牌
返回值：true可胡 false不可胡
*/
#include <ctime>
#include <cstdlib>
#include <iostream>
using namespace std;
struct CTiao{
int pai[10];//0表示这组牌的百搭牌个数 1-9表示1-9条的个数
int min,max;//最小/大的条
int sum;//条的个数
int summod;//sum mod 3
CTiao(){
for(int i = 0;i<10;i++)
pai[i] = 0;
min = max = sum = summod = 0;
}
};
bool hu(const CTiao cmj)//无百搭
{
CTiao mj = cmj;
int i;
if(mj.sum == 0)
return true;
for(i=mj.min;i<8;i++){
if(mj.pai[i] == 1 || mj.pai[i] == 2){
mj.pai[0] -= 3 * mj.pai[i];
if((mj.pai[i+2] -= mj.pai[i])<0)
return false;
if((mj.pai[i+1] -= mj.pai[i])<0)
return false;
mj.pai[i] = 0;
return hu(mj);
}
else if(mj.pai[i]>=3){
mj.pai[i] -= 3;
mj.pai[0] -= 3;
return hu(mj);
}
}
if(mj.pai[8] % 3 == 0 && mj.pai[9] % 3 == 0)
return true;
else
return false;
}
//穷举
bool hu_baida_all(const CTiao cmj)
{
CTiao mj = cmj;
int i,j;
if(mj.pai[0] >= mj.sum)
return true;
mj.min = (mj.min - mj.pai[0])>0 ? mj.min - mj.pai[0] : 1;
mj.max = (mj.max + mj.pai[0])<10 ? mj.max + mj.pai[0] : 9;
CTiao tmp;
if(mj.pai[0] == 1){
for(i=mj.min;i<=mj.max;i++){
tmp = mj;
tmp.sum += mj.pai[0];
tmp.summod = tmp.sum % 3;
tmp.pai[i] ++;
tmp.pai[0] = 0;
if(hu(tmp))
return true;
}
return false;
}
else if(mj.pai[0] == 2){
for(i=mj.min;i<=mj.max;i++)
for(j=mj.min;j<=mj.max;j++){
tmp = mj;
tmp.sum += mj.pai[0];
tmp.summod = tmp.sum % 3;
tmp.pai[i] ++;
tmp.pai[j] ++;
tmp.pai[0] = 0;
if(hu(tmp))
return true;
}
return false;
}
}
4 楼
yxs0001 [专家分：9560] 发布于 2006-06-30 09:43:00
发部上了
发到你的油箱里面 zikaizhang@gmail.com
楼主帮我贴出来吧
郁闷
5 楼
太没劲了 [专家分：2050] 发布于 2006-06-30 11:38:00
tested under Gcc 3.4.3
bool solve(const char pai[], int count,int pos,int baidanum)
{
int type;
char backup[20],*curp;
curp = const_cast<char *>(pai);
if( count>0 && pos<count )
{
int startpos,kk;
memcpy(backup,&curp[pos],count-pos);
for(kk=pos;kk<count && (unsigned char)curp[kk] > (unsigned char)0x90 ; ++kk);
startpos = kk;
if( startpos==count && (baidanum>1 || 0==baidanum) ) return(true);
for(type=0;type<3;++type) /* 0 shun, 1 jiang, 2 ke */
{
char outloop=0;
for(int i=startpos; i<count && !outloop; ++i)
{
if( (unsigned char)curp[i] > (unsigned char)0x90 ) continue;
switch(type)
{
case 0: /* shun */
{
int getv;
if( (getv=curp[i]/10)>=0 && getv<3 )
{
int k=1,getpos[2];
for(int j=i+1; j<count && k<3; ++j)
if( curp[i]+k ==curp[j] ) getpos[k-1] = j, ++k;
if( 3==k )
{
curp[i] = curp[getpos[0]] = curp[getpos[1]] = (unsigned char)0x91;
if( solve(pai,count,i+1,baidanum) ) return(true);
memcpy(&curp[pos], backup, count-pos);
}
if( k+baidanum>2 )
{
curp[i] = (unsigned char)0x91;
if( baidanum>1 && solve(pai,count,i+1,baidanum-2) ) return(true);
memcpy(&curp[pos], backup, count-pos);
if( k>1 )
{
curp[i] = curp[getpos[0]] = (unsigned char)0x91;
if( baidanum>0 && solve(pai,count,i+1,baidanum-1) ) return(true);
memcpy(&curp[pos], backup, count-pos);
}
}
}
outloop = 1;
break;
}
case 1: /* jiang */
case 2: /* ke */
{
int k=0,getpos[2];
for(int j=i+1; j<count && k<2; ++j)
if( curp[i]==curp[j] ) getpos[k] = j, ++k;
if( 2==k )
{
curp[i] = curp[getpos[0]] = curp[getpos[1]] = (unsigned char)0x91;
if( solve(pai,count,i+1,baidanum) ) return(true);
memcpy(&curp[pos], backup, count-pos);
}
if( 1==k )
{
curp[i] = curp[getpos[0]] = (unsigned char)0x91;
if( solve(pai,count,i+1,baidanum) ) return(true);
memcpy(&curp[pos], backup, count-pos);
}
if( baidanum>0 )
{
curp[i] = (unsigned char)0x91;
if( solve(pai,count,i+1,baidanum-1) ) return(true);
memcpy(&curp[pos], backup, count-pos);
if( k>0 )
{
curp[i] = curp[getpos[0]] = (unsigned char)0x91;
if( solve(pai,count,i+1,baidanum-1) ) return(true);
memcpy(&curp[pos], backup, count-pos);
}
if( baidanum>1 )
{
curp[i] = (unsigned char)0x91;
if( solve(pai,count,i+1,baidanum-2) ) return(true);
memcpy(&curp[pos], backup, count-pos);
}
}
outloop = 1;
break;
}
}
}
}
}
else return( baidanum>1 || 0==baidanum );
return(false);
}
bool TestHu(const char pai[], int count, char baida)
{
int pos=0,baidanum;
char *curp;
curp = const_cast<char *>(pai);
for(int i=0;i< count; ++i)
if( !(pai[i]==0 || ((unsigned char)baida==(unsigned char)0x90 && pai[i]==baida)) ) curp[pos++] = pai[i];
baidanum = count - pos;
return( solve(pai,pos,0,baidanum) );
}
6 楼
ccpp [专家分：9360] 发布于 2006-06-30 12:18:00
int NumberOfBaiTa(const char pai[], int count); /*百搭牌的数量*/
int Jiang(const char pai[], int count, int n); /*是否成将（可以补牌），返回牌的位置 */
int Sun(const char pai[], int count, int n); /*是否成顺（可以补牌），返回牌的位置 */
int Ke(const char pai[], int count, int n); /*是否成刻（可以补牌），返回牌的位置 */
int (*Pattern[])(const char*,int,int) = {Jiang, Sun, Ke}; /*转移表*/
int nbaita, njiang;/*百塔牌数和将牌数*/
bool SlovePai(const char pai[], int count,int n);
bool TestHu(const char pai[], int count, char baida);
bool TestHu(const char pai[], int count, char baida)
{
int n ;
njiang = 0;
nbaita = n = NumberOfBaiTa(pai,count);
if(nbaita > 2) return true;
return SlovePai(pai,count,n);
}
bool SlovePai(const char pai[], int count, int n)
{
int i,t,tb,tj;
if(n == count)
{
if(nbaita == 0 && njiang == 1)
return true;
else
return false;
}
for(i = 0; i < 3; i++)/*轮换使用，将（一次），顺，刻*/
{
tb = nbaita; tj = njiang;
t = Pattern[i](pai,count,n);
if(t != 0 && SlovePai(pai,count,n+t))
return true;
nbaita = tb;njiang = tj;
}
return false;
}
int Jiang(const char pai[], int count, int n)
{
if( (n+1) < count && pai[n] == pai[n+1])
{
njiang += 1;
return 2;
}
if(nbaita > 0)/*使用一张百塔*/
{
nbaita -= 1;
njiang += 1;
return 1;
}
if(nbaita > 1)/*使用两张*/
{
nbaita -= 2;
njiang +=1;
return 0;
}
return 0;
}
int Sun(const char pai[], int count, int n)
{
if( (n+2) < count &&(pai[n+2]-pai[n+1]) == 1 && (pai[n+1]-pai[n]) == 1)
{
return 3;
}
if( (n+1) < count && (pai[n+1]-pai[n]) <= 2 && nbaita > 0)
{
nbaita -= 1;/*使用一张*/
return 2;
}
if(nbaita > 1)/*使用两张*/
{
nbaita -= 2;
return 1;
}
return 0;
}
int Ke(const char pai[], int count, int n)
{
if( (n+2) < count && pai[n] == pai[n+1] && pai[n] == pai[n+2])
{
return 3;
}
if( (n+1) < count && pai[n] == pai[n+1] && nbaita > 0)
{
nbaita -= 1;/*使用一张*/
return 2;
}
if(nbaita > 1)/*使用两张*/
{
nbaita -= 2;
return 1;
}
return 0;
}
int NumberOfBaiTa(const char pai[], int count)
{
int n = 0;
while(n < count && pai[n] == 0) ++n;
return n;
}
7 楼
ccpp [专家分：9360] 发布于 2006-06-30 12:33:00
int NumberOfBaiTa(const char pai[], int count); /*百搭牌的数量*/
/*是否成将，刻，顺（可以补牌），返回牌的位置 */
int Jiang(const char pai[], int count, int n);
int Ke(const char pai[], int count, int n);
int Sun(const char pai[], int count, int n);
int (*Pattern[])(const char*,int,int) = {Jiang,Ke,Sun}; /*转移表*/
int nbaita, njiang;/*百塔牌数和将牌数*/
bool SlovePai(const char pai[], int count,int n);
bool TestHu(const char pai[], int count, char baida);
bool TestHu(const char pai[], int count, char baida)
{
int n ;
njiang = 0;
nbaita = n = NumberOfBaiTa(pai,count);
if(nbaita > 2) return true;
return SlovePai(pai,count,n);
}
bool SlovePai(const char pai[], int count, int n)
{
int i,t,tb,tj;
if(n == count)
{
if(nbaita == 0 && njiang == 1)
return true;
else
return false;
}
for(i = 0; i < 3; i++)/*轮换使用，将（一次）刻,顺，*/
{
tb = nbaita; tj = njiang;
t = Pattern[i](pai,count,n);
if(t != 0 && SlovePai(pai,count,n+t))
return true;
nbaita = tb;njiang = tj;
}
return false;
}
int Jiang(const char pai[], int count, int n)
{
if( (n+1) < count && pai[n] == pai[n+1])
{
njiang += 1;
return 2;
}
if(nbaita > 0)/*使用一张百塔*/
{
nbaita -= 1;
njiang += 1;
return 1;
}
if(nbaita > 1)/*使用两张*/
{
nbaita -= 2;
njiang +=1;
return 0;
}
return 0;
}
int Ke(const char pai[], int count, int n)
{
if( (n+2) < count && pai[n] == pai[n+1] && pai[n] == pai[n+2])
{
return 3;
}
if( (n+1) < count && pai[n] == pai[n+1] && nbaita > 0)
{
nbaita -= 1;/*使用一张*/
return 2;
}
if(nbaita > 1)/*使用两张*/
{
nbaita -= 2;
return 1;
}
return 0;
}
int Sun(const char pai[], int count, int n)
{
if( (n+2) < count &&(pai[n+2]-pai[n+1]) == 1 && (pai[n+1]-pai[n]) == 1)
{
return 3;
}
if( (n+1) < count && (pai[n+1]-pai[n]) <= 2 && nbaita > 0)
{
nbaita -= 1;/*使用一张*/
return 2;
}
return 0;
}
int NumberOfBaiTa(const char pai[], int count)
{
int n = 0;
while(n < count && pai[n] == 0) ++n;
return n;
}
我来回复
您所在位置：