問題 ハノイの塔 ３つの塔とN枚のサイズの異なる円盤がある。１つの塔から別の塔に移動させる。 １度に１つの円盤しか動かせない。 塔の一番上の円盤だけ移動できる 円盤はそれよりも大きいものの上にしか置けない。 考え方 まずは具体的にやってみる。塔をs…

問題 ある集合の全ての部分集合を返す 考え方 再帰的に考える。 N-1この要素の全ての部分集合がわかっているときに、次の部分集合はどうなるか？ N個目の要素を加えたsubsetsを元のsubsetsに加えれば良い。 f(n) = f(n-1) + {f(n-1), set[n]} コード例 def a…

問題 ソートされた配列からA[i] = iとなるindexを探す。配列が重複した値を持つ場合にどうするか。 考え方 2分探索的な方法で探す。 重複した値がある時は少しややこしくて、結局両側を探すしかない。ただし、探す範囲は mid > A[mid]ならば、左側はindexが0…

問題 r行c列のグリッドに障害物がいくつかある。左上から右下にいく経路を探索する。ただし、動ける方向は右と下のみ。 考え方 グリッド (i,j)にたどり着けるかどうかをTrue or Falseで格納する。flg[i][j]は左側flg[i][j-1]と上側flg[i-1][j]を見れば到達で…

問題 n段の階段を上がるときに、１ステップで１段、２段、３段のどれかであがれるときに考えられる上がり方の合計は？ 考え方 n段目にはn-1段目から１段で、n−２段目からは2段、n-3段目には３段であがれる。 つまり、f(n) = f(n-1) + f(n-2) + f(n-3)である…