CCF-201712-2-游戲
CCF題目
問題描述
有n個小朋友圍成一圈玩游戲，小朋友從1至n編號，2號小朋友坐在1號小朋友的順時針方向，3號小朋友坐在2號小朋友的順時針方向，……，1號小朋友坐在n號小朋友的順時針方向?！ ∮螒蜷_始，從1號小朋友開始順時針報數(shù)，接下來每個小朋友的報數(shù)是上一個小朋友報的數(shù)加1。若一個小朋友報的數(shù)為k的倍數(shù)或其末位數(shù)（即數(shù)的個位）為k，則該小朋友被淘汰出局，不再參加以后的報數(shù)。當游戲中只剩下一個小朋友時，該小朋友獲勝。
例如，當n=5, k=2時： 1號小朋友報數(shù)1； 2號小朋友報數(shù)2淘汰； 3號小朋友報數(shù)3； 4號小朋友報數(shù)4淘汰； 5號小朋友報數(shù)5； 1號小朋友報數(shù)6淘汰； 3號小朋友報數(shù)7； 5號小朋友報數(shù)8淘汰； 3號小朋友獲勝。
給定n和k，請問最后獲勝的小朋友編號為多少？
輸入格式
輸入一行，包括兩個整數(shù)n和k，意義如題目所述。
輸出格式
輸出一行，包含一個整數(shù)，表示獲勝的小朋友編號。
樣例輸入
5 2
樣例輸出
3
樣例輸入
7 3
樣例輸出
4
數(shù)據(jù)規(guī)模和約定
對于所有評測用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9。
成功案例
用兩個變量來記錄報數(shù)和下標的問題，一個while循環(huán)，一次性解決。
#include<iostream>
#include?<fstream>
using?namespace?std;
int?main()?{
????int?n,?k;
????cin?>>?n?>>?k;
????//?生成數(shù)組，記錄每個孩子本身的編號
????int?*child?=?new?int[n];
????for?(int?i?=?0;?i?<?n;?i++)?{
????????child[i]?=?i?+?1;
????}
????int?num?=?n;?//?記錄剩下的總人數(shù)
????int?count??=?1;//?報數(shù)
????int?index?=?0;//?遍歷孩子數(shù)組的下標
????while?(num?!=?1)?{?//?直到最后只剩下一個人才結束
????????if?(child[index]?!=?0)?{
????????????//?滿足淘汰條件就將人數(shù)減一，數(shù)值置為零并繼續(xù)報數(shù)
????????????if?(count??%?k?==?0?||?count??%?10?==?k)?{
????????????????count?++;
????????????????child[index]?=?0;
????????????????num--;
????????????}?else?{
????????????????count?++;
????????????????index?=?(index?+?1)?%?n;
????????????????continue;
????????????}
????????}?else?{
????????????index?=?(index?+?1)?%?n;
????????}
????}
????//?最后輸出存活孩子的編號
????for?(int?i?=?0;?i?<?n;?i++)?{
????????if?(child[i]?!=?0)?{
????????????cout?<<?child[i];
????????}
????}
????return?0;
}心得
這道題一開始我還以為是約瑟夫環(huán)的問題，埋著頭就開始寫。
約瑟夫環(huán)的問題是這樣的：n個人依次編號。第一個人從 1 開始報數(shù)，數(shù)到 k 的人會被殺掉，然后下一個人重新從 1 開始報數(shù)。如此往復，直到最后只剩下一個人。然而這道題，他是在報數(shù)后繼續(xù)加一！
構建環(huán)形鏈表的爆棧解法在體量小的時候可以使用，其實數(shù)組也是一樣的，都是按照游戲規(guī)則一步一步去運算，到最后輸出結果。
我嘗試去統(tǒng)計規(guī)律，但我仍然沒找到……
一共7個孩子，k值為3
淘汰第3名孩子,報數(shù)是3，還剩6個人
淘汰第6名孩子,報數(shù)是6，還剩5個人
淘汰第2名孩子,報數(shù)是9，還剩4個人
淘汰第7名孩子,報數(shù)是12，還剩3個人
淘汰第1名孩子,報數(shù)是13，還剩2個人
淘汰第5名孩子,報數(shù)是15，還剩1個人
最后活下來的是4感謝
源碼文件：
gitee：https://gitee.com/JunKuangKuang/KeenCPPTest-all/tree/main/ccf/2017-12/2
github：https://github.com/JunKuangKuang/KeenCPPTest-all/tree/main/ccf/2017-12/2
感謝現(xiàn)在好奇的自己，堅持編寫到現(xiàn)在，為了成為更好的自己。
- 中國計算機學會官網(wǎng)
