質問: ポストの対応問題 非可解問題にポストの対応問題というのがあって。 ポストの対応問題とは、 インスタンス:列の有限集合 {(x_1,y_1),(x_2,y_2)...(x_k,y_k)} があって、x_i1x_i2...x_in=y_i1y_i2...y_in であるような正数列i_1i_2...i_nが存在するかどうか調べる問題です。 具体例として {(1,111),(10111,10),(10,0)} つまりx_1=1,y_1=111,x_2=10111,y_2=10,x_3=10,y_3=0 であり,このとき2113とインスタンスを並べたとき、 x_2x_1x_1x_3=101111110 y_2y_1y_1y_3=101111110 となって同じ数列になる。その他の組み合わせを調べるのに力ずくで見つけるのは、限界があるので、このポストの 対応問題のプログラムは作るろうと思ったのですがプログラム歴が浅いのでまったく歯が立ちませんでした、c言語でどのようにプログラムを作ったらよいでしょうか? プログラム形として、解の上限数を決めて、x_1=1,y=111, x_2=10111,y_2=10,x_3=10,y_3=0と入力して、 結果として x=101111110,y=101111110、解2113、2113の繰り返しを除いたその他のxとyの数列が同じの値と解が出てくるようなプログラムです、質問が分かりにくいとは思いますが、よろしくおねがいします。
回答: 文字列の比較は、xとyの文字をそれぞれstrncatで連結したあとでstrncmpすればいいかと。 サンプル(問題固定、重複解削除なし)です。 文字数を計算しておくとか、解にならない組み合わせを排除しておくなどの工夫をしてないので遅いです。 #include #include #define n 20 /* 解の最大長 */ #define m 3 /* 要素数 */ char xstr[m][10]={"1","100","11"}; char ystr[m][10]={"11","0","0"}; int retsu[n]; /* 解(長さnum)の文字列結合&比較 */ void check(int num) { int i; char xbuf[n*10]="", ybuf[n*10]=""; for (i=0; i