ページ 1 ／ 1
配列の要素にランダムで入力
Posted: 2012年11月26日(月) 16:59
by マコトスパルビエロ
初めまして。遺伝的アルゴリズムを使って最適配置を探すプログラムをC++にて作ろうとしています。
配列a[500]にランダムで0か1を入力し、要素が1ならばそこに配置というように符号化を考えています。
今回、配置する箇所の数的制限を作って、その数以内で配置したいと考えています。
つまり、a[500]の要素のうち、1の入る箇所をたとえば150箇所以内としたいのです。
私の考えた方法は、
①配列a[500]にランダムに0、1を入力
②配列a[500]の要素の総和を計算
③②の総和が150以上の場合、配列のどこかを(ランダムで)0に置き換える
④②へ繰り返し
という形です。
この方法の③の箇所、「配列のどこかを(ランダムで)0に置き換える」ことをしたいのですが、どのような方法がありますでしょうか？
また、上記の方法はとても効率的には見えません。もっと効率の良い方法があれば教えていただけると幸いです。
なお、配列内の要素の順番は入れ替えることはできません。(最適配置を探しているため)
また、0、1がすでにランダムで入力された状態であることが前提です。配列に入力する段階での工夫はできません。(アルゴリズム内で交叉させるため)
以上になります。お時間があれば返信をよろしくお願いします。
Re: 配列の要素にランダムで入力
Posted: 2012年11月26日(月) 17:37
by non
質問ですが、1にする箇所が150未満であればいくらでもいいのですか？
例えば、常に149でも。
それとも、何らかの分布がありますか？
Re: 配列の要素にランダムで入力
Posted: 2012年11月26日(月) 18:01
by マコトスパルビエロ
ご質問ありがとうございます。
この場合、150という基準は一定の整数です。
わかりにくくて申し訳ありません。
Re: 配列の要素にランダムで入力
Posted: 2012年11月26日(月) 18:03
by マコトスパルビエロ
常に149でも構いません。
1の個数は1～150のいずれかになれば大丈夫です。
よろしくお願いします。
Re: 配列の要素にランダムで入力
Posted: 2012年11月26日(月) 18:47
by Tatu
この方法はどうでしょうか？
1.a[500]のうちa[0]を1、a[1～149]をランダムに0か1とし、残りを0とする。
2.aの中身をシャッフルする。
コード
► スポイラーを表示
コード:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(){
int a[500]={0};
int numA,numB;
int temp;
int count;
int i;
//乱数シードの変更
srand((unsigned)time(NULL));
//aのうち150個をランダムで1か0にし、残りは0とする
for(i=0;i<500;i++){
if(i<150){
a[i]=rand()%2;
}
else a[i]=0;
}
//aをシャッフル
for(i=0;i<20000;i++){
numA=rand()%500;
numB=rand()%500;
temp=a[numA];
a[numA]=a[numB];
a[numB]=temp;
}
//結果表示
count=0;
for(i=0;i<500;i++){
printf("%d",a[i]);
if(a[i]==1) count++;
if(i%50==49){
printf("\n");
}
}
printf("1の数は%d個です\n",count);
return 0;
}
Re: 配列の要素にランダムで入力
Posted: 2012年11月26日(月) 20:25
by マコトスパルビエロ
わざわざソースまでありがとうございます。
残念ながら、シャッフルする点で私の考えているものとズレが生じています。
配列に含まれる1、0は設備の配置を表しているため、順序を変えることはできません。
ランダムにa[500]まで0か1がすでにびっしり埋まっている状態から、工夫をしなければなりません。
すでに配列に含まれている1のうち、150個を超えた分をどうにかしてランダムで0に変換したいのです。
丁寧に書いていただいたのに、申し訳ないです。
わかりにくい問題ですいません。
Re: 配列の要素にランダムで入力
Posted: 2012年11月26日(月) 20:50
by beatle
0以上499以下の整数をランダムに150個生成し、その生成した整数をaの添字に使う方法はいかがでしょう。
コード:
for (i = 0; i < 150; ++i) {
r = rand() % 500;
a[r] = 1;
}
Re: 配列の要素にランダムで入力
Posted: 2012年11月26日(月) 21:05
by たいちう
②で１の個数を数えながら、vector<int>に1のindexをpush_back。
vectorをrandom_shuffle。
150を超えた分だけ、vectorの先頭のindexが指す要素を0にする。
Re: 配列の要素にランダムで入力
Posted: 2012年11月26日(月) 21:15
by マコトスパルビエロ
beatleさんの方法でできるようです！
ありがとうございます！
その他、返信していただいた方々、返信しようと考えてくださった方々、ありがとうございました。
非常に助かりました。
難しいことではなかったですが、自分ではなかなか思いつけませんでした。
重ねてお礼申し上げます。