原文:

给定三个整数 nab ,任务是计算掷骰子恰好 n 次得到的数之和位于 ab 之间的概率。

示例:

输入: n = 1,a = 2,b = 3 输出: 0.333333 说明:掷骰子 n ( = 1)得到 2 之和的方法是 1 {2}。因此,所需概率= 1/6 = 0.33333

输入: n = 2,a = 3,b = 4 t3】输出: 0.138889

按照以下步骤解决问题:

  • 计算 ab 之间所有数字的概率并相加得到答案。
  • 调用函数 find(n,sum) 计算从 ab 每个数字的概率,其中 ab 之间的数字将作为 sum 传递。
    • 基本案例有:
      • 如果之和大于 6 * n 或小于 n ,则返回 0,因为不可能有大于 n * 6 或小于 n 的和。
      • 如果 n 等于 1 且在 1 和 6 之间,则返回 1/6。
    • 由于在每种状态下,一次掷骰子 1 到 6 中的任何一个数都可能出现,因此应该对(该状态的总和–i)进行递归调用,其中 1≤ i ≤ 6。
    • 返回合成概率。

递归调用:

下面是上述方法的实现:

c

// c   program for above approach
#include 
using namespace std;
// function to calculate the
// probability for the given
// sum to be equal to sum in
// n throws of dice
long double find(int n, int sum)
{
    // base cases
    if (sum > 6 * n || sum < n)
        return 0;
    if (n == 1) {
        if (sum >= 1 && sum <= 6)
            return 1.0 / 6;
        else
            return 0;
    }
    long double s = 0;
    for (int i = 1; i <= 6; i  )
        s = s   find(n - 1, sum - i) / 6;
    return s;
}
// driver code
int main()
{
    int n = 4, a = 13, b = 17;
    long double probability = 0.0;
    for (int sum = a; sum <= b; sum  )
        probability = probability   find(n, sum);
    // print the answer
    cout << fixed << setprecision(6) << probability;
    return 0;
}

java 语言(一种计算机语言,尤用于创建网站)

// java program for the above approach
import java.util.*;
class gfg
{
// function to calculate the
// probability for the given
// sum to be equal to sum in
// n throws of dice
static double find(int n, int sum)
{
    // base cases
    if (sum > 6 * n || sum < n)
        return 0;
    if (n == 1)
    {
        if (sum >= 1 && sum <= 6)
            return 1.0 / 6;
        else
            return 0;
    }
    double s = 0;
    for (int i = 1; i <= 6; i  )
        s = s   find(n - 1, sum - i) / 6;
    return s;
}
// driver code
public static void main(string[] args)
{
    int n = 4, a = 13, b = 17;
    double probability = 0.0;
    for (int sum = a; sum <= b; sum  )
        probability = probability   find(n, sum);
    // print the answer
    system.out.format("%.6f", probability);
}
}
// this code is contributed by code_hunt.

python 3

# python 2 program for above approach
# function to calculate the
# probability for the given
# sum to be equal to sum in
# n throws of dice
def find(n, sum):
    # base cases
    if (sum > 6 * n or sum < n):
        return 0
    if (n == 1):
        if (sum >= 1 and sum <= 6):
            return 1.0 / 6
        else:
            return 0
    s = 0
    for i in range(1, 7):
        s = s   find(n - 1, sum - i) / 6
    return s
# driver code
if __name__ == "__main__":
    n = 4
    a = 13
    b = 17
    probability = 0.0
    for sum in range(a, b   1):
        probability = probability   find(n, sum)
    # print the answer
    print(round(probability, 6))
    # this code is contributed by chitranayal.

c

// c# program for the above approach
using system;
class gfg
{
    // function to calculate the
    // probability for the given
    // sum to be equal to sum in
    // n throws of dice
    static double find(int n, int sum)
    {
        // base cases
        if (sum > 6 * n || sum < n)
            return 0;
        if (n == 1)
        {
            if (sum >= 1 && sum <= 6)
                return 1.0 / 6;
            else
                return 0;
        }
        double s = 0;
        for (int i = 1; i <= 6; i  )
            s = s   find(n - 1, sum - i) / 6;
        return s;
    }
  // driver code
  static void main()
  {
    int n = 4, a = 13, b = 17;
    double probability = 0.0;
    for (int sum = a; sum <= b; sum  )
        probability = probability   find(n, sum);
    // print the answer
    console.writeline(math.round(probability,6));
  }
}
// this code is contributed by divyeshrabadiya07

