彭泽横琴

用户名：uq_97083909623

访问量：12507

签　名：

让回忆纪念最初的感动

等　　级
排　　名	1319
经　　验	2979
参赛次数	1
文章发表	22
年　　龄	20
在职情况	学生
学　　校
专　　业	软件工程

　　自我简介：

TA的其他文章

[编程入门]报数问题-题解(C语言描述（算法初步约瑟夫问题）)
浏览：439

[编程入门]结构体之时间设计-题解(C语言代码)
浏览：622

二级C语言-计算素数和-题解(C语言描述（超简单写法！！！）)
浏览：431

你可能喜欢

[编程入门]报数问题-题解(C语言描述（算法初步约瑟夫问题）)

　　作者: 彭泽横琴　　　　发表时间：2020-01-31 10:52:29 浏览：439　|　评论：1　

原题链接：[编程入门]报数问题

##约瑟夫问题（算法）
**1.大部分人都应该第一想到链表，比较简单不说了
2.然后便是数组法，比较麻烦：
```c
#include <stdio.h>
int main(void)
{
    int  * num, test=1, i=0, n;
    scanf_s("%d", &n);
    num = (int*)malloc(sizeof(int) * n);
    for (int h = 0; h < n; h++) 
        num[h] = h+1;
    while (n > 1) {
        if ((test == 3) && (i == n - 1)) {
            i = -1;
            test = 0;
            n--;
        }
        if (test == 3) {
            for (int j = i; j < (n - 1); j++) {
                num[j] = num[j + 1];
            }
            i--;
            test = 0;
            n--;
        }
        test++;
        i++; 
        if (i > n - 1) 
            i = 0;
    }
    printf("%d", num[0]);
}
```
3.公式法，建议记住，比较简单：
约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
递推公式：
f(N,M)=(f(N−1,M)+M)%N                  
 f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号
f(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号

下面将讲解怎么推导这个公式。（用的**高中数学**知识假设法）
**问题1：**假设我们已经知道11个人时，胜利者的下标位置为6。那下一轮10个人时，胜利者的下标位置为多少？
**答：**其实吧，第一轮删掉编号为3的人后，之后的人都往前面移动了3位，胜利这也往前移动了3位，所以他的下标位置由6变成3。
**问题2：**假设我们已经知道10个人时，胜利者的下标位置为3。那下一轮11个人时，胜利者的下标位置为多少？
**答：**这可以看错是上一个问题的逆过程，大家都往后移动3位，所以f(11,3)=f(10,3)+3。不过有可能数组会越界，所以最后模上当前人数的个数，f(11,3)=（f(10,3)+3）%11
**问题3：**现在改为人数改为N，报到M时，把那个人杀掉，那么数组是怎么移动的？
**答：**每杀掉一个人，下一个人成为头，相当于把数组向前移动M位。若已知N-1个人时，胜利者的下标位置位f(N−1,M，则N个人的时候，就是往后移动M为，(因为有可能数组越界，超过的部分会被接到头上，所以还要模N)，既f(N,M)=(f(N−1,M)+M)%n

```c
#include <stdio.h>
int main(void)
{
    int  n, z=0;
    scanf_s("%d", &n);
    for (int k = 2; k <= n; k++) {
        z = (z + 3) % k;
    }
   
    printf("%d",z+1);
}
```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

GodsWill

链表表示不会

2020-11-16 09:38:43

彭泽横琴

TA的其他文章

你可能喜欢

C语言考试练习题_一元二次方程（C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

统计字符（C语言描述运用ctype.h）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

点我有惊喜！你懂得！

[编程入门]报数问题-题解(C语言描述（算法初步约瑟夫问题）)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

输出正反三角形（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

Cylinder （C语言描述，蓝桥杯）

1035 题解

GC的苦恼（C语言代码）

判定字符位置（C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

彭泽横琴

TA的其他文章

你可能喜欢

C语言考试练习题_一元二次方程 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

统计字符 （C语言描述运用ctype.h）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

点我有惊喜！你懂得！

[编程入门]报数问题-题解(C语言描述（算法初步约瑟夫问题）)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

输出正反三角形 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

Cylinder （C语言描述，蓝桥杯）

1035 题解

GC的苦恼 （C语言代码）

判定字符位置 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

统计字符（C语言描述运用ctype.h）

　　评论区

输出正反三角形（C语言代码）

GC的苦恼（C语言代码）

判定字符位置（C语言代码）