ある場において出発地点、目的地点、通過可能な場所が与えられた時、出発地点から目的地点までたどり着くことが可能かどうかを判定する到達可能問題を解こうと思います。問題を想定します。幅 width 高さ height の場が与えられ、出発地点と目的地点が与えら…

C++ と OCaml でダイクストラ法の実装を行いました。 ダイクストラ法では、夫々の辺に負でない長さが与えられたグラフ上で、二つの頂点間の最短距離とそれを与える経路を求められます。まずグラフを用意します。 インターネット上でいい感じのグラフを見つけ…

再帰をスタックに直したことが無かったので、 factorial と fibonacci について実行してみた。（ factorial(0) が正しく動かないのは見逃してください。） #include <iostream> #include <stack> using namespace std; int factorial(int n){ int ans = 1; stack<int> s; s.push(n)</int></stack></iostream>…

動的計画法を用いる機会が無くてナップザック問題すら解いたことが無いのでナップザック問題を解きました。入力 n w w1 v1 ... wn vnn 種類の荷物から自由に選択し、重さ w 以下で価値が最大となる組み合わせを選択する。 i 番目の荷物の重さは wi で価値は …

動的計画法を学習してから数年、全然使っていないと思って DNA 配列の LCS を求めるプログラムを書きました。 長さ n の文字列 s と長さ m の文字列 t が与えられたとして、部分文字列がより長く一致する空白（ギャップ）の与え方を求めます。 s の i 番目ま…