数学パズル

 投稿者：山中和義  投稿日：2016年 4月13日(水)10時28分49秒
  問題
長さn[cm]の1本の棒を1[cm]単位に切り分けることを考える。
ただし、1本の棒を一度に切ることができるのは、1人だけである。
切り分けた棒が3本あれば、同時に3人で切ることができる。
最大m人の人がいるとき、最短何回で切り分けることができるかを求めよ。
たとえば、m=3,n=8のときは4回となる。

出題  Q04  プログラム脳を鍛える数学パズル  増井敏克著  翔泳社


PRINT cutbar(3,8)
PRINT
PRINT cutbar(36,100)
PRINT
PRINT cutbar(12,50)
PRINT
PRINT cutbar(24,80)
END
EXTERNAL FUNCTION cutbar(M,N) !1[cm]の棒をm人で結合してn[cm]にする
LET CNT=0 !回数
LET T=1 !棒の長さ
DO WHILE T<N
   IF T<M THEN LET T=T+T ELSE LET T=T+M
   PRINT T !debug
   LET CNT=CNT+1
LOOP
LET cutbar=CNT
END FUNCTION

 		 

Re: 数学パズル

 投稿者：山中和義  投稿日：2016年 4月18日(月)10時05分16秒
  > No.4037[元記事へ]

> プログラム脳を鍛える数学パズル  増井敏克著  翔泳社

Rubyのサンプルコードが掲載されているので、いくつか移植してみる。


問題
ある階段を下からAさんが上がっていくと同時に、上からBさんが下りていく。
階段は1段ずつ上がる（下りる）必要がなく、最大で3段まで飛ばし進む（一気に4段進む）ことができる。
2人が同時に1回ずつ移動するとき、「2人が同じ段に止まるような動き方」が何通りあるかを考える。
10段の階段で同じように移動したとき、2人が同じ段に止まるのは何通りあるか。

出題  Q15  プログラム脳を鍛える数学パズル  増井敏克著  翔泳社


LET N=10 !段数
LET STP=4 !一気に進める段数
DIM DP(0 TO (N+1)-1) !dp=array.new(N+1,0)  t回の移動で移動した位置を集計する
MAT DP=ZER
LET CNT=0
LET DP(N)=1
FOR i=0 TO N-1 !N.times{|i|  移動回数（最大n）
   FOR J=0 TO (N+1)-1 !(N+1).times{|j|  移動元の段
      FOR K=1 TO STP !(1..STP).each{|k|
         IF K>J THEN EXIT FOR !break if k>j
         LET DP(J-K)=DP(J-K)+DP(J) !dp[j-k]+=dp[j]
      NEXT K
      LET DP(J)=0 !移動をクリア
   NEXT J
   IF MOD(i,2)=1 THEN LET CNT=CNT+DP(0) !偶数回の移動で逆に到着
NEXT i
PRINT CNT
END

 		 

戻る