ページ 1 ／ 1
C言語での河渡りの問題
Posted: 2011年1月07日(金) 16:50
by 初心者
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関数ないで移動を制御をするには
どのようにすればよいでしょうか。教えてくださいお願いします。
Re: C言語での河渡りの問題
Posted: 2011年1月07日(金) 17:02
by みけCAT
とりあえずフォーラムルールを読んでから質問してください。
また、「初心者です」「初心者」「初めまして」「名無し」のような
その場だけの名前、また、多くの人が重複して使うであろう名前は避けてください。
Re: C言語での河渡りの問題
Posted: 2011年1月07日(金) 17:19
by maru
「C言語 川渡り」で検索したら、ほとんど同じ問題とそのプログラムが出てきました。
http://www.slis.tsukuba.ac.jp/~hiraga/AI/src/#S_boat1
状態を表わす変数が違いますが、考え方が書いてありますので、移植すればできるでしょう。
ただし、探索経路を記録する変数を用意しておく必要があると思われます。
Re: C言語での河渡りの問題
Posted: 2011年1月07日(金) 17:26
by リサ
みけ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さんありがとうございます。
教えてくださったページは見ていますが
わからなかったので。。。
もう一度見直してみます。
Re: C言語での河渡りの問題
Posted: 2011年1月07日(金) 17:36
by dic
問題に制限はないでしょうか？
いまの条件のままだと 人、犬、うさぎ、キャベツ ４つ同時に動かせば解決します
おそらく、同時に２つしか動かせないですよね？
Re: C言語での河渡りの問題
Posted: 2011年1月07日(金) 17:42
by リサ
制限あります。
また書き忘れてしまいました。すみません。
同時に動かせるのは、人とそれ以外1つまでです。
犬、うさぎ、キャベツが移動する時は人とともに移動し
人は単独で移動できます。
Re: C言語での河渡りの問題
Posted: 2011年1月07日(金) 18:53
by みけCAT
とりあえず作ってみました。
仕様がいろいろ変ってしまっていますので、必要なら直してください。
コード:
#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;
}
Re: C言語での河渡りの問題
Posted: 2011年1月07日(金) 19:28
by maru
リサ さんが書きました:提出期限が今日の夜までで、
今日の夜までで、C言語を始めたばかりだとちょっと厳しいですね。
リサ さんが書きました:教えてくださったページは見ていますが
わからなかったので。。。
もう一度見直してみます。
ではヒントを。
と思いましたが、まず質問があります。
あなたのプログラムでは、状態を int b[4][2]; で表していますが、これは指示されているのですか？
単純に考えると、川のこちらにいる場合は反対側にはいないので、b[x][0] = 1 のときは必ず b[x][1] = 0 になり、
b[x][0] = 0 のときは必ず b[x][1] = 1 になるので、２次元配列にする必要はありません。
int b[4];で充分です。
件のページではこの状態を表すものを
コード:
struct NODE { // 状態を表す構造体（配列は経路を表す）
int T, W, G, C; // T, W, G, C はそれぞれ LEFT, RIGHT のいずれか
};
で宣言しています。
それで、移動はこの構造体の要素を変更することで表しています。
で状態を int b[4][2];で表さなければならないとすると、探索経路を３次元配列か、２次元配列のポインタ配列
を用意する必要があります。
まぁこの制約がないとすれば、すでにプログラムは提示されているので丸写しできちゃいますけどね。
Re: C言語での河渡りの問題
Posted: 2011年1月07日(金) 20:17
by リサ
みけCATさんありがとうございます
実行して、内容理解してみます
maruさんありがとうございます
特に指定はされていないのでb[4]でも大丈夫です。
構造体はまだ習っていないので難しいです。
Re: C言語での河渡りの問題
Posted: 2011年1月07日(金) 20:20
by みけCAT
ところで、出力の形式の指定などはありますか？
リサ さんが書きました:提出期限が今日の夜までで
日本時間ですか？
具体的に何時までですか？
本当にこんなに遅くなってしまって大丈夫なのですか？
差し支えなければお答えください。
Re: C言語での河渡りの問題
Posted: 2011年1月07日(金) 20:29
by リサ
提出期限は今日が終わるまでです。
遅れる時も報告すれば少し猶予がもらえるので間に合わなかったら報告します。
出力形式の指定はありません。
Re: C言語での河渡りの問題
Posted: 2011年1月07日(金) 21:10
by maru
リサ さんが書きました:特に指定はされていないのでb[4]でも大丈夫です。
構造体はまだ習っていないので難しいです。
構造体といってもint型の要素が４つなので配列と考えても大差ありません。
コード:
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];
というように読み替えることが可能です。
ここまで書いちゃえば、ほとんど答えを書いているのと同様です。
なんかカンニングの片棒を担いているようであまりいい気がしませんが。
それにしてもプログラム例がすでに公開されている問題を課題にする方も問題ですね。
もしかすると構造体を教えていないのに使っていたらカンニングだと判定しようとしていたんですかね。