しりとりプログラム

[p3]

[1] 質問文
　[1.1] しりとりを行うプログラムです。
　[1.2]
　[1.3]
　[1.4] 土台となる部分から作ることができませんでした。

[2] 環境 　
　[2.1] OS ： Windows
　[2.2] コンパイラ名 ： gcc
[3] その他
　・Ｃ言語はある程度の基礎は分かっております。

問題文は以下のようなものです。
ファイルword.txt から英単語を読み込み、その中で最初の文字がa である単語から始ま
るしりとりを行うプログラムを作成せよ。より多くの単語をつなげられるほど望ましい。
なお、しりとりを行うプログラムとword.txt は同じディレクトリにあるものとする。
入力ファイルの形式
ファイルword.txt は小文字のアルファベットのみで構成される英単語を複数個(1 以上
10000 以下)含む。1 つの単語の文字数は1 以上40 以下である。単語間の区切りとして1 つ
以上の空白が挿入されている。
しりとりのルール
ある単語に対して次の単語をつなげるためには、ある単語の最後の文字と次の単語の最
初の文字が等しくなければならない。最後の文字として使用が禁止されている文字はない
(任意のアルファベットで終了する単語を使用してもよい)。同じ単語は、word.txt の中身で
登場した回数だけ使用できる。
例. the note this the pool key the がword.txt の中身であった場合、しりとりにおいて
the は3 回、note、this、pool、key はそれぞれ1 回使用できる。
出力
最初の文字がa である単語を1 番目として、しりとりの順序につなげられた単語のみを
順に出力すること。各単語の間には1 つの空白文字を入れること。出力先は標準出力とす
る。
実行例
ファイルword.txt の例：
dot pwd rmdir through file current list change concatenate or copy text ls directory file
cp mv directories make mkdir contents working a browse change or cat files rm display
the cd the permissions chmod the and directories of or of of more directory directory
working directory display move a remove files pathname mode files the rename remove
page
しりとりプログラムの実行結果：
a a and dot text the

どなたかよろしくお願いします。

　

[Haru]

ちょっと長すぎて最後までしっかり読んでないんですが・・・
word.txt に英単語を入力するところまでは手動で行うんですよね？

そこまで終わったら次は、とりあえず
word.txt ファイルオープン → 最初の文字がa である単語を探す
→　表示 ・・・

って感じなのかと思うんですが、ここまではできてますか？

[Mist]

少しずつ進めていくのがいいかと思います。

まず、word.txtから全ての文字を配列に取り込むところまで作れますか？

[p3]

最初の部分からできていない状態です。。。
ちなみにword.txtというファイルにははじめから英単語がいくつか入っています。

[Haru]

　
>>・Ｃ言語はある程度の基礎は分かっております。

基礎はわかっているようなので、Mistさんのおっしゃるとおり少しずつ
進めてみましょう。

ちなみに、何がわかりませんか？

[non]

質問があります。

１　word.txt ファイルをすべて、メモリに読み込んで良いのか、否か？

２　>より多くの単語をつなげられるほど望ましい。
これは、一番単語数が多くなるような解を求めなければいけないということなのか？

３　>土台となる部分から作ることができませんでした。
プログラムはできなくても、アルゴリズムが組めるなら、その考えを示して欲しい。

４　>Ｃ言語はある程度の基礎は分かっております。
再帰呼び出しはわかりますか？
構造体はわかりますか？
リスト構造はわかりますか？
２分木構造はわかりますか？

以上、回答をお願いします。

　
　　

[p3]

質問があります。

１　word.txt ファイルをすべてメモリに読み込んで良いです。
２　一番単語数が多くなるような解を求めなければいけないということはありません。
３　今のところ考えているプログラムとしては、
単語の読み込み→記憶された文字(一番初めならa)の発見→出力→発見した文字の終わりの文字を記憶
→発見した単語の消去→単語の読み込み・・・とういような動作を考えています。

４再帰呼び出し、構造体は一応習っております。

[たかぎ]

参考までにC++で書いてみました。

#include <iostream>
#include <fstream>
#include <deque>
#include <map>
#include <string>
#include <cctype>

int main()
{
	std::ifstream ifs("word.txt");
	std::map<char, std::deque<std::string> > m;
	std::string s;

	while (ifs)
	{
		ifs >> s;
		m[std::tolower(s[0])].push_back(s);
	}

	for (s = "a";  !s.empty(); )
	{
		std::cout << s << ' ';
		char c = std::tolower(*s.rbegin());
		std::deque<std::string>& d = m[c];
		if (!d.empty())
		{
			s = d.front();
			d.pop_front();
		}
		else
		{
			s.clear();
		}
	}
	std::cout << std::endl;
}

これを参考にして、Cのコードは自分で考えてみてください。

[Mist]

http://detail.chiebukuro.yahoo.co.jp/qa ... 1328789843

マルチさん

[non]

>２　一番単語数が多くなるような解を求めなければいけないということはありません。

