Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Интересные и занимательные задачи по программированию > Комбинаторика - Задача верблюдов обратная

Автор: Domen 18.10.2009, 21:07

Доброе время дня и ночи!
Вот запутался с задачей очень нужна помощь. smile

Идут 9 верблюдов.
Сколько существует комбинаций перестановки верблюдов,при которых ни один не идет впереди того, впереди которого шел раньше.
Сначала я думал так что если впереди, значит запрещенные пары (2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,9)
Свойств 7. И формула будет 7!*C_7^1
_____________________
Но потом сообразил что получается я первую пару откинул, а ведь варианты тоже составляются и с ней.Тогда запрещенные пары (1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,8)(8,9)
Свойств 8. И формула 8!*C_8^1

Автор: Akina 18.10.2009, 21:31

Цитата(Domen @ 18.10.2009, 22:07

)

Сколько существует комбинаций перестановки верблюдов,при которых ни один не идет впереди того, впереди которого шел раньше.

Возьмём любую пару верблюдов. Если в первой расстановке верблюд А был впереди верблюда Б, то во второй расстановке верблюд А должен быть позади верблюда Б... а третьей расстановки не может быть вообще. Итого 2 расстановки.
Если же "впереди" трактовать как "непосредственно впереди", то аналогично для 9 верблюдов имеем не более 9 расстановок.

Автор: Domen 18.10.2009, 21:48

Непосредственно впереди.То есть 9!-8!*С_8^1..+1!*C_8^8=142729
Так получается?

Автор: Akina 18.10.2009, 21:54

Ты чо??? Задачка для второго класса. Не надо мудрить.

Впереди первого верблюда может быть:

никто (он первый)
верблюд 2
верблюд 3
...
верблюд 9

Всё. 9 вариантов. Не более. В десятом варианте будет повторен один из этих девяти.

Добавлено через 1 минуту и 32 секунды
Или ты неверно пересказываешь условие задачи.

Автор: Domen 18.10.2009, 22:06

Там написано комбинаций перестановок.А не идет впереди , впереди кого шел раньше.
То есть
123456789
234567891
.......
Приблизительно по идее так.

Автор: Akina 18.10.2009, 22:31

Тогда дополнительное условие НИКАК не влияет на количество перестановок.

Автор: Domen 18.10.2009, 22:39

//ММММММ.Чуть не так, условие влияет.
//Это почти тоже самое что стандартная задача про караван.
//Где условие такое Сколько существует комбинаций перестановок верблюдов при которых ни один верблюд не идет за тем, за кем шел ранее.
//А я решаю задачу с условием наоборот

Автор: Akina 18.10.2009, 23:07

Цитата(Domen @ 18.10.2009, 23:39

)

я решаю задачу с условием наоборот

Это одна и та же задача. Только во втором случае они идут задницей вперёд.

Автор: Domen 18.10.2009, 23:17

Спасибо.Я сейчас попялился в эту задачу часок и понял.

Автор: Domen 20.10.2009, 22:36

Здравствуйте! (Надеюсь так можно писать еще одну задачу.)
//Сколько N чисел меньших 10^6 содержат 1,2,3,4 ?
Насчет решения честно говоря не знаю особо как здесь подойти:
Вроде условие дано так, что бесконечно много.
Ну а если они имели ввиду до нуля.
Я думал что решается так 10*10*4! ,но ведь есть пары которые входят во все значения Пример (1,2), здесь всен два числа, следовательно одна комбинация уже для двух случаев....