鱼C论坛

 找回密码
 立即注册
查看: 20|回复: 0

[学习笔记] c++刷剑指offer(面试题60. n个骰子的点数)

[复制链接]
最佳答案
0 
发表于 7 天前 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 糖逗 于 2020-3-26 14:17 编辑

题目描述:面试题60. n个骰子的点数

  1. 把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。

  2.  

  3. 你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

  4.  

  5. 示例 1:

  6. 输入: 1
  7. 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
  8. 示例 2:

  9. 输入: 2
  10. 输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
  11.  

  12. 限制:

  13. 1 <= n <= 11
复制代码
  1. #include <vector>
  2. #include <math.h>
  3. #include<iostream>

  4. using namespace std;

  5. vector<double> solution(int input){
  6.         vector<double> result;
  7.         int dp[input][6*input] = {0};
  8.         for(int i = 0; i < 6; i++){
  9.                 dp[0][i] = 1;
  10.         }
  11.         for(int i = 1; i < input; i++){
  12.                 for(int j = 0; j < input * 6; j++){
  13.                         for(int k = 1; k <= 6; k++){
  14.                                 if(j - k < 0) break;
  15.                                 dp[i][j] += dp[i-1][j-k];
  16.                         }
  17.                 }
  18.         }
  19.         int total = pow(6, input);
  20.         for(int i = input - 1; i < 6*input; i++){
  21.                 result.push_back(dp[input-1][i] * 1.0 / total);
  22.         }
  23.         return result;
  24.          
  25. }

  26. int main(void){
  27.         int input;
  28.         cout << "send a number" << endl;
  29.         cin >> input;
  30.        
  31.         vector<double> result;
  32.         result = solution(input);
  33.         for(int i = 0; i < result.size(); i++){
  34.                 cout << result[i] << " ";
  35.         }
  36.         cout << endl;
  37.         return 0;
  38. }
复制代码


注意:
1.动态规划的思路
(1)确定状态
(2)确定状态转移矩阵
(3)确定边界
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2020-4-2 00:34

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表