問題1.14

木構造を手で書け

うおー、しんどい・・・。
でも練習にはちょうどいいか。

; 11の場合
(cc 11 5)
  (cc 11 4)
    (cc 11 3)
      (cc 11 2)
        (cc 11 1)
          (cc 11 0) -> 0
          (cc 10 1)
            (cc 10 0) -> 0
            (cc 9 1)
              (cc 9 0) -> 0
              (cc 8 1)
                (cc 8 0) -> 0
                (cc 7 1)
                  (cc 7 0) -> 0
                  (cc 6 1)
                    (cc 6 0) -> 0
                    (cc 5 1)
                      (cc 5 0) -> 0
                      (cc 4 1)
                        (cc 4 0) -> 0
                        (cc 3 1)
                          (cc 3 0) -> 0
                          (cc 2 1)
                            (cc 2 0) -> 0
                            (cc 1 1)
                              (cc 1 0) -> 0
                              (cc 0 1) -> 1
        (cc 6 2)
          (cc 6 1)
            (cc 6 0) -> 0
            (cc 5 1)
              (cc 5 0) -> 0
              (cc 4 1)
                (cc 4 0) -> 0
                (cc 3 1)
                  (cc 3 0) -> 0
                  (cc 2 1)
                    (cc 2 0) -> 0
                    (cc 1 1)
                      (cc 1 0) -> 0
                      (cc 0 1) -> 1
          (cc 1 2)
            (cc 1 1)
              (cc 1 0) -> 0
              (cc 0 1) -> 1
            (cc -4 1) -> 0
      (cc 1 3)
        (cc 1 2)
          (cc 1 1)
            (cc 1 0) -> 0
            (cc 0 1) -> 1
          (cc -4 2) -> 0
        (cc -9 3) -> 0
    (cc -14 4) -> 0
  (cc -39 4) -> 0

木構造による探索の場合

• スペースの増加量は木の深さ
• ステップの増加量は木の広さ

の増加量となる。

木構造が最も深くなるのは全て1セントを使った場合なので、

スペース : θ(n)

硬貨の種類が5種類なので、

ステップ : θ(n^5)

ステップ数の増加量はなぜそうなるのかいまいち分からない・・・。