剑指offer-Q60 n个骰子的点数

python版本代码

g_maxValue = 6 # 单个骰子最大的点数

def PrintProbability(number):
    '''
    :param number: 骰子的个数 
    :return: 打印概率分布,返回表示概率分布的数组
    '''
    if number < 1: # 骰子个数小于1
        return
    maxSum  = number * g_maxValue 
    pProbabilities = [0 for i in range(maxSum - number + 1)]
    Probability(number, pProbabilities)

    total = pow(g_maxValue, number)
    for i in range(number , maxSum + 1):
        ratio = pProbabilities[i-number]/total
        print(i, ratio)
    return pProbabilities

def Probability(number, pProbabilities):
    '''
    :param number: 骰子个数 
    :param pProbabilities:概率分布(计算频数)
    :return: None
    '''
    for i in range(1, g_maxValue+1):
        _Probability(number, number, i, pProbabilities)

def _Probability(original, current, sum, pProbabilities):
    '''
    :param original: 等于骰子的个数,表示的意义是最小的点数之和,作为pProbabilities定位索引的一个offset 
    :param current: 还剩下的未考虑的骰子的个数
    :param sum: 考虑过的骰子的点数之和
    :param pProbabilities: 概率分布(计算频数)
    :return: None
    '''
    if current == 1:
        pProbabilities[sum - original]+=1
    else:
        for i in range(1, g_maxValue+1):
            _Probability(original, current - 1, i+sum, pProbabilities)

PrintProbability(1)
上一篇:121. 买卖股票的最佳时机


下一篇:用js实现动态规划解决背包问题