Форум программистов, компьютерный форум CyberForum.ru

Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Член класса управляемый не может относиться к типу класса не управляемый http://www.cyberforum.ru/cpp-beginners/thread1223284.html
"член класса управляемый не может относиться к типу класса не управляемый" Не могу понять что делать с этой ошибкой и как исправить
C++ Как расшифровывается библиотека cstdlib? ... http://www.cyberforum.ru/cpp-beginners/thread1223268.html
Что применить "\n" или "endl"? C++
Эти две операции похожи - они переходят на новую строку. Но endl очищает буфер, но при этом дольше выполняется. Так что же лучше применять?
C++ Позиционирование в потоке, переставить все нулевые элементы в начало файла
создать функцию, которая с использованием функций позиционирования в потоке переставляет все нулевые элементы в начало файла содержащего файла, переданного ей???????????
C++ Как считается угол альфа http://www.cyberforum.ru/cpp-beginners/thread1223238.html
#include<iostream> #include<cmath> using namespace std; int main() { setlocale(0,""); double alpha,V,L,k; const double g=9.8; cout<<"Введите угол:\n"; cin>>alpha;
C++ Проблема с указателем на функцию Доброго времени суток, пишу приложение, которое реализует все функции АТД (двусвязный список). Есть стандартная библиотека, есть функция в этой библиотеке int DLWalk(DLLIST *List, int(*Func)(int, void *, void *), void *Args) { DLLIST *ThisItem = List; int Result = 0; if(List != NULL) подробнее

Показать сообщение отдельно
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.07.2014, 18:06     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме
Под спойлером - ряд, являющийся ответом и формула, как его получить
Кликните здесь для просмотра всего текста
http://oeis.org/A006355
Сначала рассмотрим частные случаи. Для флагов длинны 1 решение очевидно

Попробуем полчить флаги длинны N. Для этого сначала к каждому флагу добавим R/W (это разрешено правилами) - первый синтезированный флаг. Второй флаг может быть получен добавлением B в предпоследнюю позицию (может быть запрещено, поскольку две B рядом недопустимы).

Получим следующий реультат (см вложение):

Как видим, у нас образуются мертвые ветки. Попробуем определить количество живых веток.

Видно, что каждая ветка на предыдущем шаге дает две ветки, из которых отмирают те, у которых предпоследняя буква B. Количество таких букв определяется на шаге N - 3 (текущий шаг N). Получаем общую формулу:

f(1) = 2
f(2) = 2
f(3) = 4
f(n) = f(n - 1) * 2 - f(n - 3)

P.S. Подходит также формула f(n) = f(n - 1) + f(n - 2), но мне уже лень доказывать
Миниатюры
Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме  
 
Текущее время: 11:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru