Нa полке в беспорядке стоит 100-томная энциклопедия, один из томов которой — в красном переплете. Красный том можно поменять местами с любым другим. Какого наименьшего количества таких обменов заведомо хватит, чтобы расставить тома по порядку?

не знаю, сколько обменов, но водка точно подорожает...

(1) Страшно жить...

200?

(3) не

9.332622e+157

100, если красный изначально на своем месте, 99, если не на своем

видимо из текста неочевидно, но менять можно только красный том!

(0) зачем в условии красный том?

а, я знаю, именно в красном томе энциклопедии спрятан глубокий смысл

мб 50?

(0) 100*log2(100)

определяем, на каком месте стоит красный, ищем том с этого места, меняем..... по сути нужно 99 перестановок, но, в какой-то момент красный станет на свое место, а сортировка еще не будет закончена, по этому понадобиться одна промежуточная перестановка, то есть 100 ))))

Ну если совсем идеальная ситуация, то 0, ибо вдруг все тома на своих местах стоят..

(12) да, в (6) не подумал, что он в процессе может всать на свое место. 100

Да вы чо, какой 100?
Представьте ряд
1.7.85.56.3.54.32.....100.83.2
А меняете местами только 2 тома одновременно

(15) представил :)
За одну перестановку мы ставим на место 1 том. Далее см. (12)

(16) за первую перестановку мы ставим на первое место красный том, потом меняем его с томом 1, потом на второй том, меняем его с томом 2 и тд

200

ток позицию красного надо учесть потом в пропуске 199 или 198, лень думать

Худший случай когда тома образуют цикл длиной 1.
например 2.1.4.3.6.5
Чтобы переставить цикл в правильной порядке требуется 3 обмена
Ответ думаю 300

(17) Зачем так сложно? Меняем красный том с тем томом, на месте которого красный том сейчас стоит и всё. 100 обменов в самом худшем случае.

(20) Возможно, я что-то делаю не так, но эту цепочку можно отсортировать за 7 ходов. Если предположить, что красный том 1, то получаем картинку:
2.5.4.3.6.1
2.5.4.3.1.6
2.1.4.3.5.6
1.2.4.3.5.6
3.2.4.1.5.6
3.2.1.4.5.6
1.2.3.4.5.6

+(20) циклов то 50, исключая цикл с красным томом, 49 * 3 + 1
Ответ 148

(16) в ходе перестановок красный может несколько раз попадать на своё место ((((
(21) Красный - один из.... пусть он будет тридцать третьим... и сейчас стоит на позиции 52, а том 52 стоит на позиции 33. Что делать после первой перестановки?

(20) допустим красный том имеет номер 57 стоит изначално на  позиции 56
Крас на 1 поз
Крас на 2 поз забрал 1 том
Крас на 56 поз забрал 2 том
Крас на 3 поз
Крас на 4 поз забрал 3 том
Крас на 56 поз забрал 4 том
Крас на 5 поз
Крас на 6 поз забрал 5 том
Крас на 56 забрал 6 том

Итого 9 ходов на 6 томов

(22)
За 6 ходов только, ровно по количеству томов.

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

если он находится в одном из мест в середине, то опять таки 0 перестановок в лучшем случае, и 99 в худшем.

Так что ответ 99.

(24) Ставим на любую позицию, например первую, и вперёд.

(22) Да, ошибка. 6 томов, 2 цикла, тогда 2* 3 + 1

(27) "Красный том можно поменять местами с любым другим." - чёрт. Не обязательно с ближайшим.

(28) на позиции 1 стоит том 15, на позиции 2 том 15, на позиции 15 том 2? )))))

(22) 6.5.3.2.4.1 ? как?

(31)
Как том 15 может стоять на 1 и 2 позициях одновременно? Даже если учесть, что на второй позиции стоит том 1, то просто выходим из цикла на любой другой том.
Видимо поболее 100 перестановок понадобится.

6.5.3.2.4.1
1.5.3.2.4.6
5.1.3.2.4.6
5.2.3.1.4.6
5.2.3.4.1.6
1.2.3.4.5.6

+25 правильно посчитал

Дано 214365....к....

1) к14365.....2....
2) 1к4365.....2....
3) 124365.....к....
4) 12к365.....4....
5) 123к65.....4....
6) 123465.....к....
7) 1234к5.....6....
8) 12345к.....6....
9) 123456.....к....

Предположу, что существует эффективная стратегия обмена.

Шаг1. Том стоит на месте 5 (слева от него 4 тома). Прыгаем на место, где стоит 5 том, а он идет на то место, где стоял красный том.

...

Шаг N. Том стоит на месте N (слева от него N-1 тома). Прыгаем на место, где стоит N том, а он идет на то место, где стоял красный том.

Всё равно 99 в худшем случае.

(Но я не доказал, что нет более эффективной стратегии)

(32) опечатался.... на позиции 1 - том 15, на позиции 2 - том 1, на позиции 15 - том 2. две перестановки и красный снова на своей позиции ((((

Меняем его с томом, который стоит на позиции 3 и поехали дальше.

(35) В худшем варианте всегда будем попадать на такие тройки, Итого 133 или около того перестановок?

(4) ну хорошо 99

(0) 243

(34) а чего тут доказывать, 99 минимум, так как вообще в худшем случае нужно 99 перестановок (не обязательно с красным)

50 ессно

Мнения разделились, но правильный ответ в теме прозвучал.
(40) если взять 3 тома, расставь 1,3,2 за 2 хода?)

(40) В том то и фишка, что менять можно только красный.
2 1 4 3 6 5 8 7 10 9
Пусть красным будет том 1.

2 1 4 3 6 5 8 7 10 9
1 2 4 3 6 5 8 7 10 9
4 2 1 3 6 5 8 7 10 9
4 2 3 1 6 5 8 7 10 9
1 2 3 4 6 5 8 7 10 9
6 2 3 4 1 5 8 7 10 9
6 2 3 4 5 1 8 7 10 9
1 2 3 4 5 6 8 7 10 9
8 2 3 4 5 6 1 7 10 9
8 2 3 4 5 6 7 1 10 9
1 2 3 4 5 6 7 8 10 9
10 2 3 4 5 6 7 8 1 9
10 2 3 4 5 6 7 8 9 1
1 2 3 4 5 6 7 8 9 10

13 перестановок для 10 томов.
133 для 100 томов.

n+(n-1)/3

(42) ага, правильный ответ таки в (6)

(45)
Расставь за 10 ходов:
2 1 4 3 6 5 8 7 10 9
Пусть красным будет том 1.

(44) вы же понимаете, что число перестановок должно быть целым?)

правильный ответ в (23), я в экселе по своей методе посчитал
(43) у тебя ошибка закралась где-то

(46) 4 цикла, получается 4*3 + 1 = 13
для 100 томов будет 148
(42) Колись, я прав?

Но это если ряд хаотичный.. Минимальное число перестановок 0 или 1

(49) осталось доказать, что "Худший случай когда тома образуют цикл длиной 1")

(49) Вернее цикл длиной 2.
1 случай: для цикла длиной 2 тома требуется 3 обмена
2 случай: для цикла длиной 3 тома требуется 4 обмена

Возьмем 6 томов, для 1 случая получим 9 перестановок, для 2 случая получим 8. 1 случай "хуже" 2 случая. Аналогично доказывается для остальных n

(52)
2 1 4 3 6 5
1 2 4 3 6 5
4 2 1 3 6 5
4 2 3 1 6 5
1 2 3 4 6 5
6 2 3 4 1 5
6 2 3 4 5 1
1 2 3 4 5 6

За 7 ходов 6 томов составил с циклами длиной 2.
Где ошибся?

7 томов за 9 ходов составляются, как раз под мою формулу подходит. 7+(7-1)/3=9
Для общего случая надо усовершенствовать формулу.
Например n+цел((n-1)/3)

(54) по вашей формуле для 4х томов получается 5 перестановок?

(55) Угу. А должно 4. Ну значит формула снова не совсем верная.

А 2 тома вообще за 1 перестановку можно переставить.

99

(58) Это было бы слишком просто

(57) 3*(n-1)/2+1

(59) причем нечетном n было бы интереснее

тьфу
3*цел((n/2)-1)+1

(51) а что доказывать? из каждого цикла нужно выходить, чем короче цикл, тем их больше.
((n / 2) - 1)) + n - 1
2 - количество томов в самом коротком из возможных циклов :)
Из последнего цикла специально выходить не нужно (-1), Нужно переставить все тома, за исключением красного, последней перестановкой он сам станет на место (-1)
(n / 2) - 2 + n
для n = 10 -> 13
для n = 100 -> 148

98