C言語での河渡りの問題

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
初心者

C言語での河渡りの問題

#1

投稿記事 by 初心者 » 14年前

C言語でのプログラムについて質問があります。

人、犬、うさぎ、キャベツがいて、すべてを河を渡らせる問題です。
ルールとしては
犬は人がいないとウサギを食べ、うさぎはキャベツを食べてしまいます。

この問題を総当たりで解くというが問題です。今の考えとしては下のプログラムです

コード:

 
#include<stdio.h>
void init(int b[4][2]);             //2次元配列の初期化
void move(int b[4][2]);        //総当たりの移動
void printstate(int b[4][2]);    //状態を表示

main(){                       //b  人        1  0      2次元配列 で1が いる側 いない川をつくる
	int b[4][2];          //    犬       1   0
	init(b);               //     うさぎ     1   0
	move(b);           //      キャベツ   1    0 
}

void init(int b[4][2]){
	int i=0,j=0;
	for(i=0;i<4;i++)
		for(j=0;j<2;j++){
			if(j=0) b[i][j]=1;
			else b[i][j]=0;
		}
}

void move(int b[4][2]){
if(食べられるような移動の時) return;
else{
move(b);   //moveを再帰呼び出しする
}
printstate(b);
}

void printstate(int b[4][2]){
int i,j;
for(i=0;i<4;i++){
	for(j=0;j<2;j++)
		printf("%3d",b[i][j]);
	printf("\n");
	}
}

 


このような感じです。
move関数がまだできていません
移動の制御の部分ができていません。move関数ないで移動を制御をするには
どのようにすればよいでしょうか。教えてくださいお願いします。

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: C言語での河渡りの問題

#2

投稿記事 by みけCAT » 14年前

とりあえずフォーラムルールを読んでから質問してください。
また、「初心者です」「初心者」「初めまして」「名無し」のような

その場だけの名前、また、多くの人が重複して使うであろう名前は避けてください。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

maru
記事: 150
登録日時: 14年前

Re: C言語での河渡りの問題

#3

投稿記事 by maru » 14年前

「C言語 川渡り」で検索したら、ほとんど同じ問題とそのプログラムが出てきました。
http://www.slis.tsukuba.ac.jp/~hiraga/AI/src/#S_boat1
状態を表わす変数が違いますが、考え方が書いてありますので、移植すればできるでしょう。
ただし、探索経路を記録する変数を用意しておく必要があると思われます。

リサ

Re: C言語での河渡りの問題

#4

投稿記事 by リサ » 14年前

みけCATさんすみません。。。
名前変えました
提出期限が今日の夜までで、2日考えてもわからなかったので
急いでいたので読まずに投稿しました。
改めて
人、犬、うさぎ、キャベツがいて、すべてを河を渡らせる問題です。
ルールとしては
犬は人がいないとウサギを食べ、うさぎはキャベツを食べてしまいます。
この問題を総当たりで解くというが問題です。今の考えとしては下のプログラムです。
move関数がまだできていません
移動の制御の部分ができていません。move関数内で移動を制御をするには
どのようにすればよいでしょうか。

コード:

 
#include<stdio.h>
void init(int b[4][2]);             //2次元配列の初期化
void move(int b[4][2]);        //総当たりの移動
void printstate(int b[4][2]);    //状態を表示
 
main(){                       //b  人        1  0      2次元配列 で1が いる側 いない川をつくる
    int b[4][2];          //    犬       1   0
    init(b);               //     うさぎ     1   0
    move(b);           //      キャベツ   1    0 
}
 
void init(int b[4][2]){
    int i=0,j=0;
    for(i=0;i<4;i++)
        for(j=0;j<2;j++){
            if(j=0) b[i][j]=1;
            else b[i][j]=0;
        }
}
 
void move(int b[4][2]){
if(食べられるような移動の時) return;
else{
move(b);   //moveを再帰呼び出しする
}
printstate(b);
}
 
void printstate(int b[4][2]){
int i,j;
for(i=0;i<4;i++){
    for(j=0;j<2;j++)
        printf("%3d",b[i][j]);
    printf("\n");
    }
}


OS は Linuxでコンパイラはgccです。

C言語は始めたばかりで、あまり理解はしていません。

maruさんありがとうございます。
教えてくださったページは見ていますが
わからなかったので。。。
もう一度見直してみます。

