0
1

Добрый день, есть задача, в числе n разрядов, система счисления- 2-ая, есть одно правило, нельзя, чтобы единички находились рядом. Я опытным путем нашел решение этой задачи, то есть последовательность типа {0, 1, 2, 4, 7, 12, ...}, то есть n(i) = n(i - 1) + n(i - 2) + 1, n(1) = 1, n(2) = 2. И вижу я в этом что-то уж очень сильно напоминающее фибоначчи и подумал, а нет ли у этой последовательности какого-то названия. Также стало интересно есть ли способы решения поставленной мной задачи, не опытным путем, как я, а более шаблонно. Спасибо за внимание. (можно кинуть ссылку на ресурс, который ответит на мои вопросы)

задан 9 Апр '13 18:56

А в чем задача-то? Видимо, нужно подсчиать количество таких чисел?

(9 Апр '13 23:50) DocentI

ну, да, нужно было подсчитать кол-во таких чисел.

(10 Апр '13 10:21) fortunado
10|600 символов нужно символов осталось
0

В этой задаче ответом числа Фибоначчи и являются. То, что написано у Вас -- это они самые, уменьшенные на единицу. Разница в ответе вызвана, вероятно, тем, что Вы последовательность из одних нулей не учитываете, но удобнее было бы учитывать.

Количество двухразрядных чисел без соседних единиц получается равно трём: $%00$%, $%01$%, $%10$%. То есть $%f(2)=3$%, где $%f(n)$% означает количество $%n$%-разрядных чисел без соседних единиц.

Рекуррентную формулу, задающую числа Фибоначчи, то есть $%f(n)=f(n-1)+f(n-2)$% (при $%n\ge2$%), где $%f(0)=1$%, $%f(1)=2$%, для таких чисел доказать легко. Составим полный каталог $%n$%-разрядных чисел. Среди них есть те, которые оканчиваются на $%0$%, и те, которые оканчиваются на $%1$%. Подсчитаем отдельно то и другое.

Сколько чисел оканчивается на $%0$%? Если этот ноль справа удалить, то мы получим полный каталог $%(n-1)$%-разрядных чисел -- так как $%0$% справа приписать можно всегда. То есть таких чисел с нулём на конце у нас $%f(n-1)$%. А сколько оканчивается на $%1$%? Если мы сотрём $%1$% справа, то получим полный список $%(n-1)$%-разрядных чисел, оканчивающихся на $%0$%, так как $%1$% могла быть приписана только к нулю. И теперь, если мы удалим ещё и этот ноль справа, то перед нами будет весь список $%(n-2)$%-разрядных чисел. Итого на $%1$% оканчивается $%f(n-2)$% числа. Складывая то и другое, получаем требуемую формулу.

Можно при небольших значениях $%n$% создать такие списки, и описанная закономерность сразу себя обнаружит.

ссылка

отвечен 9 Апр '13 19:51

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×15

задан
9 Апр '13 18:56

показан
460 раз

обновлен
10 Апр '13 10:21

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru