Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

перемешивание стека

race1 © (2004-11-07 14:45:00)
есть данные, хранящиеся в виде стека, т.е. каждый эл-т имеет указатель на пред. и след. эл-ты. как теперь можно эти эл-ты случайным образом переставить местами? т.е. была цепочка с данными 1->2->3->4, а сделать цепочку, например, такую: 3->1->2->4

KilkennyCat (2004-11-08 13:29:00) [1]

> race1 (08.11.04 13:17) [11]

что-то меня тут смущает...

race1 (2004-11-08 13:17:00) [2]
>palva
спасибо

вот и я тут ещё придумал - берём 1-ый эл-т нащего списка, генерим число i = 0..n, и делаем i шагов вправо. если список закончился, переходим в начало и продолжаем смещаться. если текущий эл-т уже добавлен в новый список, смещаемся вправо пока не найдём первый недобавленный эл-т. при нахождении нового эл-та добавляем его в конец нового списка. т.е. новый список формируется по-порядку, но эл-ты для него берутся случайным образом из исходного списка. в теории тоже достаточно быстрый метод

главное что не нужно промежуточных массивов - мы работаем со списком и формируем список "на лету"

Anatoly Podgoretsky (2004-11-08 00:30:00) [3]
race1 (07.11.04 17:08) [8]
Тогда все просто

это тебе учебное задание, сделай сам

palva (2004-11-08 00:06:00) [4]
Вы правы в своих расчетах. Причем для последних чисел потребуется много обращений к датчику, прежде чем они будут выбраны. Доработать можно тем способом, что хранить все НЕВЫБРАННЫЕ числа одним куском в памяти и генерировать индекс числа внутри этого куска. При этом отрезок генерации будет все время уменьшаться, сначала от 1 до n, затем от 1 до n-1 и т. д. В Delphi есть даже специальная функция для выбора случайного целого числа из диапазона. Правда, реализовать это без большого числа перестановок - не знаю как.

Возможен такой алгоритм, который я недавно предлагал на другом форуме.
http://www.relib.com/forums/topic.asp?id=842829
Там бейсик, но не думаю, что трудно разобраться. Это перемешивание последовательности 1..n. Идея такая: Сначала массив содержит последовательность от 1 до n. Основной цикл проходит с последнего элемента до второго (i := n downto 2) На каждом шаге цикла i-й элемент меняется местами с одним из предыдущих. Кандидат на перестановку выбирается случайным образом из диапазона 1..i, причем если получилось i, то перестановку, естественно, не делаем. Получается ровно n-1 обращений к случайному датчику.

race1 (2004-11-07 17:08:00) [5]
это не учебное задание :) учебные задания я обычно сам делаю

> palva
можно доработать: создать доп. массив уже используемых значений, и генерировать не смещение, а индекс, кугда переместить текущий эл-т. при генерации числа для след. эл-та смотрим массив, если сгенерированное число уже занято - генерируем другое число

правда, в этом случае диапозон генерирования всегда будет n для каждого эл-та и может потребовать значительного времени пока сгенерятся все числа из диапозона 0..n :)

как этот момент доработать?

KilkennyCat (2004-11-07 15:33:00) [6]

> Anatoly Podgoretsky © (07.11.04 15:31) [6]

тогда я - пас :) не люблю делать учебные задания.

Anatoly Podgoretsky (2004-11-07 15:31:00) [7]
Не проще, надо выполнять учебное задание.

KilkennyCat (2004-11-07 15:25:00) [8]

> palva © (07.11.04 15:10) [4]

в этом случае, если работать как со стеком, мы потеряем какой-нить элемент, если у нас будет только одна переменная. Соответственно, если у нас будет больше переменных, то проще не рассматривать работу аналогично стеку, а юзать массив.

palva (2004-11-07 15:10:00) [9]
А переставить можно следующим образом:
Берем первый элемент, порождаем целое случайное число s из диапазона 0..n и двигаем этот элемент вправо на s шагов. Потом берем следующий элемент, порождаем случайное число s из диапазона 0..n-1 и т.д. Если s = 0, то двигать, конечно, не надо.

KilkennyCat (2004-11-07 15:07:00) [10]
очень легко: записываем в него данные в нужном порядке.

palva (2004-11-07 15:05:00) [11]
А двунаправленный список

Anatoly Podgoretsky (2004-11-07 15:03:00) [12]
Вообще то это не стек.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »