10/02/10 03:03:34
ｽﾚﾘﾝｸ(tech板:554番)
# [1] 授業単元：プログラミング 1
# [2] 問題文(含コード&リンク)：
# /*************************
# ある二つの文字列str1,str2 の編集距離はつぎの３つの操作を行うことによりstr1をstr2 に変換するのに要する操作の最低回数である
# ・ １文字挿入する
# ・ １文字削除する
# ・ １文字を他の１文字に置き換える
# たとえば str1="sport" はstr2="sort" に, 文字 'p' を削除することによりstr2 に変換できるため編集距離は 1 である
#
# str_n を文字列str の頭からn 番目までの部分列としm(i,j)をstr i とstr j の編集距離を表すものとする.m(i,j)とm(i+1,j),m(i,j+1),m(i+1,j+1)の間に成り立つ再帰式を記述しなさい
#
# この再帰式に基づき効率良く編集距離を計算するプログラムを2次元配列を利用して作成しなさい．ただし，関数m(i,j)はint型の編集距離を返り値とする．
# ******************************/