當前位置:編程學習大全網 - 編程語言 - c++報數遊戲

c++報數遊戲

法壹(模擬法):

#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;

}

  • 上一篇:人工智能在軍事領域如何發揮最大效率
  • 下一篇:伺服電機運行時過沖怎麽辦
  • copyright 2024編程學習大全網