kenjuの日記

About Programming, Mathematics and Security

アルゴリズム問題を解いてみるの巻:階段飛び越しステップ数問題

github.com

問題

以下の場合について、

  1. N=5が与えられたときのXの値は?
  2. N=6が与えられたときのXの値は?
  3. Nに大きい数が入力されても現実的な実行時間で解答できる有効なアルゴリズムを考えよ
You can go up the stairs by 1, 2, or 3 steps at once.

If N is given, answer X, which is the number of 
all combination of steps you can choose to reach the N steps.

For example,

N=1: X is 1
  1

N=2: X is 2
  1-1
  2

N=3: X is 4
  1-1-1
  1-2
  2-1

N=4: X is 7
  1-1-1-1
  2-1-1
  1-2-1
  1-1-2
  2-2
  1-3
  3-1

解答ポイント

  • 数学的帰納法に落とし込める問題は、再帰で解ける
  • 再帰アルゴリズムの最適化には、メモ化が基本の手段

考え方

まず、具体例で考えてみると

  • 1段 = 1パターン
  • 2段 = 2パターン
  • 3段 = 4パターン
  • 4段 = 7パターン
  • 5段 = 13パターン

ということが分かる。

ここで、考え方として、ジャンプの回数は「1, 2, 3」なのだから、N段ある階段を登るのに必要なステップ回数は、

  • 「(n-1)段ある階段を登るのに必要な回数」
  • 「(n-2)段ある階段を登るのに必要な回数」
  • 「(n-3)段ある階段を登るのに必要な回数」

の合計であることがわかる。

すなわち、

底となる条件:
     n = 1のとき、x = 1
     n = 2のとき、x = 2
     n = 3のとき、x = 4
繰り返しの条件:
     nメートルの距離をジャンプで移動するのに必要な回数をXnとおくと、
     Xn = X(n-1) + X(n-2) + X(n-3)
     ただし、n > 3の自然数

を満たす式に帰着できる。

答え

純粋に回答するならば、以下のような感じ。

class Answer
  def answer(n)
    if n == 1
      1
    elsif n == 2
      2
    elsif n == 3
      4
    else
      answer(n - 1) + answer(n - 2) + answer(n - 3)
    end
  end
end

ただしこれだと、answer(n - 1) + answer(n - 2) + answer(n - 3)の箇所における計算量が膨大になってしまう。O(n^3)

ここで、メモ化を導入する。具体的に言うと、一旦計算した値はメモリ上に記憶しておく。

class AnswerWithMemo
  attr_reader :memos

  def initialize
    @memos = []
  end

  def answer(n)
    return memos[n - 1] if memos[n - 1]

    if n == 1
      memos[n - 1] = 1
      1
    elsif n == 2
      memos[n - 1] = 2
      2
    elsif n == 3
      memos[n - 1] = 4
      4
    else
      memo = answer(n - 3) + answer(n - 2) + answer(n - 1)
      memos[n - 1] = memo
      memo
    end
  end
end

実行時間の違い

プロファイラを書いてみよう。

require 'benchmark'
require_relative './answer'

N = 30

answer = Answer.new
answer_with_memo = AnswerWithMemo.new

Benchmark.bm do |x|
  x.report("without memonization:") { answer.answer N }
  x.report("with    memonization:") { answer_with_memo.answer N }
end

自分の実行環境では、↓のように大きな有意差があった。

ruby profile.rb
       user     system      total        real
without memonization:  1.660000   0.000000   1.660000 (  1.667742)
with    memonization:  0.000000   0.000000   0.000000 (  0.000015)