「コマ大数学科」を Ruby で(1)
izu-mix.comプログラミングで解けそうな問題だけ解いています。
#001 フィボナッチ数列
問題:
15段の階段を上るとき、1段上るか、2段上るか、2通りの方法を組み合わせて登ると、何通りの登り方があるか。
コード。
def fib(n) return 1 if n == 1 return 2 if n == 2 fib(n - 1) + fib(n - 2) end puts fib(15) #=>987
#042 ミッシングナンバー
問題:
ホテルの部屋の扉に4と9を使わないで1号室から番号をつけていくと500番目の部屋は何号室か?
コード。
def room(goal) room_number = 1 n = 0 loop do n += 1 if room_number.to_s.scan(/[49]/).empty? return room_number if n == goal room_number += 1 end end puts room(500) #=>875
#117 バスケットボール
問題:
バスケットボールの得点は、フリースローが1点、スリーポイントラインの内側からだと2点、外側からだと3点入ります。ちょうど得点が10点になるまでの得点経過は何通りあるでしょうか?
コード。
def point(n) case n when 1 then 1 when 2 then 2 when 3 then 4 else point(n - 1) + point(n - 2) + point(n - 3) end end puts point(10) #=>274
考え方は「#001 フィボナッチ数列」の場合と同じ。
#029 カタラン数
問題:
10人が円卓に座って1人ずつ握手をするとき、全員の手が交差しないように握手する仕方は全部で何通りあるか?
コード。
def count(n) case when n.odd? then 0 when n.zero? then 1 else result = 0 2.step(n, 2) {|i| result += count(i - 2) * count(n - i)} result end end puts count(10) #=>42
これだと n = 30 くらいが限界なので、メモ化するとよい。メモ化すると例えば n = 200 くらいでも一瞬。ちなみに count(200) = 896519947090131496687170070074100632420837521538745909320 である。
#020 ラマヌジャン
問題:
10軒以上、50軒以内の家が並んでおり、1から順に番号がつけてある。
左右の端から順番に番号を足していったとき(すなわち、1から順に足していくのと、大きい方の数字から順に足していくとき)、合計がちょうど同じになる家があったとき、その家の番号を答えよ。
コード。
def find(n) (1..n).each do |i| return [n, i] if (1..i).inject(:+) == (i..n).inject(:+) end nil end p( (10..50).map {|i| find(i)}.compact ) #=>[[49, 35]]
つまり、49軒あったときの35番目の家。
#012 1000
問題:
1~1000の数字が振られている1000個の電球がある。すべてOFFの状態から始めて、1回目の操作で1の倍数の電球のスイッチのON/OFFを切り替え、2回目の操作では2の倍数の電球のON/OFFを切り替える。
このように、n回目の操作でnの倍数の電球のON/OFFを切り替える操作を、1000回目までおこなったとき、最後にONの状態の電球の数は何個か。
コード。
N = 1000 table = Array.new(N + 1, false) (1..N).each {|n| n.step(N, n) {|i| table[i] = !table[i]} } puts table.count(true) #=>31
素直すぎるくらい素直なコードですね。
#196 和と積
問題:
足し合わせても掛け合わせても同じ数になる5つの正の整数と、その数を答えなさい。
5つの数を a, b, c, d, e とおくとき、a ≦ b ≦ c ≦ d ≦ e としてよいのでそうすると、明らかに 1 ≦ e ≦ 5 である(a + b + c + d + e ≦ 5e より 5 ≦ abcd)。よって超素直にコードを書くと
N = 5 (1..N).each do |e| (1..e).each do |d| (1..d).each do |c| (1..c).each do |b| (1..b).each do |a| sum = a + b + c + d + e p [[a, b, c, d, e], sum] if sum == a * b * c * d * e end end end end end
結果は
[[1, 1, 2, 2, 2], 8] [[1, 1, 1, 3, 3], 9] [[1, 1, 1, 2, 5], 10]
となる。さすがにコードが素朴すぎるという向きもあるかも知れないので、ちょっと工夫して
N = 5 def loop(last, args) if args.size == N sum = args.inject(&:+) p [args, sum] if sum == args.inject(&:*) else (1..last).each {|i| loop(i, [i] + args)} end end loop(N, [])
とすると高級に見えるかも知れない。確かにこちらだといくつの整数でもできるという利点がある。例えば N = 13 とするとこんな結果
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3], 18] [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 5], 20] [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 7], 21] [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 13], 26]
になる。ただしこれだとこの N = 13 くらいが限度なので、さらにこうしてみる。
N = 100 def loop(last, args) product = args.inject(&:*) || 0 return if product > N ** 2 #枝刈り if args.size == N p [args, product] if product == args.inject(&:+) else (1..last).each {|i| loop(i, [i] + args)} end end loop(N, [])
途中で「枝刈り」するのである。これだったら N = 100 でも計算できる。
でもこれ、N個だけ数があるとき、最大のそれが N 以下ってちょっと微妙かな。証明できるか?
#038 モンモール問題
問題:
6人でプレゼント交換するとき、6人とも自分のプレゼントをもらわない組み合わせは全部で何通りあるか求めよ。
コード。
N = 6 co = 0 [*0...N].permutation do |presents| catch(:jump) do presents.each_index {|i| throw(:jump) if presents[i] == i} co += 1 end end puts co #=>265
プログラミングで解くと特にむずかしくもないが、紙と鉛筆で解くのはかなりむずかしい。上のリンク先も参照されたい。
ここからは
「コマ大数学科」に挑む
このサイトから問題を拝借いたします(ありがとうございます!)。でもこれ「Yahoo!ジオシティーズ」のホームページなのですが、サービス終了で消えちゃうのでしょうか。もったいないなあ。。。
2007年10月3日放送 第3問
問題:
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0710.html
直径ABの円とAの地点に点Pがある。直径(線分)ABが円に沿って等速で一回転する間に点PもAからBへ等速で移動する。このときの点Pの軌跡を書きなさい。
お絵かきですね。これは自作の Gem 'oekaki' を使ってアニメーションしてみましょう。
黄色い点が点A、緑の点が点P です。
コード。
require 'oekaki' class Vector def scrn() [150 + self[0], 150 - self[1]] end end R = 130 #円の半径 Steps = 200.0 #全ステップ数 agl_step = 2 * PI / Steps rad_step = R * 2 / Steps pa = ->(n) {Vector[cos(agl_step * n), sin(agl_step * n)] * R} pb = ->(n) {Vector[cos(PI + agl_step * n), sin(PI + agl_step * n)] * R} pp = ->(n) { a, b = pa.(n), pb.(n) a + (b - a) / (2 * R) * rad_step * n } Oekaki.app do white = color(0xffff, 0xffff, 0xffff) yellow = color(0xffff, 0xffff, 0) green = color(0, 0x8000, 0) n = 0 draw do clear(color(0xffff, 0xe709, 0xd65c)) circle(false, 150, 150, R, white) end id = timer(50) do circle(true, *pa.(n).scrn, 3, yellow) circle(true, *pp.(n).scrn, 3, green) n += 1 timer_stop(id) if n > Steps true end end
関数 pa.(n), pb.(n), pp.(n) はそれぞれ n ステップ目の点A, B, P の位置を返します。
Gem 'cairo' を使って GIFアニメにしてみました。こちらの方がきれいかな。
画像生成のためのコードはこちら。
順列組み合わせ(2007/11/6)
問題:
1枚500円のチケットを買うために、500円しか持っていない人6人と1000円札しか持っていない人6人、合わせて12人が並んでいます。しかし、いまチケット売り場にはつり銭がありません。つり銭に不足が無いようにチケットを販売できる12人の並び方は全部で何通りあるでしょうか?
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0711.html
ただし、各6人の並ぶ順序は考えなくてもよい。
コード。
N = 12 co = 0 def check(visitor500) stock = 0 N.times do |i| if visitor500.include?(i) stock += 1 else stock -= 1 return false if stock < 0 end end true end [*0...N].combination(6) do |vst| co += 1 if check(vst) end puts co #=>132
考え方としては、まず 12人の中から 500円しかもっていない 6人の位置を選んで vst
に入れます。そして、check(vst)
でその並び方でチケットが全員に売れるかチェックしています。メソッド内の変数 stock
は売り場にある 500円玉の数です。
この方法はいわゆる brute-force(総当り)ですね。リンク先ではもっと上手いやり方で考えています。
サイコロ(2007/12/19)
問題: 図のような三角形が並んだ線の上にサイコロの出た目に従って動くことにする。三回サイコロを振ったとき中央の赤い丸に戻る確率を求めよ。 |
table = [[0, 1], [1, 0], [1, -1], [0, -1], [-1, 0], [-1, 1]] co = 0 [*0...6].repeated_permutation(3) do |pips| x, y = 0, 0 pips.each do |pip| x += table[pip][0] y += table[pip][1] end co += 1 if x.zero? and y.zero? end puts Rational(co, 6 ** 3) #=>1/18
変数 table
には、出たサイコロの目に対応する移動方向を定義しています。変数 pips
に 3回サイコロを投げて出た目が入ります。6 ** 3
というのは、サイコロの出方の総数です。つまり、サイコロの目の 6とおりから 3つを重複を許して選ぶ順列の数です。
「ハノイの塔」の二重版(2007/12/28)
問題:
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0712.html
A, B, C の三本の棒があって、中央に穴の空いた大きさのちがう円盤を挿すことができます。異なる大きさの 5枚の円盤が、Aの棒に必ず下の円盤の方が大きくなるように挿してあり、まったく同じものが Cの棒にも挿さっています。
さて、ここで 1回につき 1度円盤を動かせるとして、ここでも大きい円盤は必ず小さい円盤の下になるように動かすとき、すべてを Bの棒に移すには最低何回円盤を動かさねばならないでしょうか。なお、(2枚ずつある)同じ大きさの円盤はどちらが上下でもかまいません。
コード。
def hanoi1(n, from1, to, from2) if n == 1 @procedure << "#{from1}→#{to}" @procedure << "#{from2}→#{to}" else hanoi2(n - 1, from1, to, from2) @procedure << "#{from1}→#{to}" hanoi(n - 1, from2, from1, to) @procedure << "#{from2}→#{to}" hanoi(n - 1, from1, to, from2) end end def hanoi2(n, from, via, to) if n == 1 @procedure << "#{from}→#{to}" else hanoi1(n - 1, from, via, to) @procedure << "#{from}→#{to}" hanoi(n - 1, via, to, from) end end def hanoi(n, from, to, via) if n == 1 @procedure << "#{from}→#{to}" @procedure << "#{from}→#{to}" else hanoi(n - 1, from, via, to) hanoi(1, from, to, via) hanoi(n - 1, via, to, from) end end @procedure = [] hanoi1(5, :A, :B, :C) puts @procedure.size #=>96
これはかなり複雑です。元記事を参照してみて下さい。
虫食い算(2008/3/5)
問題: 右の図の四角の中に0~9の数字を一つずつ入れて計算式が成り立つようにする。このとき、ある数字だけがこの四角に入らない。その数字を答えよ。 |
def number(ar) result = 0 ar.reverse.each_with_index {|n, i| result += n * 10 ** i} result end a = [*0..9] pool = [] a.permutation(9) do |d| next if d[0].zero? or d[4].zero? or d[7].zero? n1 = number(d[0..3]) n2 = number(d[4..6]) n3 = number(d[7..8]) pool += a - d if n1 + n2 + n3 == 2008 end puts pool.uniq #=>8
工夫のないコードですね。時間も(自分の環境で)6.5秒くらいかかっています。もっといいやり方を考えるべきですね。というか、いいやり方を考えるとそのまま解けてしまうのだが(笑)。
なお、上の虫食い算に適合する解は 468とおりもあります。それらがすべて 8 を欠いているというのはおもしろいですね。
すこし改良してみた。
def number(ar) result = 0 ar.each_with_index {|n, i| result += n * 10 ** i} result end a = [*0..9] pool = [] a.permutation(9) do |d| next if d[6].zero? or d[8].zero? next unless d[3] == 1 or d[3] == 2 next unless (d[0] + d[4] + d[7]) % 10 == 8 #高速化 n1 = number(d[0..3]) n2 = number(d[4..6]) n3 = number(d[7..8]) pool += a - d if n1 + n2 + n3 == 2008 end puts pool.uniq #=>8
変更点は三つありますが、わかるかな。これでおおよそ 1.3秒ほどに縮まりました。
フーリエ(2008/3/19)
問題: 右の図の一番下の四角に1~9の異なる数字を一つずつ入れて 隣り合う2つの数字の和を上の四角に書き込んで、一番上の四角の和が100になる場合、一番下の四角の和の最小値を求めなさい。 |
def upper_rows(line) if line.size == 1 line[0] == 100 else upper_rows( line.each_cons(2).map {|a| a[0] + a[1]} ) end end puts [*1..9].permutation(5).map {|l| upper_rows(l) ? l.inject(&:+) : nil}.compact.min #=>24
何だか我ながら再帰+ Ruby らしいコードになりすぎていて、ちょっとわかりにくいくらいですね。これはよいコードなのでしょうか。短いことは短いですけれども。ただ、やっていることは単純で、ふつうの brute-force です。
それにしても、Ruby の Enumerator, Enumerable はすごいな…。よくできている。関数型っぽい。
ペル方程式(2008/6/12)
問題:
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0806.html
同じ大きさの正方形の形に並んでいる兵士の軍団が60あります。
ここに王様1人が加わり、1つの大きな正方形に並べなおすことができるとき、王様を含めた全体の人数は何人か?
コード。
answer = 0 1.step do |i| answer = i * i * 60 + 1 n = Math.sqrt(answer) break if (n - n.to_i).zero? end puts answer #=>961
プログラミングで解くと簡単になってしまう問題。しかし、1.0 のような Float を整数と判断してくれる組み込みメソッドはないようだな。
よく考えてみたら、i が自然数のとき、必ず Math.sqrt(i * i) == i
が成り立たないと上のコードは成立しないな。どうなのだろう。
というわけで簡単に調べてみた。以下のコードを実行する。i = 1 から順に調べていって、成り立たない i が出てくれば終了する。
1.step do |i| if Math.sqrt(i * i) == i print "\e[1Gtrue: i = #{i}" else puts "\e[1Gfalse: i = #{i}" exit end end
とりあえず i = 100590651(約1億)まで調べてみて成り立つことがわかった。まあ少なくともこのあたりまでの数なら、使って大丈夫なことがわかった。
自然数(2008/8/7)
問題:
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0808.html
いくつかの連続した自然数の和が1000になりました。
このときの連続した自然数を求めなさい。
さて、この問題は少し考えてみた。高校数学でやるとおり、j から始めて n 個だけ続く自然数の和を考えて
である。これより
だから、n は 2 以上の自然数なので 2 ≦ n ≦ 44 とわかる。上の式を j について解くと
が自然数になればよい。まあ、もうこれならプログラミングでやらなくとも解けますよね。いちおうコード。
(2..44).each do |n| j = 1000.0 / n + (1 - n) / 2.0 k = j.to_i printf("%3d ~ %3d\n", k, k + n - 1) if j > 0 and (j - k).zero? end
結果。
198 ~ 202 55 ~ 70 28 ~ 52
となる。でも、これもおっかなびっくりの浮動小数点演算なのだよね。答えはいちおう正しいけれど、確信がもてない。
brute-force の整数の演算でやれば確実であるので、やってみる。n の範囲が定まっているので、j の範囲を定めることができて 2 ≦ j ≦ 499 である(理由は省略)。なので、こんなコードが書ける。
(2..44).each do |n| (2..499).each do |j| printf("%3d ~ %3d\n", j, j + n - 1) if n * (n + 2 * j - 1) == 2000 end end
先ほどと同じ答えが出る。これは確実な答えであり、また時間も充分短い(自分の環境で 0.1秒未満)。
よく考えてみたら、Rational を使えば最初のコードで厳密に解けますね。
(2..44).each do |n| j = Rational(1000, n) + Rational(1 - n, 2) k = j.to_i printf("%3d ~ %3d\n", k, k + n - 1) if j > 0 and (j - k).zero? end
魔法陣(2008/8/21)
問題:
10 8 9 7 15 1
四角に1から16までの数字を一つずつ入れ、縦・横・対角線の4つの数字の和が等しくなるようにしなさい。またこの魔方陣の特徴をできるだけ挙げよ。 http://www.geocities.jp/tfujisaki2006/sugaku/komadai0808.html
コード。
numbers = [2, 3, 4, 5, 6, 11, 12, 13, 14, 16] #残っている数字 table = [nil, nil, nil, nil, nil, 10, nil, 8, 9, nil, 7, nil, nil, 15, nil, 1] #魔法陣 def check(table, idx) x, y = idx % 4, idx / 4 sum_x = sum_y = sum_l = 0 4.times do |i| sum_x = sum_x + table[y * 4 + i] rescue nil sum_y = sum_y + table[i * 4 + x] rescue nil sum_l = sum_l + table[(3 - i) * 4 + i] rescue nil end return false if sum_x and sum_x != @sum return false if sum_y and sum_y != @sum return false if sum_l and sum_l != @sum true end def doit(nums, table) if nums.empty? p table.each_slice(4).to_a else nums.each do |n| idx = table.find_index(nil) table[idx] = n doit(nums - [n], table) if check(table, idx) table[idx] = nil end end end numbers.each do |i| table[0] = i @sum = (0..3).map {|j| table[j * 4 + j]}.inject(&:+) doit(numbers - [i], table) end
結果。2とおりあります。
[[16, 3, 2, 13], [5, 10, 11, 8], [9, 6, 7, 12], [4, 15, 14, 1]] [[16, 5, 2, 11], [3, 10, 13, 8], [9, 4, 7, 14], [6, 15, 12, 1]]
バックトラック法で求めているのですが、かなり面倒なコードになってしまいました。もっとすっきり書けないか。
考え方としては、まず左上隅のマスを埋めて、対角線の和(変数 @sum
)を求めます。あとは、まだ使っていない数字(配列 nums
に入っている)を魔法陣にひとつ入れて、check()
メソッドを呼んでその場所にその数字を置いてよいか調べ、true が返れば更にマスを埋めていきます。それの繰り返しで、使っていない数字がなくなれば完成であり、魔法陣を出力してさらに他の解を探します。
祝!100回 花の東大生数学祭り 第1問(2008/8/28)
問題:
図のAからRまでの道で各点を1回ずつ通る道を見つけなさい。
table = {:A=>[:B, :C, :E, :K], :B=>[:A, :D, :F], :C=>[:A, :E, :I, :J, :Q], :D=>[:B, :H], :E=>[:A, :C, :I, :H], :F=>[:B, :G, :K], :G=>[:H, :N, :L, :F, :O], :H=>[:E, :I, :N, :G, :D], :I=>[:C, :E, :J, :N, :H], :J=>[:C, :I, :N], :K=>[:A, :F, :O, :R], :L=>[:G, :M, :R], :M=>[:L, :Q], :N=>[:I, :J, :H, :G, :Q], :O=>[:K, :G, :P], :P=>[:O, :R], :Q=>[:C, :N, :M, :R]} solve = ->(route) { now = route[-1] if now == :R p route if route.size == 18 else table[now].each do |nxt| solve.(route + [nxt]) unless route.include?(nxt) end end } solve.([:A])
結果。
[:A, :B, :D, :H, :E, :C, :I, :J, :N, :Q, :M, :L, :G, :F, :K, :O, :P, :R] [:A, :B, :D, :H, :E, :C, :J, :I, :N, :Q, :M, :L, :G, :F, :K, :O, :P, :R] [:A, :B, :D, :H, :E, :I, :C, :J, :N, :Q, :M, :L, :G, :F, :K, :O, :P, :R] [:A, :B, :D, :H, :E, :I, :N, :J, :C, :Q, :M, :L, :G, :F, :K, :O, :P, :R] [:A, :B, :D, :H, :I, :E, :C, :J, :N, :Q, :M, :L, :G, :F, :K, :O, :P, :R] [:A, :B, :D, :H, :N, :J, :I, :E, :C, :Q, :M, :L, :G, :F, :K, :O, :P, :R] [:A, :C, :E, :I, :J, :N, :Q, :M, :L, :G, :H, :D, :B, :F, :K, :O, :P, :R] [:A, :C, :Q, :M, :L, :G, :N, :J, :I, :E, :H, :D, :B, :F, :K, :O, :P, :R] [:A, :E, :C, :I, :J, :N, :Q, :M, :L, :G, :H, :D, :B, :F, :K, :O, :P, :R] [:A, :E, :C, :J, :I, :N, :Q, :M, :L, :G, :H, :D, :B, :F, :K, :O, :P, :R] [:A, :E, :C, :Q, :M, :L, :G, :N, :J, :I, :H, :D, :B, :F, :K, :O, :P, :R] [:A, :E, :I, :C, :J, :N, :Q, :M, :L, :G, :H, :D, :B, :F, :K, :O, :P, :R] [:A, :E, :I, :J, :C, :Q, :M, :L, :G, :N, :H, :D, :B, :F, :K, :O, :P, :R] [:A, :E, :I, :N, :J, :C, :Q, :M, :L, :G, :H, :D, :B, :F, :K, :O, :P, :R] [:A, :K, :F, :B, :D, :H, :E, :C, :I, :J, :N, :Q, :M, :L, :G, :O, :P, :R] [:A, :K, :F, :B, :D, :H, :E, :C, :J, :I, :N, :Q, :M, :L, :G, :O, :P, :R] [:A, :K, :F, :B, :D, :H, :E, :I, :C, :J, :N, :Q, :M, :L, :G, :O, :P, :R] [:A, :K, :F, :B, :D, :H, :E, :I, :N, :J, :C, :Q, :M, :L, :G, :O, :P, :R] [:A, :K, :F, :B, :D, :H, :I, :E, :C, :J, :N, :Q, :M, :L, :G, :O, :P, :R] [:A, :K, :F, :B, :D, :H, :N, :J, :I, :E, :C, :Q, :M, :L, :G, :O, :P, :R]
答えは一とおりではなかったようですね。単純なバックトラック法で求めています。
続きもどうぞ。
marginalia.hatenablog.com