そうですか。ただ単に、しりとりをするだけでいいのなら、ｐ３さんの方法でいけるでしょう。
>単語の読み込み→記憶された文字(一番初めならa)の発見→出力→発見した文字の終わりの文字を記憶
>→発見した単語の消去→単語の読み込み・・・とういような動作を考えています。

ただ、１文字の単語（例えばa）の場合、aの個数だけ最初に全部しりとりしてしまった方が
必ず長くなりますね。ということは、ソートした方がいいかもしれません。

それでは。Mistさんがおっしゃっているように、配列に読み込む部分を作って、わからないところを
尋ねてください。

[KEYONN_]

p3さんへ
word.txtをアップロードして欲しいです。
お願いします。

[やそ]

>TKOZさんへ
とりあえず、問題文の最後に実行例として単語が並べられてあるようなので、それをword.txtの中身としてよいかと思います。

>p3さんへ
問題文にある前提条件（ルール）を確認してみましょう。
入力ファイルの形式
ファイルword.txt は小文字のアルファベットのみで構成される英単語を複数個(1 以上
10000 以下)含む。1 つの単語の文字数は1 以上40 以下である。単語間の区切りとして1 つ
以上の空白が挿入されている。
なのですから、
配列の大きさは４０×１００００が最大ということはわかりますか？
1文字づつ読み込んで、配列に代入し、スペースがきたらひとつの単語終了です。
これをファイル（データ)の終端まで繰り返し、配列を完成させてください。
で、printf関数などで表示してみて、思うとおりに表示されているかを確認しましょう。

おしりとっちゃうぞ！のプログラムはその次です＾＾

[KEYONN_]

３日間ねばりましたが、これが、私の限界のようです。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

#define MAX 40

typedef struct W{
    char Word[MAX];
    int kaisuu;
}W;

int WordCount(char str[/url])
{
    int i;
    int count=0;
    
    for(i=0;str!='\n';i++)
    {
        if(str==' ')
            count++;
    }
    return count+1;
}
char *ChopChopChop(char str[/url],int num)
{
    //文字列strの中の文字' 'からnum番目の文字列を取り出す関数
	static char str2[300];
	int Number=0;
	int i,j;
	
	for(j=0;j<=num;j++)
	{
		
		for(i=0;i<strlen(str2);i++)
		{
			str2=' ';
		}
		str2[i+1]='\0';
		
		for(i=Number;str!=' ';i++)
		{
			str2[i-Numbe[/url]=str;
		}
		str2[i-Numbe[/url]='\0';
		Number=i+1;
	}
	
	return str2;
}

int FileLoad(W *buf,char filename[/url])
{
    FILE *fp;
    int i=0,j=0;
    char tmp[40];
    fp=fopen("words.txt","r");
        while(fgets((buf+i)->Word,MAX,fp) != NULL)
        {
            for(j=0;j<WordCount((buf+i)->Word)-1;j++)
            {
                strcpy(tmp,ChopChopChop((buf+i)->Word,j));
                strcpy((buf+i)->Word,tmp);
                printf("tmp=%s:",tmp);
            }
            i++;
        }
    fclose(fp);
    return i;
}


char FirstCharacter(char word[/url])
{
    return word[0];
}

char LastCharacter(char word[/url])
{
    int i;
    for(i=0;word!='\0';i++)
    {
        i++;
    }
    return word[i-1];
}

int Chain(W *buf,int max)
{
    int i,j,k;
    static int flag=0;
    static int counter=0;
    static char Start[MAX];
    static char Next[MAX];
    static int missflag=0;
    
    
    if(counter==0)
    {
        strcpy(Next,(buf+rand()%max)->Word);
        printf("%s ",Next);
    }
    else
    {
        static char c;
        
        c=LastCharacter(Next);
        for(i=0;i<max;i++)
        {
            //printf("tbl[%d]=%s:",i,tbl);
            if(FirstCharacter((buf+i)->Word)==c)
            {
                
                strcpy(Next,(buf+i)->Word);
                printf("%s ",(buf+i)->Word);
                //(buf+i)->kaisuu--;
                missflag=0;
                break;
            }
            
        }
        return -1;
    }
    
    counter++;
    if(counter>1)
    counter=1;
    
}

int main()
{
    W word[10000]={0};
    int max;
    
    srand(time(NULL));
    
    max=FileLoad(word,"../words.txt");
    
    printf("maxは%d個でした。\n",max);
    
    while(1)
    {
        if(Chain(word,max)==-1)
            break;
    }
    return 0;
}

うまく行ったり、いかなかったり、よく分からないプログラムです。

[non]

まだ、少ししか見ていませんが、
FileLoadの関数で
> while(fgets((buf+i)->Word,MAX,fp) != NULL)
とありますが、１行の長さはMAXより大きいと思われますし、
あとで分解することも考えれば、fscnafを使った方が簡単だと思います。

[non]

char LastCharacter(char word[/url])
の関数ですがi++がダブってます。

単語を使用したかどうかをチェックしてませんね。
たぶん、その前がうまくいかないから途中で止めたのですね。