扔 n 个骰子，向上面的数字之和为 S。给定 Given n，请列出所有可能的 S 值及其相应的概率。

Question

算法题，网上给出的解释感觉有点抽象。不知道有哪位能够帮忙详解一下，不甚感谢！
附上搜索到解答：
http://www.7zhang.com/index/c...
http://www.cnblogs.com/bozhou...

Answer 1

$result = getResult(2);
var_dump($result);

/**
 * [getResult description]
 * @param  [type]  $n [骰子个数]
 * @return [array]    [数组，点数和=>相应概率]
 */
function getResult($n){
    // 定义骰子的点数及其概率
    $sixArr = array(
        1 => 1/6,
        2 => 1/6,
        3 => 1/6,
        4 => 1/6,
        5 => 1/6,
        6 => 1/6,
    );

    if ($n == 1) { // 只有一个骰子的情况
        return $sixArr;
    } else { // 多个骰子情况
        $result = $sixArr; 
        // 假定结果是由一个骰子和其他任意个骰子的组合成的结果集
        // 当有N个骰子的时候，需要组合N-1次
        for ($i=0; $i < $n-1; $i++) { 
            $result = getDiffArrResult($result, $sixArr);
        }
    }
    return $result;
}

/**
 * [getDiffArrResult 将2个点数概率的数组进行组合，获取这2个数组组合而成的 数字和及其概率]
 * @param  [type] $arr1 [第一个数组]
 * @param  [type] $arr2 [第二个数组]
 * @return [array]      [数组，点数和=>相应概率]
 */
function getDiffArrResult($arr1, $arr2){
    $result = array();
    foreach ($arr1 as $k1 => $v1) {
        foreach ($arr2 as $k2 => $v2) {
            if (!isset($result[$k1+$k2])) $result[$k1+$k2] = 0;
            $result[$k1+$k2] += $v1*$v2;
        }
    }
    return $result;
}

自己写的PHP版本。通过两重循环获取2个数组的键值（骰子点数）及其出现概率。并将其累加。即可获得结果

Answer 2

借着C++的代码来回答一下，思路就是随着骰子数目的增加，下一组的概率可以由上一组生成：

/* -std=c++11 */
#include <iostream>
#include <map>

#define Pmap std::map<unsigned int, double>

class Dices {
public:
  static constexpr double UNIT = 1.0 / 6.0;

private:
  Pmap possibles;
  size_t count = 0;

  void calcNext() {
    if (this->possibles.empty()) {
      // 初始状态
      this->possibles = {
        {1, UNIT}, {2, UNIT}, {3, UNIT},
        {4, UNIT}, {5, UNIT}, {6, UNIT}
      };
    } else {
      Pmap newMap;
      for (auto const &it : this->possibles) {
        for (int i = 1; i <= 6; i++) {
          unsigned int newSum = it.first + i;
          auto addtion = it.second * UNIT;

          auto search = newMap.find(newSum);
          if (search != newMap.end()) {
            search->second += addtion;
          } else {
            newMap.insert(std::make_pair(newSum, addtion));
          }
        }
      }
      this->possibles = newMap;
    }
  }

public:
  Dices () {}

  void calc(size_t c) {
    count = c;
    possibles = Pmap();

    if (count == 0) return;
    for (int i = 0; i < count; i++) {
      calcNext();
    }
  }

  void print() {
    std::cout << "all possibilities:" << std::endl;
    float sum = 0.0;
    for (auto const &it : this->possibles) {
      sum += it.second;
      std::cout << it.first << "\t" << it.second << std::endl;
    }
    std::cout << "total: " << sum << std::endl;
  }

};

int main(int argc, char **args) {
  Dices d = Dices();

  d.calc(2);
  d.print();

  d.calc(12);
  d.print();

  return 0;
}