n個の要素をもった配列で、2番目に大きい要素を見つけるコードを書きたいのですが、合っているのか不安になって、質問させてもらいます。
アルゴリズムとしては、まず、n-1回の比較をしてその中でmaxを見つけ、残りのn-1個の要素のなかでn-2回の比較をしてそのn-1個の配列のmaxを見つければ、2番目に大きい要素を見つけられると考えました。
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];
}
これであっていますでしょうか?
よろしくお願いいたします。
A 回答 (7件)
- 最新から表示
- 回答順に表示
No.7
- 回答日時:
簡単な1重ループだけでで可能です
int max, second, i;
max=0;
for ( int i=1; i<n; ++i ) if ( E(max)<E(i) ) max=i;
int second=0;
if ( max==0 ) second=1;
for ( i=second+1; i<max; ++i ) if ( E(second)<E(i) ) second=i;
for ( i=max+i; i<n; ++i ) if ( E(second)<E(i) ) second=i;
No.6
- 回答日時:
最大値を調べるのはそれでいいと思いますが
2番目の値を調べるときに、最大値を選んでしまう可能性があります。
下記は一重ループの例です。
該当データが複数ある場合には最初のデータを有効としています。複数全てチェックする場合には結果格納変数を配列にする等の処理が必要です
flagはnumに有効なデータが入っているか否かを示すフラグで、初期値を工夫するとflag処理は要らなくなり、ループの中はifが二つになります。
実際データ量が多いときには、最初に出会う値の違う2値を初期値にしてループ中のifを2つにした方が早そうです。
#define MAX(16)
void main(void)
{
int c[MAX]={1,2,3,3,4,4,5,6,7,8,8,8,9,9,9,-1};
int i, num1, num2, i1, i2, flag1, flag2;
flag1 = flag2 = 0;
i1 = i2 = -1;
for (i = 0; i < MAX; i++){
if (0 == flag1){
num1 = c[i];i1 = i;flag1 = 1; //最大値初期値
}
else if (num1 < c[i]){ //最大値交代
num2 = num1;i2 = i1;flag2 = 1; //それまでの最大値が2番目に
num1 = c[i];i1 = i; //新最大値
}
else if (num1 > c[i]){
if (0 == flag2){
num2 = c[i];i2 = i;flag2 = 1;//2番目初期値
}
else if (num2 < c[i]){ //2番目交代
num2 = c[i];i2 = i;
}
}
}
if (0 <= i2){
printf("second c[%d]=%d\n",i2,num2);
}
else{
printf("second is nothing\n");
}
printf("(ref)max c[%d]=%d\n",i1,num1);
}
No.5
- 回答日時:
>これであっていますでしょうか?
アルゴリズムとして最善かということは別にして,昇順ソートして結果E[n-2]を参照すれば,答えが求められますので正しいと思います。(main()の戻り値が答えなら間違えです。)
但しE[]に同じ値が複数ある場合は1番目と同じ値が格納される場合があります。これは考えすぎかもしれません。
とりあえずソートしないでも同じことは出来ますので参考までにサンプルを付けます。
【サンプル】
アルゴリズム:n回ループして最大値とその次の値を保存していきます。
int E[n]; // 要素配列 n個
int max1st = INT_MIN; // 最大値 初期値としてint型の最小値を設定
int max2nd = INT_MIN; // 最大値の次の値 初期値としてint型の最小値を設定
int i; // ループ用
for ( i = 0; i < n; i++ ) {
if ( E[i] > max1st ) { // 最大値よりE[i]が大きい場合は最大値を更新
max2nd = max1st; // 2番目は旧最大値
max1st = E[i]; // 最大値の更新
} else if ( ( max1st > E[i] ) && ( E[i] > max2nd ) ) { // 最大値ではないが2番目かも(max1st > E[i] > max2dの場合は更新)
max2nd = E[i]; // 2番目の最大値更新
}
}
/* 答えはmax2ndに格納されます。見つからない場合はINT_MINが格納されます。 */
No.4
- 回答日時:
>これであっていますでしょうか?
あってません。
配列を並び替える必要はありません。
int main(void)
{
int E[10]={67,-4,2,66,22,-5,65,3,0,-55};
int i,i1,i2;
i1=0;
i2=-1;
for (i = 1;i <= 9;i++) {
if (E[i1] < E[i]) i1 = i;
}
for (i = 0;i <= 9;i++) {
if (E[i1] < E[i]) i1 = i;
if (E[i1] > E[i]) {
if (i2 != -1) {
if (E[i2] < E[i]) i2 = i;
} else i2 = i;
}
}
printf("%d\n",E[i2]);
}
ANo.2の回答者さんへ
>一重ループで処理することを考えてください。
やってみれば判りますが、単純な1重ループでは実現できません。
>以上のようにすれば E(imax),E(inext)に最大値、二番目のものが求まる
求まりません。
ANo.2の回答者さんのアルゴリズムではimaxとinextの両方が0のままループを終了する可能性があります。
No.3
- 回答日時:
>アルゴリズムとしては、まず、n-1回の比較をしてその中でmaxを見つけ、残りのn-1個の要素のなかでn-2回の比較をしてそのn-1個の配列のmaxを見つければ、2番目に大きい要素を見つけられると考えました。
最大値が複数ある場合への対応が抜け落ちているようです。
「n-1回の比較をしてその中でmaxを見つけ、またn-1回の比較をして最初のmax以外のmaxを見つける」
となると思います。
しかし、コードはもっとおかしいと思います。ちなみにコードはコンパイルが通るものを提示していただきたいですね。
初期化されていない変数nを使って
>int E[n];
とか、いただけない。配列Eを初期化せず参照していることも同様。
それと"n"と"N"は違います。
文章では、(n-1)+(n-2)回ループすると書いてあるのに、n(n-1)/2回も回しているのはなぜ?forをネストするのではなく、別々に2回書くべきでは?
コードの中では最初のmaxを除いた比較もしていません。
int E[]={1,2,3,4,4};
とか小さい配列の例をいくつか実際に動作確認することを薦めます。
アルゴリズムはいろいろあるでしょうが、ご自分の考えをきちっとコードに表わせるようになるためにも大切なことです。
No.2
- 回答日時:
あっているとは思われます。
但しもっと良いやりかたがあると思われます。
まずこのやり方では内部ループの実行回数がn*n/2のオーダー実行されます。
それとアレイEはメモリ参照のみで処理できると思われます。
(メモリストアは参照よりも実行時間がかかりますので)
一重ループで処理することを考えてください。
一番、二番目に大きい数のindex:imax,inextを0に初期化する
for(i=1;i<n;i++) {
if(E(i)<=E(inext)) continue;
if (E(i)>E(imax) {...}
else {...}
}
以上のようにすれば E(imax),E(inext)に最大値、二番目のものが求まるように出来るはずですので検討してください。
No.1
- 回答日時:
>n個の要素をもった配列で、2番目に大きい要素を見つけるコード
既存のソートアルゴリズムのいずれかを用いて、
与えられた配列を降順にソートします。
このとき、いちばん大きい値が配列の[0]に入っていますね。
そして、2番目に大きい要素が配列の[1]に入っています。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
関数から配列を返すには?
-
int i, int i[1];
-
c言語
-
C#で構造体の配列を持った構造...
-
配列の要素数に変数を入れたい...
-
C言語 ファイルの指定された行...
-
C言語 数値の連続入力について
-
構造体を引数とする関数について
-
define で 配列
-
構造体のextern方法
-
C言語において、 配列要素をひ...
-
C#でのフィボナッチ数列
-
コンボボックスでデフォルト値...
-
C言語の配列のコピーについて
-
Cのエラー
-
std::vector 2次元配列の列方向...
-
Integer変数をカラにしたいので...
-
VB.NETでファイル名順にファイ...
-
配列で格納したものをmsgboxで...
-
VBAのプログラムで、DIAG = 1# ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
関数から配列を返すには?
-
構造体のextern方法
-
配列の要素数に変数を入れたい...
-
C言語において、 配列要素をひ...
-
define で 配列
-
c言語
-
C#で構造体の配列を持った構造...
-
C言語 ファイルの指定された行...
-
c言語 構造体
-
コンボボックスでデフォルト値...
-
配列のアドレス部
-
MFCのCArrayを使った二次元配列
-
MFC - ダイアログボックスのPic...
-
C言語についてです 5人のテスト...
-
C言語から質問です。
-
AfxBeginThread の引数について
-
C言語の課題が出たのですが自力...
-
Cのエラー
-
int i, int i[1];
-
C#で配列が空かを判定するには?
おすすめ情報