サル選大王-ジョセフ問題
729 ワード
【問題の説明】n匹のサルの中から1人の王を選ぶ.次の方法を使用します.
n匹のサルが輪になって、1からnまで順番に番号をつけます.Q番目のサルから始まり、1からmまで数え、mに報告されたサルは選挙を脱退し、次は脱退したサルの次のサルから1からmまで数え、残りの最後のサルが王になるまで.最後にどのサルが大王に選ばれたか教えてください.
【入力形式】コンソールは、3つの整数n,m,qを入力する.
【出力形式】最後に大王に選ばれたサル番号を出力します.
【サンプル入力】
7 4 3
【サンプル出力】
4
【サンプル説明】入力整数n=7,m=4,n=3,出力4
典型的なジョセフ問題は,1匹のサルを取り除いた後,(n−1)匹のサルを一定の法則で番号を並べ直した後に王を選ぶことに相当するという考え方である
n匹のサルが輪になって、1からnまで順番に番号をつけます.Q番目のサルから始まり、1からmまで数え、mに報告されたサルは選挙を脱退し、次は脱退したサルの次のサルから1からmまで数え、残りの最後のサルが王になるまで.最後にどのサルが大王に選ばれたか教えてください.
【入力形式】コンソールは、3つの整数n,m,qを入力する.
【出力形式】最後に大王に選ばれたサル番号を出力します.
【サンプル入力】
7 4 3
【サンプル出力】
4
【サンプル説明】入力整数n=7,m=4,n=3,出力4
典型的なジョセフ問題は,1匹のサルを取り除いた後,(n−1)匹のサルを一定の法則で番号を並べ直した後に王を選ぶことに相当するという考え方である
#include
int f(int n, int m, int q)
{
if (n == 1)
return 1;
if (q > 1)
return (f(n, m, 1) + q - 2) % n + 1;
else
return (f(n - 1, m, 1) + m - 1) % n + 1;
}
int main()
{
int n, m, q;
scanf("%d %d %d",&n,&m,&q);
printf("%d",f(n,m,q));
return 0;
}