轻松的编程学习
首页
题库
学习路径
在线商城
能力地图
下载应用
登录 / 注册
菜单
🔴 期望正好等于那个平均
👁️ 0 人浏览
💬 0 人评论
❤️ 添加收藏
随机快排的
期望
比较次数，和"固定取第一个"在全部 120 种输入上的
平均
，把这两个数比一比。用分数算，别用浮点。
提交你的答案
请登录后提交答案。
去登录
← 🔴 最坏输入里，就有已经排好序的那个
🔴 固定策略随输入变，随机策略的期望不变 →
更多题目
让程序说出"你好"
让程序欢迎你
哪个命令能显示内容
哪里是指令，哪里是结果
让程序说出你的名字
这个程序会显示什么
代码编辑器
语言：
python3
c11
cpp17
Ctrl
+
Enter
运行
👩🏫 AI
▶ 运行代码
重置代码
打印代码
from itertools import permutations def qs_cmp(a): """总是拿第一个当 pivot 的快排，返回比较次数""" c = 0 def go(x): nonlocal c if len(x) <= 1: return p = x[0] c += len(x) - 1 go([y for y in x[1:] if y < p]) go([y for y in x[1:] if y >= p]) go(list(a)) return c P = list(permutations(range(5))) from fractions import Fraction from functools import lru_cache @lru_cache(None) def expect(k): """随机 pivot 的期望比较次数（精确分数）""" if k <= 1: return Fraction(0) return Fraction(k - 1) + sum(expect(t) + expect(k - 1 - t) for t in range(k)) / k # TODO: 固定 pivot 在全部 P 种输入上的平均（用 Fraction，别用浮点） avg = Fraction(0) e = expect(5) # TODO: 两者相等就输出「相等」，否则「不等」 verdict = "不等" print(str(e.numerator) + "/" + str(e.denominator) + "/" + verdict)
本次输入：
输出：
👩🏫
AI
请登录后使用 AI 老师
×
登录后可获得解题思路、提示与错误分析。
去登录
关闭
🎉
恭喜你，回答正确！
系统判定：正确
我知道了
💬 题目评论
提交
全部评论
全部评论