約瑟夫環(huán)實(shí)在是太奇妙啦（我很高興我的這篇原創(chuàng)文章被不少人轉(zhuǎn)載了，雖然他們都沒有引用出處... ...）！
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;
} // 這是從網(wǎng)上找的做法，號(hào)稱打表法，這些數(shù)據(jù)依舊要通過建立循環(huán)鏈表或是別的模擬法來求出。但是單純?yōu)榱薃C，這種做法真的是相當(dāng)有效，講白了就是有目的的窮舉結(jié)果。
1012模擬法 C: 可惜呀可惜！這個(gè)總是 超時(shí)！我不知道是什么原因。但是思路是正確的，可能有些地方我沒有考慮到，看到這篇日志的人請(qǐng)指點(diǎn)。
#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;
}
對(duì)于 2244，建議看一個(gè)牛人的ACM博客: m.shnenglu.com/AClayton/archive/2007/11/06/35964.html
我就是看這篇博文的，很牛的一個(gè)人 AClayton ，寫的日期剛好是我生日，下面是其全部博文:
--------------------------------------------------------------------------------------------------------------------------------------------
在沒有明白約瑟夫問題之前,只能用模擬來做.
約瑟夫問題是這樣的:
假設(shè)n個(gè)人,編號(hào)為1到n,排成一個(gè)圈,順時(shí)針從1開始數(shù)字m,數(shù)到m的人殺了,剩下的人繼續(xù)游戲.活到最后的一個(gè)人是勝利者.一般來說需要編程求解最后一個(gè)人的編號(hào).
思路是這樣的:
假設(shè)當(dāng)前剩下i個(gè)人(i<=n),顯然這一輪m要掛(因?yàn)榭偸菑?開始數(shù)).經(jīng)過這一輪,剩下的人是:1 2 3 ... m- 1 m + 1 ... i, 我們將從m+1開始的數(shù)映射成1， 則m+2對(duì)應(yīng)2， n對(duì)應(yīng)i - m， 1對(duì)應(yīng)成i - m + 1 m - 1對(duì)應(yīng)i - 1，那么現(xiàn)在的問題變成了已知i - 1個(gè)人進(jìn)行循環(huán)報(bào)數(shù)m，求出去的人的序號(hào)。假設(shè)已經(jīng)求出了i- 1個(gè)人循環(huán)報(bào)數(shù)下最后一個(gè)出去的人的序號(hào)X0，那么它在n個(gè)人中的序號(hào)X1=(X0+ m - 1) % n + 1, 最初的X0=1 ,反復(fù)迭代X0和X1可以求出.
簡(jiǎn)單約瑟夫問題的解法:
#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);
}
讀一個(gè)數(shù)處理一個(gè)數(shù), Memory 68K,時(shí)間31MS,如果覺得效率不高. 優(yōu)化的辦法是打表~
-----------------------------------------------------------------------------------------------------------------------------
由此可見，將問題化歸為數(shù)學(xué)問題，用初等高等或是數(shù)論來解決的能力是多么重要。
下面是我根據(jù)AClayton的思路簡(jiǎn)化后的代碼，可直接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