Форум программистов, компьютерный форум 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) подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2803 / 1579 / 247
Регистрация: 03.05.2010
Сообщений: 3,669
06.07.2014, 23:57     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/////////////////////////////////////////////////////////////////////////////////////////
//1225. ФЛАГИ
//Ограничение времени: 1.0 секунды
//Ограничение памяти: 64 МБ
//В День флага России владелец магазина решил украсить свою витрину полосками ткани белого, 
//синего и красного цветов. Он хочет, чтобы выполнялись следующие условия:
//
//Полоски одного цвета не должны располагаться рядом друг с другом.
//Синяя полоска может быть расположена только между белой и красной или между красной и белой.
//
//Определите количество способов выполнить желание владельца магазина.
//Исходные данные
//N — количество полосок, 1 ≤ N ≤ 45.
//Результат
//M — количество способов украсить витрину.
/////////////////////////////////////////////////////////////////////////////////////////
#include <iomanip>
#include <iostream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
int     const   MAX_BANDS_COUNT     =   73;
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
/////////////////////////////////////////////////////////////////////////////////////////
double   get_variants_flags( int   n )
{
    double  sqrt_5  =   pow(5.0, 0.5);
    double  F1      =   (1 + sqrt_5) / 2;
    double  F2      =   (1 - sqrt_5) / 2;
 
    return  2/sqrt_5 * ( pow(F1, n) - pow(F2, n) );
}
/////////////////////////////////////////////////////////////////////////////////////////
void    print_prompt_and_input_value_in_segment
    (
        T_str   const   &   prompt,
        int             &   val,
        int                 left_bound,
        int                 right_bound
    )
{
    do
    {
        std::cout   <<  prompt;
        std::cin    >>  val;
    }
    while   (
                    val     <   left_bound
                ||  val     >   right_bound
            );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        int     n   =   0;
 
        print_prompt_and_input_value_in_segment
            (
                "Число полос (1..73): ",
                n,
                1,
                MAX_BANDS_COUNT
            );
 
        double   variants    =   get_variants_flags( n );
 
        std::cout   <<  std::fixed
                    <<  std::setprecision(0)
                    <<  variants
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }//for
}
Добавлено через 33 минуты
Цитата Сообщение от soon Посмотреть сообщение
Подходит также формула f(n) = f(n - 1) + f(n - 2)
Да, действительно, ответ – удвоенный n-й член последовательности Фибоначчи. Доказывается просто.
В последней тройке полос у нас синяя либо есть, либо нет. Если нет, то эту комбинацию мы можем получить
из (n - 2)-го набора, добавив к каждому варианту красную и белую полоски или наоборот.
Если в последней тройке есть синяя, то эту комбинацию мы можем получить из (n - 1)-го набора следующим образом. Если в последней паре нет синей, то вставляем ее между ними. Если же есть синяя (она предпоследняя), то вставляем в конец красную или белую. Таким образом, количество с тройками без синей равно количеству (n - 2)-го набора, а с тройками с синей – количеству (n - 1)-го.
 
Текущее время: 00:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru