扑克牌的顺子
问题描述:从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2-10为数字本身,A为1,J为11,Q为12,K为13,而大小王可以看成任意数字。
思路:可以将这5张牌排个序,然后统计出0的个数以及非0数字之间的间隔数,如果出现重复的非0数字,那么不是顺子。如果间隔数小于等于0的个数,那么是顺子。暂时未想到更好的办法。
参考代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
//函数功能 : 从扑克牌中随机抽5张牌,判断是不是一个顺子
//函数参数 : pCards为牌,nLen为牌的张数
//返回值 : 是否顺子
bool IsContinuous( int *pCards, int nLen)
{
if (pCards == NULL || nLen <= 0)
return false ;
sort(pCards, pCards + nLen); //调用标准库的排序算法
int i;
int zeroCount = 0; //大小王用0表示
int capCount = 0; //间隔数
//统计0的个数
for (i = 0; i < nLen; i++)
{
if (pCards[i] == 0)
zeroCount++;
else
break ;
}
//统计间隔数
int preCard = pCards[i];
for (i = i + 1; i < nLen; i++)
{
int curCard = pCards[i];
if (preCard == curCard) //与前一张牌比较
return false ;
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个骰子的点数和
1
2
3
|
/ = 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 < k or n > 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个骰子的和有关。这就可以用到备忘录的方法,用一张表格保存已解决的子问题的解,然后自底向上填表。考虑到当前层的计算只与下一层有关,因此只需保存一行。
参考代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
const int FACE_NUM = 6; //骰子的面数
//函数功能 : n个骰子的点数
//函数参数 : number为骰子数
//返回值 : 无
void PrintSumProbabilityOfDices( int number)
{
if (number <= 0)
return ;
int *pSum = new int [number * FACE_NUM + 1]; //和的种类
double total = pow (6.0, number); //<cmath>
int size = number * FACE_NUM;
int i,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;
}
|