|
|
> No.3837[元記事へ]
> ヨセフスの問題
> シミュレーション
●環状に並べた場合
・カード操作によるシミュレーション
上から順に1,2,3,…,nと並べた1束のカードを手元にとる。
1,2,1,2,…と数えながら、束の上からカードを1枚ずつ取っていく。
1にあたるカードは束の1番下にもっていき、2にあたるカードは捨てる。
これを繰り返す。
求める番号は、最後に残るカードである。
データ構造は、1つのキューになる。
初期の並び
────────────────
→┬→ 12 11 10 9 8 7 6 5 4 3 2 1 →┬→
↑ ──────────────── ↓
│ │
└────────────────────┘
1周目
────────────────
→┬→ 11 9 7 5 3 1 →┬→ 12 10 8 6 4 2
↑ ──────────────── ↓
│ │
└────────────────────┘
2周目
────────────────
→┬→ 9 5 1 →┬→ 11 7 3
↑ ──────────────── ↓
│ │
└────────────────────┘
3周目
────────────────
→┬→ 9 1 →┬→ 5
↑ ──────────────── ↓
│ │
└────────────────────┘
4周目
────────────────
→┬→ 9 →┬→ 1
↑ ──────────────── ↓
│ │
└────────────────────┘
DECLARE EXTERNAL SUB q.enQ, q.deQ
DECLARE EXTERNAL FUNCTION q.count
LET N=12 !石の個数 ※
LET P=2 !1つ飛ばし ※
LET S=0
FOR X=1 TO N !環状に並べる
CALL q.enQ(X)
NEXT X
DO WHILE q.count>0
CALL q.deQ(X)
LET S=MOD(S+1,P) !(p-1)個飛ばし
IF S=0 THEN !この石を取り除く
ELSE
PRINT X
CALL q.enQ(X)
END IF
LOOP
END
MODULE q !キュー
SHARE NUMERIC Q(0 TO 5000) !格納領域
SHARE NUMERIC T,B !ポインタ
LET T=0 !先頭
LET B=0 !末尾
PUBLIC FUNCTION count
EXTERNAL FUNCTION count !個数を返す
LET count=MOD(B-T,5000+1)
END FUNCTION
PUBLIC SUB enQ,deQ
EXTERNAL SUB enQ(X) !入れる
LET Q(B)=X
LET B=MOD(B+1,5000+1)
END SUB
EXTERNAL SUB deQ(X) !取り出す
LET X=Q(T)
LET T=MOD(T+1,5000+1)
END SUB
END MODULE
●直線状に並べた場合
・カード操作によるシミュレーション
上から順に1,2,3,…,nと並べた1束のカードを机に置く。
1,2,1,2,…と数えながら、束の上からカードを1枚ずつ取っていく。
1にあたるカードは隣に積んでいき新しい束をつくり、2にあたるカードは手元に取る。
これを繰り返す。
求める番号は、最後に残るカードである。
データ構造は、2つのスタックになる。
┌──────────────── │
s1│12 11 10 9 8 7 6 5 4 3 2 1 ←┘
│ ─┐
└──────────────── │
┌──────────────── │
s2│1 3 5 7 9 11 ←┘
│ ─┐
└──────────────── │
┌──────────────── │
s1│11 7 3 ←┘
│ ─┐
└──────────────── │
┌──────────────── │
s2│3 11 ←┘
│ ─┐
└──────────────── │
┌──────────────── │
s1│11 ←┘
│
└────────────────
DECLARE EXTERNAL SUB s1.push, s1.pop
DECLARE EXTERNAL FUNCTION s1.count
DECLARE EXTERNAL SUB s2.push, s2.pop
DECLARE EXTERNAL FUNCTION s2.count
LET N=12 !石の個数 ※
LET P=2 !1つ飛ばし ※
LET S=0
LET T=0 !取り除いた石の個数
FOR X=N TO 1 STEP -1 !1列に並べる
CALL s1.push(X)
NEXT X
FOR K=1 TO N*N !p=2のとき、n≧2^k ※半分ずつ減っていく
PRINT "K=";K !奇数は「行き」、偶数は「帰り」
IF MOD(K,2)<>0 THEN LET C=s1.count ELSE LET C=s2.count
DO WHILE C>0
IF MOD(K,2)<>0 THEN CALL s1.pop(X) ELSE CALL s2.pop(X)
LET S=MOD(S+1,P) !(p-1)個飛ばし
IF S=0 THEN !この石を取り除く
LET T=T+1
IF T=N-1 THEN EXIT FOR !残り1個なら
ELSE
PRINT X; !スタックの底から
IF MOD(K,2)<>0 THEN CALL s2.push(X) ELSE CALL s1.push(X)
END IF
IF MOD(K,2)<>0 THEN LET C=s1.count ELSE LET C=s2.count !次へ
LOOP
PRINT
IF S>0 THEN LET S=S-1 !折り返す
NEXT K
END
MODULE s1 !スタック
SHARE NUMERIC STK(5000) !格納領域
SHARE NUMERIC SP !スタック・ポインタ
LET SP=0
PUBLIC FUNCTION count
EXTERNAL FUNCTION count !個数を返す
LET count=SP
END FUNCTION
PUBLIC SUB push,pop
EXTERNAL SUB push(X) !入れる
LET SP=SP+1
LET STK(SP)=X
END SUB
EXTERNAL SUB pop(X) !取り出す
LET X=STK(SP)
LET SP=SP-1
END SUB
END MODULE
MODULE s2 !スタック
SHARE NUMERIC STK(5000) !格納領域
SHARE NUMERIC SP !スタック・ポインタ
LET SP=0
PUBLIC FUNCTION count
EXTERNAL FUNCTION count !個数を返す
LET count=SP
END FUNCTION
PUBLIC SUB push,pop
EXTERNAL SUB push(X) !入れる
LET SP=SP+1
LET STK(SP)=X
END SUB
EXTERNAL SUB pop(X) !取り出す
LET X=STK(SP)
LET SP=SP-1
END SUB
END MODULE
数理マジックに使えるかな!?
|
|