dic
記事: 658
登録日時: 14年前
住所: 宮崎県
連絡を取る:

Re: C言語での河渡りの問題

#5

投稿記事 by dic » 14年前

問題に制限はないでしょうか?
いまの条件のままだと 人、犬、うさぎ、キャベツ 4つ同時に動かせば解決します
おそらく、同時に2つしか動かせないですよね?

リサ

Re: C言語での河渡りの問題

#6

投稿記事 by リサ » 14年前

制限あります。
また書き忘れてしまいました。すみません。
同時に動かせるのは、人とそれ以外1つまでです。
犬、うさぎ、キャベツが移動する時は人とともに移動し
人は単独で移動できます。

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: C言語での河渡りの問題

#7

投稿記事 by みけCAT » 14年前

とりあえず作ってみました。
仕様がいろいろ変ってしまっていますので、必要なら直してください。

コード:

#include<stdio.h>

void init(int b[4][2]);             //2次元配列の初期化
void move(int b[4][2],int maei,int maed);	     //総当たりの移動
void savestate(int b[4][2]);	//状態を保存
void printstate(int b[4][2]);	//状態を表示 
int existstate(int b[4][2]);    //前に同じ状態になったか確かめる 
 
int state[10000][8]={0};
int states=0;
 
main(){					   //b  人             1  0	  2次元配列 で1が  いる側  いない川をつくる
	int b[4][2];		  //	犬            1   0
	init(b);			   //	 うさぎ        1   0
	move(b,-1,-1);		   //	  キャベツ    1	0 
}
 
void init(int b[4][2]){
	int i=0,j=0;
	for(i=0;i<4;i++)
		for(j=0;j<2;j++){
			//if(j=0) b[i][j]=1;
			if(j==0) b[i][j]=1;
			else b[i][j]=0;
		}
}
 
void move(int b[4][2],int maei,int maed){
	int i,no;
	//前に同じ状態になっていたらやめる 
	if(existstate(b))return;
	//状態を保存する 
	savestate(b);
	//終了判定
	if(b[0][0]==0 && b[1][0]==0 && b[2][0]==0 && b[3][0]==0) {
		printstate(b);
		return;
	}
	for(i=0;i<4;i++) {
		//0から1へ動かしてみる
		if(b[0][0] && b[i][0] && (maei!=i || maed!=1)) {//人がいるなら 
			//人と物を動かす
			b[0][0]--; 
			b[0][1]++;
			if(i!=0) {
				b[i][0]--;
				b[i][1]++;
			}
			//食べられてしまうかを判定 
			no=0;
			if(b[0][0]==0) {
		   		if(b[1][0] && b[2][0]) no=1;
		   		if(b[2][0] && b[3][0]) no=1;
			}
			if(b[0][1]==0) {
		   		if(b[1][1] && b[2][1]) no=1;
		   		if(b[2][1] && b[3][1]) no=1;
			}
			if(no==0){
				move(b,i,0);   //moveを再帰呼び出しする
			}
			//人と物を戻す
			b[0][0]++; 
			b[0][1]--;
			if(i!=0) {
				b[i][0]++;
				b[i][1]--;
			}
		}
		//1から0へ動かしてみる
		if(b[0][1] && b[i][1] && (maei!=i || maed!=0)) {//人がいるなら 
			//人と物を動かす
			b[0][1]--; 
			b[0][0]++;
			if(i!=0) {
				b[i][1]--;
				b[i][0]++;
			}
			//食べられてしまうかを判定 
			no=0;
			if(b[0][0]==0) {
		   		if(b[1][0] && b[2][0]) no=1;
		   		if(b[2][0] && b[3][0]) no=1;
			}
			if(b[0][1]==0) {
		   		if(b[1][1] && b[2][1]) no=1;
		   		if(b[2][1] && b[3][1]) no=1;
			}
			if(no==0){
				move(b,i,1);   //moveを再帰呼び出しする
			}
			//人と物を戻す
			b[0][1]++; 
			b[0][0]--;
			if(i!=0) {
				b[i][1]++;
				b[i][0]--;
			}
		}
	}
	states--;
}
 
void savestate(int b[4][2]) {
	state[states][0]=b[0][0];
	state[states][1]=b[1][0];
	state[states][2]=b[2][0];
	state[states][3]=b[3][0];
	state[states][4]=b[0][1];
	state[states][5]=b[1][1];
	state[states][6]=b[2][1];
	state[states][7]=b[3][1];
	states++;
}

