Упорядочить вслепую.

[nikvic]

В восьми нумерованных ящиках расположены гирьки разного веса. Их требуется расположить по возрастанию веса, использую глупого робота.
Ему можно указать пару номеров, и он поменяет две гирьки местами, если они нарушают порядок.

Каково минимальное число команд, гарантирующее результат?

Умею за 22

[arseniiv]

А сколько нужно таких обменов-или-нет $A_n$, чтобы левую половину из $2n$ элементов сделать не больше, чем правую? Тогда можно за $A_4 + 2A_2 + 4A_1$ шагов решить эту задачу.

[nikvic]

Не понял, кто у Вас есть кто.

[arseniiv]

Пускай мы вашим способом можем сделать левую половину какой-то последовательности из $2n$ гирек не меньше правой за $A_n$ команд роботу и т. д.. Формула $A_4 + 2A_2 + 4A_1$ означает, что надо сначала накопить в одной половине меньшие, а в другой большие, а потом проделать аналогичное с четвертями и восьмыми. Должно же отсортировать. Только не знаю, можно ли взять меньше. Да и числа надо найти. Ясно, что $A_1 = 1$, а вот $A_2 = 4$?

[nikvic]

А как накопить слева меньшие?

[arseniiv]

Обменами гирек из одной половины с гирьками из другой. Если всего две гири, нужен один обмен. Если по две — то, вроде, четыре. (Пусть 4 гирьки пронумерованы как 1—4. Тогда обменами 13, 14, 23, 24 гирьки правой половины станут не легче гирек левой.) Дальше не считал.

Если моя формула даёт минимум, а ваш алгоритм правильный, то $4 + 8 + A_4 \leqslant 22$, и $A_4 \leqslant 10$. Боюсь, минимума она не даёт.

[BatMan]

21

[nikvic]

А как?

[arseniiv]

А мне 22 интересно!

[venco]

19

[nikvic]

Ого!
Но без последовательности пар чисел - несчитово

[venco]

[Urnwestek]

venco Чётно-нечётная сеть Батчера кажись? (:

[BatMan]

нашел 2 лишних сравнения)

[Urnwestek]

BatMan в сообщении #803344 писал(а):

нашел 2 лишних сравнения)

Клёво, можете эмейл Кнуту послать. Он вам за это 5$, вроде как, должен переслать назад.