约瑟夫环实在是太奇妙啦（我很高兴我的这篇原创文章被不少人转载了，虽然他们都没有引用出处... ...）！
1012 Joseph
Description
The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.
Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.
Input
The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.
Output
The output file will consist of separate lines containing m corresponding to k in the input file.
2244 Eeny Meeny Moo
Description
Surely you have made the experience that when too many people use the Internet simultaneously, the net becomes very, very slow.
To put an end to this problem, the University of Ulm has developed a contingency scheme for times of peak load to cut off net access for some cities of the country in a systematic, totally fair manner. Germany's cities were enumerated randomly from 1 to n. Freiburg was number 1, Ulm was number 2, Karlsruhe was number 3, and so on in a purely random order.
Then a number m would be picked at random, and Internet access would first be cut off in city 1 (clearly the fairest starting point) and then in every mth city after that, wrapping around to 1 after n, and ignoring cities already cut off. For example, if n=17 and m=5, net access would be cut off to the cities in the order [1,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,7]. The problem is that it is clearly fairest to cut off Ulm last (after all, this is where the best programmers come from), so for a given n, the random number m needs to be carefully chosen so that city 2 is the last city selected.
Your job is to write a program that will read in a number of cities n and then determine the smallest integer m that will ensure that Ulm can surf the net while the rest of the country is cut off.
Input
The input will contain one or more lines, each line containing one integer n with 3 <= n < 150, representing the number of cities in the country.
Input is terminated by a value of zero (0) for n.
Output
For each line of the input, print one line containing the integer m fulfilling the requirement specified above.
1012打表做法 C :
#include<stdio.h>
int a[14]={2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,13482720};
int main()
{
int i;
while ( scanf("%d",&i), i != 0 )
printf("%d\n",a[i-1]);
return 0;
} // 这是从网上找的做法，号称打表法，这些数据依旧要通过建立循环链表或是别的模拟法来求出。但是单纯为了AC，这种做法真的是相当有效，讲白了就是有目的的穷举结果。
1012模拟法 C: 可惜呀可惜！这个总是 超时！我不知道是什么原因。但是思路是正确的，可能有些地方我没有考虑到，看到这篇日志的人请指点。
#include<stdio.h>
int main()
{
int i,m,k,cur,rest;
while(1)
{
i=0; // the use ... sort of m in the question
m=0;
scanf("%d",&k);
if (k == 0) break;
while (1)
{
i++;
rest=2*k; // good + bad guys
cur=0;
while (1)
{
cur=(cur+i-1)%rest; // find next from ZERO!
if (cur >= k)
rest--;
else break;
}
if (rest == k)
{
m=i;
break;
}
}
printf("%d\n",m);
}
return 0;
}
对于 2244，建议看一个牛人的ACM博客: www.cppblog.com/AClayton/archive/2007/11/06/35964.html
我就是看这篇博文的，很牛的一个人 AClayton ，写的日期刚好是我生日，下面是其全部博文:
--------------------------------------------------------------------------------------------------------------------------------------------
在没有明白约瑟夫问题之前,只能用模拟来做.
约瑟夫问题是这样的:
假设n个人,编号为1到n,排成一个圈,顺时针从1开始数字m,数到m的人杀了,剩下的人继续游戏.活到最后的一个人是胜利者.一般来说需要编程求解最后一个人的编号.
思路是这样的:
假设当前剩下i个人(i<=n),显然这一轮m要挂(因为总是从1开始数).经过这一轮,剩下的人是:1 2 3 ... m- 1 m + 1 ... i, 我们将从m+1开始的数映射成1， 则m+2对应2， n对应i - m， 1对应成i - m + 1 m - 1对应i - 1，那么现在的问题变成了已知i - 1个人进行循环报数m，求出去的人的序号。假设已经求出了i- 1个人循环报数下最后一个出去的人的序号X0，那么它在n个人中的序号X1=(X0+ m - 1) % n + 1, 最初的X0=1 ,反复迭代X0和X1可以求出.
简单约瑟夫问题的解法:
#include <stdio.h >
main()
{
int n, m,i, s=0;
printf( "N M = "); scanf("%d%d ",&n,&m);
for(i=2;i<=n;i++)s=(s+m)%i;
printf("The winner is %d\n ", s+1);
}
读一个数处理一个数, Memory 68K,时间31MS,如果觉得效率不高. 优化的办法是打表~
-----------------------------------------------------------------------------------------------------------------------------
由此可见，将问题化归为数学问题，用初等高等或是数论来解决的能力是多么重要。
下面是我根据AClayton的思路简化后的代码，可直接AC: 注意，题目让你先让City 1 挂掉
2244 编译器 C :
#include<stdio.h>
void main()
{
int i,r,m,n;
while (scanf("%d",&n) && n)
{
for (m=1; ; m++)
{
for (r=1,i=2; i<=n-1; i++)
r=(r+m-1)%i + 1;
if(r==1) break;
}
printf("%d\n",m);
}
} // 164K 16MS