小练习：20170814 骰子游戏

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

                               
登录/注册后可看大图

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即8.21 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

----回帖需写明解题思路，鼓励在程序中加上注释


一些鱼油反映题目有些过难，为此略过一部分偏难的题目。



题目：

Peter 有九个四面的（金字塔型）骰子，每个分别标上 1，2，3，4。
Colin 有六个六面（正方体）骰子，每个分别标上 1，2，3，4，5，6。

Peter 和 Colin 摇骰子，然后比较他们得到的总和：总和最高的获胜。如果相等的话，则是平局。
请问，金字塔 Peter 赢了正方体 Colin 的概率是多少？以七位小数 0.abcdefg 的形式给出你的答案。

jerryxjr1220

这题完全可以借助强大的python库暴力组合所有可能的组合，然后再依次比较。
程序比较直观，直接看代码就好了。

from itertools import product
from collections import Counter
def dice_possibilities(size, dices):
        possibilities = [range(1,size+1) for _ in range(dices)]
        summary = []
        for p in product(*possibilities):
                summary.append(sum(p))
        return Counter(summary)
Peter = dice_possibilities(4,9)
Colin = dice_possibilities(6,6)
wins = 0
for key_peter, value_peter in Peter.items():
        for key_colin, value_colin in Colin.items():
                wins += value_peter*value_colin if key_peter>key_colin else 0
print('%.7f' % (wins/(4**9*6**6)))

0.5731441
[Finished in 0.2s]

其实，这题如果计算精度不用太高的话，完全可以用模拟方法来实现，模拟1000000次投掷的比较结果。

import numpy as np 
peter = (np.random.random(9000000)*4+1)//1
colin = (np.random.random(6000000)*6+1)//1
peter_wins = 0
for i in range(1000000):
        peter_wins += 1 if np.sum(peter[i*9:i*9+9])>np.sum(colin[i*6:i*6+6]) else 0
print(peter_wins/1000000)

0.572307
[Finished in 8.6s]
可以看到模拟的结果还是非常接近的。

小Q学Python

1.遍历所有可能出现的值（总和），统计次数，分别算出该值出现概率
2.逐个值进行比较，将2边的值的出现概率相乘，累加后即为结果

jzt = {}  # 金字塔出现所有值的统计
for i in range(1,5):
    for j in range(1,5):
        for k in range(1,5):
            for l in range(1,5):
                for m in range(1,5):
                    for n in range(1,5):
                        for o in range(1,5):
                            for p in range(1,5):
                                for q in range(1,5):
                                    a = i+j+k+l+m+n+o+p+q
                                    jzt.setdefault(a,0)
                                    jzt[a]+=1
zft= {}  # 正方体出现所有值的统计
for i in range(1,7):
    for j in range(1,7):
        for k in range(1,7):
            for l in range(1,7):
                for m in range(1,7):
                    for n in range(1,7):
                        a = i+j+k+l+m+n
                        zft.setdefault(a,0)
                        zft[a]+=1
a = 4**9  # 金字塔所有值的总次数
for i in jzt:
    jzt[i] /= a  # 每个值出现的概率（该值的出现次数/所有值的次数）
a = 6**6  # 正方体所有值的总次数
for i in zft:
    zft[i] /= a
gl = 0  
for i in jzt:
    for j in zft:
        if i > j:   # 逐个值进行比较，如果金字塔>正方体,将对应的值的概率进行相乘
            gl += jzt[i]*zft[j]  # 概率累加

print(round(gl,7))

%time %run qqq2.py
0.5731441
Wall time: 254 ms

夏天和大熊

     结果是0.5731441

import time as t

# 给出投掷temp次的n面骰子的结果的和存放于列表中
def deci(n = 4, temp = 9):
    stt_list = list(range(1, n+1))
    for j in range(temp - 1):
        tr_list = []
        for i in range(len(stt_list)):
            tr_list.extend([stt_list[i] + num for num in range(1, n+1)])
        stt_list = tr_list
    return stt_list

# 统计列表中出现的各种结果的数据
def stt_data(stt_list):
    list_nums = list(set(stt_list))
    list_time = []
    for each in list_nums:
        list_time.append(stt_list.count(each))
    list_return = list(zip(list_nums, list_time))
    return list_return
        
