Форум умных людей

Задачи и головоломки => Математические задачи => Тема начата: Илья от Май 16, 2010, 15:49:27



Название: Расстановка книг
Отправлено: Илья от Май 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.
а можно как 4321?  :D


Название: 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
Так зачем логически? Ты примером докажи.
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
в этом случае получается n-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:
В своё время я получил решение для 2 из 22 за 8, но оно совсем трюкастое...
Уж не помню точно, но там надо с перекрытием.


Название: 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