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

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

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

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

06.07.2014, 13:33. Просмотров 3010. Ответов 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
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
06.07.2014, 15:18 #2
Не проверял на правильность весь алгоритм, но при N=1 выводит 0, хотя должно по идее быть 3.
Я бы вообще сделал эту задачу методом динамического программирования и не мучился б)
0
MayaNash
1291 / 459 / 50
Регистрация: 24.08.2011
Сообщений: 2,246
06.07.2014, 15:49  [ТС] #3
Dani, при 1 должно быть 2, но ясно что что-то неправильно. Поставила проверку конкретно на 1 и 2, теперь первые 3 теста проходит.
Динамическое еще не освоила, спасибо что напомнил, давно хотела
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
06.07.2014, 15:53 #4
Керра, ах, да. Синий - между красным и белым. Тогда - точно, 2. Сейчас попробую описать, как и понимаю ваше (дальше на ты, хорошо? ) решение: ты перебираешь количество синих полос - их количество может быть от 0 и до n-2, потому что... почему? Если у нас всего N полосок, получается одна белая и красная и n-2 синие. И тут получится так, что много синих полосок будут стоять на соседних местах.
0
MayaNash
1291 / 459 / 50
Регистрация: 24.08.2011
Сообщений: 2,246
06.07.2014, 15:58  [ТС] #5
Dani, поняла, действительно затупила, ща подумаю

Добавлено через 1 минуту
получается, что до 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
27
28
29
#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;
    if (n == 1 || n == 2)
        res = 1;
    else
        for (int i = 0; i <= n/2; i++)
            res += C(n-2, i);
    cout << 2*res;
    return 0;
}
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
06.07.2014, 15:59 #6
Керра, я уже писал: лучше сделать методом ДП и не мучиться
1
fio
10 / 10 / 3
Регистрация: 16.06.2014
Сообщений: 45
06.07.2014, 16:00 #7
Я обещаю, что Флаги невозможно сдать, вычисляя С.
Нужно понять совсем базовое динамическое программирование.
Иначе просто не влезет в ограничения.
1
MayaNash
1291 / 459 / 50
Регистрация: 24.08.2011
Сообщений: 2,246
06.07.2014, 16:01  [ТС] #8
но должно же быть точное математическое решение
хотя ДП все равно надо будет осваивать, это да, надо ее в любом случае и так тоже решить

Добавлено через 49 секунд
fio, ок, мерси
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
06.07.2014, 16:02 #9
Возможно, если составить решение динамическим программированием, можно получить реккурентное уравнение, решить его и получить одну формулу.
0
gng
686 / 532 / 141
Регистрация: 08.09.2013
Сообщений: 1,413
06.07.2014, 17:06 #10
45 полос - это предел для метода тупого перебора, на моем старом нетбуке (селерон 900) считает почти минуту.
C
1
2
3
4
5
6
7
8
9
unsigned long C (int n, int blue) {
  if (n < 2)  return 1;
  return blue ? C (n-1, 0) : C (n-1,0) + C (n-1, 1);
}
main() {
  int n;
  scanf ("%d", &n);
  printf ("%lu\n", 2 * C (n-1, 0));
}
0
soon
2545 / 1310 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.07.2014, 18:06 #11
Под спойлером - ряд, являющийся ответом и формула, как его получить
Кликните здесь для просмотра всего текста
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), но мне уже лень доказывать
1
Миниатюры
Определить количество комбинаций разноцветных полосок, расположенных по определенной схеме  
soon
2545 / 1310 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
06.07.2014, 18:13 #12
Решения
Кликните здесь для просмотра всего текста
Код #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
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<std::size_t> ans;
 
    ans.push_back(2);
    ans.push_back(2);
    ans.push_back(4);
 
    std::size_t n;
    std::cin >> n;
 
    --n;
 
    for(std::size_t i = 2; i <= n; ++i)
    {
        ans.push_back(ans.at(i) * 2 - ans.at(i - 2));
    }
 
    std::cout << ans.at(n) << std::endl;
 
    return 0;
}
Код #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 
int main()
{
    std::size_t prev = 2;
    std::size_t curr = 2;
 
    std::size_t n;
    std::cin >> n;
 
    for(std::size_t i = 2; i < n; ++i)
    {
        std::size_t tmp = curr;
        curr += prev;
        prev = tmp;
    }
 
    std::cout << curr << std::endl;
 
    return 0;
}
0
SlavaSSU
217 / 162 / 45
Регистрация: 17.07.2012
Сообщений: 587
06.07.2014, 20:12 #13
Керра, вот ток что сдал комбинаторикой!

C++ (Qt)
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#pragma comment(linker, "/STACK:167177216")
 
#include <stdio.h>
#include <stack>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <memory.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <time.h>
#include <cassert>
#include <cstring>
//#include <unordered_set>
 
using namespace std;
 
#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
 
typedef long long li;
typedef long double ld;
typedef unsigned long long uli;
 
const int INF = 1e9;
const ld eps = 1e-9;
const li MOD = (li)(4e6 + 37);
const li INF64 = (li)(INF) * (li)(INF);
 
const int ddx[] = {-1, 1, 1, -1};
const int ddy[] = {1, 1, -1, -1};
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dxh[] = {-1, -1, -1, 1, 1, 1, 1, -1};
const int dyh[] = {1, -1, -1, -1, -1, 1, 1, 1};
const string dirs[] = {"RIGHT", "UP", "LEFT", "DOWN"};
 
bool in(int i, int j, int n, int m)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}
 
li c[111][111];
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //freopen("errors.txt", "w", stderr);
    //ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
 
    if(n == 1)
    {
        cout << 2 << endl;
        return 0;
    }
 
    for(int i = 1; i <= 100; i++)
    {
        c[i][0] = c[i][i] = 1;
        for(int j = 1; j < i; j++)
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
 
    li ans = 0;
    for(int r = 1; r <= n; r++)
        for(int w = 1; w <= n; w++)
        {
            if(abs(r - w) > 1)
                continue;
            int left = n - r - w;
            if(left < 0)
                continue;
            
            li cur = c[r + w - 1][left];
            if(r == w)
                cur *= 2LL;
            ans += cur;
        }
 
    cout << ans << endl;
    return 0;
}
0
Somebody
2799 / 1610 / 150
Регистрация: 03.12.2007
Сообщений: 4,210
Завершенные тесты: 3
06.07.2014, 20:18 #14
SlavaSSU, первая половина файла - просто А так вообще это тоже динамика получилась...
0
SlavaSSU
217 / 162 / 45
Регистрация: 17.07.2012
Сообщений: 587
06.07.2014, 20:19 #15
Somebody, где ты там динамику увидел? делал так же, как и хотел ТС. поставил сначала красные и белые полоски, и потом вставлял синие всеми возможными способами
0
06.07.2014, 20:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2014, 20:19
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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