[已解决]Python：每日一题 261

zltzlt · 发表于 2019-10-22 20:32:23

今天的题目难度有点大，请大家认真思考

今天的题目：

扔 n 个骰子，向上面的数字之和为 S。给定 n，请列出所有可能的 S 值及其相应的概率。

示例 1：

输入：n = 1
输出：[[1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]
解释：掷一次骰子，向上的数字和可能为1,2,3,4,5,6，出现的概率均为 0.17。

示例 2：

输入：n = 2
输出：[[2,0.03],[3,0.06],[4,0.08],[5,0.11],[6,0.14],[7,0.17],[8,0.14],[9,0.11],[10,0.08],[11,0.06],[12,0.03]]
解释：掷两次骰子，向上的数字和可能在[2,12]，出现的概率是不同的。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Unicorn#

2019-10-22 20:32:24

本帖最后由 Unicorn# 于 2019-10-23 21:12 编辑

zltzlt 发表于 2019-10-23 20:08
输入：1
输出：[[1,0.17],[1,0.17],[1,0.17],[1,0.17],[1,0.17],[1,0.17]]
预期结果：[[1,0.17],[2,0.1 ...

哈哈哈哈哈哈我傻了
index函数只会返回它找到的第一个索引值
改了下

def possibility(n):
f = []
for i in range(n+1):
f.append([])
for j in range(6*n+1):
f[i].append(0)
f[0][0] = 1
for var_n in range(1, n+1):
for var_s in range(var_n, 6*var_n+1):
for i in range(1, 7):
f[var_n][var_s] += f[var_n-1][var_s-i]
ans = []
full = 6**n
print(f)
for i in range(n,len(f[n])):
ans.append([i, float(f[n][i])/full])
print(ans)

复制代码

跳转到最佳答案楼层

Unicorn# · 发表于 2019-10-22 20:32:24

这个最佳答案由 Unicorn# 给出，感谢 Unicorn# 的回答。

单击隐藏图章

本帖最后由 Unicorn# 于 2019-10-23 21:12 编辑

zltzlt 发表于 2019-10-23 20:08
输入：1
输出：[[1,0.17],[1,0.17],[1,0.17],[1,0.17],[1,0.17],[1,0.17]]
预期结果：[[1,0.17],[2,0.1 ...

哈哈哈哈哈哈我傻了
index函数只会返回它找到的第一个索引值
改了下

def possibility(n):
f = []
for i in range(n+1):
f.append([])
for j in range(6*n+1):
f[i].append(0)
f[0][0] = 1
for var_n in range(1, n+1):
for var_s in range(var_n, 6*var_n+1):
for i in range(1, 7):
f[var_n][var_s] += f[var_n-1][var_s-i]
ans = []
full = 6**n
print(f)
for i in range(n,len(f[n])):
ans.append([i, float(f[n][i])/full])
print(ans)

复制代码

冬雪雪冬 · 发表于 2019-10-22 20:56:58

def fun(n):
import itertools as it
list1 = [1, 2, 3, 4, 5, 6]
list2 = []
for i in it.product(*([list1] * n)):
list2.append(sum(i))
list3 = []
for i in range(1 * n, 6 * n +1):
list3.append([i, list2.count(i) / len(list2)])
return list3

复制代码

zltzlt · 发表于 2019-10-22 20:59:57

冬雪雪冬发表于 2019-10-22 20:56

输入 8 超时

Unicorn# · 发表于 2019-10-22 21:26:59

本帖最后由 Unicorn# 于 2019-10-23 17:07 编辑

最终版 dp

def possibility(n):
f = []
for i in range(n+1):
f.append([])
for j in range(6*n+1):
f[i].append(0)
f[0][0] = 1
for var_n in range(1, n+1):
for var_s in range(var_n, 6*var_n+1):
for i in range(1, 7):
f[var_n][var_s] += f[var_n-1][var_s-i]
ans = []
full = 6**n
for each in f[n][n:]:
ans.append([f[n].index(each),float(each)/full])
print(ans)

复制代码

danteer · 发表于 2019-10-22 22:10:15

def func(n):
if n == 0:
return []
else:
a = n
result = {}
for i in range(1,6*n+1):
result[i] = 0
result[1] = 1/6
result[2] = 1/6
result[3] = 1/6
result[4] = 1/6
result[5] = 1/6
result[6] = 1/6
while n > 1:
for i in range(a-n+1,6*(a-n+1)+1):
for j in range(1,7):
result[i+j] += 1/(6**(a-n+2))
result[i] -= 1/(6**(a-n+2))
n -= 1
for i in range(1,a):
result[i] = 0
list1 = []
for each in result:
if result[each] != 0:
list1.append([each,result[each]])
return list1

复制代码

这是纯粹拿浮点数算的，可能后面几位数字就不大对了。不过今天没空改上去了。
超时警报

Unicorn# · 发表于 2019-10-22 22:13:39

本帖最后由 Unicorn# 于 2019-10-22 22:23 编辑

我我我又来辽
想到可以用DP
哈哈哈以前机竞的内容还能用

def probility_2(n):
f = []
for i in range(n+1):
f.append([])
for j in range(6*n+1):
f[i].append(0)
for i in range(n+1):
f[i][i] = 1
for var_n in range(1, n+1):
for var_s in range(var_n, 6*var_n+1):
for i in range(1, 7):
f[var_n][var_s] += f[var_n-1][var_s-i]
ans = []
full = 6**n
for each in f[n][n:]:
ans.append([f[n].index(each),each/full])
print(ans)

复制代码

！！！！一百个骰子只要3.591205358505249秒
哈哈哈哈哈哈
我太聪明了

panheng · 发表于 2019-10-22 22:18:07

import itertools
def answer(num: int, ndigits=2):
res = []
list1 = [sum(i) for i in list(itertools.product([1, 2, 3, 4, 5, 6], repeat=num))]
min, max = num, num * 6
z = len(list1)
for i in range(min, max + 1):
temp = [i, round(list1.count(i) / z, ndigits)]
if temp not in res:
res.append(temp)
return res

复制代码

wisky · 发表于 2019-10-22 22:19:05

def deal(N, s):
if N< 1 or s < N or s > 6 * N:
return 0
elif N == 1:
return 1
else:
resCount = 0 # 骰子的点数之和
resCount = deal(N - 1, s - 1) + deal(N - 1, s - 2) + deal(N - 1, s - 3) + deal(N - 1, s - 4) + deal(N - 1,s - 5) + deal(N - 1, s - 6) #递归调用，速度比循环要慢，但是代码好懂
return resCount
N = int(input('请输入骰子个数:')) # N个骰子
# 输出结果
result = []
for s in range(N, 6 * N + 1):
N_sum_list = []
resCount = deal(N, s)
p = round(float(resCount) / (pow(6, N)), 2) #点数出现的概率
N_sum_list.append(s)
N_sum_list.append(p)
if N_sum_list:
result.append(N_sum_list)
print(result)

复制代码

战场原 · 发表于 2019-10-22 22:25:37

def solution(n: int) -> list:
import collections
count = 6**n
res = list()
tmp = 0
dfs(tmp, n, res)
mydict = collections.Counter(res)
res2 = list()
for i in mydict:
      res2.append([i, format(mydict[i]/count, '.2f')])
return res2

def dfs(tmp: int, n: int, res: list):
if n == 0:
      res.append(tmp)
      return
for i in range(1,7):
      dfs(tmp+i, n-1, res)

战场原 · 发表于 2019-10-22 22:40:09

本帖最后由战场原于 2019-10-23 00:07 编辑

Unicorn# 发表于 2019-10-22 22:13
我我我又来辽
想到可以用DP
哈哈哈以前机竞的内容还能用

666, 用dfs，跑100个骰子感觉电脑都要炸了...

wsttlj1985 · 发表于 2019-10-22 22:54:13

我想问一下，第二版的python有视频吗？

阴阳神万物主 · 发表于 2019-10-22 23:27:19

本帖最后由阴阳神万物主于 2019-10-22 23:35 编辑

数学是个很好的工具，这里我使用概率学的古典概型
毕竟，满足古典概型的特性：
1.所有可能出现的基本事件只有有限个
2.每个基本事件出现的可能性相等
基本事件：1个骰子扔出某个点数

def solve(n:'int > 0')->list:
base = dict()
for i in range(1,7):
base[i] = 1/6
old = dict()
while n:
if old:
new = dict()
for befor in old:
for add in base:
t_sum = befor + add
if t_sum in new:
new[t_sum] += old[befor] * base[add] #分类求和
else:
new[t_sum] = old[befor] * base[add] #分步求积
old = new
else:
old = base
n -= 1
index = list(old)
index.sort()
#限定小数位数的输出
#return [[each,float('%0.2f'%old[each])] for each in index]
#不限定的
return [[each,old[each]] for each in index]
if __name__ == '__main__':
print('示例1 输出：', solve(1))
print('示例2 输出：', solve(2))
print('测试大数据输出：', solve(20))#概率限制两位小数的话，会出现好多0.0

复制代码

阴阳神万物主 · 发表于 2019-10-22 23:48:57

Unicorn# 发表于 2019-10-22 22:13
我我我又来辽
想到可以用DP
哈哈哈以前机竞的内容还能用

嘿嘿，要4秒啊。（掩藏不住心中暗暗的窃喜

）我的一秒都不要就能出结果呢，就是显示时要卡一下。

阴阳神万物主 · 发表于 2019-10-22 23:49:57

wsttlj1985 发表于 2019-10-22 22:54
我想问一下，第二版的python有视频吗？

有的，就是还在更新中

Unicorn# · 发表于 2019-10-23 00:04:06

阴阳神万物主发表于 2019-10-22 23:48
嘿嘿，要4秒啊。（掩藏不住心中暗暗的窃喜）我的一秒都不要就能出结果呢，就是显示时要卡一下 ...

3.813218116760254秒
我赢了

Unicorn# · 发表于 2019-10-23 00:12:01

阴阳神万物主发表于 2019-10-22 23:48
嘿嘿，要4秒啊。（掩藏不住心中暗暗的窃喜）我的一秒都不要就能出结果呢，就是显示时要卡一下 ...

这里是你的代码，加了时间测试
100个骰子列出所有情况，多次测试用时：
4.710269451141357
4.990285634994507
4.661266565322876
3.601206064224243
4.434253454208374
4.696268558502197
平均用时：4.265958343233381秒
DP万岁

def solve(n:'int > 0')->list:
base = dict()
for i in range(1,7):
base[i] = 1/6
old = dict()
while n:
if old:
new = dict()
for befor in old:
for add in base:
t_sum = befor + add
if t_sum in new:
new[t_sum] += old[befor] * base[add] #分类求和
else:
new[t_sum] = old[befor] * base[add] #分步求积
old = new
else:
old = base
n -= 1
index = list(old)
index.sort()
#限定小数位数的输出
#return [[each,float('%0.2f'%old[each])] for each in index]
#不限定的
return [[each,old[each]] for each in index]
import time
if __name__ == '__main__':
start = time.time()
print(solve(100))
end = time.time()
print(end - start)

复制代码

wsttlj1985 · 发表于 2019-10-23 00:12:05

这更新的时间也太长了吧？

wsttlj1985 · 发表于 2019-10-23 00:13:11

我想知道，讲不讲WEB方面的

Unicorn# · 发表于 2019-10-23 00:35:50

战场原发表于 2019-10-22 22:40
666, 用dfs，跑100个骰子感觉电脑都要炸了...

DP也可以用dfs+剪枝代替嘛...
不过那也太复杂了

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

[已解决]Python：每日一题 261

最佳答案

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

浏览过的版块