|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
07.10.2010, 08:49 | #1 |
Пользователь
Регистрация: 05.10.2010
Сообщений: 46
|
Случайное число
Имеются два массива чисел - два "чёрных списка" (ч.с). Нужно сгенерировать число (0<=X<=49), отличное от элементов ч.с. Делаю так: генерирую число и сравниваю с элементами ч.с, пока не получится подходящее число. Хотя этот конкретный пример работает довольно быстро но код неэффективен при большом размере ч.с. Возникают т.н. неопределённые отсрочки. Подскажите хотя бы, в каком направлении мне думать? Спасибо.
Вот код. Написан наверное коряво, только учусь... Код:
Последний раз редактировалось rommster; 07.10.2010 в 13:33. Причина: Забыл выложить код: |
07.10.2010, 09:23 | #2 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
ну, как я понимаю, других вариантов и быть не может!
Единственное, в Ч.С. нужно ввести сортировку и проверять очередное случайное число на наличие в Ч.С. по ключу (чтобы избавиться от перебора). ДОБАВЛЕНО Цитата:
Дык, тогда чисел в чёрном списке может быть не больше 50 ?!! Тогда, как не крути - будет всё равно быстро ) А по поводу того, что других вариантов и быть не может - я не прав! Тут, как раз, раз множесто чисел такое маленькое - вариантов пруд пруди. Например, заполняем матрицу числами от 0 до 49 потом удаляем из неё те числа, которые есть в обоих Ч.С. - как удалить число из массива - думаю, вопросов не вызывает? Потом берём любое число из этого массива (получаем случайный индекс). Всё. плюс такого подхода ещё в том, что если вдруг Ч.С. полностью закрывают диапазон от 0 до 49 - то это сразу можно будет увидеть - в исходном массиве не останется ни одного числа! А в случае с перебором цикл будет крутиться до бесконечности! Последний раз редактировалось Serge_Bliznykov; 07.10.2010 в 09:29. |
|
07.10.2010, 13:49 | #3 |
Пользователь
Регистрация: 05.10.2010
Сообщений: 46
|
Serge_Bliznykov, спасибо за советы. Ну 50 это у меня так, к примеру, на самом деле может быть до 10000) Попробовал сделать, как вы советовали, не знаю насколько правильно, но работает.
Код:
Последний раз редактировалось rommster; 07.10.2010 в 13:52. |
07.10.2010, 14:00 | #4 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Цитата:
Если отсортируешь появится возможность бинарного поиска - а это самое быстрое из того что тебе нужно. Все равно у тебя числа, вот и отсортируй по возрастанию массивы а и б, и потом при получении случайного числа бинарным поиском по массиву получай ответ есть ли такое или нет. Как бинарный поиск вести знаешь?
I'm learning to live...
|
|
07.10.2010, 14:41 | #5 |
Пользователь
Регистрация: 05.10.2010
Сообщений: 46
|
Попробовал с бинарным поиском, если правильно конечно написал. Массивы по умолчанию уже отсортированы.
Код:
|
07.10.2010, 14:50 | #6 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Цитата:
Если будешь генерировать случайное число в пределах, то на такое врядли попадешся. Более того я бы даже посоветовал сдвигать пределы. Запоминать места где есть дырки и генерировать не со всей последовательности а только по тем частям массива где заведомо извесны дырки, тогда вообще ничего не придется искать. Сейчас я попробую оформить мыслю в виде кода... ДОПИСАНО: Вот что я имел ввиду: Код:
I'm learning to live...
Последний раз редактировалось Stilet; 07.10.2010 в 15:35. |
|
07.10.2010, 15:41 | #7 |
Пользователь
Регистрация: 05.10.2010
Сообщений: 46
|
|
08.10.2010, 09:09 | #8 |
пыжашийся нуб
Пользователь
Регистрация: 19.06.2010
Сообщений: 93
|
Если тебе нужно многократно и быстро генерировать уникальные случайные числа из некого диапазона, то я бы на твоем месте сначала один раз прошелся по всем черным спискам и создал массив уникальных элементов. Потом уже без всяких проверок можешь генерировать свои числа подставляя случайное число, как индекс полученного массива.
|
08.10.2010, 10:08 | #9 |
пыжашийся нуб
Пользователь
Регистрация: 19.06.2010
Сообщений: 93
|
Бывает же такое. Заинтерисовал своей задачкой. Я даже сел и написал.
Код:
при limit=50 время 0.004 секунды при больших лимитах выйгрыш вообще будет несравнимым. Последний раз редактировалось coinkrsk; 08.10.2010 в 10:20. |
08.10.2010, 13:48 | #10 |
Пользователь
Регистрация: 05.10.2010
Сообщений: 46
|
coinkrsk, спасибо, шустро летает! Я в своём посте #3 выкладывал свой код с такой же по сути идеей - составлять массив уникальных элементов. Только работает он слишком тормозно. Я конечно понимаю, что код жуткий: использую простой поиск вместо бинарного, тупое удаление элемента массива и.т.п. Но неужто только из-за этого прога может выполняться аж 100 секунд вместо долей секунды, как у вас? Дело в использовании вектора что ли?
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Случайное число. | Alex Cones | Свободное общение | 27 | 06.06.2010 09:54 |
Программа, загадывающая случайное число | fs444 | Общие вопросы C/C++ | 2 | 24.03.2010 20:19 |
случайное число | Дініс | Общие вопросы C/C++ | 3 | 07.10.2009 23:03 |
Случайное число | Altera | Общие вопросы Delphi | 4 | 05.02.2008 22:22 |
Как згенерировать случайное число | SeRhy | Помощь студентам | 2 | 25.11.2007 20:27 |