ヨセフスの問題の考察（５）の解

　ヨセフスの問題の考察（５）を示します。

考察（５）

　p=f(n,k)とすると、

　　f(n,k) = {f(n-1,k)+k} mod n

が成り立つ。ただし、f(n,k)=0のとき、f(n,k)=nとする。

　n-1人の円陣を考え、数えだしの人①から反時計回り方向に数えて、k番目の人とk+1番目の人の間に一人◎加えて、n人の円陣とする。

　新たに加えた人◎から時計回り方向に数えてk番目の人●（①の左隣り）を除くと、つぎの数えはじめの人は①になる。

すなわち、n-1人の円陣の場合に帰着する。

このとき、◎の人を1番目とみなすと、最後に残る人は、◎の人から数えて、k+f(n-1,k)番目になる。k+f(n-1,k)の値がnを超えるときは、nで割った余りとし、nに等しいときは、nとする。すなわち、

　　f(n,k) = {f(n-1,k)+k} mod n

が成り立つ。ただし、f(n,k)=0のとき、f(n,k)=nとする。

●関係式を計算するプログラム

' n人で円陣を作ってk番目ごとに除いていった場合、
' 数えだしの人からp番目の人が最後に残ったとする。
' nとkが与えられたとき、pを求めるプログラム。
'
Dim F(20,20): ' 

' 初期設定。
NMAX=20: ' nの最大値。
For K=1 To NMAX: F(1,K)=1: Next K
'
' p=f(n,k)の計算。
For N=2 To NMAX
  For K=1 To NMAX
    P=(F(N-1,K)+K) Mod N
    If P > 0 Then F(N,K)=P Else F(N,K)=N
  Next K
Next N
'
' 計算結果の表示。
Print"    ";
For K=1 To NMAX: Print Using"###";K;: Next K: Print
For J=1 To 4+3*NMAX: Print"-";: Next J: Print 
For N=1 To NMAX
  Print Using"###:";N;
  For K=1 To NMAX: Print Using"###";F(N,K);: Next K
  Print
Next N
For J=1 To 4+3*NMAX: Print"-";: Next J: Print
End