|
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 8
|
||||||
Массив случайных неповторяющихся чисел13.06.2012, 13:58. Показов 12183. Ответов 34
Метки нет (Все метки)
Ребят работал всю ночь и сейчас голова не пашет! объясните в чем проблема
и как бы я не страрался все время числа повторяются по логике вроде все правильно
0
|
||||||
| 13.06.2012, 13:58 | |
|
Ответы с готовыми решениями:
34
Генератор случайных неповторяющихся чисел Матрица из случайных неповторяющихся чисел Составить функцию, которая возвращает N случайных неповторяющихся целых чисел из диапазона |
|
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
|
||
| 13.06.2012, 19:00 | ||
|
И на будущее. Добавлено через 4 минуты Правда здесь, наверное, надо будет пояснить, почему std::set. Это реализация "самосортирующегося" контейнера данных STL. Может создан быть для любого класса, у которого определён оператор сравнения < Суть работы заключается в работе двоичного дерева поиска в общем и красно-чёрных деревьях в частности.
1
|
||
|
Чайник
70 / 70 / 9
Регистрация: 15.02.2012
Сообщений: 475
|
|
| 13.06.2012, 19:01 | |
|
AnyOne697, У вас ссылки на пустые страницы https://www.cyberforum.ru/redi... UzQXNldA==
https://www.cyberforum.ru/redi... VFRSVGMg==
0
|
|
|
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
|
|
| 13.06.2012, 19:05 | |
|
??? Фигово. Вставлял - были нормальные. Окей - всё равно вкладки не закрываю.
http://www.cplusplus.com/reference/stl/set/find/ https://www.google.ru/search?q=std::set http://ru.wikipedia.org/wiki/красно-чёрное_дерево http://ru.wikipedia.org/wiki/д... ево_поиска Добавлено через 27 секунд P.S. Проблема не моя, а форума.
1
|
|
|
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
|
||||||
| 13.06.2012, 19:20 | ||||||
|
Если диапазон чисел не сильно больше необходимого количества чисел, или равен ему, то может оказаться проще выкинуть лишние и перемешать оставшиеся. Например так:
1
|
||||||
|
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
|
||
| 13.06.2012, 19:32 | ||
|
Эх, блин. Экспер =) Почему до меня эта идея не дошла?..
0
|
||
|
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
|
||||||
| 13.06.2012, 19:38 | ||||||
|
На самом деле метод можно даже упростить, если сначала перемешать, а потом удалить.
И да, есть стандартный алгоритм для перемешивания std::random_shuffle, но мне с ним не хотелось
0
|
||||||
|
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
|
|||
| 13.06.2012, 19:38 | |||
|
Зато можем сократить немного перемешивание заменив ARRAY_SIZE на ARRAY_SIZE/2.
0
|
|||
|
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
|
||
| 13.06.2012, 19:57 | ||
|
0
|
||
|
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
|
||
| 13.06.2012, 20:05 | ||
|
ARRAY_SIZE = 1: один бессмысленный swap ( имеет ли смысл n % 1? ) ARRAY_SIZE = 2: одна итерация -> 50% будет swap, 50% - нет => всё огонь; вторая явно лишняя ARRAY_SIZE = 3: тоже самое ARRAY_SIZE = 100500^42^146: без разницы - всё равно будет МНОГО
0
|
||
|
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
|
|
| 13.06.2012, 20:19 | |
|
Если делать ARRAY_SIZE/2 итераций, то в среднем половина элементов из второй части массива останутся на своих местах. Это чересчур много. Вырожденный случай с размером 1 не показателен. Да элемент будет бессмысленно обмениваться сам с собой. Ну так для одного элемента и алгоритм никакой не нужен
Да, для двух элементов тоже достаточно было бы одной итерации, но вторая ничего не портит. А вот с большими размерами увы, половины итераций недостаточно.
0
|
|
|
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
|
||||||||||||
| 15.06.2012, 19:31 | ||||||||||||
|
Ну... Немного посидев с листом и карандашом, решил, что да. Математическая индукция здесь ни к чёрту. Как всегда
Понятно, что здесь перемещаются только соседние элементы, но не знаю. Может есть какой-то гениальный математический способ более эффективного перемешивания массива основанный на чём-то похожем. Или вообще на одной очень сложной математической истины. Какие-нибудь n-мерные пространства. А для простых смертных сойдёт и
0
|
||||||||||||
|
35 / 35 / 11
Регистрация: 25.05.2010
Сообщений: 211
|
||||||
| 15.06.2012, 21:04 | ||||||
0
|
||||||
|
Форумчанин
8217 / 5048 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
|
||||||
| 15.06.2012, 21:11 | ||||||
0
|
||||||
|
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
|
||
| 15.06.2012, 23:46 | ||
|
Сначала быстро наваял в codepad.org, прямо в input'е. Но он не хотел долго работать, а на "малых" рэнжах время конца работы почти не отличалось от времени начала (в секундах, было лениво вспоминать, как адекватно отображать миллисекунды). Переехал на minGW - массив обрабатывал очень быстро, а вот коллекция вешалась начиная с какого-то AMOUNT (кол-во требуемых элементов). Определил - где-то на 32760 элементе. Потом просто виснул. Перехал на Visual Studio - с std::set тоже самое, а массив очень долго работал (видимо антиоптимизации для дебага) - секунд 30, в тридцать раз дольше по сравнению с minGW. Хотел был переключаться на Linux, но увидел эту вкладку и стало влом.
0
|
||
| 15.06.2012, 23:46 | |
|
Сгенерировать массив из N неповторяющихся четных чисел в заданном диапазоне
Эксперты! Одномерный массив неповторяющихся чисел не могу понять почему криво работает Сформировать одномерный массив целых чисел, используя датчик случайных чисел. Сформировать одномерный массив целых чисел, используя датчик случайных чисел Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Сезонность и суточность закисления почв
anaschu 04.07.2026
200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет.
Но обычно это 50 лет и более.
Наверное, закисление почвы происходит сезонно в средней. . .
|
В чем ценность человеческого опыта в глобальном смысле?
kumehtar 03.07.2026
Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
|
интеграция AnyLogic с самописным REST API и переход на Odoo
anaschu 03.07.2026
Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS
Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
|
Поиск всех путей на ориентированном графе. Linux
dcc0 02.07.2026
Переработка старого кода из моей статьи.
Через несколько переработок от PHP кода к C89 (надеюсь, 89).
Но довольно запутанно получилось. Код для Linux.
Но если убрать time и то, что с ним. . .
|
|
Сам себя обучал rest api
anaschu 02.07.2026
Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки
Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .
|
rest api anylogic - выполнение модели на своём русском сайте
anaschu 02.07.2026
Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы
Всем привет! Хочу поделиться свежим (и довольно. . .
|
Где деньги лежат
kumehtar 02.07.2026
Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
|
Krabik для WoW 3.3.5a, многоязычный
AmbA 02.07.2026
Допилил бота, думаю что окончательно. Изменения:
- добавлена многоязычность
- добавлено снятие скриншотов
- добавлено поддержание бафов хождения по воде (для жреца, дк и шамана)
- и так, по. . .
|