阅读程序问题-第二弹
额 , 图多了点 , 但是就问几个小题目 , 别走啊(话说这个应该是 约瑟夫环问题吧 , 就是报数 , 报道 n 就退)
这道题第 2 题 为什么会不影响 , 感觉 pre 和 cur 并不是一直在一起
第3题如果 m == 0 是不是就没了 (哎它也不严谨啊)
第 4 题为啥是 nlogn , 怎么算
本帖最后由 jhq999 于 2022-9-14 22:48 编辑
2\p{pre].next的值就是cur理由：在count=n之前 pre=cur;cur=cur.next，当等于m时当时，p.next=p.next;cur就被踢出去了，cur=cur.next;后cur的值等于p.next的值 本帖最后由 jhq999 于 2022-9-14 22:52 编辑
3/m=0链表都没初始化，数组越界，可能导致死循环或者崩溃 本帖最后由 jhq999 于 2022-9-14 23:13 编辑
约瑟夫环问题吧 , 就是报数 , 报道 n 就把n踢了，直到剩下最后一个
复杂度难住了我
m
1——n n
m-1
n——2n
m-2
2n——3n
m-3
……
m-m+1
所以应该是n*（m-1）
这转换成时间复杂度是多少？
对于2，3题，你可以写个测试程序，我着急上学，回来才有时间。
对于时间复杂度，我....
真的看不懂，平常约瑟夫问题都是O(n^2)
怎么可能呢？ zhangjinxuan 发表于 2022-9-15 07:15
对于2，3题，你可以写个测试程序，我着急上学，回来才有时间。
对于时间复杂度，我....
你大几？ 编程追风梦 发表于 2022-9-15 08:13
你大几？
我小学，嘻嘻~ 本帖最后由 zhangjinxuan 于 2022-9-15 19:02 编辑
破案了！
对于2题：
测试程序：
#include <bits/stdc++.h>
using namespace std;
struct Person {
int num, next;
}p;
int main() {
int m, n, count = 0;
scanf("%d%d", &m, &n);
for (int i = 1; i < m; ++i) {
p.num = i;
p.next = i + 1;
}
p.num = m;
p.next = 1;
int cur = 1;
int pre = m;
while (p.next != cur) {
++count;
if (count == n) {
p.next = p.next].next;
count = 0;
} else
pre = cur;
cur = p.next;
}
printf("%d\n", p.num);
}
输入&输出：
10 3
4
的确是第4个人最后出列！
对于3题：
的确不严谨，在m >= 1的情况下，确实会被重置m - 1次，但像你说的m == 0那就不一样了
对于4题：
如果，他真的是O(n log n),执行100000的数据大小肯定没有问题
但是，我们来测试一下（别忘了，是报到n出列，不是有n个人)
输入&输出:
100000 99999
[超时]
自己试试，一定超时，因为 O(n log n) 的算法极大概率有二分
你在代码里看见二分的影子了吗？
你可能会说：巧合，时间复杂度是估出来的
错！
不行你试试m = 50000,n = 10000,都超时！
所以这道选择题，是书错！[不是书错，就是我错...]
结论：2题是对的，3题不严谨，4题不是书错就是我错
[对了，这是第几页，我也看看] 对于为什么，我有待研究 zhangjinxuan 发表于 2022-9-15 19:00
破案了！
对于2题：
第 192 页 , 我的书是ccf csp 第一轮认证 一本通
然后的话 , 这个是拼夕夕弄来的 , 不知道是不是错印 , 反正之前也是有错的
(另外 , 你是住论坛嘛 , 好快) zhangjinxuan 发表于 2022-9-15 19:00
破案了！
对于2题：
离谱书 , 看个乐子得了 我也四说，这书怕是****** 我的79块钱啊{:10_266:}
我*******！ 我边看这本书边刷新浏览器 zhangjinxuan 发表于 2022-9-15 20:05
我的79块钱啊
我*******！
哈哈 , 说不定我的是盗版
毕竟 十来块就有了
书我就剩最后的模拟题了
今天上课摸鱼做的最后一章 神马？10来块？？？
页:
[1]