2.5约瑟夫问题（OJ 2746）DAY 2

本文主要是介绍2.5约瑟夫问题（OJ 2746）DAY 2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

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

输入

每行是用空格分开的两个整数，第一个是 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;
 } 

这篇关于2.5约瑟夫问题（OJ 2746）DAY 2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！