Название: Расстановка книг Отправлено: Илья от Май 16, 2010, 15:49:27 1.На полке в библиотеке n книг. За один шаг можно любую книгу поставить на любое место. За какое минимальное количество шагов можно гарантированно расставить книги по порядку.
2. Задание такое же, как и в первой задаче, но за один шаг можно только поменять любые две книги местами. Название: Re: Расстановка книг Отправлено: Redirect от Май 16, 2010, 15:57:17 Я писал уже такую
Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 15:58:28 Я писал уже такую Хм, поиск выдал только мою задачу.Название: Re: Расстановка книг Отправлено: Валерий от Май 16, 2010, 16:05:47 Во 2-й можно только 2 соседние менять?
Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 16:06:35 Во 2-й можно только 2 соседние менять? Да.Название: Re: Расстановка книг Отправлено: Redirect от Май 16, 2010, 16:28:29 Библиотека (http://nazva.net/forum/index.php/topic,3133.0.html) Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 16:33:05 У меня задачи обобщены для любых n. К тому же в первой задаче у меня разрешается переставлять только одну книгу.
Название: Re: Расстановка книг Отправлено: Redirect от Май 16, 2010, 16:38:53 Решить для 1000 - решишь и для n
Название: Re: Расстановка книг Отправлено: Валерий от Май 16, 2010, 16:53:23 Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 16:57:15 Первое верно, второе нет.
Название: Re: Расстановка книг Отправлено: Redirect от Май 16, 2010, 17:00:43 n-1 и там и там
Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 17:04:40 n-1 и там и там Верно.3. На полке расставлено в обратном порядке (реверсивная расстановка) 15 книг. За сколько шагов их можно расставить в правильном порядке, если за один шаг можно взять блок из нескольких подряд идущих книг и переставить его на другое место? Название: Re: Расстановка книг Отправлено: Валерий от Май 16, 2010, 17:13:24 К задаче №2. Если расклад: 9 8 7 6 5 4 3 2 1, а нужно 1 2 3 4 5 6 7 8 9, то переставляя 2 соседние книги за 8 ходов никак не получится.
Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 17:16:02 К задаче №2. Если расклад: 9 8 7 6 5 4 3 2 1, а нужно 1 2 3 4 5 6 7 8 9, то переставляя 2 соседние книги за 8 ходов никак не получится. В условии сказано про любые две. А я, отвечая на ваш вопрос, про соседние и не заметил. :tormoz:Название: Re: Расстановка книг Отправлено: Валерий от Май 16, 2010, 17:18:08 Понял. Тогда 1-я и 2-я, это одна и та же задача.
Название: Re: Расстановка книг Отправлено: Redirect от Май 16, 2010, 17:27:41 (n-1) / 2
Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 17:34:33 (n-1) / 2 Хех, а доказательство?Название: Re: Расстановка книг Отправлено: Валерий от Май 16, 2010, 17:35:36 3. По 1-й книге можно переставлять?
Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 17:48:34 3. По 1-й книге можно переставлять? Нет, иначе это была бы аналогичная задача. :)Название: Re: Расстановка книг Отправлено: Redirect от Май 16, 2010, 17:52:31 Логически, я не умею доказывать такие :D Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 17:54:51 Цитировать Логически, я не умею доказывать такие Так зачем логически? Ты примером докажи. 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 У тебя по твоей формуле получается 7 шагов. Как будешь действовать? Название: Re: Расстановка книг Отправлено: Redirect от Май 16, 2010, 17:59:39 Тогда тоже n-1 получается :) Перетаскивание блоками ничего не дает
Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 21:42:30 Тогда тоже n-1 получается :) Перетаскивание блоками ничего не дает Это неверно.Название: Re: Расстановка книг Отправлено: Smith от Май 16, 2010, 22:01:41 Илья, условие не совсем понятно.
к примеру, берем блок 14-1, переворачиваем и ставим перед 15. один шаг? Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 22:02:46 Илья, условие не совсем понятно. Блоки переворачивать нельзя, только переставлять.к примеру, берем блок 14-1, переворачиваем и ставим перед 15. один шаг? Название: Re: Расстановка книг Отправлено: Smith от Май 16, 2010, 22:08:19 а можно, к примеру, 4321 переставить как 3421?
Название: Re: Расстановка книг Отправлено: buka от Май 16, 2010, 22:11:07 Тогда тоже n-1 получается :) Перетаскивание блоками ничего не дает Это неверно.Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 22:39:26 а можно, к примеру, 4321 переставить как 3421? Нет, можно 4321, переставить, как 4321.Название: Re: Расстановка книг Отправлено: Smith от Май 16, 2010, 22:41:38 а можно, к примеру, 4321 переставить как 3421? Нет, можно 4321, переставить, как 4321.Название: Re: Расстановка книг Отправлено: Smith от Май 16, 2010, 22:47:08 Илья, серьезно, не очень понятно условие.. да еще ты намутил слегка в прошлом посте - вообще запутал.. :roll:
Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 22:48:30 Илья, серьезно, не очень понятно условие.. да еще ты намутил слегка в прошлом посте - вообще запутал.. :roll: Так что ты имел в виду? Я понял, что блок 4321, если его взял, то так и переставил.Название: Re: Расстановка книг Отправлено: Smith от Май 16, 2010, 22:54:18 я тоже намутил, там можно было просто 4 перенести...
имелось ввиду: можно ли разделять блок, помещая между цифрами за один ход? к примеру: берем 234 из 234567 и размещаем между 567 как 253647? Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 23:03:01 Так нельзя. Можно так 789101112, переставили и получили: 10-11-12-7-8-9
Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 23:16:11 Скажу так, решение есть и оно меньше n-1, в данном случае 15-1. Думаем господа, думаем. :think:
Название: Re: Расстановка книг Отправлено: Smith от Май 16, 2010, 23:19:11 Так зачем логически? Ты примером докажи. в этом случае получается n-1, и этот случай представляется худшим вариантом. в остальных возможно меньшее к-во перестановок15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 23:20:29 Цитировать в этом случае получается n-1, и этот случай представляется худшим вариантом. в остальных возможно меньшее к-во перестановок Можно меньше. :read:Название: Re: Расстановка книг Отправлено: Redirect от Май 16, 2010, 23:39:44 (n+1) / 2 !!!!
Название: Re: Расстановка книг Отправлено: Redirect от Май 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 Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 23:47:48 Браво, Редирект. :bravo2:
О чем и шла речь. :) Название: Re: Расстановка книг Отправлено: Redirect от Май 16, 2010, 23:48:11 Это убило 3 листка А4 пока не заметил такого "приема" ))
Название: Re: Расстановка книг Отправлено: Илья от Май 16, 2010, 23:49:27 Это убило 3 листка А4 пока не заметил такого "приема" )) У меня на радиакт. шары 2 из 22 за 8 измерений ушло сегодня по меньшей мере 5 листов. Решение так и не нашел. :wall:Название: Re: Расстановка книг Отправлено: Smith от Май 16, 2010, 23:50:40 а формула справедлива для всех n или только для нечетных?
Название: Re: Расстановка книг Отправлено: buka от Май 17, 2010, 01:16:16 Это убило 3 листка А4 пока не заметил такого "приема" )) У меня на радиакт. шары 2 из 22 за 8 измерений ушло сегодня по меньшей мере 5 листов. Решение так и не нашел. :wall:Уж не помню точно, но там надо с перекрытием. Название: Re: Расстановка книг Отправлено: Илья от Май 17, 2010, 12:11:27 а формула справедлива для всех n или только для нечетных? А для этого у меня есть 4-ая задача:4. Дать любую оценку вида aN, a<1 на количество шагов достаточных для приведения любой расстановки из N книг к правильной, если за один шаг можно взять блок из нескольких подряд идущих книг и переставить его на другое место. P.S. Только ответа нет. :) Название: Re: Расстановка книг Отправлено: Redirect от Май 17, 2010, 13:42:00 Что значит aN ?
Название: Re: Расстановка книг Отправлено: Илья от Май 17, 2010, 13:46:57 Что значит aN ? Оценка, например для N=15, а будет составлять 0,53, тогда 15*0,53=7,95, округляем и получаем 8 шагов.Название: Re: Расстановка книг Отправлено: Redirect от Май 17, 2010, 14:04:54 Хз, не моё :D
|