Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 15.10.2011, 17:12   #1
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,934 пользователей)
Выбор из множества

Задача:
Есть набор элементов (дискретное, конечное множество).
Как реализовать функцию выбора (с возвращением) произвольного элемента таким образом, чтобы два идущих подряд выбора никогда не давали одинаковый результат.
Пример:
Множество {1,2,3,4,5}.
Допустимая генерация: 1,5,3,2,3,1,2,1,2,1,2
Недопустимая генерация 1,3,4,2,5,5
Демо для экспериментов:
Const Size%=3
Dim Vector(Size)
For i=1 To Size
	Vector(i)=i
Next

Global LI=0

While True
	Local k%=WaitKey()
	If Chr(k)="1" Then Exit
	;=
	ТуДу: инсёрт йо код хир
	;=
	Print Vector(LI)
Wend
End
Решение, которым многие не брезгуют:
Local newLI%=LI
	While newLI=LI
		newLI=Rand(1,Size)
	Wend
	LI=newLI
А именно:
1. сгенерить новый индекс
2. если новый совпадает со старым, гото 1
3. готово
Решение имеет уйму минусов:
1. непредсказуемое время исполнения при одинаковых входных данных
2. потенциально бесконечное время выполнения

Мой вариант решения:
Const Size%=3
Dim Vector(Size)
For i=1 To Size
	Vector(i)=i
Next

Global LI=0

While True
	Local k%=WaitKey()
	If Chr(k)="1" Then Exit
	;=
	If LI=0
		LI=Rand(1,Size)
	Else
		LI=((LI+Rand(1,Size-1)-1) Mod Size)+1
	EndIf
	;=
	Print Vector(LI)
Wend
End
При первом запросе (LI=0) мы можем выбрать любой элемент (Rand(1,Size)). При последующих обращениях у нас N-1 элементов для выбора. Логика следующая.
1) Закольцовываем индексацию элементов при помощи взятия остатка от деления:
было: 1 2 3 4 5
стало: 1 2 3 4 5 1 2 3 4 5
Mod Size
2) Чтобы исключить выбранный ранее элемент, новый будем находить как стоящий от уже выбранного на X элементов.
LI+Rand
3) Пусть X не отрицательный: мы уже реализовали цикличность и, потому, отрицательное отклонение реализуется большим положительным (Если долго двигаться по направлению от нулевого меридиана, то попадёте в него).
4) Нулевой X не подходит, т.к. результат будет соотвествовать уже выбранному элементу.
LI+Rand(1,
5) Сдвиг на длину всего набора не подходит, т.к.
а) за счёт кольца эквивалентен сдвигу на ноль (см. п. 4)
б) логично, что для выбора всегда (кроме первого раза) доступно N-1 элементов.
LI+Rand(1,Size-1)
6) Если мы будем подавать на MOD числа от 1 до N, то с выхода будем снимать числа от 0 до N-1, что нарушит логику индексации, сдвинув диапазон:
-> 1 2 3 4 5 6 7 8 9 10
<- 1 2 3 4 0 1 2 3 4 0
LI+Rand(1,Size-1)-1
7) Однако, мы имеем индексацию с единицы, а формула - с 0:
-> 1 2 3 4 5 6 7 8 9 10
= 0 1 2 3 4 5 6 7 8 9
<- 0 1 2 3 4 0 1 2 3 4
Необходимо повторно скорректировать результат:
((LI+Rand(1,Size-1)-1) Mod Size)+1
8) Итоговая формула:
LI=((LI+Rand(1,Size-1)-1) Mod Size)+1

ЗЫЖ
Можно переписать блок, используя формулу и для случая первого обращения:
LI=((LI+Rand(1,Size-COND)-1) Mod Size)+1
COND должен быть равен нулю при первом обращении, и единице - при последующих. Кроме того потребуется всё равно сгенерить значение якобы прошлого состояния индекса. Такой подход даст больше мозголомства и тормозов (на выполнении), чем позволит выиграть в количестве строк кода.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?

