- 締切済み
最大値を見つけるプログラム。
最大値を見つけるプログラム。 現在Cでプログラムを作成しているのですが、よくわからないので質問させていただきます。 最大値を見つけるのですが、まず、２次元データをもつファイルから数値データを読み込みます。 次に、ある一点(例として図の@)に注目し、そこにある値と、その周りの8つの値とを比較し、最大値を持つ点を判定します。 ただし、端の部分では周期的に接続されるものとします。 （下図で言えば、4列目が1列目と同じ値、5列目が2列目と同じ値…といった感じです。行についても同様です。） 最後に、今度はその点を@として、@の位置が最大となる（周りに@より大きな値がない）までループさせ、その状態になったらそこでプログラムを終了させる、というものです。 * | * | * ----------- * | @ | * ----------- * | * | * 単純に最大値を見つけるだけなら全部走査すれば良いだけなのですが、隣接したものに移動しながらというのがいまいちよくわかりません。どのようなアルゴリズムで進めればいいのでしょうか？アドバイスお願いいたします…。
- みんなの回答 （8）
- 専門家の回答
みんなの回答
- hashioogi
- ベストアンサー率25% (102/404)
行列内の数値にフタコブラクダのようにピークが複数個あるようなことが無いという条件が必要ですね？
No.6です。 字数の関係で、回答を分けさせて頂きました。 一応、gccでコンパイルし動作を確認しています。 但し、インデントを付ける関係上、全角空白を使用していますので、変換が必要です。 方式としては、No.3さんが述べられているようにテーブルを拡張しています。 処理としては、拡張したテーブルにセットする処理と、それを１つずつ8方向チェックしているだけです。 チョット、書いていることが良くわからなかったですが、8方向をチェックして中心が最大値のものはすべて'@'をセットしています。 このプログラムのミソは、max_chk()関数です。 指定されたポイントの上下左右8方向の最大値チェックをしています。 2次元テーブルではなく、1次元配列で処理しています。 この方が、共通ルーチン化する際には何かと都合のいい時があるからです。（今回は微妙ですが） なお、動作試験するときには行数と桁数は必ず違う値にする必要があります。 そうしないと、行数と桁数を混同して使っても正常として処理されてしまいます。 また、実際にはもっと大きなサイズにして、tblにセットしているチェックパターンをもっといろいろと増やす必要があります。 これが模範解答と言うつもりはないですが、素人ほど処理速度やメモリー使用量を少なくしたりとかに精力をつぎ込みますが、バグの（少）ないプログラムを組むには、わかりやすさが第一です。 また、わかっているかと思いますが、まず最初に考えることは、もし紙などを使って自分が手作業でやるならば、どうするかを考えることです。 もし、これすらもわかっていなければ、プログラミングはできません。 そして、それをプログラムに置き換えてやるだけです。 ほとんどは、そのような考えで合っています。 なお（わざとですが）通常2次元テーブル(tbl2)を1次元配列として処理するなど、このような質問をする人が思いつくようなことではありません。 ですから、もし何かの宿題でこのまま提出すると、必ず疑われますので、自分で理解して書き直すことをお勧めします。
#include <stdio.h> #include <string.h> #define ROW_NUM 6 /* 行数 */ #define COL_NUM 5 /* 桁数 */ #define MARK_C '@' int max_chk(int base[], int col_num); main() { int tbl[ROW_NUM][COL_NUM] = { /* 元テーブル */ 1,2,3,4,5, 5,4,3,2,1, 1,6,1,6,3, 1,1,1,1,4, 6,1,7,1,7, 2,2,2,2,3 }; int tbl2[ROW_NUM+2][COL_NUM+2]; // 拡張テーブル char ans[ROW_NUM][COL_NUM]; // @ をセットするテーブル int i,n; // tbl==>tbl2 へセット for(i=0; i < ROW_NUM; i++) { memcpy(&tbl2[i+1][1], &tbl[i][0], COL_NUM*sizeof(int)); // 元をコピー tbl2[i+1][0] = tbl[i][COL_NUM-1]; // 左端をセット tbl2[i+1][COL_NUM+1] = tbl[i][0]; // 右端をセット } memcpy(&tbl2[0][1], &tbl[ROW_NUM-1][0], COL_NUM*sizeof(int)); // 上段をセット memcpy(&tbl2[ROW_NUM+1][1], &tbl[0][0], COL_NUM*sizeof(int)); // 下段をセット tbl2[0][0] = tbl[ROW_NUM-1][COL_NUM-1]; // 左上段をセット tbl2[0][COL_NUM+1] = tbl[ROW_NUM-1][0]; // 右上段をセット tbl2[ROW_NUM+1][0] = tbl[0][COL_NUM-1]; // 左下段をセット tbl2[ROW_NUM+1][COL_NUM+1] = tbl[0][0]; // 右下段をセット memset(ans, 0, sizeof(ans)); // 0クリア // 1つずつ、最大値チェックをする for(i=0; i < ROW_NUM; i++) { for(n=0; n < COL_NUM; n++) { if(max_chk(&tbl2[i+1][n+1], COL_NUM+2)) { ans[i][n] = MARK_C; // 最大値だったので、@ をセット } } } } // ８方向の最大値チェック int max_chk(int base[], int col_num) { if(base[0] > base[-col_num-1] && /* 左上 */ base[0] > base[-col_num] && /* 上 */ base[0] > base[-col_num+1] && /* 右上 */ base[0] > base[-1] && /* 左 */ base[0] > base[+1] && /* 右 */ base[0] > base[col_num-1] && /* 左下 */ base[0] > base[col_num] && /* 下 */ base[0] > base[col_num+1]) { /* 右下 */ return 1; // 真 } return 0; // 偽 }
#3、#4です。 すみません。やはり当方の考慮が足りていませんでした。 元の行列が以下のようなものだった場合で、 ５ １ ２ ３ １ ２ ３ ４ ２ ３ ９ １ ３ ４ １ ２ この行列の周囲を周期的に拡張すると以下のようになります。 ２ ３ ４ １ ２ ３ ３ ５ １ ２ ３ ５ ４ １ ２ ３ ４ １ １ ２ ３ ９ １ ２ ２ ３ ４ １ ２ ３ ３ ５ １ ２ ３ ５ この状態で最大値検索の１回目を、元の行列の（１，１）の値（＝５）から 始めると、この段階で(５)の周辺８個の数値の中には、５より大きい数値 はないので、この段階で処理が終了し、最終的な最大値が５に確定する ことになります。 ２ ３ ４ １ ２ ３ ３ (５) １ ２ ３ ５ ４ １ ２ ３ ４ １ １ ２ ３ ９ １ ２ ２ ３ ４ １ ２ ３ ３ ５ １ ２ ３ ５ 従って、元の行列の中の最大値は９ですが、ご提示の方法で求めた 最大値は５となり、結果が違うことになりますね。 ですので、#3の当方の解釈は間違っていたことになります。 どうも、すみませんでした。 それと、回答にならなくてすみません。
#3です。 すみません。#3で訂正があります。 行列内に最大値に相当する値（＝同じ値）が２個以上あった場合は、単純に最大値を 求めた場合と、ご提示の方法で求めた場合とでは、最大値の「行列位置」が異なる 場合がある、というのを考慮していませんでした。 ですので、必ずしも単純に最大値を求めるのと、ご提示の方法で求めるのとでは、 結果（最大値の行列位置）が一致するとは限らない、ということになると思います。 失礼致しました。
こんにちは。 直接の回答でなくてすみません。 ご提示の最大値の求め方ですと、最終的に求まる最大値は、その行列内の 最大値と等しくなるように思うのですが如何でしょうか？ つまり、 ＞ ただし、端の部分では周期的に接続されるものとします。 及び ＞ 隣接したものに移動しながらというのがいまいちよくわかりません。 という部分を考えなくても、単純にその行列内の最大値を求めるのと結果は 変わらないと思えるのですが？ これは、当方の解釈が間違っているのでしょうか？ もっとも、そういう話しは抜きにして、純粋にそういう求め方のアルゴリズムを 作成したいというのであれば意味はあると思います。 以下は、ご提示の最大値の求め方（考え方＆手順）の一例です。 ※ただし、当方の解釈の仕方による方法となります。 ■最大値算出の例 １）元の行列が以下だったとします。（４行４列） ３ １ ５ ０ ４ ７ ９ ２ ６ ２ ８ ３ ５ １ ７ ４ ※以後の記述内の行列位置を表す記述（ｍ、ｎ）は、 ｍ：行位置（１～４） ｎ ：列位置（１～４） を意味します。 ２）元の行列の端の部分の周囲を、周期的に拡張して以下のような行列を 作成します。 ４ ５ １ ７ ４ ５ ０ ３ １ ５ ０ ３ ２ ４ ７ ９ ２ ４ ３ ６ ２ ８ ３ ６ ４ ５ １ ７ ４ ５ ０ ３ １ ５ ０ ３ ３）１回目として、元の行列の（１、１）の値（＝３）の周囲８個の中の最大値 を求めると、元の行列の（２、２）の値（＝７）になります。 ４ ５ １ ７ ４ ５ ０ (３) １ ５ ０ ３ ２ ４ [７] ９ ２ ４ ３ ６ ２ ８ ３ ６ ４ ５ １ ７ ４ ５ ０ ３ １ ５ ０ ３ ４）２回目として、その（２、２）の値（＝７）の周囲８個の中の最大値を求めると、 元の行列の（２、３）の値（＝９）になります。 ４ ５ １ ７ ４ ５ ０ ３ １ ５ ０ ３ ２ ４ (７) [９] ２ ４ ３ ６ ２ ８ ３ ６ ４ ５ １ ７ ４ ５ ０ ３ １ ５ ０ ３ ５）３回目として、その（２、３）の値（＝９）の周囲８個の中の最大値を求めると、 該当値なし（＝９より大きい数値なし）となるので、ここで処理が終了し、 最終的な最大値は、元の行列の（２、３）の値（＝９）となります。 ４ ５ １ ７ ４ ５ ０ ３ １ ５ ０ ３ ２ ４ ７ (９) ２ ４ ３ ６ ２ ８ ３ ６ ４ ５ １ ７ ４ ５ ０ ３ １ ５ ０ ３ 以上のように、結果として最終的な最大値は、元の行列の最大値（＝９）と同じ になります。 注）上記の例は１パターンだけですので、結論としては断定できませんので、 その他のパターンについても色々と検証してみて下さい。 以上です。
- l27074
- ベストアンサー率100% (5/5)
C言語わからないので、以下はなんとなく言語で書いてます（笑） なんとなく言語なので、動かしてません。バグがあるかも。 こんな感じでどうかなー程度で参考になれば。。 int[][] data = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; private void main(int arg1, int arg2) { //初期位置 int y = arg1; int x = arg2; //周囲の最大位置 int resY = y; int resX = x; //データの範囲 int maxY = data.length - 1; int maxX = data[0].length - 1; //周囲と比較するときの方向 int[][] move = { {-1,-1},{-1,0},{-1,1}, { 0,-1}, { 0,1}, { 1,-1},{ 1,0},{ 1,1} }; while (true) { int max = data[y][x]; //中心の値を最大とする for (int i = 0; i < move.length; i++) { //比較する先の位置を取得 int chkY = getPos(y, move[i][0], maxY); int chkX = getPos(x, move[i][1], maxX); //比較先の値のほうが大きければ保存 if (max < data[chkY][chkX]) { resY = chkY; resX = chkX; max = data[chkY][chkX]; } } //中心が一番大きければ処理終了 if (y == resY && x == resX) { break; } //中心を移動 y = resY; x = resX; } //while (true)の終わり print("Y=" + foundY + ", X=" + fouondX); } //"周期的に接続"したときの位置 private int getPos(pos, add, max) { int ret = pos + add; if (ret < 0) { ret = max; } else (ret > max) { ret = 0; } return ret; }
お礼
プログラムまで書いていただきありがとうございます。 参考にさせていただき、もう少し頑張ってみます。ありがとうございます。
- Tacosan
- ベストアンサー率23% (3656/15482)
1. 周囲で最も値が大きいところを見付ける 2. その値と今いるところの値を比べる 3. 前者の方が大きければ, そこ場所に移動して 1 に戻る だけ... では?
お礼
すいません。書き方が不適切でした。 そのようなことをすればいいと頭ではわかっているのですが、プログラミングをどうすればいいかわかりませんでした。もう少し考えて見ます。
お礼
ありがとうございます。まさにここで悩んでいました。 もし全てのデータの値が異なるならば、乱暴ではありますがもう一度全部走査してそこの配列位置を求めればよいのですが、今回の場合同じ値をもつことがありえるので困っていました。 質問文が不適切でした。申し訳ございません。