http://acm.pku.edu.cn/JudgeOnline/problem?id=2244 在沒有明白約瑟夫問題之前,只能用模擬來做.
約瑟夫問題是這樣的:
假設(shè)n個人,編號為1到n,排成一個圈,順時針從1開始數(shù)字m,數(shù)到m的人殺了,剩下的人繼續(xù)游戲.活到最后的一個人是勝利者.一般來說需要編程求解最后一個人的編號.
思路是這樣的:
假設(shè)當(dāng)前剩下i個人(i<=n),顯然這一輪m要掛(因為總是從1開始數(shù)).經(jīng)過這一輪,剩下的人是:1 2 3 ... m- 1 m + 1 ... i, 我們將從m+1開始的數(shù)映射成1， 則m+2對應(yīng)2， n對應(yīng)i - m， 1對應(yīng)成i - m + 1 m - 1對應(yīng)i - 1，那么現(xiàn)在的問題變成了已知i - 1個人進行循環(huán)報數(shù)m，求出去的人的序號。假設(shè)已經(jīng)求出了i- 1個人循環(huán)報數(shù)下最后一個出去的人的序號X0，那么它在n個人中的序號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);
} 這倒題其實不是完全的約瑟夫問題,而是稍微變了形.呵呵,聰明的讀者自己發(fā)現(xià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);
}
}
讀一個數(shù)處理一個數(shù), Memory 68K,時間31MS,如果覺得效率不高. 優(yōu)化的辦法是打表~