n个骰子的点数个数?解决方案

n个骰子的点数个数?
一道面试题:
把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，打印出S的所有可能的值出现的概率。

现在我想知道这个S有多少个值. 用数学中哪个公式可以表示出来?
谢谢!!

------解决方案--------------------
排列组合问题，这个不需要公式吧，S介于最小值和最大值之间
最小值是n,最大值是6n;即 n<=S<=6n
------解决方案--------------------
本以为会很简单，没想到手痒写了一下，我只能写这么长了：

C/C++ code

#include <vector>
#include <iostream>
#include <map>
#include <numeric>

using namespace std;

typedef vector<size_t> NumVec;
typedef NumVec::const_iterator NumVecCIter;
typedef map<size_t,NumVec > PotentialMap;

void BuildMapTo(PotentialMap& rMap,size_t n)
{
    if(n == 1)
    {
        return;
    }

    if(rMap.rbegin()->first < n-1 )
    {
        BuildMapTo(rMap, n-1);
    }

    const NumVec& vec = (rMap[n-1]);
    rMap.insert( make_pair(n,NumVec()));
    NumVec& vecN = (rMap[n]);
    const int iSize = (int)vec.size();
    for(int i=-5;i< iSize;++i)
    {
        size_t iSum = 0;
        for(int j=0;j<6;++j)
        {
            if(i+j>=0 && i+j < iSize)
                iSum += vec[i+j];
        }
        vecN.push_back(iSum);
    }
}

const NumVec& GetPotential(size_t nDiceNum)
{
    static PotentialMap mapPotential;
    if(mapPotential.empty())
    {
        NumVec vecFirst(6,1);
        mapPotential.insert( make_pair(1,vecFirst));
    }

    if( mapPotential.rbegin()->first < nDiceNum )
        BuildMapTo(mapPotential, nDiceNum);

    return mapPotential[nDiceNum];
}

const int ValidDiceNumMax = 12;

int main()
{
    int iNum;
    do
    {
        cout << "input your dice num(1-12)[any other value to exit]:";
        cin >> iNum;

        if(iNum <1 || iNum >ValidDiceNumMax)
        {
            break;
        }

        const NumVec& vec = GetPotential(iNum);
        const size_t iPotentialNum = accumulate(vec.begin(),vec.end(),0);
        cout << "value\t:  potential percent"<<endl;

        double dPercentSum=0;
        for(size_t i=0;i<vec.size();++i)
        {
            double percent = vec[i] * 1.0 / iPotentialNum * 100.0;
            dPercentSum += percent;
            cout << "  " << iNum++ << "\t\t" << percent << endl;
        }

        cout << "sum of percent is:   " << dPercentSum << "\n" << endl;
    }while(1);

}

n个骰子的点数个数?解决方案

相关推荐