java 描述语言


output: 

0.505401

时间复杂度:o((b- a 1)6n) t8】辅助空间: o(1)

动态规划法:上述递归法需要通过处理以下和进行优化:

n = 4 且和=15 的部分递归树:

对于每个状态,对于其他 6 个状态重复出现,因此 f(n,sum) 的递归定义为:

自上而下的方法:

c

// c   program for above approach
#include 
using namespace std;
float dp[105][605];
// function to calculate the
// probability for the given
// sum to be equal to sum in
// n throws of dice
float find(int n, int sum)
{
    if (dp[n][sum])
        return dp[n][sum];
    // base cases
    if (sum > 6 * n || sum < n)
        return 0;
    if (n == 1) {
        if (sum >= 1 && sum <= 6)
            return 1.0 / 6;
        else
            return 0;
    }
    for (int i = 1; i <= 6; i  )
        dp[n][sum] = dp[n][sum]
                       find(n - 1, sum - i) / 6;
    return dp[n][sum];
}
// driver code
int main()
{
    int n = 4, a = 13, b = 17;
    float probability = 0.0;
    // calculate probability of all
    // sums from a to b
    for (int sum = a; sum <= b; sum  )
        probability = probability   find(n, sum);
    // print the answer
    cout << fixed << setprecision(6) << probability;
    return 0;
}

java 语言(一种计算机语言,尤用于创建网站)

// java program for above approach
class gfg
{
    static float[][] dp = new float[105][605];
    // function to calculate the
    // probability for the given
    // sum to be equal to sum in
    // n throws of dice
    static float find(int n, int sum)
    {
        if (n < 0 | sum < 0)
            return 0;
        if (dp[n][sum] > 0)
            return dp[n][sum];
        // base cases
        if (sum > 6 * n || sum < n)
            return 0;
        if (n == 1) {
            if (sum >= 1 && sum <= 6)
                return (float) (1.0 / 6);
            else
                return 0;
        }
        for (int i = 1; i <= 6; i  )
            dp[n][sum] = dp[n][sum]   find(n - 1, sum - i) / 6;
        return dp[n][sum];
    }
    // driver code
    public static void main(string[] args)
    {
        int n = 4, a = 13, b = 17;
        float probability = 0.0f;
        // calculate probability of all
        // sums from a to b
        for (int sum = a; sum <= b; sum  )
            probability = probability   find(n, sum);
        // print the answer
        system.out.printf("%.6f", probability);
    }
}
// this code is contributed by shikhasingrajput

python 3

# python program for above approach
dp = [[0 for i in range(605)] for j in range(105)];
# function to calculate the
# probability for the given
# sum to be equal to sum in
# n throws of dice
def find(n, sum):
    if (n < 0 | sum < 0):
        return 0;
    if (dp[n][sum] > 0):
        return dp[n][sum];
    # base cases
    if (sum > 6 * n or sum < n):
        return 0;
    if (n == 1):
        if (sum >= 1 and sum <= 6):
            return (float)(1.0 / 6);
        else:
            return 0;
    for i in range(1,7):
        dp[n][sum] = dp[n][sum]   find(n - 1, sum - i) / 6;
    return dp[n][sum];
# driver code
if __name__ == '__main__':
    n = 4; a = 13; b = 17;
    probability = 0.0
    f = 0;
    # calculate probability of all
    # sums from a to b
    for sum in range(a,b 1):
        probability = probability   find(n, sum);
    # print the answer
    print("%.6f"% probability);
# this code is contributed by 29ajaykumar

c

// c# program for above approach
using system;
using system.collections.generic;
public class gfg
{
  static float[,] dp = new float[105, 605];
  // function to calculate the
  // probability for the given
  // sum to be equal to sum in
  // n throws of dice
  static float find(int n, int sum)
  {
    if (n < 0 | sum < 0)
      return 0;
    if (dp[n, sum] > 0)
      return dp[n, sum];
    // base cases
    if (sum > 6 * n || sum < n)
      return 0;
    if (n == 1) {
      if (sum >= 1 && sum <= 6)
        return (float) (1.0 / 6);
      else
        return 0;
    }
    for (int i = 1; i <= 6; i  )
      dp[n, sum] = dp[n, sum]   find(n - 1, sum - i) / 6;
    return dp[n, sum];
  }
  // driver code
  public static void main(string[] args)
  {
    int n = 4, a = 13, b = 17;
    float probability = 0.0f;
    // calculate probability of all
    // sums from a to b
    for (int sum = a; sum <= b; sum  )
      probability = probability   find(n, sum);
    // print the answer
    console.write("{0:f6}", probability);
  }
}
// this code is contributed by 29ajaykumar

