SITUATION-約瑟夫環(huán)問(wèn)題描述

已知n個(gè)人圍成一圈（編號(hào)：1，2，3，…，n），從編號(hào)為1的人開(kāi)始報(bào)數(shù)，報(bào)數(shù)為m的那個(gè)人出列；從他的下一個(gè)人又從1開(kāi)始數(shù)，同樣報(bào)數(shù)為m的人出列；依此循環(huán)下去，直到剩余一個(gè)人。求最后這一個(gè)人在最開(kāi)始的序列中編號(hào)是幾號(hào)？

ACTION-遞歸求解法

將這n個(gè)人從0~n-1編號(hào)（1是習(xí)慣從0開(kāi)始；2是如果m大于等于n時(shí)，第一個(gè)出列的人編號(hào)是m%n，m%n可能等于0，簡(jiǎn)化后續(xù)序列的模式化處理），則報(bào)數(shù)為m-1的人出列，最后結(jié)果加1就為原問(wèn)題的解，以下，我們來(lái)分析出列的過(guò)程：

• 第一次出列-n階約瑟夫環(huán)的問(wèn)題（n個(gè)人）
  0，1，2，3，4，5，…，n-2，n-1
  第一次出列的人的編號(hào)為**(m-1)%n1**（記n1為第一次編號(hào)的總?cè)藬?shù)），從他的下一個(gè)人又開(kāi)始從0開(kāi)始報(bào)數(shù)，為了方便我們記k1=m%n1，如下：
  0，1，2，3，4，5，…，k1-1(第一次出列人的編號(hào)(m-1)%n1)，k1，k1 1，…，n-2，n-1

  由于第二次出列是是從k1開(kāi)始，又從0開(kāi)始報(bào)數(shù)，為了便于模式化我們將第一次出列后的序列排序如下：
  k1，k1 1，k1 2，…，n-2，n-1，0，1，2，3，4，5，…，k1-3，k1-2（k1-1第一次已經(jīng)出列）

• 第二次出列-n-1階約瑟夫環(huán)問(wèn)題（n-1個(gè)人）
  對(duì)上述序列重新編號(hào)：
  0，1，2，3，4，5，…，n-2
  第二次出列的人的編號(hào)為**(m-1)%n2**（記n2為第一次編號(hào)的總?cè)藬?shù)），從他的下一個(gè)人又開(kāi)始從0開(kāi)始報(bào)數(shù)，為了方便我們記k2=m%n2，如下：
  0，1，2，3，4，5，…，k2-1(第二次出列人的編號(hào)(m-1)%n2)，k2，k2 1，…，n-2
  同樣重新排序如下：
  k2，k2 1，k2 2，…，n-2，n-1，0，1，2，3，4，5，…，k2-3，k2-2（k2-1第二次已經(jīng)出列）

• 第三次出列-n-2階約瑟夫環(huán)問(wèn)題（n-2個(gè)人）
  對(duì)上述序列重新編號(hào)：
  0，1，2，3，4，5，…，n-3
  …

• 第N-1次出列-2階約瑟夫環(huán)問(wèn)題（2個(gè)人）
  k(n-1)，k(n-1) 1
  重新編號(hào)：
  0，1
  第n-1次出列的人的編號(hào)為：m%n(n-1)，記下一個(gè)人的為k(n-1)=m%n2
  k(n-1)

• 第N次出列-1階約瑟夫環(huán)問(wèn)題（1個(gè)人）
  對(duì)上述序列重新編號(hào)：
  0
  直接得出結(jié)果為0。

RESULT-結(jié)論總結(jié)

以上我們將問(wèn)題轉(zhuǎn)換為模式相同且規(guī)模逐漸縮小的問(wèn)題，當(dāng)規(guī)模最小即只有一個(gè)人n=1時(shí)，報(bào)數(shù)為m-1的人出列，最后出列的人編號(hào)為0；當(dāng)n=2時(shí)，報(bào)數(shù)為m-1的人出列，最后出列人的編號(hào)是多少？應(yīng)該是只有一個(gè)人時(shí)得到最后出列的序號(hào)加上m（因?yàn)閳?bào)數(shù)為m-1的人已經(jīng)出列，剩下那個(gè)人才最后出列所以才加上m）
n=1時(shí)，f(1)=0；
n=2時(shí)，f(2)=[f(1) m]%2；
n=2時(shí)，f(3)=[f(2) m]%3；
驗(yàn)證結(jié)果：2個(gè)人圍成一圈，數(shù)到3的那人出列，求最后那個(gè)人的編號(hào)？n=2，m=3
f(2)=[f(1) m]%2=[0 3]%2=1
最后結(jié)果加1，則result=2；

遞歸解法

f(1)=0；//遞歸出口
f(n)=[f(n-1) m]%n；//遞歸體`

#include<stdio.h>
int josephus(int n,int m);
int main(){
 int n,m;
 scanf("%d %d",&n,&m);
 int ret=josephus(n,m);
 printf("%d",ret 1);
 return 0;
} 
int josephus(int n,int m){
 if(n==1)
  return 0;
 else 
  return (josephus(n-1,m) m)%n;
}

數(shù)學(xué)解法

由于遞歸的空間復(fù)雜度不太友好，進(jìn)行數(shù)學(xué)歸納，數(shù)學(xué)解法如下：

#include<stdio.h>
int main(){
 int n,m=3;
 scanf("%d",&n);
 int ans=0,i=0;
 for(i=1;i<=n;i  ){
  ans=(ans m)%i;
 }
 printf("%d",ans 1);
 return 0;
}