- ベストアンサー
整数の選択
アルゴリズムに関する質問です. n個の相異なる整数が配列 A[1..n] に格納されていて,その配列の中からk番目に小さい整数を選ぶ問題のアルゴリズムを考えています.kは 1<=k<=n を満たす自然数であり,この選択問題は O(n) で解けるものです. ヒープを使ったりして考えたのですがうまくいきません.どなたかこのアルゴリズムを教えてください.よろしくお願いします.
- bulgarian
- お礼率50% (11/22)
- その他(プログラミング・開発)
- 回答数4
- ありがとう数3
- みんなの回答 (4)
- 専門家の回答
質問者が選んだベストアンサー
私もこの問題はソートと同じだと思いますが、 ソートのアルゴリズムは大抵O(n^2)かかるものであり、 O(n)で解けというのはかなり制約になります。 単純ソートを使ってしまうとO(n^2)になり、 ヒープソートやクイックソートだとO(n*log(n))になってしまいます。 O(n)でできるソートはあまり多くありません。 それでもたとえば「ビンソート」というのがあります。 ・まず、配列をサーチして、最大値を選ぶ(nに比例)、 ・配列B[1..maxA]を確保。 ・もう一回配列Aをサーチして、B[A[x]]にフラグを立てる。(nに比例) ・配列Bを下からサーチして、k番目に小さい (フラグが立っているk番目の)数を見つける。(最大でnに比例) ただし、見てもらえばわかる通り、最大値が大きいと 必要なメモリがそのまま多くなってしまい、実用的ではありません。 O(n)のアルゴリズムは、参考URLの 『定本 Cプログラマのためのアルゴリズムとデータ構造』 近藤嘉雪著 ソフトバンクパブリッシング発行 に3種類記述されています。
その他の回答 (3)
- imogasi
- ベストアンサー率27% (4737/17068)
ヒープを積んで、積み終わり、根から1つづつ(ソート後の)データを順次取り出す時、k個目で止めれば良いのでは。 あるいはいっそのことソート後に、A(K)を取れば良いのではないですか。 この問題は実質ソートと同じことでしょう。ソートをしないでk番目が判るアルゴリズムがあるとは、私の力では予想できないです。
- tsukasa-12r
- ベストアンサー率65% (358/549)
一つ考えてみました。 (1) まず、配列 A[1...n] とは別に、配列 F[1...n] を用意します。配列 F[1...n] の各要素を全て 0 で初期化します。 (2) A[1...n] の中から最小値 A[i] を求め、A[i] は使用済み、という意味で、F[i] に 1 をセットします。 (3) A[1...n] の中で、対応する F[1...n] が 0 のものの中から最小値を求め、(2) 同様に、最小値 A[j] に対して F[j] に 1 をセットします。 この手順を繰り返して、k 番目に小さい値を取得します。 説明のために (1) → (2) → (3) と書きましたが、実際には (1) → (3) → (3) → ... と (3) を k 回繰り返せば k 番目に小さい整数を取得できます。 C で書いてみました。 #include <stdio.h> const CINT_N = 10; int a[] = { 315, 130, 3, 27, 85, 9, 17, 83, 51, 38 }; void main() { int f[CINT_N]; int iMin; /* 最小値 */ int iInitMin; /* 暫定の最小値がセットされたとき 1 */ int iIndex; /* 最小値を指すインデックス */ int i, j, k; /* f[1...n] を初期化 */ for( i = 0; i < CINT_N; i++ ) { f[i] = 0; } /* 例として、3 番目に小さい整数を求める */ k = 3; for( j = 1; j <= k; j++ ) { iInitMin = 0; for( i = 0; i < CINT_N; i++ ) { if( f[i] == 0 ) { if( iInitMin == 0 ) { iMin = a[i]; /* 暫定の最小値をセット */ iIndex = i; iInitMin = 1; } else { if( a[i] < iMin ) { iMin = a[i]; iIndex = i; } } } } /* j番目に小さい整数に対して使用済みのフラグをセットする */ f[iIndex] = 1; } printf( "%d 番目に小さい整数は %d です。\n", k, iMin ); }
お礼
ありがとうございます.これでk番目に小さい 整数を得ることができますね. ただ今回の問題では "O(n)" で解くことが必要です. このプログラムでは計算時間が O(n^2)になって しまうように思います. でも本当に丁寧に回答してくださり,ありがとうございました!
- tsukasa-12r
- ベストアンサー率65% (358/549)
>ヒープを使ったりして… というのはヒープソートのことでしょうか? 一旦、ソートして、ソートした結果を 配列 B[1...n] に格納してやれば B[k] が求める整数になると思うんですけど。
関連するQ&A
- 整数の問題
この前友人が私に出した問題です。 自然数kに対して、次の条件を満たす自然数nの最小値を求めよ。 「任意のn個の整数において、その中から上手くk個を選べば和をkの倍数にすることができる。」 例)k=2のとき…n=2ならば偶奇が異なるとき条件を満たさず、n=3ならば偶奇が一致する二整数が必ず存在するのでnの最小値は3。 k=5まではn=2k-1という関係になったそうです。kが6以上のときもそうなるのか(その場合は証明可能かどうか)、或いは全く関係の無い値になるのか知りたいのだが何か良いアイデアは無いかと聞かれました。 取り敢えずk=6について調べてみようとしましたが分岐が多いので断念しました(k=5でも結構大変そうですが…)。 良い方法がありましたら教えて下さい。
- ベストアンサー
- 数学・算数
- 部分和問題がわかりません。
部分和問題がわかりません。 [問題] n個の整数が配列Aに格納されていて、整数xの値を与えたときに、 A[i] + A[j] = x となるi,jが存在するかどうかを判定する、なるべく効率のよいアルゴリズムを示せ。 この問題は部分和問題のため、NP完全問題なので、総当たりのO(n^2)より効率のいい方法がないと思うのですが、もっと効率のよい方法が存在するのでしょうか?
- ベストアンサー
- その他(プログラミング・開発)
- 整数問題
問題文は省きます。 nは自然数です。 証明の過程で、n=3k+1のとき、 「n+2=(3k+1)+2=3(k+1)が合成数である」ことを示したいのですが、上のn=3k+1の式で、k=0としてもn=1となるので、nは自然数であることを満たしてますよね。 しかし、命題「n+2=(3k+1)+2=3(k+1)が合成数である」については、k=0とするとn+2=3となってしまい、合成数にはなりません。 参考書では、kは整数とし、「n+2=(3k+1)+2=3(k+1)は合成数である」と断定しているのですが、答案を書く際これで本当にいいのでしょうか。 回答よろしくお願いします。
- 締切済み
- 数学・算数
- 例えば、1から8までの整数を一つずつ使った……
この問題を考えて欲しいです!! 例えば、1から8までの整数を一つずつ使った数列があるとする どんな並び方でも、左から数えて左端の数の分だけ順番を逆にする操作を有限回行うと、必ず左端は1になる たとえば 56712348なら 21765348 12765348 41387652なら 83147652 25674138 52674138 47628138 26748138 62748138 18472638 という風に、必ず左端が1になって、操作は終了する このことは、1からn(nは2以上のしぜんすう)の場合にも同じことがいえ、必ず左端が1になる これを証明しろ という問題です! いろいろ考えてみたのですが、全然わからないです…… たとえば、1がk番目にある時、 k以上の数が必ず、k番目より前に存在することは、鳩ノ巣原理によって示ます また数学的帰納法とかをつかってアプローチしてみましたが、イマイチ上手く行きません! わかる方、ご教授お願いします!!
- ベストアンサー
- 数学・算数
- N個の整数の並び替えるアルゴリズム
N個の整数1,2,3,...Nから任意のM個(M < N )を取り出すのですが、重複はダメという場合、どのようなアルゴリズムがあるでしょうか。重複ありなら、Nまでの一様乱数を発生させて整数化して取り出すことは可能です。今回は重複なしです。重複があったらやり直して重複なしになるまでやり続けるというのはダメだなと思っています。 データ処理言語のRはコマンド1つのようですが。言語はFortranなのですが、アルゴリズムのレベルだとどれでも同じと考えています。よろしくお願いします。
- 締切済み
- C・C++・C#
お礼
ビンソートを使って解くことが出来ました. おっしゃる通り最大値が大きいと実用的とは言え ませんが,今回はメモリを意識する必要がないよう なので,ビンソートが有効です. ありがとうございました.