Вопрос № 62791: Здравствуйте, как решить такую задачу:
Узнать, сколько существует последовательностей из 0 и 1 длинной n, в какой не встречается двух единиц подряд. n < 45.
Число n вводится с клавиатуры.
Вывести надо количество перестановок длины n , ...
Вопрос № 62.791
Здравствуйте, как решить такую задачу:
Узнать, сколько существует последовательностей из 0 и 1 длинной n, в какой не встречается двух единиц подряд. n < 45.
Число n вводится с клавиатуры.
Вывести надо количество перестановок длины n , в которых не встречается 2-ох единиц подряд.
Пример:
Когда вводится 5 - количество перестановок - 13.
Я провел свои исследование и нашел закономерность(что-то вроде чисел Фибоначи)
Приведу таблицу:
n Количество перестановок:
0 1
1 2
2 3
3 5
4 8
5 13
6 21
Отправлен: 15.11.2006, 19:38
Вопрос задал: ataman (статус: 2-ой класс)
Всего ответов: 1 Мини-форум вопроса >>> (сообщений: 5)
Отвечает: Решетник Д
Здравствуйте, ataman!
формулы подсчета количества перестановок можно посмотреть в ЛЮБОЙ книжке по комбинаторике. берете это количество (A) для n чисел и отнимаете (B) = (n-1)*(количество перестановок для n-2) и сюда нужно прибавить некое число ~n (C).
суть: от общего количества отнимаете те перестановки (1), в которых присутствуют две единицы. но так как в (1) перестановках каждая в одном из случаев дублирует другую, то нужно прибавить некое число (посчитайте сами), которое уравновесит количество перестановок.
Попробуйет такой вариант...
--------- Жизнь коротка, чтобы писать на ассемблере
Ответ отправил: Решетник Д (статус: 10-ый класс)
Ответ отправлен: 15.11.2006, 23:12