パターン認識論 ∼ 宿題 3 ∼ 担当教員：高良富夫

パターン認識論
∼ 宿題 3 ∼
担当教員：高良富夫
学籍番号：065763J
氏名：與儀那広
DP のプログラム
A = abcad, B = acda などの文字列として
{
d(i, j) =
0 (ai = bj のとき)
1 (ai =
6 bj のとき)
DP を用いて異なる文字の数を決定するプログラムを作れ。
(1). ソースプログラムをレポートで報告せよ。プログラムの使い方、実行例、プログラムの限界などの考
察を示せ。
(2). 実行プログラムを nirai において実行できるようにし、そのありか及び使い方をメールで報告せよ。
標準入力から受け取った二つの文字列の異なる文字数を求めるプログラムを作成した。以下にそのソースを示す。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 11
void input(char *, char *);
int getMin(int, int, int);
int main(void){
char a[MAX]; /* A の文字列を格納 */
char b[MAX]; /* B の文字列を格納 */
int d[MAX][MAX]; /* 距離 d(Ai, Bj) */
int g[MAX][MAX]; /* DP 距離 g(Ai, Bj) */
int i, j, a_len, b_len;
input(a, b); /* 2 つの文字列の入力を受け付ける */
a_len = strlen(a);
b_len = strlen(b);
/* 距離 d(Ai, Bj) */
for(i=0; i<a_len; ++i){
for(j=0; j<b_len; ++j){
d[i][j] = a[i] == b[j] ? 0: 1;
}
}
/* DP 距離 g(Ai, Bj) */
g[0][0] = 2*d[0][0];
/* 初期設定 g(A1, B1) = 2d(A1, B1) */
for(i=1; i<=a_len-1; i++){
g[i][0] = g[i-1][0] + d[i][0]; /* B1 の列の計算 */
} for(j=1; j<=b_len-1; j++){
g[0][j] = g[0][j-1] + d[0][j]; /* A1 の行の計算 */
}
/* 最小値を求める */
for(i=1; i<=a_len-1; ++i) {
for(j=1; j<=b_len-1; ++j) {
g[i][j] = getMin( g[i-1][j] + d[i][j],
g[i-1][j-1] + 2*d[i][j],
g[i][j-1] + d[i][j] );
}
}
/* 距離 d(Ai, Bj) 出力 */
puts("\n\td(Ai, Bj)");
for(i=a_len-1; i>=0; i--){
printf("%c ", a[i]);
for(j=0; j<=b_len-1; j++){
printf(" %d ", d[i][j]);
}
printf("\n");
}
printf("／");
for(j=0; j<=b_len-1; j++){
printf(" %c ", b[j]);
}
puts("\n");
/* DP 距離 g(Ai, Bj) 出力 */
puts("\tg(Ai, Bj)");
for(i=a_len-1; i>=0; i--){
printf("%c ", a[i]);
for(j=0; j<=b_len-1; j++){
printf(" %d ", g[i][j]);
}
puts("");
}
printf("／");
for(j=0; j<=b_len-1; j++){
printf(" %c ", b[j]);
}
puts("\n");
printf("DP 距離 = %d\n", g[a_len-1][b_len-1]);
return 0;
}
/* 文字列 A、B を標準入力から受け取る関数 */
void input(char *a, char *b) {
char buf[BUFSIZ];
char *p;
for(;;) {
printf("文字列 A を入力してください ==> ");
fgets(buf, sizeof(buf), stdin);
p = strchr(buf, ’\n’);
*p = ’\0’;
if(strlen(buf) < MAX) {
strcpy(a, buf);
break;
} else {
fprintf(stderr, "＊＊ 10 文字以内の文字列を入力して下さい＊＊\n");
}
}
for(;;) {
printf("文字列 B を入力してください ==> ");
fgets(buf, sizeof(buf), stdin);
p = strchr(buf, ’\n’);
*p = ’\0’;
if(strlen(buf) < MAX) {
strcpy(b, buf);
break;
} else {
fprintf(stderr, "＊＊ 10 文字以内の文字列を入力して下さい＊＊\n");
}
}
}
/* 引き数の中で最も小さい値を返す関数 */
int getMin(int a, int b, int c) {
if(a<b) {
if(a<c) return a;
else return c;
}
else {
if(b<c) return b;
else return c;
}
}
以下に、このプログラムの実行例を示す。
¶
³
% ./rep3
文字列 A を入力してください ==> abcad
文字列 B を入力してください ==> acba
µ
d
a
c
b
a
／
d(Ai, Bj)
1 1 1 1
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
a c b a
d
a
c
b
a
／
g(Ai, Bj)
3 3 4 3
2 2 3 2
2 1 2 3
1 2 1 2
0 1 2 2
a c b a
DP 距離 = 3
´
プログラムを実行すると、文字列を入力するように言われるので２つの文字列を標準入力から入力する。この
プログラムは、10 文字以内の文字列を扱うようにしている。なので、それ以上の文字を入力すると警告文を表示
して、入力をやり直させるようにしている。以下にそのようすを示す。
¶
µ
³
% ./rep3
文字列 A を入力してください ==> 0123456789
文字列 B を入力してください ==> abcdefghijk
＊＊ 10 文字以内の文字列を入力して下さい＊＊
文字列 B を入力してください ==>
考察
このプログラムの限界点は、文字列の長さが制限されている点にある。文字列を格納する配列の大きさをマク
ロを使って定義してるので、10 文字以上の文字列を扱いたいときはソースコードを編集しないといけない。
このプログラムを編集するとしたらリソースを無駄無く使用し、かつ扱う文字列の大きさを動的に扱うために
malloc() 関数などを用いないといけないだろう。
´

Download Report