No.10ベストアンサー
- 回答日時:
> この任意の点を選ぶために0~3までの
> 乱数を発生することはできたのですが
> 開始点をシステムのカレンダー時刻を設定しているため
>同じ数ばかり出てきてしまいなかなかうまくいきません。
srand((unsigned)time(NULL));
for(i = 0; i < 100; i ++){
printf("%d ", rand() % 4);
}
これで、実行するたびに違う乱数系列で乱数が生成されます。
回答有難うございます。
乱数の作り方はあっていたみたいです。
迷路の大きさが偶数奇数を問わない迷路をつくるには
どのようにすればよいのでしょうか?
私は等間隔に壁を設定してその間を生めるというやり方にしたのですがこれだと奇数しかできないので
偶数の場合もできるようにするには
根本的にだめなのだと気づいたしだいです。
No.9
- 回答日時:
> どうやったら全体のプログラムを終了させずに
> maze_visitだけを終了できるのでしょうか?
maze_visit() 関数に返り値を設定すればいいのでは?
int maze_visit(int x,int y,Mazestruct *maze,int n){
maze->maze_d[x][y]=TRACE;
if(何か中断したいことが発生) return -1;
if(maze->maze_d[x+1][y]==ROAD){
if(maze_visit(x+1,y,maze,n+1) == -1) return -1;
}
... 以下同様
return 0;
}
初めの maza_visit() 呼び出しの返り値が 0 なら、
全探索して終了したことであり、-1 なら中断してます。
たびたび有難うございます。
最後にもう一つ質問なのですが
迷路の作成もやっているのですが
その中である一点から任意の点に壁を設定したいのですが
この任意の点を選ぶために0~3までの
乱数を発生することはできたのですが
開始点をシステムのカレンダー時刻を設定しているため
同じ数ばかり出てきてしまい
なかなかうまくいきません。
何かいい方法はないのでしょうか?
No.8
- 回答日時:
投稿してもらったプログラム、正しくは下記の通りになります。
void maze_visit(int x,int y,Mazestruct *maze,int n){
maze->maze_d[x][y]=TRACE;
if(maze->maze_d[x+1][y]==ROAD){
maze_visit(x+1,y,maze,n+1);
}
if(maze->maze_d[x][y+1]==ROAD){
maze_visit(x,y+1,maze,n+1);
}
if(maze->maze_d[x-1][y]==ROAD){
maze_visit(x-1,y,maze,n+1);
}
if(maze->maze_d[x][y-1]==ROAD){
maze_visit(x,y-1,maze,n+1);
}
}
迷路を TRACE で埋め尽くすってことですよね。
else if(maze->maze_d[x+1][y]==TRACE){
のように、一度 TRACE したところを再び maze_visit しては
永久に visit し続けますよ (^^;)
なぜ else if を使ったのでしょうかね?
迷路には右にも下にも両方行ける分岐点はありますよね。
n を探索した格子点と解釈されてますが、違いますよ。
n は探索した深さです。つまるところ、
「右いこうかな?左行こうかな?」って迷って
「とりえず右行こう!」ってした時、もし右がすべて
行き止まりだったら、この分岐点に帰ってきますよね。
その覚えておく(覚えている)分岐点の数が n です。
アドバイスありがとうございます。
格子点を数えるならこの関数を呼び出した回数を数えればいいのですよね?
staticな変数で呼び出した回数は分るのですが
どうやったら全体のプログラムを終了させずに
maze_visitだけを終了できるのでしょうか?
また、見当はずれなことをやっているかもしれませんが
教えてください。
No.7
- 回答日時:
最短経路は、この春のソフトウェア開発技術者試験に出ていましたよ。
■ス■■■■■■■ゴ■■
■1■5■BCD■L■■
■234■A■■■KJ■
■3■5■9■B■■I■
■4■6789A■GH■
■■■■■■A■■F■■
■GFEDCBCDEF■
■■■■■■■■■■■■
行けるところに、今のポイントよりも1多いポイントを振ります。ゴールから、1少ないポイントをたどれば最短道のりになります。
ロボットのプログラム?ロボットのメモリに余裕があれば、迷路を記憶していきます。行き止まりになれば、メモリ上の道を戻って分岐点まで戻り、行き止まりへ続く分岐を閉じればOk。センサーとメモリの両方を比べながら、メモリ上が閉じていればそちらには入らないようにすると、左手(右手)法でありながら、中心にある出口にもたどり着けます。
10年前、マッピーに対してプログラムできたのだから、今のロボットでも十分使えるでしょう。
この回答への補足
解を確かめる一歩手前として
迷路を埋め尽くす関数を使ってみたのですが
うまくいきませんでした。
どのようにしたらよいのでしょうか?
TRACE=2、WALL=1、ROAD=0です。
/*迷路の構造体*/
typedef struct Mazestruct{
/*迷路のサイズ(size[0]:横のサイズsize[1]:縦のサイズ)*/
int size[2];
/*スタートの座標(st[0]:横座標st[1]:縦座標(一番左上を(0,0))*/
int st[2];
/*ゴールの座標(goal[0]:横座標goal[1]:縦座標*/
int goal[2];
/*壁と通路のデータ*/
int maze_d[wid_max][len_max];
}Mazestruct;
void maze_visit(int x,int y,Mazestruct *maze,int n){
maze->maze_d[x][y]=TRACE;
if(n>60000){
printf("探索した格子点が60000点を越えました。\n");
printf("探索を終了します。");
}
else if(maze->maze_d[x+1][y]==ROAD){
maze_visit(x+1,y,maze,n+1);
}
else if(maze->maze_d[x][y+1]==ROAD){
maze_visit(x,y+1,maze,n+1);
}
else if(maze->maze_d[x-1][y]==ROAD){
maze_visit(x-1,y,maze,n+1);
}
else if(maze->maze_d[x][y-1]==ROAD){
maze_visit(x,y-1,maze,n+1);
}
else if(maze->maze_d[x+1][y]==TRACE){
maze_visit(x+1,y,maze,n+1);
}
else if(maze->maze_d[x][y+1]==TRACE){
maze_visit(x,y+1,maze,n+1);
}
else if(maze->maze_d[x-1][y]==TRACE){
maze_visit(x-1,y,maze,n+1);
}
else if(maze->maze_d[x][y-1]==TRACE){
maze_visit(x,y-1,maze,n+1);
}
}
No.6
- 回答日時:
右手でも左手でもいいからどちらかに固定します。
仮に右手にしたとして、
右手が右壁を触りながら迷路を進めば、出口が迷路の内部にあるような特殊な迷路で無い限り、抜けられると思います。
左手なら左壁を触りながら・・・。
ここで、出口ではなく、入口に出てしまった場合、解が無いということになると思います。
No.5
- 回答日時:
基本的には、「解がない」ことを調べるには
「全探索」するしか方法がありません。
しかし、幾分か「枝狩り」することが出来ますので
少し高速にすることはできると思います。
(例)ス→ゴ に行く迷路があるとします。
┏ス┳━━━┓
┃↓┃←←←┃
┃↓┗━━↑┃
┃▲→★→●┃
┃↓┃↓┃↓┃
┗━┻━┻ゴ┛
まず、最短経路は
・▲で右に行く
・★で右に行く
・●で下に行く
ですが,
全探索すると、
まず▲で下か右に枝分かれします。
ここで右を選んだ場合、
次に★で下か右に枝分かれしますが、
ここで下を選んだ場合、
『壁にぶつかります』
そうすると、「ス→▲→★→壁」によって
左下の区画は絶対にゴールにたどり着けない
ことが判明します。
つまり、最初の▲で下に行く探索は無意味です。
この枝狩りを効率よくプログラムに組み込んで
見てください。
# RedHat のスクリーンセーバーにこの探索の
# 様子を分かりやすく表示してたものがあって
# 見てて楽しかったのですが・・・
No.3
- 回答日時:
「塗り尽くし」の手法はあります。
(1)まず、スタート地点を特定の色で塗る。
(塗るというのは比喩で、配列か何かで表した迷路の
スタート地点のところに、特定の数値を入れる)
(2)迷路全体をスキャンして、「特定の色」に接する
マスであれば、それもまた「特定の色」に塗る。
それを繰り返す。
(3)「特定の色」に隣り合うマスがなくなれば終わり。
そのときゴールが塗られていなければ行き着くことはできない。
問題は、理論的に迷路の広さの2乗時間がかかることです。
再帰を使った方が早い場合が多いかもしれません。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(法律) 2車線以上であっても、歩行者は横断歩道がない道路を横断できますよね? 3 2022/04/19 15:58
- 計算機科学 これは迷路を解くというよりも、いかに速く最速で走り切れる経路を見出せるかや、マシン性能、プログラミン 3 2023/07/17 16:27
- バラエティ・お笑い 高校生です。文化祭でやる予定のコントを評価してください。改善点もお願いします。 設定は、 ・時間は朝 1 2023/06/15 21:45
- 運転免許・教習所 今日卒検があり、駐車場所を間違えてしまい焦っていたらミラーをぶつけて中止になってしまいました。 終わ 5 2023/05/27 13:44
- Google Maps google map 無関係な経路が出来てしまう。 3 2023/04/28 22:58
- 数学 問題:点Aから点Bまでの最短経路は全部で何通りあるか。ただし、斜線部分は通れないものとする。 解説: 4 2023/02/24 11:44
- 工学 電気回路の問題です。 (1)回路の入力インピーダンスZ0。 (2)回路の共振周波数を求めよ。また、そ 2 2023/05/28 23:09
- タクシー タクシーの運賃ってなぜJRのような大都市近郊区間のような最短経路の運賃計算にしないのですか? 実際の 7 2023/06/27 11:30
- 数学 情報処理詳しい人!! A4縦のレポート文書に4:3の大きさの横向きの写真画像を貼り付けることにした。 2 2022/12/18 02:30
- 小学校 (小学算数)「わり算の定義と文章題」について 2 2022/07/11 06:22
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語で簡単なパックマンゲーム...
-
ヒストグラム均等化処理プログラム
-
C言語
-
画像の拡大・縮小
-
分数の足し算をさせるプログラ...
-
c++ TCHARで文字化け
-
迷路を脱出する経路探索プログ...
-
直線補間について
-
関数とビット列
-
カードシャッフルのブログラム...
-
再起を使って迷路を解くプログ...
-
再起呼び出しの回数をカウント...
-
ヌメロンのプログラム
-
課題;素因数分解
-
コマンドプロンプトのウィンド...
-
2の補数を計算するプログラム
-
C言語で%を使わない余りの出し方
-
whileとifを使い偶数を出すには
-
C言語 4) 整数 a, b, c を入力...
-
fgetsなどのときのstdinのバッ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報