Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Перемешивание 
V
    Опции темы
Заппер
Дата 8.4.2006, 16:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 8.4.2006

Репутация: нет
Всего: нет
Мне кажется, можно предложить решение линейной сложности для этой задачи.
Вот оно:
массив[1..N]
...
цикл по i от 1 до N
массив[i] = массив[случайное(N-i)+i]
..,
где
Цитата
случайное(x)
- функция, выдающее случайное целое число от 1 до x-1. Отсутствие повторений чисел обеспечивает тот факт, что при каждом выборе мы сужаем рамки на 1, исключая уже выбранное на предыдущем шаге число.
PM MAIL   Вверх
esperant0
Дата 8.4.2006, 19:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14
Цитата(Заппер @ 8.4.2006, 16:49)
Мне кажется, можно предложить решение линейной сложности для этой задачи.
Вот оно:
    массив[1..N]
    ...
    цикл по i от 1 до N
        массив[i] = массив[случайное(N-i)+i]
    ..,
где
Цитата
случайное(x)
- функция, выдающее случайное целое число от 1 до x-1. Отсутствие повторений чисел обеспечивает тот факт, что при каждом выборе мы сужаем рамки на 1, исключая уже выбранное на предыдущем шаге число.

Линейные решения уже были приведены тут.

А вот ваше решение, не мешало бы обосновать. т.е доказать правильность


--------------------
 
 Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer 

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором  а затем стерто и которое он - пользователь не мог видеть. 
PM MAIL   Вверх
nostromo
Дата 9.4.2006, 15:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 194
Регистрация: 23.3.2006

Репутация: 5
Всего: 10
Цитата(maxim1000 @ 8.4.2006, 11:54)

1. вероятность каждой конкретной последовательности обменов равна 1/n^n
2. вероятность каждой конечной перестановки равна сумме вероятностей тех последовательностей обменов, которые к ней приводят
3. эта вероятность равна (должна быть равна) 1/n!
4. т.к. вероятности всех последовательностей обменов одинаковая, то 1/n!=k*1/n^n, где k - количество разных последовательностей обменов, приводящих к данной перестановке (целое)...


Согласен.
--------------------
На пыльных тропинках далеких планет останутся наши следы.
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0469 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.