- ベストアンサー
走査アルゴリズムについて
benderの回答
- bender
- ベストアンサー率45% (108/236)
N個の要素を含む配列が与えられたとき、求めるような 『連続する』部分配列の最大和を探すためには、単純に 考えると、配列のs番目（0<=s<N）からはじまってe番目 (s<e<N)で終わるような部分配列すべてについて（つまり N*(N+1)/2の部分配列について）、その和をひとつずつ 調べてみればよいわけですが、その方法では N が大きい ときには結構な時間がかかります。 問題文にあるアルゴリズムのすごいところは、配列を たった一回読み通す間に（つまり、一重のforループ だけで）求める最大和が見つかるところだと思います。 > x[0...n]までの部分配列の最大和は、x[0...n-1]の > 部分配列の最大和か、x[n]から左方向に伸びた > 配列の和のいずれかである。 このヒントは、x[0...n]というn+1個の要素を含む配列が 与えられたとき、『連続する』部分配列のうちでその和が 最大となるようなものは、x[n]を含まない配列（すなわち x[0...n-1]）の中にみつかるか、もしくはx[n]を含む 部分配列（すなわち「x[n]から左方向に伸びた配列」）で あるかのいずれかである、といっています。 このヒントがいうことは、ある意味当たり前かもしれません。 というのも、x[0...n]のどんな部分配列も、x[0...n-1]の 部分配列か、x[n]から左に伸びる配列のいずれかでしか あり得ないからです。とはいえ、このことから問題文に あるような賢いプログラムが導かれます。 ヒントにある「x[0...i-1]の部分配列の最大和」がmaxsofarと 対応していて、「x[i]から左方向に伸びた配列の和」は maxendinghere = max(0.0f, maxendinghere + x[i]) と対応 しているといえます。ただ、 maxendinghere = max(0.0f, maxendinghere + x[i]); については、おそらく、 maxendinghere = max(x[i], maxendinghere + x[i]); とした方がヒントに忠実であるように私は思います。
関連するQ&A
- データ構造とアルゴリズムの問題です
要素数がnである配列aの要素の最大値を求めるアルゴリズムのループ端によるフローチャートを完成せよ(前判定繰返し) max =a[0] i=1; while i<n do{ if(a[i]>max)max=a[i]; i++; } a[0] → max 1 → i 前判定繰返し □ | yes a[i]□max-----| | □ NO i+1 → i 前判定繰返し □の中を埋めるんですが教えてください
- 締切済み
- C・C++・C#
- String配列を扱うアルゴリズムについて
よりパフォーマンスの良いアルゴリズムが、 ございましたらご教示下さい。 数レコード分のDBテーブルデータが格納されたString[][]型が存在するとします。 配列の要素は、String[行(フィールド)][列(カラム)]です。 ここで、全レコード中の列ごとの最大文字列長を int[]型に取得したいと思います。 そうした場合、自作した下記の処理よりも、 よいパフォーマンスを得られるアルゴリズムがございましたら、 ご教示願いたいと思います。 ※処理前提条件 ●String[][]型変数に、過不足無くテーブルデータが格納済みであるとします。 ●配列の第一(行)・第二(列)要素の最大値は取得済みであるとします。 ////////////// // 変数定義 // ////////////// String[][] tableData; ← テーブルデータ格納済み(過不足はありません) int 行数 = 全行数(取得済み); int 列数 = 全列数(取得済み); //列毎の最長文字列値を格納する。 int[] maxLen = new int[列数]; ////////// // 処理 // ////////// //列の個数分、処理を繰り返す for(int i = 0; i < 列数; i++) { //行の個数分、処理を繰り返す for(int j = 0; j < 行数; j++) { //NULLを回避する if(tableData[i][j] != null) { //int配列に格納済みの数値より大きければ、改めて格納する if(maxLen[i] < tableData[i][j].length()) { maxLen[i] = tableData[i][j].length(); } } } } 以上です、どなかお知恵をお貸し頂けませんか。 宜しくお願い致します。
- ベストアンサー
- Java
- アルゴリズムの名前を教えてください
16ビットのデータが、たとえば1000個、配列で与えられているとします。 unsigned short data[1000]; このデータをしらべて、重複するものを除いて何種類の値があるかを数える場合、一番素朴な方法だと、次のようにやると思います。 int i, j; int count = 0; for(i = 0; i < 1000; i++) { for(j = 0; j < i; j++) { if(data[j] == data[i]) { break; } } if(i == j) { count++; } } この方法だと、２重のループがあって処理に時間がかかります。そこで、メモリに余裕があれば内側のループをやめて、 int i; int count = 0; int flag[0x10000]; int n; for(i = 0; i < 0x10000; i++) { flag[i] = 0; } count = 0; for(i = 0; i < 1000; i++) { n = data[i]; if(flag[n] == 0) { flag[n] = 1; count++; } } これだと、２重のループを使うものよりは速くなりますが、データが1000個しかないのに、65536個のflagをクリアするのに時間がかかり、今ひとつです。 ところが、次のような賢い方法があり、２重のループも配列のクリアも無くすことができます。 int i; int count = 0; unsigned short flag[0x10000]; unsigned short link[0x10000]; int n; for(i = 0; i < 1000; i++) { n = data[i]; if(flag[n] >= count || link[flag[n]] != n) { flag[n] = count; link[count] = n; count++; } } 私がこのアルゴリズムを知ったのはかなり昔なので、どこで知ったのか思い出せないのですが、これほど賢いアルゴリズムだから何か名前がついていると思うのですが、それがわかりません。 名前がわからないので、人に頼んだりする時、上のような長い説明をしなくてはなりませんが、名前がわかっていれば「？？法でやっといて」、と言えばいいのですけど。
- 締切済み
- C・C++・C#
- ２番目の最大値を求める
n個の要素をもった配列で、２番目に大きい要素を見つけるコードを書きたいのですが、合っているのか不安になって、質問させてもらいます。 アルゴリズムとしては、まず、n-1回の比較をしてその中でmaxを見つけ、残りのn-1個の要素のなかでn-2回の比較をしてそのn-1個の配列のmaxを見つければ、２番目に大きい要素を見つけられると考えました。 int main(void) { int E[n]; int i, j, temp; for(i=0;i<N;i++){ for(j=1;j<N-i;j++){ if(E[j-1]>E[j]){ temp=E[j-1]; E[j-1]=E[j]; E[j]=temp; } } } return E[j]; } これであっていますでしょうか？ よろしくお願いいたします。
- 締切済み
- C・C++・C#
- 配列の頭に要素を挿入する方法
初心者です。配列でご教授お願いします。 インデックス０からひとつずつ要素をずらして、配列の一番前に要素を挿入するにはどうしたらいいのでしょうか？ int[] a = new int[10]; int n = a.length; for (int i = n-1; i < 1; i--){ a[i] = a[i-1]; } a[0] = 新しい要素 といった感じで書いたのですが、どうもループの中が実行されていないようなのです。 よろしくお願いいたします。
- 締切済み
- Java
- フローチャートの書き方
要素数がnである配列aの要素の最大値を求めるアルゴリズムのループ端によるフローチャートを完成せよ(前判定繰返し) max =a[0] i=1; while i<n do{ if(a[i]>max)max=a[i]; i++; } フローチャートでかくとどうなりますか？
- 締切済み
- C・C++・C#
- 転置行列アルゴリズム
こんにちは。プログラミングを学んでいる学生です。 N*Nのint型の配列を転置するCプログラムでなるべく性能の良いものを書け、という課題が出て、それと同時にシンプルな(性能が悪いと思われる)サンプルが配布されてました。 ですが、それを超えるようなアルゴリズムがどうしても思いつきません。 何かアドバイスいただけたらうれしいです。 配布メソッド: #define N 64 //Nは64,128,512,...,2048をはかる typedef int matrix_t[N][N]; void naive_rotate(matrix_t src, matrix_t dst){ int i,j; for(i=0;i<N;i++) for(j=0;j<N;j++) dst[N-1-j][i]=src[i][j]; return; } メソッドの７行目をdst[j][i]にしたらあまり変化ありませんでした。 また、i==Jのときcontinueするようにしたら、逆に遅くなってしまいました。
- ベストアンサー
- C・C++・C#
- ２次元配列とじゃんけんアルゴリズムについて質問
以下の、過去に私が質問した、２次元配列とじゃんけんアルゴリズムの質問のURLの見た上で私の質問に答えてください。 URL：ttp://okwave.jp/qa/q7038056.html 質問： public static int janken(int n){ int[][]tb1={ {9,9,9,9}, {9,0,1,2}, {9,2,0,1}, {9,1,2,0} }; int m=rand3(); System.out.println(m+" "); return tb1[n][m]; } 上記ソースコードの２次元配列について、何故「9」という数字があるのか、又１次元目と２次元目の要素数が「4」あるのかわかりませんでした。 上記のURL先で頂いた回答を元に、私は理解に努めました。その理解が正しいか判定してください。 「この勝敗表をあらわす２次元配列について、それぞれのプレイヤーのジャンケンの『手』を要素番号『1,2,3』に対応させている。つまり要素番号『0』は使っていないので、要素数が４つ必要。 また、要素番号『0』は、このjankenプログラムでは不要なので、何の値が入っても構わないので、『たまたま』９が入ってるだけで、９という数字に特に意味はない。因みに、その２つの要素番号に対応する要素が勝敗の結果の番号になる。」 こういうことでしょうか？
- ベストアンサー
- Java
- じゃんけんプログラムとアルゴリズムについて質問
以下の、過去に私が質問した、２次元配列とじゃんけんアルゴリズムの質問のURLの見た上で私の質問に答えてください。 URL：ttp://okwave.jp/qa/q7038056.html 質問： public static int janken(int n){ int[][]tb1={ {9,9,9,9}, {9,0,1,2}, {9,2,0,1}, {9,1,2,0} }; int m=rand3(); System.out.println(m+" "); return tb1[n][m]; } 上記ソースコードの２次元配列について、何故「9」という数字があるのか、又１次元目と２次元目の要素数が「4」あるのかわかりませんでした。 上記のURL先で頂いた回答を元に、私は理解に努めました。その理解が正しいか判定してください。 私の理解： 「この勝敗表をあらわす２次元配列について、それぞれのプレイヤーのジャンケンの『手』 を要素番号『1,2,3』に対応させている。要番号1，2，3を使用するためには、Javaでは要素番号は０から始まるため、「要素数」が4つ必要。だから、要素数が4ある。よって、この要素番号『0』はこのプログラムに於いては不要。 また、２次元目の要素番号『0』に関連する要素に『9』という数字がチョイスされてるが、『9』という数字のチョイスに特に意味はないが、、０、1、2以外の数字であることに意味はある。因みに、その２つの要素番号に対応する要素が勝敗の結果の番号になる。」 こういうことでしょうか？
- ベストアンサー
- Java
- 昇順と降順
C言語でクイックソートを行うプログラムを探していたところ、希望していたものが見つかりました。 このプログラムは与えられた数列を昇順に並び替えるものなのですが、これを降順に並び替えるにはどうしたらよいでしょうか？ いろいろ試してみたのですが、無限ループになってしまいます。 #include <stdio.h> void QSort(int x[ ], int left, int right); void Swap(int x[ ], int i, int j); void ShowData(int x[ ], int n); void main(void); /* クイックソートを行う */ void QSort(int x[ ], int left, int right) { int i, j; int pivot; i = left; /* ソートする配列の一番小さい要素の添字 */ j = right; /* ソートする配列の一番大きい要素の添字 */ pivot = x[(left + right) / 2]; /* 基準値を配列の中央付近にとる */ while (1) { /* 無限ループ */ while (x[i] < pivot) /* pivot より大きい値が */ i++; /* 出るまで i を増加させる */ while (pivot < x[j]) /* pivot より小さい値が */ j--; /* 出るまで j を減少させる */ if (i >= j) /* i >= j なら */ break; /* 無限ループから抜ける */ Swap(x, i, j); /* x[i] と x[j]を交換 */ i++; /* 次のデータ */ j--; } ShowData(x, 10); /* 途中経過を表示 */ if (left < i - 1) /* 基準値の左に 2 以上要素があれば */ QSort(x, left, i - 1); /* 左の配列を Q ソートする */ if (j + 1 < right) /* 基準値の右に 2 以上要素があれば */ QSort(x, j + 1, right); /* 右の配列を Q ソートする */ } /* 配列の要素を交換する */ void Swap(int x[ ], int i, int j) { int temp; temp = x[i]; x[i] = x[j]; x[j] = temp; } /* n 個のデータを表示する */ void ShowData(int x[ ], int n) { int i; for (i = 0; i < n ; i++) printf("%d ", x[i]); printf("\n"); } void main(void) { /* ソートする配列 */ int x[ ] = {6, 3, 1, 7, 0, 4, 8, 5, 2, 9}; int n = 10; printf("ソート前:\n"); ShowData(x, n); printf("ソート中:\n"); QSort(x, 0, n - 1); printf("ソート後:\n"); ShowData(x, n); }
- 締切済み
- C・C++・C#
お礼
ありがとうございます！ すごいわかりやすかったです！ このオーダーｎはかなりビックリでした。