Последний раз редактировалось impersonalis, 15.10.2011 в 18:25.
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо impersonalis за это полезное сообщение:
genroelgvozo (15.10.2011), SBJoker (15.10.2011)
Старый 15.10.2011, 21:04   #2
dsd
Мастер
 
Аватар для dsd
 
Регистрация: 13.06.2011
Сообщений: 1,103
Написано 481 полезных сообщений
(для 1,836 пользователей)
Ответ: Выбор из множества

1.создаем массив из (n-1) элементов, где n-кол-во элементов в множестве.
2.размещаем в массиве элементры множества.
3.генерируем случайное целое число от 0 по (n-2) включительно.
4.выдаем на вывод элемент лежащий в ячейке массива с выпавшим индексом.
5.запоминаем выданный элемент
6.пишем в эту ячейку элемент множества не влезший в массив, а запомненный на место не влезшего
п.3-п6 в цикл
Профит?
Можно в принципе просто выпавший элемент менять местом с последним в множестве, а последний просто не выбирать
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
impersonalis (15.10.2011)
Старый 15.10.2011, 21:15   #3
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,934 пользователей)
Ответ: Выбор из множества

Занятно.
У моего зато вектор const
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Старый 15.10.2011, 21:44   #4
dsd
Мастер
 
Аватар для dsd
 
Регистрация: 13.06.2011
Сообщений: 1,103
Написано 481 полезных сообщений
(для 1,836 пользователей)
Ответ: Выбор из множества

Можно еще запоминать индекс выпавшего элемента.
если индекс предыдущего и выпавшего равны то если индекс выпавший не равен последнему элементу индекс выпавшего ++ иначе индекс выпавшего --.
Сорри за троллинг
(Offline)
 
Ответить с цитированием
Старый 03.11.2011, 14:23   #5
Aikon
ПроЭктировщик
 
Регистрация: 12.02.2011
Сообщений: 131
Написано 23 полезных сообщений
(для 52 пользователей)
Ответ: Выбор из множества

impersonalis, если смущает бесконечное время выполнение, то можно допилить так
	Local newLI% = LI
	newLI = Rand(1,Size)
	If newLI = LI Then
		newLI = (LI + 3) % Size
	LI=newLI
Т.е при попадании на повторный элемент будет выбран элемент, который отстоит от этого на заданное число элементов.
P.S. dsd это и написал Перечитал и твой пост подробнее - нафига вместо 3 использовать rand не сильно понятно, поскольку величина все равно псевдо-случайная получается.

Как вариант, еще можно нагенерить случайную последовательность при старте в массив каким удобно способом, а потом ее уже использовать - будет быстро и с каким угодно распределением.
(Offline)
 
Ответить с цитированием
Старый 03.11.2011, 14:59   #6
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,934 пользователей)
Ответ: Выбор из множества

Дорогой, Aikon, очень приятно, что ты осилил мой пост и даже предложил своё решние
Const Size%=3
Dim Vector(Size)
For i=1 To Size
Vector(i)=i
Next

Global LI=0

While True
Local k%=WaitKey()
If Chr(k)="1" Then Exit
;=
If LI=0
LI=Rand(1,Size)
Else
Local newLI% = LI
newLI = Rand(1,Size)
If newLI = LI Then
newLI = (LI + 3) Mod Size
LI=newLI
EndIf
EndIf
;=
Print Vector(LI)
Wend
End

которое, к сожалению, выдаёт следующий ряд 22222222222222222222222222222222222222222222222222 222222222
Угадай: почему? Уж не из-за отсутствия "нафиг" ненужного рнд? Хотя прибавка размера (+3) тоже сильно "помогает".

Что касается предложения dsd (последнего, на которое ты сослался), то, такой механизм:
1) работает (опять-таки) разное время
2) потащит за собой дополнительные проверки на выход за границы массива
3) увеличивает вероятность выпадания одного из элементов на P`=1/(N-1), повышая тем самым автокорреляцию распределения.
4) при этом выгоды (перевешивающей п.1-3) я не вижу чего-то
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 16:42.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com