1.Josephus问题
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列，类似于丢手绢。
2.分析
选择什么数据结构？
解决的方式有多种，这里用一种较为简单的方式实现,基于 Python的列表和C语言的数组来实现
为什么用数组？
基本思想就是人推出了，但是保留其位置，将其位置标记为0，这样做的好处就是，保留了整个表的结构是不变的，处理起来很方便，代码简洁易懂
算法思路
- 通过数组,将N个人看成数组元素;
- 出局时元素设为0
- 循环报数时只将数组元素为1的元素计数
3.代码实现
C语言
#include <stdio.h>
void main()
{
int N,M;
printf("请输入总人数:n \n");
scanf("%d",&N); //获取键盘输入的总人数 10
printf("请输入报数上限m: \n");
scanf("%d",&M); //获取键盘输入的报数上限 5
int a[N], i, count = 0, out_people = 0; //定义数组和两个计数器
for (i = 0; i < N; i++) a[i] = 1; //初始化数组长度为N,初值全为1
i = 0;
while (1) {
if(a[i] == 1) { // i=1表示这里的人没有出局
if (out_people == (N - 1)) break; //如果仅剩一人（out_people表示出局人数）
count++; //往下计数 1...5
count %= M; //count = count % M 取模运算，最大为M，大于M就从0开始 1..0
if(count == 0) { //count == 0,表明 count = M
a[i] = 0; //出局标记
out_people++; //出局人数 +1
printf("%d\n", i + 1);// 打印出局人编号
}
}
i++; i %= N; // i = i % N 取模运算，最大为N，大于N就从0开始进入下一轮循环 1
}
printf("\n最后剩余者的编号是：%d\n", i + 1);
}
- 运行效果
62.png
Python
def josephus_A(n,k,m):
People = list(range(1,n+1)) #生成列表[1,2,...,n]
i=k-1 #从第k位同学开始,其索引为k-1
for num in range(n):
count = 0
while count < m:
if People[i]>0: #此位置的同学还未推出
count += 1
if count == m: #报数到m该同学推出
print(People[i]," ",end = "")
People[i] =0 #标记
i = (i+1) % n #i+1使之指向下一位同学;并且取模,当i>n循环完了一圈,从头新一轮
return
josephus_A(100,5,6)
>>>10 16 22 28 34 40 46 52 58 64 70 76 82 88 94 100 6 13 20 27 35 42 49 56 63 71 78 85 92 99 7 15 24 32 41 50 59 67 75 84 93 2 11 21 31 43 53 62 73 83 95 4 17 29 39 54 66 79 90 3 18 33 47 61 77 91 8 25 44 60 80 97 14 37 57 81 1 26 51 74 5 36 68 96 30 69 9 48 89 45 98 65 23 12 87 19 55 38 86 72
用Python来实现较为简单，需要注意的是i=(i+1)%n,i+1使列表的索引指向下一位同学;同时取模做运算,目的是当i>n时循环完了一圈,从头新一轮的筛选
投喂我
写文不易，如果本文对你有帮助，点击Donate,微信和支付宝投喂我
