http://acm.pku.edu.cn/JudgeOnline/problem?id=2244 在沒有明白約瑟夫問題之前,只能用模擬來做.
約瑟夫問題是這樣的:
假設(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可以求出.
簡單約瑟夫問題的解法:
#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);
} 這倒題其實(shí)不是完全的約瑟夫問題,而是稍微變了形.呵呵,聰明的讀者自己發(fā)現(xiàn)!這一點(diǎn)費(fèi)了我很久的時(shí)間,還害我逃了課被點(diǎn)名...
這道題的我解法是這樣的.
#include <stdio.h >
int y(int n,int m)
{
int s=1,i;
for(i=2;i<=n-1;i++)
s=(s+m-1)%i+1;
return s+1;
}
main()
{
int m,n;
while(1)
{
scanf("%d",&n);
if(n==0)break;
for(m=1;;)
{
if(y(n,m)==2)break;
m++;
}
printf("%d\n",m);
}
}
讀一個(gè)數(shù)處理一個(gè)數(shù), Memory 68K,時(shí)間31MS,如果覺得效率不高. 優(yōu)化的辦法是打表~