DouKaku?beta

challenge いちばん長いしりとり

単語のリストを読み込んで、そのリストにある単語で「しりとり」をします。
一番長くしりとりを続けるためのプログラムを書いてください。
また、単語数に対して、計算量がどのように増えていくかも考えて下さい。

なお、単語リストの一例として
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/index-j.htmlで公開されている
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/fam55_40.txtがあります。

ただし、
・一度使った単語は使わないこと(リストに重複がある可能性は考えなくてよい)
・「ん」で終わる単語を使用するか、リスト内にしりとりを続けられる単語がなくなったときに、しりとりは終了する
・一番最初は、好きな単語から初めてもよい
・「一番長くしりとりを続ける」とは、しりとりが終了するまでに使用する単語数が最大になるよう、しりとりの単語を選ぶことをいう

see: 難聴者のための単語了解度試験用単語リスト

post comment

Posted feedbacks - C

単純に比較しているだけなので、160単語くらいが限界のようです。

お題のサンプルでは、(アイアイ、イチブン、…、ソノミチ、タテガミ）の161単語で(シールド、ドウナガ、…、ムササビ、ビンラン)の8連続が見つかりました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<stdio.h>
#include<string.h>
#define WORDMAX 500
#define MAXLEN 50

char word[WORDMAX][MAXLEN];
int check[WORDMAX], temp[WORDMAX], words[WORDMAX], cnt = 0, cntmax = 0, maxmax = 0;

void siritori(char *word, char *base, int *check, int wordnum, int n)
{
    int i, j;
    
    temp[cnt++] = wordnum;                                    //tmp[]に現在までの語順を保存
    for(i = 0; i < n; i++)                                    //word[0]からword[n-1]までについて、繋がるか調べる
    {
        if(!strcmp(word, base + i * MAXLEN))    continue;    //自分自身が比較対象になった場合
        if((*(word + strlen(word) - 1) == *(base + (i * MAXLEN) + 1)) 
            && (*(word + strlen(word) - 2) == *(base + (i * MAXLEN)))
            && *(check + i))
        {
            *(check + i) = 0;
            siritori(base + i * MAXLEN, base, check, i, n);
            if(cnt > cntmax)
            {
                cntmax = cnt;
            }
            if(cntmax > maxmax)
            {
                maxmax = cntmax;
                for(j = 0; j < cntmax; j++)                    //最も長続きする場合の語順をコピー
                {
                    words[j] = temp[j];
                }
            }
            cnt = 0;
            *(check + i) = 1;
        }
    }
}
    
int main(void)
{
    int i = 0, n = 0;
    char check[1000], buf[100][1000];
    FILE *in;
    
    if((in = fopen("wordlist.txt", "r")) == NULL)
    {
        puts("wordlist.txtが読み込めませんでした");
        exit(1);
    }
    while(!feof(in))
    {
        fscanf(in, "%s", word[i++]);
        n++;
    }
    fclose(in);
    
    for(i = 0; i < n; i++)
    {
        check[i] = 1;
    }
    for(i = 0; i < n; i++)                                //word[i]を始点とする
    {
        check[i] = 0;                                    //word[i]を使用済みとする
        cnt = 0;                                        //cntをリセット
        siritori(word[i], word, check, i, n);
        check[i] = 1;                                    //調べ終わったら、word[i]を未使用とする
    }
    puts("result:");
    for(i = 0; i < cntmax; i++)
    {
        printf("%s\n", word[words[i]]);
    }
    return 0;
}

すみません、コード＆サンプルデータに欠陥があったので修正しました。

(アイアイ、イチブン、…、ヌリムラ、ハヤブサ)の180単語で、(ミズヒキ、キャクアシ、…、ガイユウ、ウラガネ)の13連続が見つかりました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<stdio.h>
#include<string.h>
#define WORDMAX 500
#define MAXLEN 50

char word[WORDMAX][MAXLEN];
int temp[WORDMAX], words[WORDMAX], cnt = 0, cntmax = 0, maxmax = 0;

void siritori(char *word, char *base, int *check, int wordnum, int n)
{
    int i, j;
    
    temp[cnt++] = wordnum;                                    //tmp[]に現在までの語順を保存
    for(i = 0; i < n; i++)                                    //word[0]からword[n-1]までについて、繋がるか調べる
    {
        if(!strcmp(word, base + i * MAXLEN))    continue;    //自分自身が比較対象になった場合
        if((*(word + strlen(word) - 1) == *(base + (i * MAXLEN) + 1)) 
            && (*(word + strlen(word) - 2) == *(base + (i * MAXLEN)))
            && *(check + i))
        {
            *(check + i) = 0;
            siritori(base + i * MAXLEN, base, check, i, n);
            if(cnt > cntmax)
            {
                cntmax = cnt;
            }
            if(cntmax > maxmax)
            {
                maxmax = cntmax;
                for(j = 0; j < cntmax; j++)                    //最も長続きする場合の語順をコピー
                {
                    words[j] = temp[j];
                }
            }
            cnt = 0;
        }
    }
}
    
int main(void)
{
    int i = 0, n = 0, j;
    char check[WORDMAX];
    FILE *in;
    
    if((in = fopen("wordlist.txt", "r")) == NULL)
    {
        puts("wordlist.txtが読み込めませんでした");
        exit(1);
    }
    while(!feof(in))
    {
        fscanf(in, "%s", word[i++]);
        n++;
    }
    fclose(in);
    
    for(i = 0; i < n; i++)
    {
        check[i] = 1;
    }
    for(i = 0; i < n; i++)                                //word[i]を始点とする
    {
        check[i] = 0;                                    //word[i]を使用済みとする
        cnt = 0;                                        //cntをリセット
        siritori(word[i], word, check, i, n);
        for(j = 0; j < n; i++)
        {
            check[i] = 1;
        }
    }
    puts("result:");
    for(i = 0; i < cntmax; i++)
    {
        printf("%s\n", word[words[i]]);
    }
    return 0;
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]