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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
MayaNash
1285 / 453 / 47
Регистрация: 24.08.2011
Сообщений: 2,214
#1

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

06.07.2014, 13:33. Просмотров 2568. Ответов 29
Метки нет (Все метки)

Задание:
В День флага России владелец магазина решил украсить свою витрину полосками ткани белого, синего и красного цветов. Он хочет, чтобы выполнялись следующие условия:
  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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.07.2014, 13:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме (C++):

Определить количество различных комбинаций монет, которые могут сложиться в определенную сумму - C++
Напишите программу, которая определяет количество различных комбинаций монет, которые могут сложиться в определенную сумму. Input: ...

Определить количество комбинаций шайб, гаек и болтов для общей суммы покупки в 100 рублей - C++
Задачка по программированию. Дано: Стоимость Болтов =10, Гаек=5, Шайб =0.5; Определить количество комбинаций для общей суммы покупки...

Из двухмерного массива сформировать одномерный по определенной схеме - C++
дано двухмерный массив A необходимо создать одномерный массив B располагая в нем элементы по данной схеме

Запуск программ по определенной схеме с использованием Fiber и Thread - C++
Необходимо выполнить запуск программ калькулятора (сalc.exe), Графического редактора Paint (mspaint.exe), блокнота (notepad.exe) по такой...

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

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

29
gray_fox
06.07.2014, 20:21     Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме
  #16

Не по теме:

Цитата Сообщение от SlavaSSU Посмотреть сообщение
C++
1
2
3
4
5
6
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define x first
#define y second
Не надо так...

0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,198
Завершенные тесты: 1
06.07.2014, 20:23 #17
Цитата Сообщение от SlavaSSU Посмотреть сообщение
C++
1
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
Ну, я вижу, считается C, но это по сути тоже динамика.
0
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
06.07.2014, 20:26 #18
Somebody, и че? само решение не динамикой! если в задаче не на динамику будет подзадача(например, найти максимум в массие, и я этот максимум в массиве буду искать динамикой), то ты же не скажешь, что ты динамикой сдал. а так да, С-шки удобно так считать динамикой(треугольник паскаля, если кто не згал)
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
06.07.2014, 20:38 #19
Цитата Сообщение от SlavaSSU Посмотреть сообщение
где ты там динамику увидел?
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
Для посчета c[i][j] используются меньшие подзадачи (уже посчитанные значения) c[i-1][j-1] и c[i-1][j]
Цитата Сообщение от gray_fox Посмотреть сообщение
Не надо так...
Это у SlavaSSU такой заранее написанный заголовок для участия в контестах. Такие замены, например, pb вместо push_back, помогают сэкономить время во время турнира и быстрее сдать задачу.
1
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
06.07.2014, 20:42 #20
Dani, Dani, да знаю, выше ответил что подсчет Сшек динамикой не в счет! Само решение типа комбинаторное! А ты участвуешь в контестах? У тебя какие ники на codeforces и topcoder? Чето кажется ты крутой да там?
0
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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)-го.
2
MayaNash
1285 / 453 / 47
Регистрация: 24.08.2011
Сообщений: 2,214
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 минут
Видимо скорость теряется за счет вызовов функции, значит надо организовать то же самое без рекурсивной функции
1
soon
2542 / 1307 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.07.2014, 14:27 #23
Керра, я бы посоветовал не решать в лоб, а все-таки попробовать вывести формулу. Представьте, что вам известно количество флагов для всех длинн от 1 до (N - 1) и попробуйте вывести из нее количество флагов длинны N. Разберите на листе, как формируются флаги.
Другой вариант - порешать задачи на динамическое программирование, но менее сложные. Начать можно с
1
MayaNash
1285 / 453 / 47
Регистрация: 24.08.2011
Сообщений: 2,214
10.07.2014, 10:16  [ТС] #24
soon, последовательность Фибоначчи, только начинающаяся с 2 2. Но почему именно так, не понимаю.
0
soon
2542 / 1307 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
10.07.2014, 10:23 #25
Керра, у меня в ответе под спойлером объяснение (там несколько другая формула, конкретно про Фибоначчи у Mr.X)
1
MayaNash
1285 / 453 / 47
Регистрация: 24.08.2011
Сообщений: 2,214
10.07.2014, 23:01  [ТС] #26
Надеюсь я это пойму хотя бы завтра
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,198
Завершенные тесты: 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;
}
0
Trwsdf
Заблокирован
11.07.2014, 18:27 #28
Всего два варианта.
0
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
11.07.2014, 19:38 #29
***

Добавлено через 1 минуту
Цитата Сообщение от Somebody Посмотреть сообщение
Ускорение существующего кода
Ну, самый скорый у меня вроде бы.
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,198
Завершенные тесты: 1
11.07.2014, 20:27 #30
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, самый скорый у меня вроде бы.
Ну, это да. Можно ещё округлять к ближайшему, тогда на один pow меньше. (Хотя тут всего один раз считается, но вообще так...)
0
11.07.2014, 20:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2014, 20:27
Привет! Вот еще темы с ответами:

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

Определить количество четных элементов матрицы, расположенных на главной и побочной диаганалях - C++
Ввести матрицу размером NxM. Память для массива выделить динамически.Определить количество четных элементов, расположенных на главной и...

Определить сумму и количество простых чисел расположенных вне диагоналей матрицы - C++
Вообщем, я не знаю как решить вот эти 2 данные задачи из лабораторной, когда проходили эти темы в универе я проболел, и нужно срочно эту...

Определить сумму и количество элементов массива, расположенных до первого отрицательного числа - C++
Ввести целочисленный массив, состоящий из 10 элементов. определить сумму и количество элементов, расположенных до первого отрицательного...


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

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru