題目相關(guān)
題目描述
有n人圍成一圈届慈，順序排號陵像。從第1個人開始報數(shù)（從1到3報數(shù)）呀伙，凡報到3的人退出圈子知举，問最后留下的是原來的第幾號的那位瞬沦。
輸入
初始人數(shù)n
輸出
最后一人的初始編號
分析
? 在讀完題目發(fā)現(xiàn)太伊，這道題目就是需要我們模擬循環(huán)報數(shù)的過程，可以想象一下小時候玩擊鼓傳花時候的情景逛钻。這道題目的難點(diǎn)在于如何判斷某個同學(xué)是不是還在隊伍中僚焦，不是簡單的判斷是否是3的倍數(shù)，這種方法曙痘，僅適用于不循環(huán)的報數(shù)芳悲，一旦首尾相連，倍數(shù)的判斷就不太合適了边坤。
構(gòu)造數(shù)組表明學(xué)生的狀態(tài)
? 每個同學(xué)在這道題目中的數(shù)據(jù)信息有兩個名扛，學(xué)號（編號），是否在隊伍中（在/不在）茧痒。如何采用一定的方法肮韧，將這兩者結(jié)合起來則能迅速處理這一問題。此時旺订，我們可以構(gòu)造一個標(biāo)記數(shù)組弄企，將這兩者結(jié)合起來。將數(shù)組的下標(biāo)作為學(xué)生學(xué)號区拳，存儲的內(nèi)容用來表示學(xué)生狀態(tài)拘领。共有兩個狀態(tài)，我們可以使用布爾類型(bool)數(shù)組分別用true和false來表示兩種狀態(tài)樱调，也可以使用整數(shù)類型數(shù)組表示對應(yīng)狀態(tài),為了方便從下標(biāo)1開始约素，開辟空間時可開辟人數(shù)+1的空間。
//開辟bool類型數(shù)組stu笆凌，用來表示各個學(xué)生的狀態(tài)
//stu[x] 為true 表示報到了3不在隊伍中圣猎， false 表示還在隊伍中
bool *stu = new bool[n + 1];// n 為學(xué)生人數(shù)
利用取余實(shí)現(xiàn)模擬循環(huán)
? 該題的另一個難點(diǎn)在于怎么進(jìn)行循環(huán)?無論是 從1~3反復(fù)進(jìn)行報數(shù)還是，n個同學(xué)圍成一圈菩颖，都涉及到了這一點(diǎn)样漆。一種方法是判斷，當(dāng)判斷到結(jié)尾時晦闰，將值重新改成開頭放祟。類似下面這樣
if(num==3) num=1;
if(i==n) i=1;
但這么寫有些麻煩，也得需要考慮變化過程對他的影響呻右。這事我們可以考慮另一種方法跪妥，使用取余符號(%)進(jìn)行模擬。
已知%符號的作用是獲取余數(shù)声滥，例如 7%5=2眉撵。當(dāng)能整除時侦香，結(jié)果為0。所以當(dāng)一個數(shù)字%n時纽疟，結(jié)果一定在0~n-1之間罐韩。并且當(dāng)a%b,a<b時，a%b=a污朽。利用這些特性可以寫出這樣的一個式子:x=(x+1)%n ,這樣x能變成x+1散吵；當(dāng)x為n-1時，x會變成0蟆肆，不斷重復(fù)x就能在0n-1之間循環(huán)矾睦。若想在1n之間循環(huán)可以修改成x=x%n+1。
int i = 1; //學(xué)生的學(xué)號 1~n
while (ren > 1) //循環(huán)報數(shù)炎功，直到剩下一個人
{
if (stu[i] == false) // 如果在隊伍中
{
num = num % 3 + 1; //報數(shù)
if (num == 3)
{ //報到3
stu[i] = true; //退出隊伍
ren--; //在隊伍中的人數(shù)減一
}
}
i = i % n + 1; //下一個學(xué)生的編號
}
枚舉法找出最后剩下的人的編號
最后只剩下最后一人枚冗，必定是這樣的狀態(tài):所有人都是true,只有他是false。那么我們只需要枚舉遍歷下蛇损，找出狀態(tài)為false的即可赁温。
for (int j = 1; j <= n; j++)
{//枚舉學(xué)號1~n的同學(xué)
if (stu[j] == false)
{//當(dāng)狀態(tài)為false,則說明j在隊伍中
cout << j;//輸出編號
break;//結(jié)束循環(huán)
}
}
代碼實(shí)現(xiàn)
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
//n-存儲人數(shù) num-報的數(shù)字 ren-留下的人數(shù)
int n, num = 0, ren;
cin >> n; // 輸入在人數(shù)
ren = n; //確定在隊伍中的人數(shù)
//開辟bool類型數(shù)組stu，用來表示各個學(xué)生的狀態(tài)
//stu[x] 為true 表示報到了3不在隊伍中州藕， false 表示還在隊伍中
bool *stu = new bool[n + 1];
//初始化 stu,使初始值為false
memset(stu, false, sizeof(bool) * (n + 1));
int i = 1; //學(xué)生的學(xué)號 1~n
while (ren > 1) //循環(huán)報數(shù)束世，直到剩下一個人
{
if (stu[i] == false) // 如果在隊伍中
{
num = num % 3 + 1; //報數(shù)
if (num == 3)
{ //報到3
stu[i] = true; //退出隊伍
ren--; //在隊伍中的人數(shù)減一
}
}
i = i % n + 1; //下一個學(xué)生的編號
}
for (int j = 1; j <= n; j++)
{//枚舉學(xué)號1~n的同學(xué)
if (stu[j] == false)
{//當(dāng)狀態(tài)為false,則說明j在隊伍中
cout << j;//輸出編號
break;//結(jié)束循環(huán)
}
}
return 0;
}
做題時，可從全局角度出發(fā)床玻，將題目分解成若干個小問題毁涉，解決后再整合起來。通過本題锈死，可以練習(xí)數(shù)組的構(gòu)造使用以及循環(huán)的處理贫堰。
