再帰関数とメモ化と分割統治法
- 再帰関数
- GCD(m, n) - 2つの整数から最大公約数を求める
- ベースケース
- 可視化
- GCD(m, n) - 2つの整数から最大公約数を求める
再帰関数とメモ化
部分和問題(最適な部分集合を見つける) with 分割統治法
- 再帰関数を使うことで問題を少問題に分割できる
再帰関数
- ベースケース
- 振る舞いの可視化
ユークリッドの互除法
2つの整数m, n(m ≧ n)において、以下の手順を繰り返すことで最大公約数を求めることができる。
- 入力を m, n (m ≧ n) とする。
- n = 0 なら、 mを出力してアルゴリズムを終了する。
- mをnで割った余りを新たに nとし更に 元のnを新たにm とし 2. に戻る。
fn gcd(m: u32, n: u32) -> u32 { return if n == 0 { m } else { gcd(n, m % n) } }
ベースケースと処理の可視化
無限ループしないように、ベースケースを定め、returnする。
再帰関数とメモ化
フィボナッチ数列
部分和問題 with 分割統治法
参考書籍
https://www.amazon.co.jp/問題解決力を鍛える!アルゴリズムとデータ構造-KS情報科学専門書-大槻兼資-ebook/dp/B08PV83L3N