# 将所有P大于C的结果加起来 求出概率
def compare(n_p = 4, t_p = 9, n_c = 6, t_c = 6):
    t1 = t.time()
    list_p = stt_data(deci(n_p, t_p))
    list_c = stt_data(deci(n_c, t_c))
    temp_b = 0
    for each_p in list_p:
        time = 0
        for each_c in list_c:
            if each_p[0] > each_c[0]:
                time += each_c[1]
            else:
                break
        temp_b += time*each_p[1]
    p = temp_b/(n_p**t_p * n_c**t_c)
    t2 = t.time()
    print('用时%.7f秒，结果是%.7f' % (t2 - t1, p))
    return ('%.7f' % p)

if __name__ == '__main__':
    compare()

运维小书童

import itertools
import time
time.perf_counter()
result1 = {}   #存放9*4骰子结果  key为点数之和  值为总的骰子组合总数
result2 = {}    #存放6*6骰子结果  key为点数之和  值为总的骰子组合总数

a = ['1','2','3','4']
b = 9
for x1 in itertools.product(*[a]*b):  #获取4*9所有排列 存放结果到字典
    total = 0
    for each in x1:
        total += int(each)
    result1.setdefault(total,0)
    result1[total] += 1


a = ['1','2','3','4','5','6']
b = 6
for y1 in itertools.product(*[a]*b):  #获取6*6所有排列 存放结果到字典
    total = 0
    for each in y1:
        total += int(each)
    result2.setdefault(total,0)
    result2[total] += 1


for each in result1.keys():   #转换为各自概率
    result1[each] /= 4**9
for each in result2.keys():
    result2[each] /= 6**6

rate_total = 0
for x in result1.keys():
    rate = 0        
    for y in result2.keys():
        if x > y:           #获取colin骰子点数小于peter的总概率
            rate  += result2[y]
    rate *= result1[x]      #获取本次情况Peter点数大的概率
    rate_total += rate      #所有点数情况概率加起来就是总的概率
print('金字塔Peter赢立方体Colin的概率为%.7f'%rate_total)   
print('程序耗时：%.7f s'% time.perf_counter())                                   

                                     
                                    

            

小剑剑

