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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
Керра
Модератор
 Аватар для Керра
1270 / 438 / 45
Регистрация: 24.08.2011
Сообщений: 2,123
06.07.2014, 13:33     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #1
Задание:
В День флага России владелец магазина решил украсить свою витрину полосками ткани белого, синего и красного цветов. Он хочет, чтобы выполнялись следующие условия:
  1. Полоски одного цвета не должны располагаться рядом друг с другом.
  2. Синяя полоска может быть расположена только между белой и красной или между красной и белой.

Определите количество способов выполнить желание владельца магазина.

Исходные данные:
N — количество полосок, 1 ≤ N ≤ 45.
Результат:
M — количество способов украсить витрину.
http://acm.timus.ru/problem.aspx?space=1&num=1225

Я подумала, что у нас есть 2 изначальных варианта (б - белый, к - красный): бкбкбк... и кбкбкб... И уже в эти варианты мы вставляем синий между белым и красным - сначала один синий во всю цепочку, потом 2 синих и т.д., т.е. у нас есть сочетания по 1, по 2 и т.д. из n-2. Но это абсолютно неправильно - даже первый тест не проходит. Почему?

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
#include <iostream>
using std::cin;
using std::cout;
 
#define I unsigned __int64
 
I C(int n, int k)
{
    I res = 1;
    for (int i = 1; i <= k; i++)
        res *= n - k + i;
    for (int i = 1; i <= k; i++)
        res /= i; // делим отдельно, чтобы точно не должно было возникнуть дробных чисел
    return res;
}
 
int main()
{
    int n;
    cin >> n;
    I res = 0;
    for (int i = 0; i <= n-2; i++)
        res += C(n-2, i);
    cout << 2*res; // два варианта цепочки
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.07.2014, 13:33     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме
Посмотрите здесь:

C++ Определить количество отрицательных элементов, расположенных вы-ше главной диагонали матрицы.
C++ Для вещественных массивов a и b определить максимальное количество подряд расположенных элементов
C++ Определить количество четных элементов, расположенных на главной и побочной диагоналях матрицы
Определить количество отрицательных элементов, расположенных выше главной диагонали матрицы C++
Из двухмерного массива сформировать одномерный по определенной схеме C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
06.07.2014, 23:57     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #21
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)-го.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Керра
Модератор
 Аватар для Керра
1270 / 438 / 45
Регистрация: 24.08.2011
Сообщений: 2,123
09.07.2014, 14:11  [ТС]     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #22
Извиняюсь, не читала решения, хочу решить сама без готового решения. Почитала на хабре, получилось что вроде вот так вот, но лимит по времени на 8м тесте не проходит. Как ускорить?
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
#include <iostream>
using std::cin;
using std::cout;
 
#define I unsigned __int64
 
I Variants(int n, int i, char cur_color, char prev_color) // 1 - белый, 2 - красный, 3 - синий
{
    if (i+1 <= n)
        switch (cur_color)
        {
        case 1: return Variants(n, i+1, 2, 1) + (i+1 < n? Variants(n, i+1, 3, 1) : 0);
        case 2: return Variants(n, i+1, 1, 2) + (i+1 < n? Variants(n, i+1, 3, 2) : 0);
        case 3: switch (prev_color)
                {
                case 1: return Variants(n, i+1, 2, 3);
                case 2: return Variants(n, i+1, 1, 3);
                };
        }
    else
        return 1;
}
 
int main()
{
    int n;
    cin >> n;
    cout << Variants(n, 1, 1, 0) + Variants(n, 1, 2, 0);
    return 0;
}
Добавлено через 13 минут
Видимо скорость теряется за счет вызовов функции, значит надо организовать то же самое без рекурсивной функции
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.07.2014, 14:27     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #23
Керра, я бы посоветовал не решать в лоб, а все-таки попробовать вывести формулу. Представьте, что вам известно количество флагов для всех длинн от 1 до (N - 1) и попробуйте вывести из нее количество флагов длинны N. Разберите на листе, как формируются флаги.
Другой вариант - порешать задачи на динамическое программирование, но менее сложные. Начать можно с Зайца
Керра
Модератор
 Аватар для Керра
