izu-mix.comプログラミングで解けそうな問題だけ解いています。
問題：
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)
#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)
#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)
考え方は「#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)
これだと n = 30 くらいが限界なので、メモ化するとよい。メモ化すると例えば n = 200 くらいでも一瞬。ちなみに count(200) = 896519947090131496687170070074100632420837521538745909320 である。
問題：
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
answer = (10..50).map {|i| find(i)}.compact
p answer
つまり、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)
素直すぎるくらい素直なコードですね。
#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
プログラミングで解くと特にむずかしくもないが、紙と鉛筆で解くのはかなりむずかしい。上のリンク先も参照されたい。
ここからは
「コマ大数学科」に挑む
このサイトから問題を拝借いたします（ありがとうございます！）。でもこれ「
Yahoo!ジオシティーズ」のホームページなのですが、サービス終了で消えちゃうのでしょうか。もったいないなあ。。。
2007年10月3日放送 第3問
問題：
直径ＡＢの円とＡの地点に点Ｐがある。直径（線分）ＡＢが円に沿って等速で一回転する間に点ＰもＡからＢへ等速で移動する。このときの点Ｐの軌跡を書きなさい。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0710.html
お絵かきですね。これは自作の 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）
問題：
１枚５００円のチケットを買うために、５００円しか持っていない人６人と１０００円札しか持っていない人６人、合わせて１２人が並んでいます。しかし、いまチケット売り場にはつり銭がありません。
つり銭に不足が無いようにチケットを販売できる１２人の並び方は全部で何通りあるでしょうか？
ただし、各６人の並ぶ順序は考えなくてもよい。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0711.html
コード。
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).each do |vst|
co += 1 if check(vst)
end
puts co
考え方としては、まず 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).each 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)
変数 table には、出たサイコロの目に対応する移動方向を定義しています。変数 pips に 3回サイコロを投げて出た目が入ります。6 ** 3 というのは、サイコロの出方の総数です。つまり、サイコロの目の 6とおりから 3つを重複を許して選ぶ順列の数です。
「ハノイの塔」の二重版（2007/12/28）
問題：
A, B, C の三本の棒があって、中央に穴の空いた大きさのちがう円盤を挿すことができます。異なる大きさの 5枚の円盤が、Aの棒に必ず下の円盤の方が大きくなるように挿してあり、まったく同じものが Cの棒にも挿さっています。
さて、ここで 1回につき 1度円盤を動かせるとして、ここでも大きい円盤は必ず小さい円盤の下になるように動かすとき、すべてを Bの棒に移すには最低何回円盤を動かさねばならないでしょうか。なお、（2枚ずつある）同じ大きさの円盤はどちらが上下でもかまいません。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0712.html
コード。
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
これはかなり複雑です。元記事を参照してみて下さい。
