使用C语言求解扑克牌的顺子及n个骰子的点数问题
扑克牌的顺子
问题描述：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。
思路：可以将这5张牌排个序，然后统计出0的个数以及非0数字之间的间隔数，如果出现重复的非0数字，那么不是顺子。如果间隔数小于等于0的个数，那么是顺子。暂时未想到更好的办法。
参考代码：
//函数功能：从扑克牌中随机抽5张牌，判断是不是一个顺子
//函数参数：pCards为牌，nLen为牌的张数
//返回值：是否顺子
boolIsContinuous(int*pCards,intnLen)
{
if(pCards==NULL||nLen<=0)
returnfalse;
sort(pCards,pCards+nLen);//调用标准库的排序算法
inti;
intzeroCount=0;//大小王用0表示
intcapCount=0;//间隔数
//统计0的个数
for(i=0;i<nLen;i++)
{
if(pCards[i]==0)
zeroCount++;
else
break;
}
//统计间隔数
intpreCard=pCards[i];
for(i=i+1;i<nLen;i++)
{
intcurCard=pCards[i];
if(preCard==curCard)//与前一张牌比较
returnfalse;
else
capCount+=curCard-preCard-1;//累加间隔数
preCard=curCard;
}
return(zeroCount>=capCount)?true:false;//只要王的个数大于间隔数
}
n个骰子的点数
问题描述：把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，打印出S的所有可能的值出现的概率。
思路：这是一道应用动态规划思想的题目，而动态规划最难的就是要找最优子结构。并采取一种称为备忘录的方法避免重复计算。因为备忘录方法为每个解过的子问题建立了备忘录，以备需要时参看，避免了相同子问题的重复求解。
本题的最优子结构为：F(k,n)表示k个骰子点数和为n的种数，k表示骰子个数，n表示k个骰子的点数和
/=F(k-1,n-6)+F(k-1,n-5)+F(k-1,n-4)+F(k-1,n-3)+F(k-1,n-2)+F(k-1,n-1)对于k>0,k<=n<=6*k F(k,n)= \=0对于n<korn>6*k
当k=1时,F(1,1)=F(1,2)=F(1,3)=F(1,4)=F(1,5)=F(1,6)=1。
从上面公式可以看出，k个骰子点数和为n的种数只与k-1个骰子的和有关。这就可以用到备忘录的方法，用一张表格保存已解决的子问题的解，然后自底向上填表。考虑到当前层的计算只与下一层有关，因此只需保存一行。
参考代码：
constintFACE_NUM=6;//骰子的面数
//函数功能：n个骰子的点数
//函数参数：number为骰子数
//返回值：无
voidPrintSumProbabilityOfDices(intnumber)
{
if(number<=0)
return;
int*pSum=newint[number*FACE_NUM+1];//和的种类
doubletotal=pow(6.0,number);//<cmath>
intsize=number*FACE_NUM;
inti,j,k;
//初始化
pSum[0]=0;
for(i=1;i<=FACE_NUM;i++)
pSum[i]=1;
for(;i<=size;i++)
pSum[i]=0;
for(i=2;i<=number;i++)//骰子个数从2到n
{
for(j=i*FACE_NUM;j>=i;j--)//第i个骰子的和的范围为[i,i*FACE_NUM]
{
pSum[j]=0;
for(k=1;k<=6&&j>=k;k++)//其实展开就是F(i,j)=F(i-1,j-6)+F(i-1,j-5)+F(i-1,j-4)+F(i-1,j-3)+F(i-1,j-2)+F(i-1,j-1)
{
pSum[j]+=pSum[j-k];
}
}
//不可能的情况，即i个骰子的和不可能小于i
for(j=i-1;j>=0;j--)
pSum[j]=0;
}
//打印结果
for(i=0;i<=size;i++)
cout<<"sum="<<i<<",p="<<pSum[i]/total<<endl;
}