def func1(dice,num):
    A=[1]
    temp=1
    for i in range(num):
        temp*=(i+2)
        A.append(temp)
    pro=[1]
    distru=[]
    distru.append([1,num]+[0]*(dice-1))
    count=dice*num-num+1
    for i in range((count+1)//2-1):
        temp=[]
        for d in distru:
            for j in range(1,dice):
                if d[j]:
                    t=d[:]
                    t[0]=(t[j]*t[0])//(t[j+1]+1)
                    t[j]-=1
                    t[j+1]+=1
                    if t not in temp:
                        temp.append(t)
        distru=temp
        pro.append(sum([i[0] for i in distru]))
    return pro

def func2(dice1,num1,dice2,num2):
    pro1=func1(dice1,num1)
    pro2=func1(dice2,num2)
    count1=dice1*num1-num1
    if count1&1:
        pro1+=pro1[::-1]
    else:
        pro1+=pro1[:-1][::-1]
    count2=dice2*num2-num2
    if count2&1:
        pro2+=pro2[::-1]
    else:
        pro2+=pro2[:-1][::-1]
    numerator=0
    denominator=dice1**num1*dice2**num2
    if num2<=num1:
        for i in range(count1+1):
            numerator+=sum(pro2[0:i+num1-num2])*pro1[i]
    else:
        temp=num2-num1
        for i in range(temp,count+1):
            numerator+=sum(pro2[0:i+num1-num2])*pro1[i]
    return '%.7f'%(numerator/denominator)
    

print(func2(4,9,6,6))

0.5731441

达锅

我的答案：0.5504525
没有四舍五入

#思路就是找到所有骰子可能的组合,计算和，然后比较。因为同样的和可能有不同的组合方式，所以每一种都要记录下来

import time as t 
tt=t.time()

def js(m,n):#m个n面的骰子
    tot=m*n#最大的和
    zd={i:0 for i in range(m,tot+1)}#生成所有可能的和的字典
    xl=[1]*m #记录每一种骰子的组合状态,第一种为m个1
    te=sum(xl)#求和
    zd[te]=1#和为键
    
    while te<tot:
        if xl[0]<n:#左边第一列+1，加满后向右第一列未满的+1，同时该列左边都等于该列,保证任意相邻的两列右边不大于左边
            xl[0]+=1
        else:
            k=1
            while xl[k]==n:
                k+=1
            xl[k]+=1
            xl[:k+1]=[xl[k]]*(k+1)
            
        te=sum(xl)
        zd[te]+=1

    return zd

pe=js(9,4)
co=js(6,6)   

print(str(sum(pe[p]*co[c] for p in pe for c in co if p>c)/sum(pe.values())/sum(co.values()))[:9])

print(t.time()-tt)

还有一种运行较慢的，基于对和值的出现规律进行总结的

import time as t 

tt=t.time()

def js(m,n):#m个n面的骰子
    xl=[0]*n
    for i in range(n):
        xl[i]=list(range(2*i,i+n))
    for i in range(m-1):
        for j in range(n):
            te=[]
            for k in range(j,n):
                te+=[m+j for m in xl[k]]
            xl[j]=te
    xl=xl[0]
    return {i+m:xl.count(i) for i in set(xl)}

pe=js(9,4)
co=js(6,6)  
print(str(sum(pe[p]*co[c] for p in pe for c in co if p>c)/sum(pe.values())/sum(co.values()))[:9])

print(t.time()-tt)

参考依据：

撒法空间

#!/usr/bin/env python3
#coding:utf-8

#总体思路：使用random模拟扔骰子
#当次数足够多时，所得出的概率无限接近真实概率。

#导入random模块
import random
#使用win统计peter赢了多少次
win = 0
#比较次数
count = 10000000
#定义一个函数，返回不同人每次扔骰子的总值
#number接收骰子个数, n接收每个骰子最大数字
def rm(number,n):
    num = 0
    for x in range(number): #循环number次
        r = random.randint(1,n) #生成每个骰子的随机值
        num += r
    return num #返回所有骰子扔完后加起来的总值

#比较100万次，如果perter的总值大于colin，则胜利次数加1
for x in range(count):
    if rm(9,4) > rm(6,6):
        win += 1

print(win/count) #打印perter赢了colin的概率。

perter胜率为：0.5732381    也就是大概57.32381%的胜率
程序用时：262秒，大概4分钟。可以减少比较次数来减少运行时间。10万次的比较和1000万的比较的误差精确到0.00001.

解题思路：
        使用random产生随机数，模拟扔骰子，两个人分别扔1000万次。每扔一次比较两个值。perter胜利次数加1.得出perter赢的总次数。
        再用perter胜利次数除1000万。最终得出胜率。

suloman

先算出 所有可能的结果
然后每次结果相加 得到每种结果可能出现的次数  除以总数就是 每个结果的概率(笨办法)
四面的每种概率乘以六面比自己小的概率 所有相加 就是最后的结果

def zhi(x,n):
    zha=[]
    for i in range(x*n+1):
        zha.append(0)        
    for i in range(x**n):
        temp=i
        aw=0
        while temp/x>0:
            aw=aw+temp%x
            temp=temp//x
        aw+=n
        zha[aw]=zha[aw]+1   
    return(zha)


from decimal import *
getcontext().prec = 7
a=zhi(4,9)
b=zhi(6,6)
x=0
y=0
for i in range(37):
    x=x+a[i]
    y=y+b[i]
gl=0
for i in range(9,37):
    for j in range(6,i):
        gl=gl+(a[i]/x)*(b[j]/y)
g=Decimal(gl)/Decimal(1)   
print("概率为:",g)

Greenland

def exhaustPeter():
    # 9 dices in range(1,5)
    results = {}
    dice = [1] * 9
    for dice[0] in range(1, 5):
        for dice[1] in range(1, 5):
            for dice[2] in range(1, 5):
                for dice[3] in range(1, 5):
                    for dice[4] in range(1, 5):
                        for dice[5] in range(1, 5):
                            for dice[6] in range(1, 5):
                                for dice[7] in range(1, 5):
                                    for dice[8] in range(1, 5):
                                        total = sum(dice)
                                        if total in results:
                                            results[total] += 1
                                        else:
                                            results[total] = 1
    return results


def exhaustColin():
    # 6 dices in range(1,7)
    results = {}
    dice = [1] * 6
    for dice[0] in range(1, 7):
        for dice[1] in range(1, 7):
            for dice[2] in range(1, 7):
                for dice[3] in range(1, 7):
                    for dice[4] in range(1, 7):
                        for dice[5] in range(1, 7):
                            total = sum(dice)
                            if total in results:
                                results[total] += 1
                            else:
                                results[total] = 1
    return results


def calculateWinrate():
    peter = exhaustPeter()
    colin = exhaustColin()
    wins = 0
    for p in peter:
        for c in colin:
            if p > c:
                wins += peter[p] * colin[c]
    total = sum(peter[p] for p in peter) * sum(colin[c] for c in colin)
    return float('%.7f' % (wins / total))


print(calculateWinrate())

chunchun2017

答案为：0.5731441
不知道对不对，哈哈
思路：
用迭代的方式分别计算6个六面骰子和9个四面骰子抛出各种点数的概率：
借签了网上动态规划的思路：
用f(n, s) 表示n个骰子点数的和为s的排列情况总数。
n个骰子点数和为s的种类数只与n-1个骰子的和有关。因为一个骰子有六个点数，那么第n个骰子可能出现1到6的点数。所以第n个骰子点数为1的话，f(n,s)=f(n-1,s-1)，当第n个骰子点数为2的话，f(n,s)=f(n-1,s-2)，…，依次类推。在n-1个骰子的基础上，再增加一个骰子出现点数和为s的结果只有这6种情况！那么有：

f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6) ，0< n<=6n
f(n,s)=0, s< n or s>6n

