小练习：20170814 骰子游戏

冬雪雪冬 · 发表于 2017-8-13 19:33:57

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由冬雪雪冬于 2017-8-21 16:52 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：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 · 发表于 2017-8-14 08:37:32

本帖最后由 jerryxjr1220 于 2017-8-14 08:55 编辑

这题完全可以借助强大的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 · 发表于 2017-8-14 09:40:39

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

夏天和大熊 · 发表于 2017-8-14 15:06:53

本帖最后由夏天和大熊于 2017-8-18 15:08 编辑

结果是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()

复制代码

运维小书童 · 发表于 2017-8-16 17:32:51

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())

复制代码

小剑剑 · 发表于 2017-8-17 10:07:40

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

达锅 · 发表于 2017-8-18 00:41:23

我的答案：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)

复制代码

参考依据：

撒法空间 · 发表于 2017-8-18 01:22:34

本帖最后由撒法空间于 2017-8-18 01:47 编辑

#!/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 · 发表于 2017-8-18 03:40:29

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

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 · 发表于 2017-8-18 10:36:27

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 · 发表于 2017-8-18 11:48:48

本帖最后由 chunchun2017 于 2017-8-18 12:27 编辑

答案为：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 · 发表于 2018-2-24 13:19:14

# 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

复制代码

账号		自动登录	找回密码
密码			立即注册

[技术交流] 小练习：20170814 骰子游戏

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分

评分