Приветствую друзья.

Сегодня речь пойдет о перемешивании одномерно массива. Будем пользоваться Алгоритмом P, описанным Дональдом Кнутом (Искусство программирования. Том 2, с.163).

Для начала процитируем описание алгоритма.

Алгоритм P (Перемешивание). Пусть X1, X2, …, Xt – множество t чисел для перемешивания.

P1. “Инициализация”. Присвоить j <- t.

P2. “Генерация U”. Генерировать случайное число U, равномерно распределенное между 0 и 1.

P3. “Замена”. Присвоить j <- round(j*U) + 1, где round() – операция округления до целого числа. Заменим Xk <-> Xj.

P4. “Уменьшение j”. Уменьшить j на 1. Если j>1, возвратиться к шагу P2.

Задача: Ползут три черепахи. Первая черепаха знает, что впереди никого, сзади две. Вторая – одна впереди, одна сзади. Третья – одна сзади, другая впереди.
Вопрос: Как должны располагаться черепахи?