|
发表于 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))
复制代码 |
评分
-
查看全部评分
|