約瑟夫環–自殺環問題
約瑟夫環問題有著這樣的歷史：
Josephus有過的故事：39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓，于是決定了自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后下一個重新報數，直到所有人都自殺身亡為止，然而Josephus 和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲，
大致意思
一共有N個人圍坐在一起， 回圈周期是M， 第一個人報數1， 第二個人報數2， 當報數到M時， 這個人就會出列， 下一個人繼續從1開始報數， 整個程序持續到所有人出列為止， 這種問題一般會問最后一個出列的人是誰， 或者問你某個人是第幾個出列的，，，
對于學習了計算機的我們來說，重復性如此強的程序，當然要交給計算機來幫我們完成吶，所以我們一起來撰寫這個程式吧，
題目描述：
報數游戲是這樣的：有n個人圍成一圈，按順序從1到n編好號，從第一個人開始報數，報到m（<n）的人退出圈子；下一個人從1開始報數，報到m的人退出圈子，如此下去，直到留下最后一個人，
本題要求撰寫函式，給出每個人的退出順序編號，
函式介面定義：
void CountOff( int n, int m, int out[] );
其中n是初始人數；m是游戲規定的退出位次（保證為小于n的正整數），函式CountOff將每個人的退出順序編號存在陣列out[]中，因為C語言陣列下標是從0開始的，所以第i個位置上的人是第out[i-1]個退出的，
做題思路
直接暴力操作，模擬出整個程序，
- 我們可以引入vis陣列，將其初始化為0，代表這個人是否已經出列，如果陣列元素是0，則代表這個人還未出列，如果我需要讓這個人出列，我會將他出列的次序存入vis陣列，方便之后的輸出，
- 整個回圈大體為while（出列人數<原有人數），
- 引入start變數，它相當于一個移動指標，幫助我們模擬整個程序，
代碼實作
#include<iostream>
#include<cstring>//memset函式頭檔案
using namespace std;
int vis[1000];//訪問陣列，未訪問則為0，陣列元素表示出列次序，
int n, m;//n是總人數，m是報數周期，
void CountOff(int n, int m, int out[]){
int cnt=0;//初始出圈人數為0.
int start=-1;//初始遍歷的位置為-1，將由start變數幫我們模擬整個程序，
while(cnt<n){
int i=0;
while(1){
start = (start+1)%n;//start向下一個元素移動
if(vis[start]==0){//如果元素沒有出列則，計數加一，
i++;
}
if(i==m){//當報數到m時，則要出列了，
vis[start]=++cnt;//出列人數加一，
break;
}
}
}
for(int j=0;j<=n-1;j++){
printf("%d ", vis[j]);
}
}
int main()
{
memset(vis, 0, sizeof(vis));
cin >> n >> m;
CountOff(n, m, vis);
return 0;
}
這個題我們是用的笨方法寫的，直接讓計算機模擬了整個程序，但是如果題目僅僅只是問的最后一個出圈的人是誰，我們就有更加簡便的數學方法了，
遞推式
f(N,M)=(f(N?1,M)+M)%n
我們可以知道，當只剩下一個人的時候，他的下標絕對為0，也就是說f(1,M)=0，然后我們就可以根據這個式子和遞推式一步步的往前推，就能推出最后出列的那個人的下標了，因為是陣列下標，所以下標要加一才是我們想要的序號，
int find(int n,int m)
{
int p=0;
for(int i=2;i<=n;i++)
{
p=(p+m)%i;
}
return p+1;
}
我過幾天更新鏈表解法，謝謝觀看！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/240897.html
標籤：其他