[已解决]阅读程序问题-第二弹

柿子饼同学

额 , 图多了点 , 但是就问几个小题目 , 别走啊
(话说这个应该是 约瑟夫环问题吧 , 就是报数 , 报道 n 就退)
这道题第 2 题 为什么会不影响 , 感觉 pre 和 cur 并不是一直在一起
第3题如果 m == 0 是不是就没了 (哎它也不严谨啊)
第 4 题为啥是 nlogn , 怎么算

最佳答案

月排行榜 / 总排行榜

zhangjinxuan

2022-9-15 19:00:38

破案了！

对于2题：

测试程序：

#include <bits/stdc++.h>

using namespace std;

struct Person {
        int num, next;
}p[100001];

int main() {
        int m, n, count = 0;
        scanf("%d%d", &m, &n);
        for (int i = 1; i < m; ++i) {
                p[i].num = i;
                p[i].next = i + 1;
        }
        p[m].num = m;
        p[m].next = 1;
        int cur = 1;
        int pre = m;
        while (p[cur].next != cur) {
                ++count;
                if (count == n) {
                        p[pre].next = p[p[pre].next].next;
                        count = 0;
                } else 
                        pre = cur;
                cur = p[cur].next;
        }
        printf("%d\n", p[cur].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题不是书错就是我错

[对了，这是第几页，我也看看]

跳转到最佳答案楼层

jhq999

2\p{pre].next的值就是cur  理由：在count=n之前 pre=cur;cur=cur.next，当等于m时当时，p[pre].next=p[cur].next;cur就被踢出去了，cur=cur.next;后cur的值等于p[pre].next的值

jhq999

3/m=0链表都没初始化，数组越界，可能导致死循环或者崩溃

jhq999

约瑟夫环问题吧 , 就是报数 , 报道 n 就把n踢了，直到剩下最后一个
复杂度难住了我
m
1——n n
m-1
n——2n
m-2
2n——3n
m-3
……
m-m+1
所以应该是n*（m-1）
这转换成时间复杂度是多少？

zhangjinxuan

对于2，3题，你可以写个测试程序，我着急上学，回来才有时间。

对于时间复杂度，我....

真的看不懂，平常约瑟夫问题都是O(n^2)

怎么可能呢？

编程追风梦

zhangjinxuan 发表于 2022-9-15 07:15
对于2，3题，你可以写个测试程序，我着急上学，回来才有时间。

对于时间复杂度，我....

你大几？

zhangjinxuan

编程追风梦 发表于 2022-9-15 08:13
你大几？

我小学，嘻嘻~

zhangjinxuan

破案了！

对于2题：

测试程序：

#include <bits/stdc++.h>

using namespace std;

struct Person {
        int num, next;
}p[100001];

int main() {
        int m, n, count = 0;
        scanf("%d%d", &m, &n);
        for (int i = 1; i < m; ++i) {
                p[i].num = i;
                p[i].next = i + 1;
        }
        p[m].num = m;
        p[m].next = 1;
        int cur = 1;
        int pre = m;
        while (p[cur].next != cur) {
                ++count;
                if (count == n) {
                        p[pre].next = p[p[pre].next].next;
                        count = 0;
                } else 
                        pre = cur;
                cur = p[cur].next;
        }
        printf("%d\n", p[cur].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

对于为什么，我有待研究

柿子饼同学

zhangjinxuan 发表于 2022-9-15 19:00
破案了！

对于2题：

第 192 页 , 我的书是  ccf csp 第一轮认证 一本通
然后的话 , 这个是拼夕夕弄来的 , 不知道是不是错印 , 反正之前也是有错的
(另外 , 你是住论坛嘛 , 好快)

柿子饼同学

zhangjinxuan 发表于 2022-9-15 19:00
破案了！

对于2题：

离谱书 , 看个乐子得了

zhangjinxuan

我也四说，这书怕是******

zhangjinxuan

我的79块钱啊

我*******！

zhangjinxuan

我边看这本书边刷新浏览器

柿子饼同学

zhangjinxuan 发表于 2022-9-15 20:05
我的79块钱啊

我*******！

哈哈 , 说不定我的是盗版
毕竟 十来块就有了
书我就剩最后的模拟题了
今天上课摸鱼做的最后一章

zhangjinxuan

神马？10来块？？？