快捷導(dǎo)航

使用C語言求解撲克牌的順子及n個骰子的點數(shù)問題

更新時間：2016年03月15日 16:15:33 作者：wuzhekai1985

這篇文章主要介紹了使用C語言求解撲克牌的順子及n個骰子的點數(shù)問題的方法,解答實例主要為了突出解題的算法,需要的朋友可以參考下

撲克牌的順子
    問題描述：從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這5張牌是不是連續(xù)的。2-10為數(shù)字本身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數(shù)字。
         思路：可以將這5張牌排個序，然后統(tǒng)計出0的個數(shù)以及非0數(shù)字之間的間隔數(shù)，如果出現(xiàn)重復(fù)的非0數(shù)字，那么不是順子。如果間隔數(shù)小于等于0的個數(shù)，那么是順子。暫時未想到更好的辦法。
         參考代碼：

//函數(shù)功能 ： 從撲克牌中隨機抽5張牌，判斷是不是一個順子 
//函數(shù)參數(shù) ： pCards為牌，nLen為牌的張數(shù) 
//返回值 ： 是否順子 
bool IsContinuous(int *pCards, int nLen) 
{ 
 if(pCards == NULL || nLen <= 0) 
  return false; 
 
 sort(pCards, pCards + nLen); //調(diào)用標(biāo)準(zhǔn)庫的排序算法 
 
 int i; 
 int zeroCount = 0; //大小王用0表示 
 int capCount = 0; //間隔數(shù) 
 //統(tǒng)計0的個數(shù) 
 for(i = 0; i < nLen; i++) 
 { 
  if(pCards[i] == 0) 
   zeroCount++; 
  else 
   break; 
 } 
 //統(tǒng)計間隔數(shù) 
 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; //累加間隔數(shù) 
  preCard = curCard; 
 } 
 return (zeroCount >= capCount)? true: false; //只要王的個數(shù)大于間隔數(shù) 
}

n個骰子的點數(shù)
問題描述：把n個骰子扔在地上，所有骰子朝上一面的點數(shù)之和為S。輸入n，打印出S的所有可能的值出現(xiàn)的概率。
思路：這是一道應(yīng)用動態(tài)規(guī)劃思想的題目，而動態(tài)規(guī)劃最難的就是要找最優(yōu)子結(jié)構(gòu)。并采取一種稱為備忘錄的方法避免重復(fù)計算。因為備忘錄方法為每個解過的子問題建立了備忘錄，以備需要時參看，避免了相同子問題的重復(fù)求解。
本題的最優(yōu)子結(jié)構(gòu)為：F(k, n) 表示k個骰子點數(shù)和為n的種數(shù)，k表示骰子個數(shù)，n表示k個骰子的點數(shù)和

     /  = 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

         當(dāng)k=1時, F(1,1)=F(1,2)=F(1,3)=F(1,4)=F(1,5)=F(1,6)=1。
         從上面公式可以看出，k個骰子點數(shù)和為n的種數(shù)只與k-1個骰子的和有關(guān)。這就可以用到備忘錄的方法，用一張表格保存已解決的子問題的解，然后自底向上填表?？紤]到當(dāng)前層的計算只與下一層有關(guān)，因此只需保存一行。
         參考代碼：

const int FACE_NUM = 6; //骰子的面數(shù) 
 


//函數(shù)功能 ： n個骰子的點數(shù) 
//函數(shù)參數(shù) ： number為骰子數(shù) 
//返回值 ： 無 
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++) //骰子個數(shù)從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; 
 } 
 
 //打印結(jié)果 
 for(i = 0; i <= size; i++) 
  cout<<"sum = "<<i<<", p = "<<pSum[i] / total<<endl; 
}

您可能感興趣的文章: