1.Josephus問題
約瑟夫環(huán)（約瑟夫問題）是一個數(shù)學(xué)的應(yīng)用問題：已知n個人（以編號1竿开，2谱仪，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數(shù)否彩，數(shù)到m的那個人出列疯攒；他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列列荔；依此規(guī)律重復(fù)下去敬尺，直到圓桌周圍的人全部出列，類似于丟手絹贴浙。
2.分析
選擇什么數(shù)據(jù)結(jié)構(gòu)砂吞？
解決的方式有多種，這里用一種較為簡單的方式實現(xiàn),基于 Python的列表和C語言的數(shù)組來實現(xiàn)
為什么用數(shù)組崎溃？
基本思想就是人推出了蜻直，但是保留其位置，將其位置標記為0袁串，這樣做的好處就是概而，保留了整個表的結(jié)構(gòu)是不變的，處理起來很方便囱修，代碼簡潔易懂
算法思路
- 通過數(shù)組,將N個人看成數(shù)組元素;
- 出局時元素設(shè)為0
- 循環(huán)報數(shù)時只將數(shù)組元素為1的元素計數(shù)
3.代碼實現(xiàn)
C語言
#include <stdio.h>
void main()
{
int N,M;
printf("請輸入總?cè)藬?shù):n \n");
scanf("%d",&N); //獲取鍵盤輸入的總?cè)藬?shù) 10
printf("請輸入報數(shù)上限m: \n");
scanf("%d",&M); //獲取鍵盤輸入的報數(shù)上限 5
int a[N], i, count = 0, out_people = 0; //定義數(shù)組和兩個計數(shù)器
for (i = 0; i < N; i++) a[i] = 1; //初始化數(shù)組長度為N,初值全為1
i = 0;
while (1) {
if(a[i] == 1) { // i=1表示這里的人沒有出局
if (out_people == (N - 1)) break; //如果僅剩一人（out_people表示出局人數(shù)）
count++; //往下計數(shù) 1...5
count %= M; //count = count % M 取模運算到腥，最大為M，大于M就從0開始 1..0
if(count == 0) { //count == 0,表明 count = M
a[i] = 0; //出局標記
out_people++; //出局人數(shù) +1
printf("%d\n", i + 1);// 打印出局人編號
}
}
i++; i %= N; // i = i % N 取模運算蔚袍，最大為N乡范，大于N就從0開始進入下一輪循環(huán) 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位同學(xué)開始,其索引為k-1
for num in range(n):
count = 0
while count < m:
if People[i]>0: #此位置的同學(xué)還未推出
count += 1
if count == m: #報數(shù)到m該同學(xué)推出
print(People[i]," ",end = "")
People[i] =0 #標記
i = (i+1) % n #i+1使之指向下一位同學(xué);并且取模,當i>n循環(huá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來實現(xiàn)較為簡單，需要注意的是i=(i+1)%n,i+1使列表的索引指向下一位同學(xué);同時取模做運算,目的是當i>n時循環(huán)完了一圈,從頭新一輪的篩選
投喂我
寫文不易啤咽，如果本文對你有幫助晋辆，點擊Donate,微信和支付寶投喂我
