Страниц: 1 2 [3] 4
  Печать  
Автор Тема: Расстановка книг  (Прочитано 13906 раз)
0 Пользователей и 1 Гость смотрят эту тему.

1.На полке в библиотеке n книг. За один шаг можно любую книгу поставить на любое место. За какое минимальное количество шагов можно гарантированно расставить книги по порядку.
2. Задание такое  же, как и в первой задаче, но за один шаг можно только поменять любые две книги местами.

Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #30 : Май 16, 2010, 22:48:30 �

Илья, серьезно, не очень понятно условие.. да еще ты намутил слегка в прошлом посте - вообще запутал.. Roll Eyes
Так что ты имел в виду? Я понял, что блок 4321, если его взял, то так и переставил.
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #31 : Май 16, 2010, 22:54:18 �

я тоже намутил, там можно было просто 4 перенести...
имелось ввиду: можно ли разделять блок, помещая между цифрами за один ход? к примеру:
берем 234 из 234567 и размещаем между 567 как 253647?
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #32 : Май 16, 2010, 23:03:01 �

Так нельзя. Можно так 789101112, переставили и получили: 10-11-12-7-8-9
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #33 : Май 16, 2010, 23:16:11 �

Скажу так, решение есть и оно меньше n-1, в данном случае 15-1. Думаем господа, думаем. Думаю
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Smith
Из мудрейших мудрейший
**
Offline 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 Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #35 : Май 16, 2010, 23:20:29 �

Цитировать
в этом случае получается n-1, и этот случай представляется худшим вариантом. в остальных возможно меньшее к-во перестановок
Можно меньше. Чтение
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Redirect
Гений-Говорун
*
Offline Offline

Сообщений: 1472

СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214


Is it cocktail hour yet?

497367901
Просмотр профиля
Ответ #36 : Май 16, 2010, 23:39:44 �

(n+1) / 2 !!!!
Записан

Когда деревья были большими,
Папа - самый сильный, мама - самая красивая,
Я верил этим книгам, фильмам,
И думал никогда курить не буду, даже с фильтром.
Не буду пить, чтоб не расстраивать мать
Буду учиться на пять, чтобы всё узнать.
Redirect
Гений-Говорун
*
Offline Offline

Сообщений: 1472

СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214


Is it cocktail hour yet?

497367901
Просмотр профиля
Ответ #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

Эти пользователи сказали вам СПАСИБО :

Илья

За это сообщение 1 пользователь сказал спасибо!
Записан

Когда деревья были большими,
Папа - самый сильный, мама - самая красивая,
Я верил этим книгам, фильмам,
И думал никогда курить не буду, даже с фильтром.
Не буду пить, чтоб не расстраивать мать
Буду учиться на пять, чтобы всё узнать.
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #38 : Май 16, 2010, 23:47:48 �

Браво, Редирект. Браво
О чем и шла речь. Smiley
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Redirect
Гений-Говорун
*
Offline Offline

Сообщений: 1472

СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214


Is it cocktail hour yet?

497367901
Просмотр профиля
Ответ #39 : Май 16, 2010, 23:48:11 �

Это убило 3 листка А4 пока не заметил такого "приема" ))
Записан

Когда деревья были большими,
Папа - самый сильный, мама - самая красивая,
Я верил этим книгам, фильмам,
И думал никогда курить не буду, даже с фильтром.
Не буду пить, чтоб не расстраивать мать
Буду учиться на пять, чтобы всё узнать.
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #40 : Май 16, 2010, 23:49:27 �

Это убило 3 листка А4 пока не заметил такого "приема" ))
У меня на радиакт. шары 2 из 22 за 8 измерений ушло сегодня по меньшей мере 5 листов. Решение так и не нашел. Стена
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #41 : Май 16, 2010, 23:50:40 �

а формула справедлива для всех n или только для нечетных?
Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #42 : Май 17, 2010, 01:16:16 �

Это убило 3 листка А4 пока не заметил такого "приема" ))
У меня на радиакт. шары 2 из 22 за 8 измерений ушло сегодня по меньшей мере 5 листов. Решение так и не нашел. Стена
В своё время я получил решение для 2 из 22 за 8, но оно совсем трюкастое...
Уж не помню точно, но там надо с перекрытием.
Записан
Илья
Высший разум
*****
Offline Offline

Сообщений: 7695

СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030


Терпение, мой друг, терпение...


Просмотр профиля
Ответ #43 : Май 17, 2010, 12:11:27 �

а формула справедлива для всех n или только для нечетных?
А для этого у меня есть 4-ая задача:
4. Дать любую оценку вида aN, a<1 на количество шагов достаточных для приведения любой расстановки из N книг к правильной, если за один шаг можно взять блок из нескольких подряд идущих книг и переставить его на другое место.
P.S. Только ответа нет. Smiley
Записан

Рост воровства у нас  неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
Redirect
Гений-Говорун
*
Offline Offline

Сообщений: 1472

СПАСИБО
-вы поблагодарили: 108
-вас поблагодарили: 214


Is it cocktail hour yet?

497367901
Просмотр профиля
Ответ #44 : Май 17, 2010, 13:42:00 �

Что значит aN ?
Записан

Когда деревья были большими,
Папа - самый сильный, мама - самая красивая,
Я верил этим книгам, фильмам,
И думал никогда курить не буду, даже с фильтром.
Не буду пить, чтоб не расстраивать мать
Буду учиться на пять, чтобы всё узнать.
Страниц: 1 2 [3] 4
  Печать  
 
Перейти в: