質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

5回答

2437閲覧

c言語 アルゴリズム

miso_soup

総合スコア19

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

2クリップ

投稿2019/05/23 21:52

c言語で宝探しゲームのようなプログラムを作りました。
そこで自動で宝を探してくるようなプログラムを作りたくて、
アルゴリズムなどを考えたのですがどのようにしたら良いのか難しくて、
良い方法がありましたらご回答頂きたいです。

イメージ説明
10×10の図の中にランダムに宝が8個配置される。
Input : b1と入力すると周囲8近傍に宝がいくつあるか表示される。
宝がある座標をInput:に入力すると$と返す。

私が考えたのはb1,e1,h1,j1,b4,e4,h4,j4,b7,e7,h7,j7,b9,e9,h9,j9
をinputで入力したら被りが一番少なく探せるのかなと思いました。
それをどのような手順ですれば良いのでしょうか?
宝8個を全て自動で探索するアルゴリズムはどのようにしたら良いでしょうか?

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2019/05/24 01:48

> 宝がある座標をInput:に入力すると$と返す。 これは,例えば,「c5」と入力してその箇所に宝があったら,該当のc5マスには「$」と表示される (=b1マスのように周囲の宝の個数は教えてくれない) ということでしょうか?
xebme

2019/05/24 07:50

周囲8近傍の意味が分かりません。e5の場合どこからどこまでの範囲?a1の場合どこからどこまでの範囲?追記をお願いします。
jimbe

2019/05/24 11:52

> 宝8個を全て自動で探索するアルゴリズム a0~j9 まで全てを入力すればよいのではないでしょうか. コンピュータがやってくれるのですから一瞬でしょう.
ikadzuchi

2019/05/24 14:05

「被りが一番少なく」の意味が不明瞭です。 被りとは何ですか? また、配置によって可能な数は変わるでしょうけれど、どの時を少なくするのですか? すべての配置のうち最も少ないとき、最も多いとき、平均など。
miso_soup

2019/05/24 17:08

Inputにe5を入力した場合はd4,e4,f4,d5,f5,d6,e6,f6が周囲8近傍ということになります。 その周囲8近傍にランダムに配置した宝が1つあったらInputに入力した座標に1と表示されます。 なかったら0と表示されるので周囲8近傍をInputで表示して宝を探す必要がないということです。 Inputにa1を入力したらa0,b0,b1,a2,b2に宝が何個あるかどうががa1に表示されます。
miso_soup

2019/05/24 17:10

全てを考えると100手かかってしまうので、もっと効率的な方法を考えたいということです。
miso_soup

2019/05/24 17:23

説明が下手で申し訳ないです。 Inputにa0と入力するとb0,a1,b1に宝が何個あるかどうかをInputにb0を入力するとa0,c0,a1,b1,c1に宝が何個あるかどうかをa0とb0の座標に返してくれるので、a1,b1が2回調べられることになるので、それをできるだけ少なく調べようとしたらb1,e1,h1,j1,b4,e4,h4,j4,b7,e7,h7,j7,b9,e9,h9,j9をまず調べるのがいいのかなと思いました。 b1,e1,h1,j1,b4,e4,h4,j4,b7,e7,h7,j7,b9,e9,h9,j9をInputで入力したら全てのマスの宝があるいうことが わかるので、そこからどのようにして宝を見つけていけば良いのでしょうか?
miso_soup

2019/05/24 17:29

> 宝がある座標をInput:に入力すると$と返す。 これは,例えば,「c5」と入力してその箇所に宝があったら,該当のc5マスには「$」と表示される (=b1マスのように周囲の宝の個数は教えてくれない) ということでしょうか? そうですね、c5と入力して宝があった場合は$と表示されるので周囲8近傍の宝の数は数えてくれないので そうなった時の処理も考えないといけないですよね
ikadzuchi

2019/05/25 07:14

> 全てを考えると100手かかってしまうので、もっと効率的な方法を考えたいということです。 では「被りが」一番少なくではなく、「手数が」一番少なくが目的ということでよいですね? あとは「一番少なく」の方ですが、まあ話を聞く感じでは最悪値を少なくするのかなあという気はします。 まあ何にせよそう簡単に厳密解が求まるものではないと思います。
guest

回答5

0

(早いとは思わないので,回答としては不適切かもしれませんけど)
ものすごく簡単に思いつく方法としては
【とりあえずマス毎に「宝がありそうな確率」を持っておいて,確率が高い個所から掘っていく】
という方法が考えられますね.
同じ確率のマスが複数ある場合には,掘られていない隣接マスが多い個所を優先するとかで.

初期状態は,10×10マスに宝が8個だから,全マスの確率値は8/100

b1を掘ったら「1」が出た
→その周囲のマスの確率を1/8に更新
→他の箇所の確率は 7/91 に更新

{b2,c1,c2}のどれかを選んで掘る

みたいな.

投稿2019/05/24 01:56

fana

総合スコア11632

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2019/05/24 02:59

自分で書いたくせして,【確率の更新が馬鹿(=私)には無理なレベルで難しい】ことに気付いたので,誰か低評価しておいてください.
fana

2019/05/25 02:19

低評価って言ったのに+になってる謎
raccy

2019/05/25 02:48

すまん、俺が高評価を押しました。 確率の出し方は考えるだけでも凄くめんどくさいですが、方向性としては十分にありだと思います。
xebme

2019/05/25 05:13

ベイズ推定、潜水艦沈没事故。
guest

0

「マインスイーパー アルゴリズム」で検索してください。

投稿2019/05/23 22:53

Zuishin

総合スコア28656

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

miso_soup

2019/05/23 23:13

Inputをどのように入力していくと宝が早く見つかるのでしょうか?
Zuishin

2019/05/23 23:18 編集

マインスイーパーですよね? このキーワードで解法アルゴリズムみつかりませんでした? 私のところでは複数表示されたんですが。 Google を使ってみてください。https://google.com
raccy

2019/05/24 13:16 編集

マインスイーパーとは全くルールが異なりますよ。0のマスを踏んでも、周りが勝手に開いてくれると言うことはないのですから。似たようなモノで言うと、海戦ゲームやバトルシップと言われるゲームに近い物があると思います。
Zuishin

2019/05/24 13:13

ルールの一部が伏せられているのかと思ったんですが、外れっぽいですね。
guest

0

  • 絶対に宝が無いとわかるところを選ばない
  • ヒントの数値がでかいやつの周囲を先に選ぶ

みたいな簡素な方法を実装してみました.
(微妙にところどころC++成分入ってますが,読める範疇かと.)


全体的に使う構造体と定数

//[Pos.h] #pragma once //座標(x,y)を表すだけの構造体 struct Pos { int x, y; Pos( int x=0,int y=0 ) : x(x),y(y) {} };
//[SysDefs.h] #pragma once //マップのサイズ #define MAP_W 10 #define MAP_H 10 //宝の総数 #define N_TREASURE 8

ゲームのルール部分側の実装("Sys"とかいう命名がダサい^^)

//[SysSide.h] //ゲームのルール側の実装 #pragma once #include "Pos.h" //状態初期化. void Sys_Init(); //指定のマスを開く. //・Sys_Show()によって表示される内容が更新される. //・指定マスに関する情報を返す. // //戻り値は, //・指定マスに宝が無い場合は,その8近傍に存在する宝の個数 //・指定マスが宝の場合には,負の値 int Sys_Open( const Pos &OpenPos ); //現状態の表示 void Sys_Show();
//[SysSide.cpp] #include "stdafx.h" //VC #include "SysSide.h" #include "SysDefs.h" #include <cmath> //表示内容バッファ static char ShowBuff[MAP_H][MAP_W + 1]; //※とりあえず宝の位置は固定のハードコーディング※ static const Pos TreasurePos[N_TREASURE] = { Pos( 0,1 ), Pos( 1,8 ), Pos( 2,2 ), Pos( 5,0 ), Pos( 5,4 ), Pos( 6,4 ), Pos( 6,3 ), Pos( 8,7 ) }; // void Sys_Init() { //全マスの表示内容を'+'に初期化 for( int y=0; y<MAP_H; ++y ) { for( int x=0; x<MAP_W; ++x ){ ShowBuff[y][x] = '+'; } ShowBuff[y][MAP_W] = '\0'; } //※本来はここで,TreasurePos[]の内容を乱数とか使って決めれば良いかと※ } // int Sys_Open( const Pos &OpenPos ) { int nTreasureArround = 0; for( int i=0; i<N_TREASURE; ++i ) { int dx = abs( OpenPos.x - TreasurePos[i].x ); int dy = abs( OpenPos.y - TreasurePos[i].y ); if( dx==0 && dy==0 ) { ShowBuff[OpenPos.y][OpenPos.x] = '$'; return -1; } if( dx<=1 && dy<=1 ){ ++nTreasureArround; } } ShowBuff[OpenPos.y][OpenPos.x] = '0' + nTreasureArround; return nTreasureArround; } // void Sys_Show() { for( int y=0; y<MAP_H; ++y ){ printf( "%s\n", ShowBuff[y] ); } }

アルゴリズム側のヘッダ

//[AlgoSide.h] //宝を探すアルゴリズム側の実装 #pragma once #include "Pos.h" //状態初期化 void Algo_Init(); //開くマスを決める. Pos Algo_DecideOpenPos(); //アルゴリズムに,マスPに関する情報を与える. //( Algo_DecideOpenPos()が返した場所Pに関する,Sys_Open(P)の結果をアルゴリズムに教える用 ) // //InfoVal は //・マスPに宝が無い場合は,その8近傍に存在する宝の個数 //・マスPが宝の場合には,負の値 void Algo_Update( const Pos &P, int InfoVal );

mainはこんな感じで.

#include "SysSide.h" #include "SysDefs.h" #include "AlgoSide.h" int _tmain(int argc, _TCHAR* argv[]) { //初期化 Sys_Init(); Algo_Init(); //宝探す処理 int nIter = 0; int nTreasureRest = N_TREASURE; //未発見の宝の個数 while( nTreasureRest>0 && nIter<MAP_W*MAP_H ) { ++nIter; Pos OpenPos = Algo_DecideOpenPos(); int OpenResult = Sys_Open( OpenPos ); if( OpenResult < 0 ){ --nTreasureRest; } Algo_Update( OpenPos, OpenResult ); printf( "Turn %d : (%d,%d) -> %c\n", nIter, OpenPos.x, OpenPos.y, (OpenResult<0 ? '$' : '0'+OpenResult) ); Sys_Show(); printf( "-------------------------------\n\n" ); } printf( "Total Turn = %d\n", nIter ); printf( "Rest Treasure Count = %d\n", nTreasureRest ); getchar(); //Press Enter_Key to Quit return 0; }

(…と,ここまでくらいの物を質問する側で指定してもらえると,回答書く人もそれを読む人もやり易くてよいのではないなかぁ,とか思う)

で,アルゴリズムの実装.

//[AlgoSide.cpp] #include "stdafx.h" //VC #include "AlgoSide.h" #include "SysDefs.h" //作業関数. //Pの8近傍のマスの座標をDstの先頭側に入れる. //戻り値は入れた個数(=近傍マスの個数) int GetNeighbors( const Pos &P, Pos (&Dst)[8] ) { const int DX[8] = { -1, 0, 1, -1,1, -1,0,1 }; const int DY[8] = { -1,-1,-1, 0,0, 1,1,1 }; int nNeighbor = 0; for( int i=0; i<8; ++i ) { int x = P.x + DX[i]; int y = P.y + DY[i]; if( x<0 || y<0 || x>=MAP_W || y>=MAP_H )continue; Dst[ nNeighbor ] = Pos(x,y); ++nNeighbor; } return nNeighbor; } //マスの情報用構造体 struct Info { bool IsOpened; //開いたマスはtrueにする bool TreasureNotExist; //宝が無いとわかった場所はtrueにする→次回から見なくていい int InfoVal; //マスを開いて得られた結果. int NotOpenedPosArround; //8近傍で開いていないマスの個数 int nFoundTreasureArround; //8近傍に見つけた宝の個数 Info() : IsOpened(false), TreasureNotExist(false), InfoVal( -1 ), NotOpenedPosArround(8), nFoundTreasureArround(0) {} }; //情報バッファ static Info Data[MAP_H][MAP_W]; //(x,y)のスコアを計算する作業関数 double CalcScore( int x, int y ) { if( Data[y][x].IsOpened || Data[y][x].TreasureNotExist )return -1; double Score = 0; Pos NeighborPos[8]; int n = GetNeighbors( Pos(x,y), NeighborPos ); for( int i=0; i<n; ++i ) { const auto &ND = Data[ NeighborPos[i].y ][ NeighborPos[i].x ]; if( ND.IsOpened ) { if( ND.InfoVal < 0 )continue; //宝のマスからは情報を得られない if( ND.InfoVal <= ND.nFoundTreasureArround ) {//このマスに宝はない Data[y][x].TreasureNotExist = true; //次回以降見なくていいフラグを立てておく return -1; } Score += (double)ND.InfoVal / ND.NotOpenedPosArround; } } return Score; } //初期化 void Algo_Init() { for( int x=1; x<=MAP_W-2; ++x ) { Data[0][x].NotOpenedPosArround = Data[MAP_H-1][x].NotOpenedPosArround = 5; } for( int y=1; y<=MAP_H-2; ++y ) { Data[y][0].NotOpenedPosArround = Data[y][MAP_W-1].NotOpenedPosArround = 5; } Data[0][0].NotOpenedPosArround = 3; Data[MAP_H-1][0].NotOpenedPosArround = 3; Data[0][MAP_W-1].NotOpenedPosArround = 3; Data[MAP_H-1][MAP_W-1].NotOpenedPosArround = 3; } //開く箇所を決める Pos Algo_DecideOpenPos( ) { //全てのマスに関して,適当なルールで得点を算出し,一番得点が高い個所を開く場所とする Pos Ret; double MaxScore = -1; for( int y=0; y<MAP_H; ++y ) { for( int x=0; x<MAP_W; ++x ) { double Score = CalcScore( x,y ); if( MaxScore < Score ) { Ret = Pos( x,y ); MaxScore = Score; } } } return Ret; } //情報更新 void Algo_Update( const Pos &P, int InfoVal ) { if( Data[P.y][P.x].IsOpened )return; //一応チェック //マスPの情報更新 Data[P.y][P.x].IsOpened = true; Data[P.y][P.x].InfoVal = InfoVal; {//Pの周囲のマスの情報を更新 Pos NeighborPos[8]; int n = GetNeighbors( P, NeighborPos ); for( int i=0; i<n; ++i ) { --Data[ NeighborPos[i].y ][ NeighborPos[i].x ].NotOpenedPosArround; if( InfoVal<0 ) //マスPに宝が見つかったとき { ++Data[ NeighborPos[i].y ][ NeighborPos[i].x ].nFoundTreasureArround; } } } }

