首页 > 试题广场 >

K点游戏

[编程题]K点游戏
  • 热度指数:2474 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小招喵某日闲来无事,想验一下自己的人品,于是给自己定了一个游戏规则:
这个游戏有三个因素:N,K,W
游戏开始的时候小招喵有0点,之后如果发现自己手上的点不足K点,就随机从1到W的整数中抽取一个(包含1和W),抽到哪个数字的概率都是相同的。
重复上述过程,直到小招喵获得了K或者大于K点,就停止获取新的点,这时候小招喵手上的点小于等于N的概率是多少?

输入:N = 5, K = 1, W = 5
输出:1.00000
说明:开始有0点,不足1点,从[1,5]中随机取一个整数(一共5个数字,所以每个数字取到的概率都是1/5),获得后得分无论如何都大于了1点,停止,概率为1

输入:N = 6, K = 1, W = 10
输出:0.60000
说明:开始有0点,不足1点,从[1,10]中随机取一个整数(一共10个数字,所以每个数字取到的概率都是1/10),获得后有6/10的概率小于6点,且满足大于1点的条件,概率为0.6

输入描述:
输入为3个整数,分别对应N,K,W,中间用空格隔开

其中0 <= K <= N <= 10000,1 <= W <= 10000


输出描述:
输出为概率值,保留5位小数
示例1

输入

21 17 10

输出

0.73278
头像 牛客题解官
发表于 2020-06-05 15:15:29
精华题解 题目难度:三星 考察点:动态规划、前缀和 方法1:动态规划 1.分析: 这个题其实可以采用动态规划的思想来做,我们设 dp[n] 表示的是当前点数为 n 的概率,如果不考虑 K 的话,那么就有dp[n]的 展开全文
头像 岩之痕
发表于 2019-08-25 22:25:36
题目 输入:N, K, W输出:从0点开始每次增加[1, W]的随机数,直到大于等于K点。问最终点数小于等于N的概率。 符号定义: A[start, end) = A[start] + A[start+1] + ... + A[end - 1]A[start, end] = A[start] + A 展开全文