上面就是状态转移方程，已知初始阶段的解为：
当n=1时, f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。
用迭代（因为迭代比递归效率高）分别求出了6个六面骰子和9个四面骰子抛出各种点数的概率后，只需要记录每一种六面骰子比四面骰子点数大的情况下两者的概率，相乘，然后把这些乘出来的结果相加
最后得到结果（原谅我概率学得不好，这段分析不知道对不对，觉得很复杂，肯定不是最优的算法，求大神指点）

def getSixCount(n, count1):#六面骰子
   if(n<1):
           return -1
   if(n==1):
           return 0
       #初始化最初状态
   for i in range(6):
       count1[i]=1 
  
   for i in range(2,n+1):
         for sum in range(6*i,i-1,-1):
                tmp1 = count1[sum-i] if sum-i>=0 else 0 #上一阶段点数和sum-1的排列总数
                tmp2 = count1[sum-i-1] if sum-i-1>=0 else 0
                tmp3 = count1[sum-i-2] if sum-i-2>=0 else 0
                tmp4 = count1[sum-i-3] if sum-i-3>=0 else 0
                tmp5 = count1[sum-i-4] if sum-i-4>=0 else 0
                tmp6 = count1[sum-i-5] if sum-i-5>=0 else 0 
                count1[sum-i]=tmp1+tmp2+tmp3+tmp4+tmp5+tmp6
   return 0

def getFourCount(n, count2):#四面骰子
   if(n<1):
           return -1
   if(n==1):
           return 0
       #初始化最初状态
   for i in range(4):
         count2[i]=1
   for i in range(2,n+1):
         for sum in range(4*i,i-1,-1):
                tmp1 = count2[sum-i] if sum-i>=0 else 0 #上一阶段点数和sum-1的排列总数
                tmp2 = count2[sum-i-1] if sum-i-1>=0 else 0
                tmp3 = count2[sum-i-2] if sum-i-2>=0 else 0
                tmp4 = count2[sum-i-3] if sum-i-3>=0 else 0
                count2[sum-i]=tmp1+tmp2+tmp3+tmp4;
   return 0