投稿2019/05/30 04:07

fana

総合スコア11632

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

より少ない回数を目指すならfanaさんの回答みたいな手段がいいと思いますが、確率を出していくのが非常に面倒です。ということで、もうちょっと妥協したものを考えたいと思います。

  1. 全てのマス分の整数値二次元配列(takara_m)を用意して0にする。
  2. 全てのマス分の整数値二次元配列(num_m)を用意して0にする。
  3. takara_mで0のマスから一つランダムに開く。
  4. それが宝の場合は8.へ飛ぶ。数値の場合は5.以降を行う。
  5. (数値の場合分岐)takara_mを-2にする。
  6. マスを開いた出た数値をnum_mに追加する。
  7. num_mが0になる場合は、近傍8マスについてtakara_mが0のものは全て-1にする。
  8. 最初の1.に戻る。
  9. (宝の場合分岐)takara_mを1にする。
  10. 近傍8マスについてnum_mを一つ減らす。
  11. 近傍8マスでtakara_mが-2かつnum_mが0になる場合は、そのマスの近傍8マスについてtakara_mが0のものは全て2にする。
  12. 最初の1.に戻る。

宝が「0ある可能性がある」「1ある」「-1ある可能性はない」「-2ない」かをフラグ管理する二次元配列(takara_m)と、周りの個数を数える二次元配列(num_m)を用意します。周りの個数は、宝が周りに見つかる度に1減らしていき、そのマスを開いたときにその数値を足すというものです。既に開いたマスでnum_mが0になるということは、そのマスを開いたときの数値分の宝はすべて見つかっているはずですので、他のマスを「-1ある可能性はない」に変えていきます。

こうしてフラグを変えながら「0ある可能性がある」だけを次々に開いていけば、「-1ある可能性はない」というマスは避けられますので、ある程度は効率的にできるのではないだろうかと思われます。

投稿2019/05/25 05:09

編集2019/05/25 05:13
raccy

総合スコア21733

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2019/05/27 01:19

手順3.の開く箇所の選び方は完全ランダムなんでしょうか. 感覚的にはヒントの数字がたくさん隣り合う箇所ほど「確定ではいが宝がありそう」な気がするからそういう箇所を優先的に開いてみたくなりそうだけども, 別の箇所を先に開いてヒントを増やして宝の箇所を確定させていく方が早くなるのかも?
raccy

2019/05/27 09:43

この方法では完全ランダムです。もっとありそうと言うところを開いて行ければ良いのですが、妥協して、確率が0のところだけ注意してみようというものです。数値が見つかったら、数値に応じて周りの確率をあげるとか、そういった工夫をしていけば、もっと少ない回数で宝を見つけることができるでしょう。
guest

0

どのようなルールなのか分かりませんが、下記のような感じで探索していけばいいのでは?

C

1 2int 探索(int x,int y){ 3 int sum; 4 char c = Input[x][y]; 5 if(c == '1'){ return x*10 + y; } 6 if(x < 10 || y < 10){ 7 sum = 探索(x + 1,y); 8 if(sum != -0xFF){ return sum; } 9 sum = 探索(x,y + 1); 10 if(sum != -0xFF){ return sum; } 11 } 12 return -0xFF;//ここは適当 13}

すみません。
疑似的なのと、多分C++の仕様で書いてしまった?からそのまま移植しても動かないと思うけど...
こんな雰囲気だけ伝わればいいです。

投稿2019/05/24 03:34

stdio

総合スコア3307

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問