|
投稿者：山中和義
投稿日：2015年 9月16日(水)09時25分2秒
|
|
|
|
問題 2009年 開成中学
1,2,3,…,nの数が1つずつ書かれたn枚のカードを時計回りに数の小さい順に円形に並べます。
次の規則にしたがって、カードを1枚ずつ取り除いていくとき、最後に残るカードがどれであるかを考えます。
・まず、1の書かれたカードを取り除く。
・あるカードを取り除いたら、次に、そのカードから時計回りに数えて2枚目のカードを取り除く。
これをカードが1枚だけ残るまで繰り返す。
(1) n=8とき、最後に残るカードに書かれた数を答えなさい。
(2),(3),(4)は省略
(5) n=2009のとき、最後に残るカードに書かれた数を答えなさい。
答え
(1) 8 ※n=2^kのとき、2^kが残る
(5) 2009=1024+985より、985枚を取り除いたら残り1024（=2^10）枚なので、
985×2+1=1971が1に相当すると考えて、その1つ前の1970が残る。
LET N=8 !2009
LET T=1 !n≦2^k
DO WHILE T<N
LET T=T*2
LOOP
PRINT 2*N-T
END
シミュレーションによる
LET N=8 !2009 !石の個数 ※
DIM A(0 TO N-1) !連番が付いた石
MAT A=ZER
LET P=2 !1つ飛ばし ※
LET i=0 !最初に取り除く石の番号 0～(n-1) ※
LET S=P-1
LET T=0 !取り除いた石の個数
DO WHILE T<N
IF A(i)=0 THEN !石があるなら
LET S=MOD(S+1,P) !(p-1)個飛ばし
IF S=0 THEN !この石を取り除く
PRINT i+1 !debug
LET A(i)=1
LET T=T+1
END IF
END IF
LET i=MOD(i+1,N) !次の石を探す ※
LOOP
END
類題 ヨセフスの問題、継子立ての問題
200枚のカードが1から順に並んで束ねられています。
1番上のカードを1番下に持っていき、次のカードを捨てるという作業を繰り返したとき、
最後に残るカードは何番か答えなさい。
答え
n=2^kのとき、残るのは1が書かれたカードである。
200-72=128=2^7なので、1に相当するのは、72×2+1=145
LET N=200
LET T=1 !n≦2^k
DO WHILE T<N
LET T=T*2
LOOP
PRINT 2*N-T+1
PRINT
!その２
LET B$=BSTR$(N,2) !2進法表記
PRINT B$
LET S$=RIGHT$(B$,LEN(B$)-1) & "1" !最上位の1を最下位へ ※2N-T+1に相当する
PRINT S$
PRINT BVAL(S$,2)
END
|
|
|
|
投稿者：山中和義
投稿日：2015年 9月17日(木)09時38分31秒
|
|
|
|
> No.3835[元記事へ]
> ヨセフスの問題
直線状に並べた場合
k=1,2,3,4,…とする。
p=2のとき、nが2k-1と2kの値は同じになる。
シミュレーションによる
LET N=2015 !石の個数 ※
DIM A(N) !連番が付いた石
MAT A=ZER
LET P=2 !1つ飛ばし ※
LET i=P !最初に取り除く石の番号 ※
LET S=P-1
LET D=1 !方向 ±1
LET T=0 !取り除いた石の個数
DO WHILE T<N-1
IF A(i)=0 THEN !石があるなら
LET S=MOD(S+1,P) !(p-1)個飛ばし
IF S=0 THEN !この石を取り除く
PRINT i !debug
LET A(i)=1
LET T=T+1
END IF
END IF
IF (D<0 AND i=1) OR (D>0 AND i=N) THEN !折り返す
LET D=-D
IF S>0 THEN LET S=S-1
ELSE
LET i=i+D !次の石を探す
END IF
LOOP
FOR i=1 TO N !残った石を探す
IF A(i)=0 THEN PRINT i;
NEXT i
PRINT
END
|
|
|
|
投稿者：山中和義
投稿日：2015年 9月17日(木)13時37分44秒
|
|
|
|
> 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
数理マジックに使えるかな!?
|
|
|
|
投稿者：GAI
投稿日：2015年 9月17日(木)15時35分58秒
|
|
|
|
> No.3837[元記事へ]
山中和義さんへのお返事です。
> > ヨセフスの問題
円形に並べた場合と直線に並べた場合のプログラム有り難うございます。
たまたま
n=2015（個）をp=4（３つ飛ばし）でスタートも4番目の石から取り出すことで調べていたら
円形も直線も共に最後に1522の石が残ることになりました。
これって偶然でしょうがとても興味が涌きました。
そこで円形にも直線にも並べて最後のものが一致する(n,p)の組合せを見つけるプログラムを作って頂けませんか？
ただし共にスタートで取り出す石はp番目の石からとします。
今のところn<=100
を出力して、目をしばしばさせながら探したら
n=19のp=3で17残り
n=34のp=4で22残り
n=77のp=4で34残り
があるようです。
|
|
|
|
投稿者：山中和義
投稿日：2015年 9月17日(木)19時25分15秒
|
|
|
|
> No.3839[元記事へ]
GAIさんへのお返事です。
> そこで円形にも直線にも並べて最後のものが一致する(n,p)の組合せを見つけるプログラムを作って頂けませんか？
> 今のところn<=100
> を出力して、目をしばしばさせながら探したら
> n=19のp=3で17残り
> n=34のp=4で22残り
> n=77のp=4で34残り
> があるようです。
環状の場合は、数理的処理（ヨセフス数）が可能です。
直線の場合は、現状、数理的処理がわかりませんので、シミュレーションさせます。
f(n,1)=nは自明です。
DIM A(5000) !連番が付いた石
FOR N=1 TO 100 !石の個数 ※
FOR P=2 TO N
MAT A=ZER
LET i=P !最初に取り除く石の番号
LET S=P-1
LET D=1 !方向 ±1
LET T=0 !取り除いた石の個数
DO WHILE T<N-1
IF A(i)=0 THEN !石があるなら
LET S=MOD(S+1,P) !(p-1)個飛ばし
IF S=0 THEN !この石を取り除く
!!!PRINT i !debug
LET A(i)=1
LET T=T+1
END IF
END IF
IF (D<0 AND i=1) OR (D>0 AND i=N) THEN !折り返す
LET D=-D
IF S>0 THEN LET S=S-1
ELSE
LET i=i+D !次の石を探す
END IF
LOOP
FOR i=1 TO N !残った石を探す
IF A(i)=0 THEN EXIT FOR
NEXT i
IF i=josephus(N,P,N) THEN PRINT N;P;i !一致するなら
NEXT P
NEXT N
END
EXTERNAL FUNCTION josephus(N,S,K) !ヨセフス数（Josephus Number）
LET ret=S*K
DO WHILE ret>N
LET ret=INT( ((ret-N)*S-1)/(S-1) )
LOOP
LET josephus=ret
END FUNCTION
|
|
|
戻る