1270 / 438 / 45
Регистрация: 24.08.2011
Сообщений: 2,123
10.07.2014, 10:16  [ТС]     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #24
soon, последовательность Фибоначчи, только начинающаяся с 2 2. Но почему именно так, не понимаю.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
10.07.2014, 10:23     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #25
Керра, у меня в ответе под спойлером объяснение (там несколько другая формула, конкретно про Фибоначчи у Mr.X)
Керра
Модератор
 Аватар для Керра
1270 / 438 / 45
Регистрация: 24.08.2011
Сообщений: 2,123
10.07.2014, 23:01  [ТС]     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #26
Надеюсь я это пойму хотя бы завтра
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
11.07.2014, 17:23     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #27
Ускорение существующего кода с минимальными затратами:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
I Variants(int n, int i, char cur_color, char prev_color) // 1 - белый, 2 - красный, 3 - синий
{
    static I results[46][46][4][4];
    I& r = results[n][i][cur_color][prev_color];
    if (r != 0)
        return r;
    if (i+1 <= n)
        switch (cur_color)
        {
        case 1: return r = Variants(n, i+1, 2, 1) + (i+1 < n? Variants(n, i+1, 3, 1) : 0);
        case 2: return r = Variants(n, i+1, 1, 2) + (i+1 < n? Variants(n, i+1, 3, 2) : 0);
        case 3: switch (prev_color)
                {
                case 1: return r = Variants(n, i+1, 2, 3);
                case 2: return r = Variants(n, i+1, 1, 3);
                };
        }
    else
        return r = 1;
}
Переход от приведённого кода к Фибоначчи:
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
I Variants(int n, int i, char cur_color, char prev_color) // 1 - белый, 2 - красный, 3 - синий
{
    if (i+1 <= n)
        switch (cur_color)
        {
        case 1: return Variants(n, i+1, 2, 1) + (i+1 < n? Variants(n, i+1, 3, 1) : 0);
        case 2: return Variants(n, i+1, 1, 2) + (i+1 < n? Variants(n, i+1, 3, 2) : 0);
        case 3: switch (prev_color)
                {
                case 1: return Variants(n, i+1, 2, 3);
                case 2: return Variants(n, i+1, 1, 3);
                };
        }
    else
        return 1;
}
 
// правила для красных и белых полосок одинаковые - можно объединить
 
I Variants(int n, int i, char cur_color, char prev_color) // 1 - белый, 2 - красный, 3 - синий
{
    if (i+1 <= n)
        switch (cur_color)
        {
        case 1:
        case 2:
            return Variants(n, i+1, 1, 1) + (i+1 < n? Variants(n, i+1, 3, 1) : 0);
        case 3:
            return Variants(n, i+1, 1, 3);
        }
    else
        return 1;
}
 
// теперь prev_color не используется;
// case 3: пожно подставить во второй вызов Variants
 
I Variants(int n, int i, char cur_color)
{
    if (i+1 <= n)
        switch (cur_color)
        {
        case 1:
        case 2:
            return Variants(n, i+1, 1) + (i+1 < n? Variants(n, i+2, 1) : 0);
        }
    else
        return 1;
}
Trwsdf
Заблокирован
11.07.2014, 18:27     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #28
Всего два варианта.
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
11.07.2014, 19:38     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #29
***

Добавлено через 1 минуту
Цитата Сообщение от Somebody Посмотреть сообщение
Ускорение существующего кода
Ну, самый скорый у меня вроде бы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2014, 20:27     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме
Еще ссылки по теме:

Определить количество четных элементов, расположенных на главной и побочной диагоналях C++
C++ Определить количество различных комбинаций монет, которые могут сложиться в определенную сумму
Запуск программ по определенной схеме с использованием Fiber и Thread C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
11.07.2014, 20:27     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме #30
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, самый скорый у меня вроде бы.
Ну, это да. Можно ещё округлять к ближайшему, тогда на один pow меньше. (Хотя тут всего один раз считается, но вообще так...)
Yandex
Объявления
11.07.2014, 20:27     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме
Ответ Создать тему
Опции темы

Текущее время: 23:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru