法壹(模擬法):
#include<iostream>using?std::cin;
using?std::cout;
int?main()
{
int?n,m;
cout<<"請輸入n=?";
cin>>n;
if(n<1)
{
cout<<"n必須大於1!\n請重新輸入n=?";
cin>>n;
}
cout<<"請輸入m=?";
cin>>m;
bool?*?a?=?new?bool?[n+1];
a[0]=false;
for(int?i=1;i<n+1;i++)
a[i]=true;
int?x,k=n;x=i=0;//i為每次循環計數變量,x為人員序號,K為剩余人數
while(k!=0)
{
x++;
if(x>n)?x=1;//當人員到達數組尾,序號重設為1
if(a[x])i++;?//?跳過已退出人員
if(i==m)
{a[x]=false;i=0;k--;}//當數到m時,退出人員設為false,剩余人數減1,i設為0,重新計數
}
cout<<"留下來的人序號為:?"<<x<<"\n";
delete?[]?a;
cin.get();
cin.get();//等待下壹次鍵擊關閉窗口
return?0;
}
法二(遞歸法):
此題可用數學方法求解。
設有n個人(編號0~(n-1)),從0開始報數,報到(m-1)的退出,剩下的人繼續從0開始報數 (用數學方法解的時候需要註意應當從0開始編號,因為取余會取到0解。)
實質是壹個遞推,n個人中最終留下來的序號與n-1個人中留下來的人的序號有壹個遞推關系式。
假設除去第k個人,則
0, 1, 2, 3, ..., k-2, k-1, k, ..., n-1 // 原始序列 (1)
0, 1, 2, 3, ..., k-2, ?, k, ..., n-1 ? // 除去第k人,即除去序號為k-1的人 ? (2)
k, k+1, ..., n-1, 0, 1, ..., k-2 // 以序號k為起始,從k開始報0? (3)
0, 1, ..., n-k-1, n-k, n-k+1, ..., n-2 ? // 作編號轉換,此時隊列為n-1人 (4)
變換後就完完全全成為了(n-1)個人報數的子問題,註意(1)式和(4)式,是同壹個問題,不同的僅僅是人數。比較(4)和(3),不難看出,0+k=k, 1+k=k+1, ... ,(3)式中'0'後面的數字,
((n-3)+k)%n=k-3,((n-2)+k)%n=k-2, 對於(3)式中'0'前面的數字,由於比n小,也可看作(0+k)%n=k,? (1+k)%n=k+1,? 故可得出規律:
設(3)中某壹數為x' , (4)中對應的數為x,則有:x'=(x+k)%n.
設x為最終留下的人序號時,隊列只剩下1人時,顯然x=0; 此時可向前回溯至2人時x對應的序號,3人時x對應的序號……直至n人時x的序號,即為所求。
#include?<iostream>using?namespace?std;
int?main()
{
int?n,m,f=0;
cin>>n>>m;
for(int?i=2;i<=n;i++)?
f=(f+m)%i;
cout<<f+1<<endl;
}