小明参加了少年宫的一项趣味活动:每个小朋友发给一个空白的骰子(它的6个面是空白的,没有数字),要小朋友自己设计每个面写哪个数字。但有如下要求:
-
每个面只能填写 0 至 8 中的某一个数字。
-
不同面可以填写同样的数字,但6个面总和必须等于24。
填好后,小朋友可以用自己填写好数字的骰子向少年宫的两个机器人挑战----玩掷骰子游戏。规则如下:
三方同时掷出自己的骰子,如果出现任何相同的数字,则三方都不计分。
如果三方数字都不同,则最小数字一方扣 1 分,最大数字一方加 1 分。
小明看到了两个机器人手中的骰子分别是:
0 0 0 8 8 8
1 1 4 5 6 7
请你替小明算一下,他如何填写,才能使自己得分的概率最大。
请提交小明应该填写的6个数字,按升序排列,数字间用一个空格分开。
如果认为有多个答案,提交字母序最小的那个方案。
请严格按照格式,通过浏览器提交答案。
注意:只提交一行内容,含有6个被空格分开的数字。不要写其它附加内容,比如:说明性的文字。
DFS
Code
def calculateProbability():
"""
计算获胜概率
"""
global ans, maxInf
x1, x2, m = 0, 0, 0
for i in range(6):
x1, x2 = 0, 0
for j in range(6):
if ans[i] > a[j]:
x1 += 1
else:
break
for j in range(6):
if ans[i] > b[j]:
x2 += 1
else:
break
m += x1 + x2
if m > maxInf:
maxInf = m
print(ans)
def dfs(n: int, c: int, s: int):
"""
n: 骰子的六个面
c: 当前面的点数
s: 当前点数之和
"""
if s > 24:
return
if n == 6:
if s == 24:
calculateProbability()
return
for i in range(c, 9):
# 剪枝,如果剩下的所有面全部用 8 点能够满足点数之和的需求
if (5 - n) * 8 >= 24 - s - i:
ans[n] = i
dfs(n + 1, i, s + i)
ans[n] = 0
if __name__ == '__main__':
a, b = [0, 0, 0, 8, 8, 8], [1, 1, 4, 5, 6, 7]
ans, maxInf = [0] * 6, 0
dfs(0, 0, 0)