IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Сложная задача на комбинаторику, никак не могу решить((
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 38
Пол: Мужской

Репутация: -  0  +


Люди помогите плииз! я никак не могу решить эту задачу...вот третий день мучаюсь,все никак((
Кто чем может помогите...ну мне очень надо...вот условие задачки:

Подсчитать число двоичных N-значных натуральных чисел (N<36), в каждом из которых нет трех единиц идущих подряд, а незначащие нули в записи чисел отсутствуют.
Ваша программа должна запросить значение N; найти и сообщить число n- значных двоичных чисел без трех единиц подряд.
Пример: Исходные данные: 4 Ответ: 6 (Имеются ввиду числа 1000, 1001, 1010, 1011, 1100, 1101)

P.S в этой теме я постарался учесть все замечания сделанные мне ранее) просто очень нужна помощь..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Можно использовать рекуррентное соотношение:

f(0) = 1
f(1) = 2
f(2) = 4
f(n) = f(n - 1) + f(n - 2) + f(n - 3)

Формула получается следующим образом:

Если в n-значном числе первая цифра - 0, то дальше может идти что угодно, т.е. вариантов будет f(n-1).

Если в n-значном числе первая цифра - 1, а за ней идет 0, то дальше тоже может идти что угодно, и таких вариантов будет f(n-2), т.к. после "10" остается n-2 неопределенные цифры.

Если в n-значном числе первая цифра - 1, и за ней идет 1, то третьей цифрой может быть только 0 (иначе нарушится правило), а за ним может идти что угодно, и таких вариантов будет f(n-3).

Таким образом, f(n) = f(n - 1) + f(n - 2) + f(n - 3).

Ответом к задаче будет f(N) - f(N - 1), потому что от нас требуют числа без незначащих нулей, поэтому мы из общего числа устраивающих нас чисел - f(N) - вычитаем количество чисел, начинающихся с нуля - f(N - 1).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 5:07
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name