Привет воины Есть массив указателей unsigned integer AddrArray[100] Из этого массива нужно выбрать случайным образом 20 адресов. Подскажите, как реализовать эффективнее всего? Сейчас у меня при каждом выборе нового адреса, выбраный адрес сравнивается с уже выбранными и если совпадение - выбираем адрес повторно... И вот так до полного заполнения 20 указателей. Но чую - это неправильно и можно как-то сделать красивее.
ставеть на место уже выбранного ноль... чтото типа Код (Text): for (i=0;i<n;i++) x=0; while (!viborka[i]) { k=rand()%n; viborka[i]=AddrArray[k]; } AddrArray[k]=0; }
Freeman нннет.... Все-равно прийдется проверять на ноль...А если ноль - то повторно вызывать процедуру выборки. В нашем случае вызов rand() и сравнение. Теоретически, если ранд() будет возврашать одну и ту же величину либо всего 19 значений вместо 20 - вся система повиснет... Т.е. за подобную реализацию мне снимут балы. Нужно как-то проще... Например разбить массив на интервалы и брать элементы от каждого интервала...Или что-то подобное..
Можно наподобие как стандартный random_shuffle работает: Код (Text): for (int i=0; i<20; ++i) { int j = i + rand() % (n-i); swap (a[j], a[i]); } По окончании первые 20 элементов массива будут случайно выбранными 20 элементами из него.
Тут в разделе статей по вирусологии есть какой-то особохитров..анный алгоритм обращения к рандомным элементам (там это используется для расшифровки тела из декриптора), псевдослучайные обращения каждый раз к разным элементам, пока не переберуться все. Имхо то что нужно.... А вобще, это форум по низкоуровневому программированию, вопросы по СИ можно задать на форумах соответствующей тематики...
тьфу ты. перепутал. циклический код. http://ru.wikipedia.org/wiki/%D0%A6%D0%B8%D0%BA%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%BE%D0%B4 все просто и ничего сложного.
Для С есть отдельная ветка, A&O и другие ветки по умолчанию для ассемблера. В сортировках массива нет ничего системного и низкоуровневого...
Элементарно. Юзай идею линейного конгруэнтного ДПСЧ: 1) выбери С=100 2) выбери A=8t+5, где t - целое число. Например: 13, 21 и т.п. 3) выбери B= нечетное и не кратное 5 число (а можно и не выбирать). 4) возьми какую-нить начальную затравку 0<R(0)<100. 5) все остальные индексы получай как R(i)=(R(i-1)*A+B) mod C или просто R(i)=(R(i-1)*A) mod C. При этих условиях товарищ Кнут гарантирует 100 _неповторяющихся_ чисел в интервале от 0 до 99, что, сопсно гря, и нужно.
Можно применить алгоритм, аналогично ловле льва в пустыне (разбиением на полупустыни/кусочки): 0. Получаем границы отрезка start=0, end=100. Если start==end, то добавляем это число к результирующей выборке, инкрементируем счётчик count и дуем на проверку счётчика (в п.3). Иначе, если start<end переходим к п.1 1. Генерируем случайное число (rnd) от 0 (start) до 100 (end), добавляем его к результирующей выборке, инкрементируем счётчик count. 2. Число rnd фактически разбивает отрезок [start,end] на 2 интервала: [start, rnd) и [rnd, end] 3. Для каждого из отрезков из п.2 поступаем аналогично как в п.1, пока либо счётчик не достигнет нужного значения 20, либо пока отрезки из п.2 не выродятся (т.е. start==end - начало и конец отрезка будут совпадать). Если чисел будет только 19, то алгоритм, выведет все 19 возможных чисел (в случайном порядке) и остановится (все отрезки выродятся в точки), зависания не будет. process [0, 100]: rnd[0,100]=37 => result={37} => process [0, 37) & process [37, 100] process [0, 37): rnd[0,37)=13 => result={37,13} => process [0, 13) & process [13, 37) process [37, 100]: rnd[37, 100]=69 => result={37,13,69} => process [37, 69) & process [69, 100] ну и т.д. Собственно, тут важен сам принцип, ибо в вышеописанном алгоритме могут быть косяки, но они решаемы. Главное, что выпадения одного и того же случайного числа дважды мы избегаем by design
Более быстрым получался вариант "топания" к соседним элементам в массиве, чтобы не вызывать выборку заново. Вроде считаем, что если попал в выбранный, то попал просто рядом. А сравнение с выбранным - быстрее по меткам в параллельном массиве.
