鱼C论坛

 找回密码
 立即注册
查看: 2629|回复: 15

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

[复制链接]
发表于 2022-9-14 21:44:04 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
额 , 图多了点 , 但是就问几个小题目 , 别走啊 微信图片_20220914213442.jpg 微信图片_20220914213528.jpg
(话说这个应该是 约瑟夫环问题吧 , 就是报数 , 报道 n 就退)
这道题第 2 题 为什么会不影响 , 感觉 pre 和 cur 并不是一直在一起
第3题如果 m == 0 是不是就没了 (哎它也不严谨啊)
第 4 题为啥是 nlogn , 怎么算
最佳答案
2022-9-15 19:00:38
本帖最后由 zhangjinxuan 于 2022-9-15 19:02 编辑

破案了!

对于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题不是书错就是我错

[对了,这是第几页,我也看看]
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-9-14 22:30:57 | 显示全部楼层
本帖最后由 jhq999 于 2022-9-14 22:48 编辑

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的值
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-14 22:38:41 | 显示全部楼层
本帖最后由 jhq999 于 2022-9-14 22:52 编辑

3/m=0链表都没初始化,数组越界,可能导致死循环或者崩溃
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-14 22:53:56 | 显示全部楼层
本帖最后由 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)
这转换成时间复杂度是多少?

评分

参与人数 1荣誉 +5 鱼币 +5 贡献 +3 收起 理由
柿子饼同学 + 5 + 5 + 3 确实 , 这书很有问题

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2022-9-15 07:15:22 From FishC Mobile | 显示全部楼层
对于2,3题,你可以写个测试程序,我着急上学,回来才有时间。

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

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

怎么可能呢?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-15 08:13:44 | 显示全部楼层
zhangjinxuan 发表于 2022-9-15 07:15
对于2,3题,你可以写个测试程序,我着急上学,回来才有时间。

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

你大几?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-15 18:30:59 | 显示全部楼层

我小学,嘻嘻~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-15 19:00:38 | 显示全部楼层    本楼为最佳答案   
本帖最后由 zhangjinxuan 于 2022-9-15 19:02 编辑

破案了!

对于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题不是书错就是我错

[对了,这是第几页,我也看看]
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-15 19:04:28 | 显示全部楼层
对于为什么,我有待研究
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-15 19:57:13 | 显示全部楼层
zhangjinxuan 发表于 2022-9-15 19:00
破案了!

对于2题:

第 192 页 , 我的书是  ccf csp 第一轮认证 一本通
然后的话 , 这个是拼夕夕弄来的 , 不知道是不是错印 , 反正之前也是有错的
(另外 , 你是住论坛嘛 , 好快)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-15 19:58:41 | 显示全部楼层
zhangjinxuan 发表于 2022-9-15 19:00
破案了!

对于2题:

离谱书 , 看个乐子得了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-15 20:02:41 From FishC Mobile | 显示全部楼层
我也四说,这书怕是******
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-15 20:05:56 From FishC Mobile | 显示全部楼层
我的79块钱啊

我*******!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-15 20:08:30 From FishC Mobile | 显示全部楼层
我边看这本书边刷新浏览器
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-15 20:45:02 | 显示全部楼层
zhangjinxuan 发表于 2022-9-15 20:05
我的79块钱啊

我*******!


哈哈 , 说不定我的是盗版
毕竟 十来块就有了
书我就剩最后的模拟题了
今天上课摸鱼做的最后一章
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-15 20:47:25 | 显示全部楼层
神马?10来块???
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-16 19:38

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表