UVa 305 / POJ 1012 Joseph (如何得到約瑟夫環的下一個位置？)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=241

http://poj.org/problem?id=1012

注意代碼中的遞推式并不能指出實際的位置，但是要讓m是滿足題意的，這個位置（在減一映射後）必須>=k

當然你也可以打表實作。

/*0.079s*/

#include<bits/stdc++.h>
using namespace std;

int solve(int k)
{
	int m, pos, n = k << 1, i, next;
	///注意為了取模的友善，一開始所有人的編号減一
	for (m = k;; m++)
	{
		pos = m % n;
		if (pos >= k && pos < n)
		{
			///開始對所有的bad guy行刑，注意已經行刑了一個pos位置的bad guy
			for (i = 1; i < k; ++i)
			{
				next = (pos + m) % (n - i); /// 人越來越少，是以模越來越小
				if (next < k || next >= n) break; /// 錯誤，選了一個good guy
				pos = next;
			}
			if (i == k) break;
		}
	}
	return m + 1;
}

int main()
{
	int k, ans[14];
	for (int i = 1; i < 14; ++i)
		ans[i] = solve(i);
	while (scanf("%d", &k), k)
		printf("%d\n", ans[k]);
	return 0;
}