猴子报数（兰州大学/湖南大学机试题）

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

n个猴子围坐一圈并按照顺时针方向从1到n编号，从第s个猴子开始进行1到m的报数，报数到第m的猴子退出报数，从紧挨它的下一个猴子重新开始1到m的报数，如此进行下去知道所有的猴子都退出为止。求给出这n个猴子的退出的顺序表。

输入输出格式

输入描述:

有做组测试数据．每一组数据有两行，第一行输入n（表示猴子的总数最多为100）第二行输入数据s(从第s个猴子开始报数)和数据m(第m个猴子退出报数)．当输入０ ０ ０时表示程序结束．

输出描述:

每组数据的输出结果为一行，中间用逗号间隔。

输入输出样例

输入样例#:

10 2 5 5 2 3 0 0 0

输出样例#:

6,1,7,3,10,9,2,5,8,4 4,2,1,3,5

#include<bits/stdc++.h> using namespace std; int count(int n, int s, int m, const vector<int>&monkey){//看看到那个猴子出去了 int temp = 0, num = 0, i = s; for(int i = 1; i <= n; i ++){//还剩几只猴子 if(monkey[i] == 1){ num ++; } } if(num == 0){//没有了 return -1; } while(temp < m){//还有猴子 if(monkey[i] == 1){//该位置猴子还在 temp ++; //报数 if(temp == m){break;}//== i ++;//往后走 if(i > n){//序号超过就重置 i = 1; } } else{//猴子不在 i ++;//往后走 if(i > n){//序号超过就重置 i = 1; } } } return i; } int main(){ int n, s, m; while(cin>>n>>s>>m){ if(n == 0 && s == 0 && m == 0){ return 0; } vector<int>monkey(n + 1, 1);//初始都为1 int num = 0; while(num < n){ int temp = count(n, s, m, monkey);//本次报数的结果 if(temp != -1){//还有猴子 num ++; monkey[temp] = 0;//退出了 if(temp < n){ s = temp + 1; } else{ s = 1; } if(num == 1){//第一只 cout<<temp; } else{ cout<<","<<temp; } } } cout<<endl; } }