V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
zhangfa0x11
V2EX  ›  问与答

求解一个算法,使用 go 程序实现

  •  
  •   zhangfa0x11 · 351 天前 · 1173 次点击
    这是一个创建于 351 天前的主题,其中的信息可能已经有所发展或是发生改变。

    1.给定一个正整数 n(n>5 )随机分成 5 个随机数(正整数), 2.每个随机数必须小于 m(m<n), 3.并且 5 个随机数之和等于 n ,

    重点:随机数不可以大于 m ,和必须等于 n

    13 条回复    2023-07-06 11:24:08 +08:00
    stevenshuang
        1
    stevenshuang  
       351 天前
    🐶把所有的情况算出来,然后随机选择

    ```go
    package main

    import "fmt"

    func solution(n, sum, depth int, path []int, ans *[][]int) {
    if depth == 0 {
    if sum == 0 {
    dst := make([]int, len(path))
    copy(dst, path)
    *ans = append(*ans, dst)
    }
    return
    }

    for i := 1; i < n; i++ {
    solution(n, sum-i, depth-1, append(path, i), ans)
    }
    }
    func main() {
    n := 6
    ans := make([][]int, 0)
    solution(n, n, 5, []int{}, &ans)
    for _, item := range ans {
    fmt.Printf("solution: %v\n", item)
    }
    }
    ```

    solution: [1 1 1 1 2]
    solution: [1 1 1 2 1]
    solution: [1 1 2 1 1]
    solution: [1 2 1 1 1]
    solution: [2 1 1 1 1]
    zhangfa0x11
        2
    zhangfa0x11  
    OP
       351 天前
    这个时间有点久,最后需要 5 个随机数就可以,比如 1000 ,分成不大于 300 的 5 个随机数,和等于 1000
    cloudyi666
        3
    cloudyi666  
       351 天前
    chatgpt 的答案
    package main

    import (
    "fmt"
    "math/rand"
    "time"
    )

    func main() {
    rand.Seed(time.Now().UnixNano()) // 设置随机数种子

    n := 10 // 给定的正整数 n
    m := 4 // 每个随机数必须小于 m

    nums := make([]int, 5) // 存储随机数的切片

    for i := 0; i < len(nums); i++ {
    if i == len(nums)-1 { // 最后一个随机数直接使用剩余的 n
    nums[i] = n
    } else {
    max := n - (len(nums)-i-1)*1 // 计算当前随机数最大值
    if max > m { // 如果最大值超过了 m ,则将其设置为 m
    max = m
    }
    nums[i] = rand.Intn(max) + 1 // 随机生成当前随机数
    n -= nums[i] // 减去已经生成的随机数
    }
    }

    fmt.Println(nums)
    }
    leonshaw
        4
    leonshaw  
       351 天前
    没有概率分布要求?
    AItsuki
        5
    AItsuki  
       351 天前
    ```golang
    func main() {
    if len(os.Args) != 2 {
    log.Fatalln("Args count error")
    }

    n, err := strconv.Atoi(os.Args[1])
    if err != nil {
    log.Fatalf("Args format error: %v\n", err)
    }

    if n <= 5 {
    log.Fatalln("N must be greater than 5")
    }

    result := fiveRandomNumber(n)
    sum := 0
    for _, v := range result {
    sum += v
    }
    fmt.Printf("result = %v, sum = %v\n", result, sum)
    }

    func fiveRandomNumber(n int) []int {
    results := make([]int, 5)
    for i := 0; i < 4; i++ {
    max := n - 4 + i
    x := rand.Intn(max) + 1
    results[i] = x
    n -= x
    }
    results[4] = n
    return results
    }
    ```

    ```shell
    go run . 1000000000
    result = [111902874 389879172 249550111 192568957 56098886], sum = 1000000000
    ```
    zhangfa0x11
        6
    zhangfa0x11  
    OP
       351 天前
    可以的感谢各位
    yougg
        7
    yougg  
       351 天前   ❤️ 1
    第一种 n 越大就越趋向于平均分布
    第二种分布更加随机

    ```go
    func main() {
    res, err := rand5alpha(666, 1000)
    fmt.Println(res, err)
    res, err = rand5beta(666, 1000)
    fmt.Println(res, err)
    }

    func rand5alpha(m, n int) (*[5]int, error) {
    if n < 5 || m >= n || m*5 < n {
    return nil, errors.New("invalid input number")
    }

    var res [5]int
    var tmp = res[:]
    var tmpLen = len(tmp)
    for i := 0; i < n; i++ {
    index := rand.Intn(tmpLen)
    if tmp[index] >= m {
    if index != tmpLen-1 {
    tmp[index], tmp[tmpLen-1] = tmp[tmpLen-1], tmp[index]
    }
    tmp = tmp[:tmpLen-1]
    tmpLen = len(tmp)
    index = rand.Intn(tmpLen)
    }
    res[index]++
    }
    return &res, nil
    }

    func rand5beta(m, n int) (*[5]int, error) {
    if n < 5 || m >= n || m*5 < n {
    return nil, errors.New("invalid input number")
    }

    var res [5]int
    var tmp = res[:]
    var tmpLen = len(tmp)
    var step int
    for n > 0 {
    index := rand.Intn(tmpLen)
    if tmp[index] >= m {
    if index != tmpLen-1 {
    tmp[index], tmp[tmpLen-1] = tmp[tmpLen-1], tmp[index]
    }
    tmp = tmp[:tmpLen-1]
    tmpLen = len(tmp)
    index = rand.Intn(tmpLen)
    }
    space := m - res[index]
    var r int
    if space < n {
    r = rand.Intn(space)+1
    } else {
    r = rand.Intn(n)+1
    }
    step = rand.Intn(r)+1
    res[index] += step
    n -= step
    }
    return &res, nil
    }
    ```
    iOCZ
        8
    iOCZ  
       351 天前
    m 应该大于 n/5
    zhangfa0x11
        9
    zhangfa0x11  
    OP
       351 天前
    对 m 大于 n/5 ,速度越快越好
    yxd19
        10
    yxd19  
       350 天前
    输入:正整数 m, n, k 。要求输出数组 a ,a 有 k 个元素,每个元素都\leq m ,和为 n 。

    假设 a[i] = m - b[i],则 b[i]之和为 mk - n 。在[0, mk-n]上随机生成 k-1 个正整数并排序,设为 c[i],令 b[i] = c[i] - c[i-1],其中 c[-1]=0, c[k-1]=mk-n ,a[i] = m-b[i]即可。不会写 go 。
    LLaMA2
        11
    LLaMA2  
       350 天前
    1.一个>5 的正整数 n 随机分成 5 个随机正整数,
    2.每个随机数必须小于 m(m<n && m > n/5)
    3.并且 5 个随机数之和等于 n

    总结了一下,题目有点问题

    加入 n=6 则 n/5=1.2
    那么 m=[2,3,4]
    如取 m=3 或 m=4 则无法完成步骤 3
    zihuyishi
        12
    zihuyishi  
       350 天前
    这个需求看起来好眼熟是,这是要实现开箱子抽卡的功能么?
    zhangfa0x11
        13
    zhangfa0x11  
    OP
       350 天前
    @zihuyishi 突然奇想,一个初中的题吧应该
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5046 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 08:27 · PVG 16:27 · LAX 01:27 · JFK 04:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.