骰子游戏

[编程题]骰子游戏

热度指数：3259 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小易参加了一个骰子游戏,这个游戏需要同时投掷n个骰子,每个骰子都是一个印有数字1~6的均匀正方体。
小易同时投掷出这n个骰子,如果这n个骰子向上面的数字之和大于等于x,小易就会获得游戏奖励。
小易想让你帮他算算他获得奖励的概率有多大。

输入描述:

输入包括两个正整数n和x(1 ≤ n < 25, 1 ≤ x < 150),分别表示骰子的个数和可以获得奖励的最小数字和。

输出描述:

输出小易可以获得奖励的概率。
如果概率为1,输出1,如果概率为0,输出0,其他以最简分数(x/y)的形式输出。

示例1

输入

3 9

输出

20/27

算法知识视频讲解

波千鸟

Goalng

package main

import (
    "fmt"
)

func gcd(a, b int) int {
    for b > 0 {
        a, b = b, a % b
    }
    return a
}

func f(n, x int) (t, m int) {
    if x <= n {
        t = 1
        m = 1
        return
    }
    if x > n * 6{
        t = 0
        m = 1
        return
    }
    s := make([][]int, n)
    for i:=0; i<n; i++ {
        s[i] = make([]int, 6*n)
        for j:=0; j < 6*n; j++ {
            s[i][j] = 0
        }
    }
    for i:=0; i<n; i++ {
        for j:=i; j < 6*i + 6; j++ {
            if i == 0{
                s[i][j] = 1
            } else {
                tmp := 0
                for k:=max(0, j - 6); k < j; k++ {
                    tmp += s[i - 1][k]
                }
                s[i][j] = tmp
            }
        }
    }

    for i:=x-1; i<6*n; i++ {
        t += s[n-1][i]
    }
    m = 1
    for i:=0; i<n; i++ {
        m = m * 6
    }
    g := gcd(t, m)
    t = t / g
    m = m / g
    return
}

func main() {
    var n, x int
    fmt.Scan(&n, &x)
    t, m := f(n, x)
    if t == 0 {
        fmt.Println(0)
    } else if t == m {
        fmt.Println(1)
    } else {
        fmt.Printf("%d/%d", t, m)
    }
}

func max(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

发表于 2021-08-17 13:56:23 回复(0)