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

请教一个随机抽题问题

  •  
  •   ydpro · 2021-09-13 09:18:00 +08:00 · 1520 次点击
    这是一个创建于 1179 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题库中有 N 条是数据 有一个总分,可以随意设置(例:100 分) 有一个题目数量,可以随意设置(例:20 个) 如何实现从题库中随机抽 20 道题,这 20 道题总分满足 100 ? 有什么比较好的解法,求推荐!!

    26 条回复    2021-09-13 16:10:19 +08:00
    murmur
        1
    murmur  
       2021-09-13 09:20:57 +08:00   ❤️ 1
    需求不合理,建议拿需求出来,一般的考卷是成组出题的,填空、选择、计算这样,只要分组确定了,每一组题目的分值也是确定的

    不要为了提问随随便便想需求,直接把具体场景抛出来说
    jiangboenoch
        2
    jiangboenoch  
       2021-09-13 09:43:56 +08:00   ❤️ 1
    @murmur 这不应该是个算法题吗,为啥谈需求。n 个随机自然数(>=20),随机从 n 中取出 20 个数,要求 20 个数返回的和刚好等于 100,如果所有的排列组合都不满足和等于 100,返回 false 。PS:拓展--要求对每个不同组合进行计数
    murmur
        3
    murmur  
       2021-09-13 09:46:20 +08:00
    @jiangboenoch 需求和算法是有区别的,考试不仅要分数加起来满足总值,还要考点覆盖当前考纲或者是特定章节内容

    一个考试 150 分,全出计算题和实验题这样的主观题,然后每个题的分值不能调整,我倒是想见识下什么考试这么智障

    实际上算法不需要按背包那样装满 100 分,比如我装满了 102 分,但是最后一道题是难度系数报表,那很简单,最后一个题从 9 分改成 7 分就可以了
    ydpro
        4
    ydpro  
    OP
       2021-09-13 09:46:34 +08:00
    @murmur 具体场景:从题库中随机抽取指定题目,这些题目分数加起来满足用户指定的总分
    背景:
    用户可以设置题库
    用户可以指定随机抽题的题目数量
    用户可以指定随机抽题题目数量的总分是多少

    场景描述:
    后台有一个数据表,用户输入的题目会保存在表中,每道题目都有标题,选项,分数
    用户要从题库中抽取 N(比如 20)道题,这 N 道题分数加起来要满足用户指定的总分(比如 100 分),请问有什么比较好的解法吗?
    Anshi
        5
    Anshi  
       2021-09-13 09:47:21 +08:00
    这不是典型的 two sum 问题么。。。。先算出分数组合,再随机抽题目
    ydpro
        6
    ydpro  
    OP
       2021-09-13 09:47:28 +08:00
    @jiangboenoch 对,请问有什么比较好的解法吗?
    maplerecall
        7
    maplerecall  
       2021-09-13 09:56:20 +08:00 via Android
    简单的思路:按分值和题数 dfs 出若干组合,随机抽一种组合,再随机每个分值对应的题目
    jiangboenoch
        8
    jiangboenoch  
       2021-09-13 09:59:58 +08:00   ❤️ 1
    @Anshi #5 细想了下,还真不一样,首先这个题不能去重,因为可以满足 32212=10 的情况,

    而且穷举所有的排列组合,已知单个数最大是 81 最小是 1,所有的排列组合先穷举出来。可能没有 80²º,但是先穷举不可取。

    我的方案是组合进行排序,然后单指针循环组合。
    将题库的分值进行计数,当组合递归到计数结束时,结束循环。
    murmur
        9
    murmur  
       2021-09-13 10:00:05 +08:00
    @Anshi 这就是问题所在了,如果分数组合是要抽的

    那么题目的分数确定是为什么?题型不同还是难度不同?

    你抽了 20 个简单题,他抽了 10 个高难题,或者你抽了 20 个选择题,他抽了 30 个填空,这考试怕不是毫无公平性可言

    所以我一开始就在想需求,每种题型的数量究竟是确定的还是抽的
    Anshi
        10
    Anshi  
       2021-09-13 10:04:22 +08:00
    @murmur 可能目前需求对题目类型没有权重吧😂
    jiangboenoch
        11
    jiangboenoch  
       2021-09-13 10:04:33 +08:00
    @murmur #9 好哥哥要不去刷刷 leetcode 吧,你提的问题就相当于问 李雷为什么去找韩梅梅出去玩,不应该在家学习吗;为什么要把鸡蛋从 100 楼丢下去,这不是浪费粮食吗;

    这是算法题题干,你谈需求。
    murmur
        12
    murmur  
       2021-09-13 10:08:24 +08:00
    @jiangboenoch 所以楼主也没说他是在刷题还是在做项目啊?
    jiangboenoch
        13
    jiangboenoch  
       2021-09-13 10:12:49 +08:00
    @murmur show me the code

    // 用 js 做演示
    const picker=(list)=>{
    const counter={}
    list.forEach(o=>{
    if (counter.hasOwnProperty(o)){
    counter[o]++
    }else {
    counter[o]=0
    }
    })
    //用 5 个数做演示
    const foo=[6,1,1,1,1]
    // [6,1,1,1,1]
    // [5,2,1,1,1]
    // [4,3,1,1,1]
    // [4,2,2,1,1]
    // [3,3,2,1,1]

    // 这里的递归需要再仔细想下,第一个递归下来就是 4 数之和 第二个递归下来就是 3 数之和 第三个递归下来就是 2 数之和
    // 大概思路就是到这里,然后对 foo 进行计数,counter 对比,如果计数满足就 return
    // 如果需要对 foo.length 做参数处理,那就写个生成 foo 的方法
    }
    KousukeSakurako
        14
    KousukeSakurako  
       2021-09-13 10:48:07 +08:00 via iPhone
    看起来像典型的动态规划问题, 如果题库里的题有类似这样的形式:5,6,7 分题都有无限个
    jiangboenoch
        15
    jiangboenoch  
       2021-09-13 10:54:50 +08:00
    @KousukeSakurako #14 我搜了哈动态规划,其中一条
    “fucking-algorithm/动态规划详解进阶.md at master - GitHub”

    “fucking-algorithm” 哈哈哈哈哈哈哈哈哈哈哈哈哈哈
    geelaw
        16
    geelaw  
       2021-09-13 10:58:35 +08:00   ❤️ 1
    需要先定义什么“随机”,如果是所有可能的出题组合(顺序不同不算不同)中均匀选择一个组合,那么可以这样做:

    1. 用动态规划计算 F(i, j, k) = 从前 i 道题目里选 j 道使总分是 k 有多少种组合。
    2. 如果 F(N, 20, 100) 是零,则失败;否则运行递归算法 SampleCombination(N, 20, 100),它工作方式如下:

    SampleCombination(n, m, s):
    令 n0, m0, s0 = n - 1, m, s
    令 n1, m1, s1 = n - 1, m - 1, s - V(n)
    令 p = F(n0, m0, s0) / F(n, m, s)
    以 p 的概率不选择第 n 题且运行 F(n0, m0, s0)
    如果没有不选择第 n 题,则选择之且运行 F(n1, m1, s1)

    其中 V(n) 是题目 n 的分数。
    geelaw
        17
    geelaw  
       2021-09-13 10:59:11 +08:00
    @geelaw * 且运行 F(...) => 且运行 SampleCombination(...)
    xz410236056
        18
    xz410236056  
       2021-09-13 11:09:04 +08:00
    概率论不是计算机必修课?
    我第一反应是切比雪夫不等式
    ch2
        19
    ch2  
       2021-09-13 11:18:26 +08:00   ❤️ 1
    背包问题,全部组合都找出来,然后 random.choice
    jiangboenoch
        20
    jiangboenoch  
       2021-09-13 11:24:01 +08:00
    不好意思 没有认真审题,需要随机抽 20 满足,我的方法只能满足找出第一个满足 100 分的组合,无视我的思路 #13
    LxExExl
        21
    LxExExl  
       2021-09-13 11:24:22 +08:00 via iPhone   ❤️ 1
    mgcnrx11
        22
    mgcnrx11  
       2021-09-13 11:26:31 +08:00   ❤️ 1
    https://www.jianshu.com/p/7fe9d3bb00ac 最近也在做类似的组卷算法,遗传算法好像是用得比较多的。关键是算法中找到适合自己的适应度计算方式
    yEhwG10ZJa83067x
        23
    yEhwG10ZJa83067x  
       2021-09-13 11:28:30 +08:00
    总分和题目数量都可以随意设置对吧,不用考虑题目类别以及难以程度导致的公平性吗?
    mgcnrx11
        24
    mgcnrx11  
       2021-09-13 11:32:46 +08:00
    @mgcnrx11 之前花了 2 天去尝试和调整这个算法,相信是能满足题主的要求的
    ydpro
        25
    ydpro  
    OP
       2021-09-13 11:48:49 +08:00
    @justrand 嗯,都是可以随意设置,不需要考虑类别和难度
    maplelin
        26
    maplelin  
       2021-09-13 16:10:19 +08:00
    这是求刚好装满背包情况的背包问题吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5246 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 40ms · UTC 03:49 · PVG 11:49 · LAX 19:49 · JFK 22:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.