(cc 11 5) - (cc 11 4) - (cc 11 3) - (cc 11 2) - (cc 11 1) - (cc 11 0)
| | | | |
(cc -39 5) (cc -14 4) | | (cc 10 1) - (cc 10 0)
| | |
| | (cc 9 1) - (cc 9 0)
| | |
| | (cc 8 1) - (cc 8 0)
| | |
| | (cc 7 1) - (cc 7 0)
| | |
| | (cc 6 1) - (cc 6 0)
| | |
| | (cc 5 1) - (cc 5 0)
| | |
| | (cc 4 1) - (cc 4 0)
| | |
| | (cc 3 1) - (cc 3 0)
| | |
| | (cc 2 1) - (cc 2 0)
| | |
| | (cc 1 1) - (cc 1 0)
| | |
| | (cc 0 1)
| |
| (cc 6 2) - (cc 6 1) - (cc 6 0)
| | |
| | (cc 5 1) - (cc 5 0)
| | |
| | (cc 4 1) - (cc 4 0)
| | |
| | (cc 3 1) - (cc 3 0)
| | |
| | (cc 2 1) - (cc 2 0)
| | |
| | (cc 1 1) - (cc 1 0)
| | |
| | (cc 0 1)
| |
| (cc 1 2) - (cc 1 1) - (cc 1 0)
| | |
| (cc -4 2) (cc 0 1)
|
(cc 1 3) - (cc 1 2) - (cc 1 1) - (cc 1 0)
| | |
(cc -9 3) (cc -4 2) (cc 0 1)
プロセスが使うスペースについて。木構造再帰的プロセスに必要なスペースは、木構造の最大の深さに比例する。1セントだけで両替した場合が最も木構造が深く、両替する金額に比例するため、増加の程度はΘ(n)。
プロセスのステップ数について。両替する金額をnとする。1セントだけで両替した場合、nに比例する深さのステップの枝が一本、1セントと5セントで両替した場合、1セントでの両替に分岐する枝が、nに比例する本数存在する。1セントと5セントと10セントの場合、1セントと5セントの両替に分岐する枝が同様となる。このように、ステップ数は、nを底、硬貨の種類を指数とする冪乗に比例する。つまり、五種類の硬貨での増加の程度はΘ(n^5)。
とりあえず、木構造の書き方に困った。画像でも良かったけど、作るのも管理するのも面倒だし。書き方は各所を参考にさせてもらった。
返信削除ステップ数は、最初はピンと来なかったけど、図を見ながら良く考えると、仕組みが理解できた。苦手だからといって、すぐに諦めるのは、やはり良くない。