Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
milka495
2 / 2 / 0
Регистрация: 12.12.2013
Сообщений: 73
1

Перечислить все последовательности длины n из символов {0,1,2}

21.12.2014, 20:20. Просмотров 478. Ответов 11
Метки нет (Все метки)

2. Перечислить все последовательности длины n из символов {0,1,2}, в которых никакая группа цифр не встречается три раза подряд. То есть, нет куска вида XX, где X – некоторая непустая подстрока.

П.С. Знаю, что тут решали для случая когда цифры не встречаются два раза подряд. Я прошу вас, помогите решить такую. И еще можно с комментариями к коду. Зачет горит!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.12.2014, 20:20
Ответы с готовыми решениями:

Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX )
Перечислить все последовательности из n нулей, единиц и двоек, в которых...

Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX )
Перечислить все последовательности из n нулей, единиц и двоек, в которых...

найти последовательности символов произвольной длины, которые повторяются и заменить их кодами
Пожалуйста помогите написать,просто совершенно ничего в голову не лезет.:cry:...

Удалить из строки символов все слова нечетной длины
Помогите написать на языке С++, желательно простым языком, чтобы...

Заменить все последовательности символов 'on' на 'online'
Дана символьная строка. Заменить все последовательности символов 'on' на...

11
zer0mail
2452 / 2089 / 216
Регистрация: 03.07.2012
Сообщений: 7,571
Записей в блоге: 1
21.12.2014, 20:46 2
Цитата Сообщение от milka495 Посмотреть сообщение
не встречается три раза подряд. То есть, нет куска вида XX,
Так 2 (два) или 3 (три) раза? Определитесь уж сами как-нибудь...
0
milka495
2 / 2 / 0
Регистрация: 12.12.2013
Сообщений: 73
21.12.2014, 22:29  [ТС] 3
Три
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
21.12.2014, 22:32 4
milka495, n до скольки?
0
milka495
2 / 2 / 0
Регистрация: 12.12.2013
Сообщений: 73
21.12.2014, 22:35  [ТС] 5
Его задает пользователь
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
21.12.2014, 22:38 6
milka495, вдруг пользователь задаст 1000000? такое возможно? или препод будет вводить? и он не сможет ввести много, т.к. не сможет проверить правильность?
0
milka495
2 / 2 / 0
Регистрация: 12.12.2013
Сообщений: 73
21.12.2014, 22:42  [ТС] 7
К сожалению, ничего по этому поводу сказать не могу. Преподаватель не уточнял
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
21.12.2014, 23:05 8
milka495, я написал перебор, он уже для 15 вывел почти 4 миллиона таких последовательностей.

как предмет называется? никаких ссылок препод не давал?
0
milka495
2 / 2 / 0
Регистрация: 12.12.2013
Сообщений: 73
21.12.2014, 23:18  [ТС] 9
Комбинаторные алгоритмы. А тема" Обход дерева вариантов. Метод ветвей и границ"
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
21.12.2014, 23:53 10
я хз. не знаю этого.
могу только вот перебор кинуть.

Добавлено через 1 минуту
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
#include <iostream>
 
using namespace std;
 
const int N = 111;
 
int a[N];
int n;
int cnt = 0;
 
bool equal(int lf, int rg, int lf2, int rg2)
{
    int i = lf, j = lf2;
 
    while(i <= rg)
    {
        if(a[i] != a[j])
            return false;
        i++, j++;
    }
 
    return true;
}
 
bool check(int pos)
{
    int mx = (pos + 1) / 3;
    for(int len = 1; len <= mx; len++)
    {
        for(int i = 0; i + 3 * len - 1 <= pos; i++)
        {
            if(equal(i, i + len - 1, i + len, i + 2 * len - 1) && equal(i + len, i + 2 * len - 1, i + 2 * len, i + 3 * len - 1))
                return false;
        }
    }
 
    return true;
}
 
void rec(int pos)
{
    if(pos >= n)
    {
        cnt++;
        for(int i = 0; i < n; i++)
            printf("%d ", a[i]);
        printf("\n");
        return;
    }
 
    for(int next = 0; next < 3; next++)
    {
        a[pos] = next;
        if(check(pos))
            rec(pos + 1);
    }
 
    return;
}
 
int main(){
    scanf("%d", &n);
 
    rec(0);
 
    printf("vsego takix posledovatelnostey == %d\n", cnt);
 
    return 0;
}
Добавлено через 8 минут
я чет тупанул. кажется, этот переббор можно сильно улучшить.

Добавлено через 11 минут
не. не сильно он улучшается.
1
milka495
2 / 2 / 0
Регистрация: 12.12.2013
Сообщений: 73
22.12.2014, 00:19  [ТС] 11
И на этом большое спасибо!
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
22.12.2014, 00:44 12
Цитата Сообщение от milka495 Посмотреть сообщение
Комбинаторные алгоритмы. А тема" Обход дерева вариантов. Метод ветвей и границ"
Что я понимаю под обходом дерева и ветвями с границами:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
char *pb, *pe;
 
void tstf(char *p)
{   if (p==pe) {cout<<pb<<endl;} else
    for (int i=0; i<3; i++) {
        *p=i+'0';
        // условие ветвей и границ
        if (p>=pb+2 && *(p-1)==*p && *(p-2)==*p) continue;
        tstf(p+1);
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    int n; cout << "Input n (<=50) :"; cin >> n;
    char r[51]; pb=r; pe=r+n; *pe=0;
    tstf(r);
    system("pause");
    return 0;
}
1
22.12.2014, 00:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.12.2014, 00:44

Заменить в последовательности символов после первого вхождения знака ‘+’ все цифры на символ –
Заменить в последовательности символов после первого вхождения знака ‘+’ все...

Перечислить все подмножества n элементного множества {1,2,.,n}
Помогите пожалуйста написать программу для этой задачи: Перечислить все...

Перечислить все K элементные подмножества n элементарного множества
Перечислить все K элементные подмножества n элементарного множества пример и...


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

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

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