 |
|
 |
|
|
Рандомизация числа без цикла перегенерации
|
|
| Duosora | Дата: Вторник, 03 Марта 2015, 00:19:46 | Сообщение # 1 |
|
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:  | Здравствуйте. Я к вам с довольно интересным вопросом из области псевдослучайных чисел.
Существует некоторая прямоугольная область типа rect. Условно назовём её R. В ней находится другая прямоугольная область типа rect, условно названная S, имеющая центральную точку, которая совпадает с центральной точкой области R, но область S своими размерами намного меньше области R. От области S есть равноудалённые от неё области типа rect, условно названные T, U, V и W, одного и того же размера (см. рисунок ниже).
Требуется, не используя циклов, сгенерировать случайную точку в области R, которая бы не находилась ни в области S, ни в области Т, ни в области U, ни в области V, ни в области W.
Как это возможно сделать? Заранее благодарен плюсами в репутацию за любую попытку ответа либо полноценный ответ.
Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
Сообщение отредактировал Duosora - Вторник, 03 Марта 2015, 00:20:50 |
| |
|
|
| Srezi | Дата: Вторник, 03 Марта 2015, 00:34:01 | Сообщение # 2 |
7 уровень
Группа: Проверенные
Сообщений: 414
Награды: 0
Репутация: 116
Блокировки: | без циклов о_О ну... проверять не относится ли твоя точка к ректам. Вернее создавать случайную точку и условием проверять По информатике такое изучали)
Либо добавлять области ректа в условие.
Например
set x=GetRandomReal(minXкарты,maxXкарты)
if x в промежутке одного из rect(S,T,U,V,W), то
set x=GetRandomReal(maxX(ректа в который точка попала),maxX(карты))
И так далее...
Без циклов делать данную вещь как то необычно скучно и...
Нет места чести на войне,
Враг церемониться не будет,
Убей его любым путём,
Ведь победителей не судят.
|
| |
|
|
| Duosora | Дата: Вторник, 03 Марта 2015, 00:57:24 | Сообщение # 3 |
|
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки: | Всё дело в том, что количество витков такого цикла так же рандомно, как и само число. А цикл-то может затянуться.
Такими ифами тут не отделаешься - это развёртка цикла.
Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
|
| |
|
|
| Srezi | Дата: Вторник, 03 Марта 2015, 01:46:47 | Сообщение # 4 |
7 уровень
Группа: Проверенные
Сообщений: 414
Награды: 0
Репутация: 116
Блокировки: | Используй математику. Находи по обеим координатам координаты внутри Областей и вырезай. If и endif там обязательно будут.
Нет места чести на войне,
Враг церемониться не будет,
Убей его любым путём,
Ведь победителей не судят.
|
| |
|
|
| sumert | Дата: Вторник, 03 Марта 2015, 04:10:35 | Сообщение # 5 |
10 уровень
Группа: Проверенные
Сообщений: 2330
Награды: 2
Репутация: 1094
Блокировки: | Если без циклов, то надо создавать новые области, которые не лежат в (S,T,U,V,W) и выбирать случайную точку там.
|
| |
|
|
| Extremator | Дата: Вторник, 03 Марта 2015, 12:50:58 | Сообщение # 6 |
10 уровень
Группа: Проверенные
Сообщений: 3199
Награды: 0
Репутация: 1018
Блокировки: | задаёшь точке случаные координаты внутри области
а потом если эту точка попала в одну из ненужных областей - перемещаешь её в другое место, за края области
если например размер малых областей хотя бы 500 по строне
то можно в таком случаи сдвигать точку на ~500 центра этой области, в рандомном направлении
типа выбор выпал в ней, но был выдвинут из неё...
Ну и с большой так же
Можно циклом все 5 областей чекать
. . .
А вообще наверняка там координатами расчёт идёт
Поэтому можно просто задать X случайно от minX до maxX области
а далее уже выдать случайный Y, но уже от minY и до maxY, при этом не более чем некоторые пересекающиеся значения
. . .
Либо вариант очень простой, но топорный
Создать во всех остальных местах новые области, которые покроют общую область, будет как пазл с забаненными деталями
И при выборе случайно выбирать точку на одной из случайно выбранных областей (не забаненных).Добавлено (03 Марта 2015, 12:50:58)
---------------------------------------------
Хотя не думаю что то что описал топик-стартер для него вообще является вопросом.
Скорее всего он пилит что-то более сложное, и более грузящее...
И для простоты объяснения выбрал вот такой интерпретацию.
У него может таких областей штук 50 будет, и они в добавок будут ещё динамическими х))
|
| |
|
|
| Gr0m | Дата: Вторник, 03 Марта 2015, 13:20:13 | Сообщение # 7 |
8 уровень
Группа: Проверенные
Сообщений: 729
Награды: 0
Репутация: 249
Блокировки: | Интересна я тема! создавать точку случайно каждый раз игнорируя ненужные нам области, она может создаваться в другой такой же области довольно много раз и будет это повторяться, можно проверить если точка входит в координаты (STUVW) области дать ей новую координату где-то с краю области в которую вошла точка.
Примитивный метод
|
| |
|
|
| Duosora | Дата: Вторник, 03 Марта 2015, 14:27:27 | Сообщение # 8 |
|
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки: | Gr0m,
Это вновь предложение цикла, от которого я хочу уйти из-за случайного количества итераций в самом цикле. Это говорит уже само понятие "каждый раз". Но за попытку благодарочка плюсом)
Extremator,
Цитата Extremator (  ) А вообще наверняка там координатами расчёт идёт
Поэтому можно просто задать X случайно от minX до maxX области
а далее уже выдать случайный Y, но уже от minY и до maxY, при этом не более чем некоторые пересекающиеся значения
Ты пришёл практически к тому же решению, какое подумывал использовать я, но, если областей вдруг станет больше, то вариант внезапно станет куда затратнее. =)
Цитата Extremator ( ) Либо вариант очень простой, но топорный
Создать во всех остальных местах новые области, которые покроют общую область, будет как пазл с забаненными деталями
И при выборе случайно выбирать точку на одной из случайно выбранных областей (не забаненных).
Что-то мне кажется, что такой вариант сожрёт гораздо больше, да ещё и потребует дополнительную память для его реализации (в памяти как rect, так и ссылку на него надо где-то хранить). Действительно, топор.
Цитата Extremator ( ) Скорее всего он пилит что-то более сложное, и более грузящее...
Немного открою карты - пилю достаточно навороченный боссфайт. =)
Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
|
| |
|
|
| Extremator | Дата: Вторник, 03 Марта 2015, 14:51:58 | Сообщение # 9 |
10 уровень
Группа: Проверенные
Сообщений: 3199
Награды: 0
Репутация: 1018
Блокировки: | Ну тогда наверняка всё же будет проще при попадании точки в ненужную область - просто выталкивать точку за край области, вот и всё
Будет например 12 областей таких по кругу, и в центре 13я
Задашь точке случайную позицию.
Циклом от 1 до 13 проверишь чтобы точка не была в областях
если вдруг оказалась - берём эту область, и выпихиваем точку на некое расстояние из области.
в итоге - если рандомнуло в область, то точка будет около области, а не в ней х)
помойму это будет самый лучший вариант
(ну вместо точек координаты там сравнивать как полагается)
|
| |
|
|
| Duosora | Дата: Вторник, 03 Марта 2015, 15:00:16 | Сообщение # 10 |
|
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки: | Extremator,
Кстати, отличная идея! Спасибо огромное =)
Но не откажусь послушать ещё варианты. =)
Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
|
| |
|
|
| Borodach | Дата: Вторник, 03 Марта 2015, 15:52:43 | Сообщение # 11 |
9 уровень
Группа: Проверенные
Сообщений: 930
Награды: 0
Репутация: 422
Блокировки: | Еще вариант перепрыгивать области
Первый рандом для указания направления. Второй промежутки прыжков...
Karamba
Сообщение отредактировал Borodach - Вторник, 03 Марта 2015, 15:55:27 |
| |
|
|
| Impregnable | Дата: Вторник, 03 Марта 2015, 16:19:36 | Сообщение # 12 |
6 уровень
Группа: Проверенные
Сообщений: 231
Награды: 0
Репутация: 92
Блокировки: | Находим смещение искомой точки по X от центра R, S:
Код
xOffset = <ширина S>*0.5 + случайное число в диапазоне (0; (<ширина R> - <ширина S> - <ширина T> - <ширина U>)*0.5]
if( xOffset > <расстояние от центра S до края T по X> )
xOffset += <Ширина T>
На данный момент мы имеем абсолютное значение смещения. Чтобы получить само смещение необходимо сменить знак xOffset или оставить как есть.
По аналогии проделываем то же самое и с Y.
Если долго мучиться, то может,
все равно нихуя не получится.
Сообщение отредактировал Impregnable - Вторник, 03 Марта 2015, 16:23:39 |
| |
|
|
| Extremator | Дата: Вторник, 03 Марта 2015, 16:23:27 | Сообщение # 13 |
10 уровень
Группа: Проверенные
Сообщений: 3199
Награды: 0
Репутация: 1018
Блокировки: | http://rghost.ru/6znNZgn7m
|
| |
|
|
| sumert | Дата: Вторник, 03 Марта 2015, 19:06:39 | Сообщение # 14 |
10 уровень
Группа: Проверенные
Сообщений: 2330
Награды: 2
Репутация: 1094
Блокировки: | Цитата Duosora ( ) Это вновь предложение цикла, от которого я хочу уйти из-за случайного количества итераций в самом цикле. Это говорит уже само понятие "каждый раз". Но за попытку благодарочка плюсом)
Можно сделать ограниченное кол-во итераций. Скажем, разделить главную область на, скажем. 12 областей (главное, чтобы хотя бы одна не входила в область S,W итд), которые полностью покрывают главную область. Затем в каждой из области создавать случайную точку и пихать в массив, если она удовлетворяет начальным условиям. Затем из этого массива выбирать случайную точку..
|
| |
|
|
| VladSekret | Дата: Среда, 04 Марта 2015, 21:41:29 | Сообщение # 15 |
6 уровень
Группа: Проверенные
Сообщений: 198
Награды: 0
Репутация: -50
Блокировки: | Цитата Duosora ( ) Требуется, не используя циклов, сгенерировать случайную точку в области R, которая бы не находилась ни в области S, ни в области Т, ни в области U, ни в области V, ни в области W.
Ты что-то имеешь против циклов? 
Сообщение отредактировал VladSekret - Среда, 04 Марта 2015, 21:44:13 |
| |
|
|
| Duosora | Дата: Четверг, 05 Марта 2015, 09:33:26 | Сообщение # 16 |
|
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки: | Цитата VladSekret ( ) Ты что-то имеешь против циклов? B)
Смотря как, где и для чего используются.
Конкретно здесь...
Цитата Duosora ( ) цикла, от которого я хочу уйти из-за случайного количества итераций в самом цикле.
Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
|
| |
|
|
| Melodia | Дата: Суббота, 07 Марта 2015, 10:14:15 | Сообщение # 17 |
Группа: Проверенные
Сообщений: 8026
Награды: 5
Репутация: 5041
Блокировки: | Создаём юнит ЮНИТ в области R.
Событие ЮНИТ входит в области S T U W
Действие - б.е. - двинуть юнит в случайную точку в регионе R
Установить ТОЧКА - позиция ЮНИТа.Добавлено (05 Марта 2015, 11:34:53)
---------------------------------------------
Если кто не понял. Вводим непустое сообщение и наблюдаем Добавлено (07 Марта 2015, 10:14:15)
---------------------------------------------
че не доехало чтоль?
Ну дуос ты даёшь.
|
| |
|
|
| Bibo | Дата: Суббота, 07 Марта 2015, 19:05:42 | Сообщение # 18 |
Группа: Проверенные
Сообщений: 741
Награды: 0
Блокировки: | Самый простой:
Получить случайную точку, проверить ее принадлежность недопустимым областям, в случае совпадения - сдвинуть в случайном направлении к краю (или как душе угодно).
Минус:
В случае возможности нахлеста одной недопустимой области на другую(либо их плотного стыка), после сдвига в случайном направлении, придется снова проверять точку на вхождение, что приводит к заявленной проблеме циклов.
Тяжелый вариант:
Исходить из набора допустимых областей. Сразу за появлением новой недопустимой области, произвести расчет нового набора допустимых областей, создав его триггерно и уничтожив старый набор. После чего выбрать случайную область из набора допустимых и уже затем точку внутри выбранной области.
Ну и третий вариант:
Разделить большую область R на множество очень маленьких, определить в массив допустимых областей. Прямоугольники же T, S, U, V и W удалять из массива допустимых областей R.
Сообщение отредактировал Bibo - Суббота, 07 Марта 2015, 19:09:07 |
| |
|
|
| SirNikolas | Дата: Вторник, 10 Марта 2015, 17:44:41 | Сообщение # 19 |
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки: | Прагматичный ответ: ключевые слова в вопросе - "своими размерами намного меньше области R", а так как областей всего пять, ими можно пренебречь. Посчитай мат. ожидание геометрического распределения при p = 1 - μ(S ∪ T ∪ U ∪ V ∪ W) / μ(R). Графики справа показывают, что даже при p = 50% вероятность получить шесть итераций ничтожно мала.
Математическое решение: пусть у нас есть множество доступных областей, изначально включающее только область R. При "вырезании" каждой из областей S, T, U, V, W проделаем следующее: "разрежем" каждую область из множества доступных по четырем прямым, совпадающим со сторонами текущей области, и удалим те, которые попали "в середину".
Затем подсчитаем площадь каждой получившейся части и заполним массив частичных сумм: a[0] = 0; a[i] = a[i - 1] + (площадь i-той части). Сгенерируем случайное число x = random(0, a[n]). Бинарным поиском найдем элемент a[i], в котором находится x: a[i - 1] < x ≤ a[i]. Теперь мы знаем i ∈ 1, n - индекс части, выбранной наугад со "справедливой" (т. е. зависящей от площади) вероятностью. Бросаем в нее точку.
В этом решении наибольшая часть времени тратится на составление массива частей, то есть оно будет эффективным, если области двигаются значительно реже, чем бросаются точки.
|
| |
|
|
|
|
 |
|
 |
|
|
