配列要素の比較

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
マコトスパルビエロ

配列要素の比較

#1

投稿記事 by マコトスパルビエロ » 7年前

遺伝的アルゴリズムを使って最適配置を探すプログラムをC++にて作ろうとしています。
質問自体は遺伝的アルゴリズムの本質からは離れます。

評価配列double V[N]の要素の値を比較して、その値が小さいものから、順番にE個分の添え字を取り出したいと考えています。

例えば、N=5、E=2とすると
V[5]={1.7,2.5,3.4,10.5,8.1,2.0}
から、0と5を選んでほしいのです。

コード:

for(i=0;i<N;i++){
       if(V[i]<temp){
	temp=V[i];
	}
}
上記のような方法で最小値や、その添え字を選ばせることはできます。
ただ、じゃあ2番目に小さい値はどこ?3番目は?で困っています。

2週間ほど前にもお世話になりました。
その時のプログラムは、おかげさまでほぼ完成することができました。
ところが、挙動に不満点があり、改良をしています。
時間がある時にお力をお貸しください。よろしくお願いします。

jay
記事: 314
登録日時: 9年前
住所: 大阪市
連絡を取る:

Re: 配列要素の比較

#2

投稿記事 by jay » 7年前

こんな感じでどうでしょう?

コード:

#define NUM 2	//取得する数値の個数

int temp[NUM];	//取得した数値
int sr;

//検索する個数分ループさせる
for(int n=0; n<NUM; n++)
{
	sr=0;
	temp[n] = 1000000;

	//配列から数値を検索
	for(int i=0; i<N; i++)
	{
		//既に取得した値と比較する
		for(int s=0; s<n; s++)
		{
			if(V[s]==temp[n])
			{
				//同じ数値があれば既に取得されたということ
				sr = 1;
			}
		}
		//temp[n]よりより小さく、まだ取得されていなければ数値をtemp[n]に保管
		if(V[i]<temp[n] && sr==0)
		{
			temp[n]=V[i];
		}
	}
}

追記:
>マコトスパルビエロさん
3つめのfor文のn++の部分はミスですね、これは失礼(一応訂正しておきました)
よく読んでなくてこちらも失礼しましたが、取得する必要があるのは添え字との事ですね
このコードの応用でそれも可能です、と言うか修正コードを載せるまでもなくそれは出来たみたいですね

何はともあれお役に立てたようで良かったです
最後に編集したユーザー jay on 2012年12月08日(土) 22:52 [ 編集 3 回目 ]
♪僕たちは まだ森の中 抜け出そう 陽のあたる場所へ

マコトスパルビエロ

Re: 配列要素の比較

#3

投稿記事 by マコトスパルビエロ » 7年前

jay様
丁寧にコードまでありがとうございます!
書いていただいたコードのn++をs++に置き換えれば理解できたと思います。
要するに、一時に保存しておいた最小値と比較して同じものなら、採用しないと。
それなら、次々と検出できそうですね!
わかりやすい説明まで書いていただき、本当にありがとうございます。
とても素早い返信で感謝しています。

かずま

Re: 配列要素の比較

#4

投稿記事 by かずま » 7年前

解決したのなら、そのコードを提示してほしいものです。
取り出したいのは添え字ではないのですか?
jay さんのプログラムは、かなり改変しないとダメな気がします。

C++ なら map に放り込めば、ソートが完了します。

コード:

#include <iostream>
#include <map>

int main()
{
    const int N = 6, E = 3;
    double V[N] = { 1.7, 2.5, 3.4, 10.5, 8.1, 2.0 };

    typedef std::map<double, int> Map;
    Map a;  
    for (int i = 0; i < N; i++) a[V[i]] = i;

    Map::iterator it = a.begin();
    for (int i = E; --i >= 0 && it != a.end(); ++it)
        std::cout << it->second << std::endl;
}    

マコトスパルビエロ

Re: 配列要素の比較

#5

投稿記事 by マコトスパルビエロ » 7年前

かずま様
解決後であるにもかかわらず返信ありがとうございます。
私はコードを丸パクリしたくないので、考え方を聞いて、それをもとにコードを書いてみようと思っています。
実際時間はかかるかもしれませんが、jayさんのやり方でできそうだと理解したので、解決!とさせていただきました。
添え字に関しては、最後のifの中で、求めている最小値を見つけた時に、iを他のところにストックしておけばいいと考えました。
ただ、そのコード自体はまだできてません。添え字部分は下記です。

コード:

if(V[i]<temp[n] && sr==0)
        {
            temp[n]=V[i];
soeji[n]=i;
        }
そして、かずま様のコードはとてもありがたいことに、このまま利用ができました。
非常にシンプルで簡潔なもので、素晴らしいです。
ただ、私がC++にて作ろうとしているのですが、mapを勉強していません。
したがって、コードのトレースができません。
この機会に勉強してみます。いい機会ですし、間違いなくこの機会に勉強すべきでしょう。
ありがとうございました!

YuO
記事: 941
登録日時: 9年前
住所: 東京都世田谷区

Re: 配列要素の比較

#6

投稿記事 by YuO » 7年前

  1. 添字の配列等を作る
  2. std::nth_element or std::partial_sortに,値を配列の添字とみなして,配列の値の比較を行うラムダ式等と共に放り込む
なんて方法も。
  • std::nth_element
    上位N個が欲しい。N個の順序は問わない
  • std::partial_sort
    上位N個が欲しい。N個も順序づけされていて欲しいが,残りは順序づけされている必要は無い
  • std::sort, std::stable_sort
    全てを順序づけしたい

かずま

Re: 配列要素の比較

#7

投稿記事 by かずま » 7年前

YuO さんが書きました:
  1. 添字の配列等を作る
  2. std::nth_element or std::partial_sortに,値を配列の添字とみなして,配列の値の比較を行うラムダ式等と共に放り込む
なんて方法も。
なるほど、map より効率がよさそうですね。
ラムダ式の代わりに関数オブジェクトを使うと、

コード:

#include <iostream>
#include <algorithm>

class Comp {
    double *v;
public:
    Comp(double *x) : v(x) {}
    bool operator()(const int& a, const int & b) { return v[a] < v[b]; }
};

int main()
{
    const int N = 6, E = 3;
    double V[N] = { 1.7, 2.5, 3.4, 10.5, 8.1, 2.0 };

    int index[N];
    for (int i = 0; i < N; i++) index[i] = i;
    std::partial_sort(index, index + E, index + N, Comp(V));
 
    for (int i = 0; i < E; i++)  std::cout << index[i] << std::endl;
}

閉鎖

“C言語何でも質問掲示板” へ戻る