動的計画法

[nobu]

C言語始めて2年の学生です。

改行で区切られた2つの文字列が書かれたテキストファイルを読み込み、動的計画法を使ってその2つの文字列の編集距離を求めるプログラムをつくっています。
コンパイルは通ったんですが、編集距離が正しい値で出ません。
どこがおかしいかわかる方教えてください。よろしくお願いします。

ソースコード長いですがすみません・・・

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 10

int min3(int a, int b, int c)
{

int min;

min = a;

if(min > b)
{
min = b;
}

if(min > c)
{
min = c;
}

return min;
}

int p(const char *x, const char *y)
{

if (x != y)
{
return 1;
} else {
return 0;
}
}

int main(int argc, char *argv[])
{
char data[MAXSIZE][300];
int DP[80][80]; /* DP行列 */
int i, j, k, l, m, n, o, a_string, b_string;
FILE *fp;

if(argc != 2)
{
fprintf(stderr, "Usage: %s <filename>\n", argv[0]);
exit(0);
}

if ((fp = fopen(argv[1], "r")) == NULL)
{
fprintf(stderr, "File %s is not found.\n", argv[1]);
exit(0);
}

for(i = 0; i < MAXSIZE; i++)
{
if (fscanf(fp,"%s", &data[300]) == EOF)
break;

}

a_string = strlen(data[1]);
b_string = strlen(data[2]);

DP[0][0] = 0;

for(k = 1; k <=a_string; k++)
{
DP[k][0] = k;
}

for(l = 1; l <=b_string; l++)
{
DP[0][l] = l;
}

m = DP[k-1][l] + 1;
n = DP[k][l-1] + 1;
o = DP[k-1][l-1] + p(&data[1][k-1], &data[2][l-1]);

for(l = 1; l <=b_string; l++){
for(k = 1; k <=a_string; k++)
{

DP[k][l] = min3(m, n, o);
}
}

printf("edit distance=%d", DP[a_string][b_string]);

return 0;
}

[h2so5]

コードはコードタグで囲ってください。

if (fscanf(fp,"%s", &data[300]) == EOF)
少なくともこの部分はおかしいと思います。

[non]

>if (fscanf(fp,"%s", &data[300]) == EOF)
>少なくともこの部分はおかしいと思います。

>a_string = strlen(data[1]);
>b_string = strlen(data[2]);

data[1]になっているところをみると、間違いじゃないかも？

動的計画法の編集距離なんてプログラムは作ったことがないから、中身はしらない。
何がどうすれば、どんな結果が望ましいかぐらい質問者が説明すべきだろう。
たとえば、２つの文字列なのになぜ、#define MAXSIZE 10　なのだとか？

[box]

data[1]になっているところをみると、間違いじゃないかも？

２次元目の[300]という添字が、配列定義範囲外である点を指摘しているんじゃないかなぁ、なんて思ったりしてます。

[non]

２次元目の[300]という添字が、配列定義範囲外である点を指摘しているんじゃないかなぁ、なんて思ったりしてます。

理由はわかりませんが、わかった上で、故意に使用しているという気もしますよ。
うまく編集距離が出ていないのは、別の原因のようですし。

[box]

わかった上で、故意に使用しているという気もしますよ。

個人的には、とてもそうは思えませんけどね。 (^^;)
よくないであろうことを故意に行なっているという状況が、私の悪い頭ではじゅうぶん理解できてません。

[xxx]

DPの状態はk文字目,l文字目になるまでの編集回数だと思うけど・・・

DP[k][l] = min3(m, n, o);
だと直前の状態を考慮してないんでうまくいかないかと

[h2so5]

私の曖昧な書き込みが波紋を呼んでしまっているようで...すみません。

しかし故意にやっているのだとしたら、
&data[300]　
という表記ではなく、
&data[i+1][0]
と記するのではないでしょうか？
本人に答えていただかないと結局は分かりませんが。　

[box]

私の曖昧な書き込みが波紋を呼んでしまっているようで...すみません。

全然あいまいではありませんし、おわびする必要もないです。
[300]
と定義した配列を参照するときに
[300]
と書いてあったら何かおかしい、と思うのは、ごく当たり前のことです。

[h2so5]

マルチポストです
http://detail.chiebukuro.yahoo.co.jp/qa ... 1265015777

[non]

私の曖昧な書き込みが波紋を呼んでしまっているようで...すみません。

全然あいまいではありませんし、おわびする必要もないです。
[300]
と定義した配列を参照するときに
[300]
と書いてあったら何かおかしい、と思うのは、ごく当たり前のことです。

その通りです。私が，あのような書き方をしたのは，h2so5さんに対するものではなく，スレ主さんに対するものです。
[300]など，いいわけがない。当然です。
わからないのは，スレ主さんが，なぜあのような使い方をしているのか，その理由が知りたいのです。

[きゅーと]

初めて書き込みます！
細かい部分に目をつぶればだいたいあってると思います。
ただ入力した文字列がずれているような気がします。