请教一个随机抽题问题

2021-09-13 09:18:00 +08:00
 ydpro

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

1539 次点击
所在节点    问与答
26 条回复
murmur
2021-09-13 09:20:57 +08:00
需求不合理,建议拿需求出来,一般的考卷是成组出题的,填空、选择、计算这样,只要分组确定了,每一组题目的分值也是确定的

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

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

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

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

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

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

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

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

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

这是算法题题干,你谈需求。
murmur
2021-09-13 10:08:24 +08:00
@jiangboenoch 所以楼主也没说他是在刷题还是在做项目啊?
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
2021-09-13 10:48:07 +08:00
看起来像典型的动态规划问题, 如果题库里的题有类似这样的形式:5,6,7 分题都有无限个
jiangboenoch
2021-09-13 10:54:50 +08:00
@KousukeSakurako #14 我搜了哈动态规划,其中一条
“fucking-algorithm/动态规划详解进阶.md at master - GitHub”

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

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
2021-09-13 10:59:11 +08:00
@geelaw * 且运行 F(...) => 且运行 SampleCombination(...)
xz410236056
2021-09-13 11:09:04 +08:00
概率论不是计算机必修课?
我第一反应是切比雪夫不等式
ch2
2021-09-13 11:18:26 +08:00
背包问题,全部组合都找出来,然后 random.choice
jiangboenoch
2021-09-13 11:24:01 +08:00
不好意思 没有认真审题,需要随机抽 20 满足,我的方法只能满足找出第一个满足 100 分的组合,无视我的思路 #13

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/801454

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX