Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
0 / 0 / 0
Регистрация: 26.12.2015
Сообщений: 6

Поиск наибольшей общей подпоследовательности методом методом полного перебора

16.05.2016, 01:24. Показов 2463. Ответов 5

Студворк — интернет-сервис помощи студентам
Здравствуйте!
Помогите пожалуйста с этим адом
Нужно решить задачу о поиске наибольшей общей подпоследовательности методом динамического программирования и методом полного перебора! Методом динамического программирования у меня она решается, но только если пользователь сам вводит строки. Есть функция, которая рандомит сами строки, но она у меня не работает почему то..
Поэтому код представил , который работает со строками пользователя.
Убил весь день на это и не понимаю как сделать так, чтобы работало хотя бы с помощью динамического программирования.
Подскажите хотя бы идею как делать полным перебором, потому что понятия нет.
Спасибо большое заранее тем, кто поможет хоть чем то!!

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
81
82
83
84
85
86
87
88
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cctype>
#include <ctime>
#include <cstdlib>
 
 
using namespace std;
string LCS(const string& a, const string& b);
void alphabet(string& arr, int size);
 
 
int main (void)
{
clock_t time;
string a; 
cin>> a;
cout << endl;
string b;
cin >> b;
string c;
unsigned int start_time =  clock();
c = LCS(a,b);
unsigned int end_time = clock();
unsigned int search_time = end_time - start_time;
cout << c << endl;
cout << search_time << endl;
return 0;
}
 
 
string LCS(const string& a, const string& b)
    {
        vector<vector<int> > max_len;
        max_len.resize(a.size() + 1);
        for(int i = 0; i <= static_cast<int>(a.size()); i++)
            max_len[i].resize(b.size() + 1);
        for(int i = static_cast<int>(a.size()) - 1; i >= 0; i--)
        {
            for(int j = static_cast<int>(b.size()) - 1; j >= 0; j--)
            {
                if(a[i] == b[j])
                {
                    max_len[i][j] = 1 + max_len[i+1][j+1];
                }
                else
                {
                    max_len[i][j] = max(max_len[i+1][j], max_len[i][j+1]);
                }
            }
        }
        string res;
        for(int i = 0, j = 0; max_len[i][j] != 0 && i < static_cast<int>(a.size()) && j < static_cast<int>(b.size()); )
        {
            if(a[i] == b[j])
            {
                res.push_back(a[i]);
                i++;
                j++;
            }
            else
            {
                if(max_len[i][j] == max_len[i+1][j])
                    i++;
                else
                    j++;
            }
        }
        return res;
    }
 
void alphabet(string& arr, int size)
{
   srand(time(NULL));
    for(int i = 0; i < size;)
    {
        char ch = rand() % 127;
        if (isalnum(ch))//проверяет, является ли символ буквой или цифрой
        {
            arr[i] = ch;
            cout << arr[i];
            ++i;
        }
    }
    cin.get();
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
16.05.2016, 01:24
Ответы с готовыми решениями:

При сортировке методом полного перебора массив сбивается
Массив сбивается ровно на единицу при сортировке. Понять не могу где же. Может у кого-нибудь была похожая проблема? #include...

Задача о рюкзаке методом полного перебора. Нужно пояснение по коду
Здравствуйте, нужно пояснение по этому коду. Код не мой, также в нем много ошибок. Заранее спасибо. #include &lt;memory.h&gt; ...

Аппроксимация данных методом полного перебора
В универе дали задание, а с какого боку подходить к ним я даже и не знаю. Помогите пожалуйста, кто в этом разбирается: 1)Разработать...

5
управление сложностью
 Аватар для Почтальон
1693 / 1306 / 259
Регистрация: 22.03.2015
Сообщений: 7,545
Записей в блоге: 5
17.05.2016, 09:22
По поводу динамики - почитайте про вектора, ну и двухсвязные списки(вроде так называется)
0
0 / 0 / 0
Регистрация: 26.12.2015
Сообщений: 6
17.05.2016, 09:36  [ТС]
Почтальон, так в плане динамического программирования, работает всё нормально, но если только пользователь сам вводит строки. Я не могу передать рандомные значения строки из функции в main. Точней я передаю,но почему то функция по поиску НОП ломается от них! В чём может быть проблема?
0
управление сложностью
 Аватар для Почтальон
1693 / 1306 / 259
Регистрация: 22.03.2015
Сообщений: 7,545
Записей в блоге: 5
17.05.2016, 10:45
Ну тут отладчиком лучше смотреть, ну и если есть ошибки компилятора - привести ее текст.
0
0 / 0 / 0
Регистрация: 26.12.2015
Сообщений: 6
17.05.2016, 21:04  [ТС]
Почтальон, Компилятор выдаёт ошибку в коде функции :
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string alphabet(string *arr, int size)
{
   srand(time(NULL));
    for(int i = 0; i < size;)
    {
        string ch = rand() % 127;//string
        if (isalnum(ch))//проверяет, является ли символ буквой или цифрой
        {
            arr[i] = ch;
            cout << arr[i];
            ++i;
        }
    }
    return 0;
}
Ошибка именно в строке :
C++
1
string ch = rand() % 127;
Сама ошибка : |81|error: invalid conversion from 'int' to 'const char*' [-fpermissive]|

Я не знаю как правильно сделать рандомные значения в функции string и передать их в main.
0
управление сложностью
 Аватар для Почтальон
1693 / 1306 / 259
Регистрация: 22.03.2015
Сообщений: 7,545
Записей в блоге: 5
17.05.2016, 21:40
rand() - возвращает число, у вас же символ. Т.е. вам нужно сначала получить случайное число, потом привести его к коду символа.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
17.05.2016, 21:40
Помогаю со студенческими работами здесь

Решить задаче о рюкзаке методом полного перебора через рекурсию
Здравствуйте. Помогите, пожалуйста, решить задаче о рюкзаке методом полного перебора через рекурсию

Напишите программу, которая определяет тождественную истинность формулы методом полного перебора
Напишите программу, которая определяет тождественную истинность формулы методом полного перебора.

Нужна реализация итерационного алгоритма наибольшей общей подпоследовательности
Или я нуб в гугле, или реализации этого алгоритма на паскале в сети нет. Мне нужен именно итерационный алгоритм, т.е. без рекурсий. Также,...

Поиск массива методом последовательного перебора
Поиск массива методом последовательного перебора в С++

Решение уравнения методом перебора и методом деления отрезка пополам
Решите уравнение x^2=5cos(x-1) методом перебора и методом деления отрезка пополам. Сравните кол-во шагов цикла при использовании каждого...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Новые блоги и статьи
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек SDL3 и Box2D из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия SDL 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual. . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru