1.На полке в библиотеке n книг. За один шаг можно любую книгу поставить на любое место. За какое минимальное количество шагов можно гарантированно расставить книги по порядку.
2. Задание такое же, как и в первой задаче, но за один шаг можно только поменять любые две книги местами.
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #30 : Май 16, 2010, 22:48:30 � |
|
Илья, серьезно, не очень понятно условие.. да еще ты намутил слегка в прошлом посте - вообще запутал.. Так что ты имел в виду? Я понял, что блок 4321, если его взял, то так и переставил.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
Smith
Из мудрейших мудрейший
Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305
PeAcE
|
|
� Ответ #31 : Май 16, 2010, 22:54:18 � |
|
я тоже намутил, там можно было просто 4 перенести... имелось ввиду: можно ли разделять блок, помещая между цифрами за один ход? к примеру: берем 234 из 234567 и размещаем между 567 как 253647?
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #32 : Май 16, 2010, 23:03:01 � |
|
Так нельзя. Можно так 789101112, переставили и получили: 10-11-12-7-8-9
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #33 : Май 16, 2010, 23:16:11 � |
|
Скажу так, решение есть и оно меньше n-1, в данном случае 15-1. Думаем господа, думаем.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
Smith
Из мудрейших мудрейший
Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305
PeAcE
|
|
� Ответ #34 : Май 16, 2010, 23:19:11 � |
|
Так зачем логически? Ты примером докажи. 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
в этом случае получается n-1, и этот случай представляется худшим вариантом. в остальных возможно меньшее к-во перестановок
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #35 : Май 16, 2010, 23:20:29 � |
|
в этом случае получается n-1, и этот случай представляется худшим вариантом. в остальных возможно меньшее к-во перестановок Можно меньше.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
Redirect
Гений-Говорун
Offline
Сообщений: 1472
СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214
Is it cocktail hour yet?
|
|
� Ответ #36 : Май 16, 2010, 23:39:44 � |
|
(n+1) / 2 !!!!
|
|
|
Записан
|
Когда деревья были большими, Папа - самый сильный, мама - самая красивая, Я верил этим книгам, фильмам, И думал никогда курить не буду, даже с фильтром. Не буду пить, чтоб не расстраивать мать Буду учиться на пять, чтобы всё узнать.
|
|
|
Redirect
Гений-Говорун
Offline
Сообщений: 1472
СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214
Is it cocktail hour yet?
|
|
� Ответ #37 : Май 16, 2010, 23:41:41 � |
|
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
8 7 6 5 4 3 2 15 14 13 12 11 10 9 1
8 7 6 5 4 3 14 13 12 11 10 9 1 2 15
8 7 6 5 4 13 12 11 10 9 1 2 3 14 15
8 7 6 5 12 11 10 9 1 2 3 4 13 14 15
8 7 6 11 10 9 1 2 3 4 5 12 13 14 15
8 7 10 9 1 2 3 4 5 6 11 12 13 14 15
8 9 1 2 3 4 5 6 7 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|
Когда деревья были большими, Папа - самый сильный, мама - самая красивая, Я верил этим книгам, фильмам, И думал никогда курить не буду, даже с фильтром. Не буду пить, чтоб не расстраивать мать Буду учиться на пять, чтобы всё узнать.
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #38 : Май 16, 2010, 23:47:48 � |
|
Браво, Редирект. О чем и шла речь.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
Redirect
Гений-Говорун
Offline
Сообщений: 1472
СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214
Is it cocktail hour yet?
|
|
� Ответ #39 : Май 16, 2010, 23:48:11 � |
|
Это убило 3 листка А4 пока не заметил такого "приема" ))
|
|
|
Записан
|
Когда деревья были большими, Папа - самый сильный, мама - самая красивая, Я верил этим книгам, фильмам, И думал никогда курить не буду, даже с фильтром. Не буду пить, чтоб не расстраивать мать Буду учиться на пять, чтобы всё узнать.
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #40 : Май 16, 2010, 23:49:27 � |
|
Это убило 3 листка А4 пока не заметил такого "приема" ))
У меня на радиакт. шары 2 из 22 за 8 измерений ушло сегодня по меньшей мере 5 листов. Решение так и не нашел.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
Smith
Из мудрейших мудрейший
Offline
Сообщений: 2950
СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305
PeAcE
|
|
� Ответ #41 : Май 16, 2010, 23:50:40 � |
|
а формула справедлива для всех n или только для нечетных?
|
|
|
Записан
|
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #42 : Май 17, 2010, 01:16:16 � |
|
Это убило 3 листка А4 пока не заметил такого "приема" ))
У меня на радиакт. шары 2 из 22 за 8 измерений ушло сегодня по меньшей мере 5 листов. Решение так и не нашел. В своё время я получил решение для 2 из 22 за 8, но оно совсем трюкастое... Уж не помню точно, но там надо с перекрытием.
|
|
|
Записан
|
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #43 : Май 17, 2010, 12:11:27 � |
|
а формула справедлива для всех n или только для нечетных?
А для этого у меня есть 4-ая задача: 4. Дать любую оценку вида aN, a<1 на количество шагов достаточных для приведения любой расстановки из N книг к правильной, если за один шаг можно взять блок из нескольких подряд идущих книг и переставить его на другое место. P.S. Только ответа нет.
|
|
|
Записан
|
Рост воровства у нас неудержим, И мы кривою роста дорожим: Раз все воруют, значит, все при деле! На этом-то и держится режим!
|
|
|
Redirect
Гений-Говорун
Offline
Сообщений: 1472
СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214
Is it cocktail hour yet?
|
|
� Ответ #44 : Май 17, 2010, 13:42:00 � |
|
Что значит aN ?
|
|
|
Записан
|
Когда деревья были большими, Папа - самый сильный, мама - самая красивая, Я верил этим книгам, фильмам, И думал никогда курить не буду, даже с фильтром. Не буду пить, чтоб не расстраивать мать Буду учиться на пять, чтобы всё узнать.
|
|
|
|