java 描述语言


output: 

0.505401

时间复杂度:o(n 和) 辅助空间:o(n 和)

自下而上的方法:

c

// c   program for above approach
#include 
using namespace std;
float dp[105][605];
// function to calculate probability
// that the sum of numbers on n throws
// of dice lies between a and b
float find(int n, int a, int b)
{
    float probability = 0.0;
    // base case
    for (int i = 1; i <= 6; i  )
        dp[1][i] = 1.0 / 6;
    for (int i = 2; i <= n; i  ) {
        for (int j = i; j <= 6 * i; j  ) {
            for (int k = 1; k <= 6; k  ) {
                dp[i][j] = dp[i][j]
                             dp[i - 1][j - k] / 6;
            }
        }
    }
    // add the probability for all
    // the numbers between a and b
    for (int sum = a; sum <= b; sum  )
        probability = probability   dp[n][sum];
    return probability;
}
// driver code
int main()
{
    int n = 4, a = 13, b = 17;
    float probability = find(n, a, b);
    // print the answer
    cout << fixed << setprecision(6) << probability;
    return 0;
}

java 语言(一种计算机语言,尤用于创建网站)

// java program for above approach
import java.util.*;
class gfg{
static float [][]dp = new float[105][605];
// function to calculate probability
// that the sum of numbers on n throws
// of dice lies between a and b
static float find(int n, int a, int b)
{
    float probability = 0.0f;
    // base case
    for (int i = 1; i <= 6; i  )
        dp[1][i] = (float) (1.0 / 6);
    for (int i = 2; i <= n; i  )
    {
        for (int j = i; j <= 6 * i; j  )
        {
            for (int k = 1; k <= 6 && k <= j; k  )
            {
                dp[i][j] = dp[i][j]
                             dp[i - 1][j - k] / 6;
            }
        }
    }
    // add the probability for all
    // the numbers between a and b
    for (int sum = a; sum <= b; sum  )
        probability = probability   dp[n][sum];
    return probability;
}
// driver code
public static void main(string[] args)
{
    int n = 4, a = 13, b = 17;
    float probability = find(n, a, b);
    // print the answer
    system.out.printf("%.6f",probability);
}
}
// this codeis contributed by shikhasingrajput

python 3

# python3 program for above approach
dp = [[0 for i in range(605)] for j in range(105)]
# function to calculate probability
# that the sum of numbers on n throws
# of dice lies between a and b
def find(n, a, b) :
    probability = 0.0
    # base case
    for i in range(1, 7) :
        dp[1][i] = 1.0 / 6
    for i in range(2, n   1) :
        for j in range(i, (6*i)   1) :
            for k in range(1, 7) :
                dp[i][j] = dp[i][j]   dp[i - 1][j - k] / 6
    # add the probability for all
    # the numbers between a and b
    for sum in range(a, b   1) :
        probability = probability   dp[n][sum]
    return probability
n, a, b = 4, 13, 17
probability = find(n, a, b)
# print the answer
print('%.6f'%probability)
# this code is contributed by divyesh072019.

c

// c# program for above approach
using system;
public class gfg
{
static float [,]dp = new float[105, 605];
// function to calculate probability
// that the sum of numbers on n throws
// of dice lies between a and b
static float find(int n, int a, int b)
{
    float probability = 0.0f;
    // base case
    for (int i = 1; i <= 6; i  )
        dp[1, i] = (float) (1.0 / 6);
    for (int i = 2; i <= n; i  )
    {
        for (int j = i; j <= 6 * i; j  )
        {
            for (int k = 1; k <= 6 && k <= j; k  )
            {
                dp[i, j] = dp[i, j]
                             dp[i - 1, j - k] / 6;
            }
        }
    }
    // add the probability for all
    // the numbers between a and b
    for (int sum = a; sum <= b; sum  )
        probability = probability   dp[n, sum];
    return probability;
}
// driver code
public static void main(string[] args)
{
    int n = 4, a = 13, b = 17;
    float probability = find(n, a, b);
    // print the answer
    console.write("{0:f6}",probability);
}
}
// this code is contributed by shikhasingrajput

java 描述语言


output: 

0.505401

时间复杂度: o(n 和) 辅助空间: o(n 和)