撲克牌的順子
問題描述：從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這5張牌是不是連續的。2-10為數字本身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數字。
思路：可以將這5張牌排個序，然后統計出0的個數以及非0數字之間的間隔數，如果出現重復的非0數字，那么不是順子。如果間隔數小于等于0的個數，那么是順子。暫時未想到更好的辦法。
參考代碼：
//函數功能 ： 從撲克牌中隨機抽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個骰子的點數和
/ = 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個骰子的和有關。這就可以用到備忘錄的方法，用一張表格保存已解決的子問題的解，然后自底向上填表。考慮到當前層的計算只與下一層有關，因此只需保存一行。
參考代碼：
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; } 新聞熱點
疑難解答
圖片精選
