2.5约瑟夫问题(OJ 2746)DAY 2

描述

约瑟夫问题:有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。
 

输入

每行是用空格分开的两个整数,第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是:

0 0
 

输出

对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号

样例输入

6 2
12 4
8 3
0 0

样例输出

5
1
7

这题,啊,不知道为什么会超时啊,明天再想吧。符上错误代码

#include <iostream>
using namespace std;
int flag[305];		//多开几个,防止溢出 
int main() 
{
	for (int i = 0; i < 305; ++i) 
		flag[i] = 0;
	int n, m;
	int cnt, index;
	//数组默认置0 
	cin >> n >> m;
	while (n != 0 && m !=0) {
		cnt = 0;
		index = -1;
		for (int i = 1; i < n; ++i) {		//一共要将n-1个元素给置1 
			cnt = 0;
			while (cnt != m) {
				index = (index + 1) % n;
				if (flag[index] == 0) {
					cnt ++;
					if (cnt == m) {
						flag[index] = 1;
					} 
				}
			}
		} 
		for (int j = 0; j < n; ++j)
			if (flag[j]) {
				cout << flag[j] << endl;
				break;
			}
		cin >> n >> m;	
	}
	return 0;
 } 

上一篇:ip判断(oj)


下一篇:OJ---百钱买百鸡问题