void printstate(int b[4][2]){
	int i,j;
	printf("---------------------------\n");
	for(i=0;i<states;i++) {
		for(j=0;j<8;j++) {
			printf("%3d",state[i][j]);
			if(j==3)printf(" | ");
		}
		printf("\n");
	}
}

int existstate(int b[4][2]) {
	int i;
	for(i=0;i<states;i++) {
		if(state[i][0]==b[0][0] &&
		   state[i][1]==b[1][0] &&
		   state[i][2]==b[2][0] &&
		   state[i][3]==b[3][0] &&
		   state[i][4]==b[0][1] &&
		   state[i][5]==b[1][1] &&
		   state[i][6]==b[2][1] &&
		   state[i][7]==b[3][1])return 1;
	}
	return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

maru
記事: 150
登録日時: 14年前

Re: C言語での河渡りの問題

#8

投稿記事 by maru » 14年前

リサ さんが書きました:提出期限が今日の夜までで、
今日の夜までで、C言語を始めたばかりだとちょっと厳しいですね。
リサ さんが書きました:教えてくださったページは見ていますが
わからなかったので。。。
もう一度見直してみます。
ではヒントを。
と思いましたが、まず質問があります。
あなたのプログラムでは、状態を int b[4][2]; で表していますが、これは指示されているのですか?
単純に考えると、川のこちらにいる場合は反対側にはいないので、b[x][0] = 1 のときは必ず b[x][1] = 0 になり、
b[x][0] = 0 のときは必ず b[x][1] = 1 になるので、2次元配列にする必要はありません。
int b[4];で充分です。
件のページではこの状態を表すものを

コード:

struct NODE {				// 状態を表す構造体(配列は経路を表す)
	int T, W, G, C;			// T, W, G, C はそれぞれ LEFT, RIGHT のいずれか
}; 
で宣言しています。
それで、移動はこの構造体の要素を変更することで表しています。

で状態を int b[4][2];で表さなければならないとすると、探索経路を3次元配列か、2次元配列のポインタ配列
を用意する必要があります。

まぁこの制約がないとすれば、すでにプログラムは提示されているので丸写しできちゃいますけどね。

リサ

Re: C言語での河渡りの問題

#9

投稿記事 by リサ » 14年前

みけCATさんありがとうございます
実行して、内容理解してみます

maruさんありがとうございます
特に指定はされていないのでb[4]でも大丈夫です。
構造体はまだ習っていないので難しいです。

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: C言語での河渡りの問題

#10

投稿記事 by みけCAT » 14年前

ところで、出力の形式の指定などはありますか?
リサ さんが書きました:提出期限が今日の夜までで
日本時間ですか?
具体的に何時までですか?
本当にこんなに遅くなってしまって大丈夫なのですか?
差し支えなければお答えください。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

リサ

Re: C言語での河渡りの問題

#11

投稿記事 by リサ » 14年前

提出期限は今日が終わるまでです。
遅れる時も報告すれば少し猶予がもらえるので間に合わなかったら報告します。

出力形式の指定はありません。

maru
記事: 150
登録日時: 14年前

Re: C言語での河渡りの問題

#12

投稿記事 by maru » 14年前

リサ さんが書きました:特に指定はされていないのでb[4]でも大丈夫です。
構造体はまだ習っていないので難しいです。
構造体といってもint型の要素が4つなので配列と考えても大差ありません。

コード:

struct NODE {				// 状態を表す構造体(配列は経路を表す)
	int T, W, G, C;			// T, W, G, C はそれぞれ LEFT, RIGHT のいずれか
} node[NODES];

int Status[16][4];
と読み換えれば、構造体を触っている部分は
node[step].T => Status[step][0];
node[step].W => Status[step][1];
node[step].G => Status[step][2];
node[step].C => Status[step][3];
というように読み替えることが可能です。
ここまで書いちゃえば、ほとんど答えを書いているのと同様です。
なんかカンニングの片棒を担いているようであまりいい気がしませんが。

それにしてもプログラム例がすでに公開されている問題を課題にする方も問題ですね。
もしかすると構造体を教えていないのに使っていたらカンニングだと判定しようとしていたんですかね。

閉鎖

“C言語何でも質問掲示板” へ戻る