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

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

ACTION-遞歸求解法

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

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

  由于第二次出列是是從k1開始，又從0開始報數(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)問題（n-1個人）
  對上述序列重新編號：
  0，1，2，3，4，5，…，n-2
  第二次出列的人的編號為**(m-1)%n2**（記n2為第一次編號的總?cè)藬?shù)），從他的下一個人又開始從0開始報數(shù)，為了方便我們記k2=m%n2，如下：
  0，1，2，3，4，5，…，k2-1(第二次出列人的編號(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)問題（n-2個人）
  對上述序列重新編號：
  0，1，2，3，4，5，…，n-3
  …

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

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

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

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