import time
tt=time.time()
n1=6
n2=9
total1 = 6**n1
total2 = 4**n2
count1 = [0 for i in range(5*n1+1)]
count2 = [0 for i in range(3*n2+1)]
sum=0
list0_0 = [i for i in range(n1,6*n1+1)]
getSixCount(n1,count1)
list0_1 = [i/total1 for  i  in count1 ]
dict0 = dict(zip(list0_0,list0_1))
list1_0 = [ i for i in range(n2,4*n2+1)]
getFourCount(n2,count2)
list1_1 = [i/total2 for  i  in count2]
dict1 = dict(zip(list1_0,list1_1))
for each1 in dict0.keys():
    for each2 in dict1.keys():
        if (each2>each1):
            sum=sum+dict0[each1]*dict1[each2]
print(round(sum,7))
print('time used:{}'.format(time.time()-tt))

再来一个版本，思路跟上面一样，只不过是先求小于等于的情况，然后用1减去，发现速度快些，也写上

def getSixCount(n, count1):#六面骰子
   if(n<1):
           return -1
   if(n==1):
           return 0
       #初始化最初状态
   for i in range(6):
       count1[i]=1 
  
   for i in range(2,n+1):
         for sum in range(6*i,i-1,-1):
                tmp1 = count1[sum-i] if sum-i>=0 else 0 #上一阶段点数和sum-1的排列总数
                tmp2 = count1[sum-i-1] if sum-i-1>=0 else 0
                tmp3 = count1[sum-i-2] if sum-i-2>=0 else 0
                tmp4 = count1[sum-i-3] if sum-i-3>=0 else 0
                tmp5 = count1[sum-i-4] if sum-i-4>=0 else 0
                tmp6 = count1[sum-i-5] if sum-i-5>=0 else 0 
                count1[sum-i]=tmp1+tmp2+tmp3+tmp4+tmp5+tmp6
   return 0

def getFourCount(n, count2):#四面骰子
   if(n<1):
           return -1
   if(n==1):
           return 0
       #初始化最初状态
   for i in range(4):
         count2[i]=1
   for i in range(2,n+1):
         for sum in range(4*i,i-1,-1):
                tmp1 = count2[sum-i] if sum-i>=0 else 0 #上一阶段点数和sum-1的排列总数
                tmp2 = count2[sum-i-1] if sum-i-1>=0 else 0
                tmp3 = count2[sum-i-2] if sum-i-2>=0 else 0
                tmp4 = count2[sum-i-3] if sum-i-3>=0 else 0
                count2[sum-i]=tmp1+tmp2+tmp3+tmp4;
   return 0

import time
tt=time.time()
n1=6
n2=9
total1 = 6**n1
total2 = 4**n2
count1 = [0 for i in range(5*n1+1)]
count2 = [0 for i in range(3*n2+1)]
sum=0
list0_0 = [i for i in range(n1,6*n1+1)]
getSixCount(n1,count1)
list0_1 = [i/total1 for  i  in count1 ]
dict0 = dict(zip(list0_0,list0_1))
list1_0 = [ i for i in range(n2,4*n2+1)]
getFourCount(n2,count2)
list1_1 = [i/total2 for  i  in count2]
dict1 = dict(zip(list1_0,list1_1))
for each1 in dict0.keys():
    for each2 in dict1.keys():
        if (each2<=each1):
            sum=sum+dict0[each1]*dict1[each2]
print(round(1-sum,7))
print('time used:{}'.format(time.time()-tt))

shigure_takimi

# simulation
import random
def peterWin(n = 100000):
# 一次模拟让peter与colin比大小100000次，计算胜率
    count = 0
    for i in range(n):
        peter = sum([random.randint(1,4) for a in range(9)])
        colin = sum([random.randint(1,6) for a in range(6)])
        if peter > colin:
            count += 1
    return '%.7f'%(count/n)

for i in range(10):
    print(i+1, '->', peterWin())

##  模拟10次，可见peter赢的概率在57%。
##    1 -> 0.5730000
##    2 -> 0.5714700
##    3 -> 0.5744500
##    4 -> 0.5728400
##    5 -> 0.5725300
##    6 -> 0.5759700
##    7 -> 0.5724100
##    8 -> 0.5754600
##    9 -> 0.5738100
##    10 -> 0.5745400