Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Программирование под Windows > C++ Builder
Перезагрузить страницу Как найти наибольшую общую последовательность для двух числовых массивов
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
viktorr viktorr вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.05.2010
По умолчанию Как найти наибольшую общую последовательность для двух числовых массивов - 22.05.2010, 13:57

У меня задание найти наибольшую общую последовательность(далее НОП) для двух числовых массивов. (Найдите НОП последовательностей (10010101) и (010110110)). Есть код но только для символьных массивов и программа подсчитывает количество символов в НОП а мне нужно вывести саму НОП. Помогите отредактировать. Зарание спасибо.
Код:
     a=Edit1->Text.c_str();
     b=Edit2->Text.c_str();
     n= StrLen(a);
     m=StrLen(b);
      int yes = 0;
    for( j = 0; j < m; j++ )
    {
       if( b[j] == a[0] ) yes = 1;
       s[0][j] = yes;
    }
    yes = 0;
    for(i = 0; i < n; i++)
    {
       if( a[i] == b[0] ) yes = 1;
       s[i][0] = yes;
    }

    for(i = 0; i < n; i++)
    {
       for(j = 0; j < m; j++)
       {
          if( a[i] == b[j] )  {
             
             s[i][j] = s[i-1][j-1] + 1;
            }

          else
           {  s[i][j]=max(s[i-1][j],s[i][j-1]);
            }
       }
       Memo1->Lines->Add(AnsiString(b[j]));
    }
Ответить с цитированием
  (#2 (permalink)) Старый
rotmaister rotmaister вне форума
программист-недосамоучка
 
Сообщений: 94
Сказал(а) спасибо: 0
Поблагодарили 3 раз(а) в 3 сообщениях
Регистрация: 23.03.2010
Адрес: город Сибай
Post 22.05.2010, 14:20

Всегда рад помочь :-D . Вот код функции, взял из Википедии.
Код:
string getLongestCommonSubsequence(const string& a, const string& b)
    {
        vector<vector<int> > max_len;
        max_len.resize(a.size() + 1);
        for(int i = 0; i <= (int)a.size(); i++)
            max_len[i].resize(b.size() + 1);
        for(int i = (int)a.size() - 1; i >= 0; i--)
        {
            for(int j = (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<(int)a.size() && j<(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;
    }
Компилить не пробовал, но должно работать.
Ответить с цитированием
  (#3 (permalink)) Старый
viktorr viktorr вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.05.2010
По умолчанию 22.05.2010, 14:44

У меня проблемы с самой адаптацией в Builder. Я немогу сделать правильный вывод и проблемы с преобразованием типов переменных. :wall:
Ответить с цитированием
  (#4 (permalink)) Старый
rotmaister rotmaister вне форума
программист-недосамоучка
 
Сообщений: 94
Сказал(а) спасибо: 0
Поблагодарили 3 раз(а) в 3 сообщениях
Регистрация: 23.03.2010
Адрес: город Сибай
Post 22.05.2010, 17:40

Тяжелый случай... Короче объяснение для чайника. Берешь запускаешь билдер, кидаешь на форму 3 Edit'а и 1 Button.
Щелкаешь дважды по Button'у дабы создать событие по умолчанию(в данном случае OnClick или как в MFC (ON_WM_CLICK || ON_COMMAND)). Билдер тебе покажет код. Добавь #include <vector> и #include<string>, и using namespace std; Дальше вставь код процедуры, который я тебе привел. В обработчике события OnClick для Button1 напиши этот код:
Код:
void __fastcall TForm1::Button1Click(TObject *Sender)
{
string NOP;
string str1,str2;
str1 = Edit1->Text.c_str();
str2 = Edit2->Text.c_str();
NOP = getLongestCommonSubsequence(str1,str2);
Edit3->Text = NOP.c_str();
}
Если не понял, то привожу весь листинг.Имена Элементов: Button'ы Button1,Edit'ы: Edit1,Edit2,Edit3.
Код:
#include <vcl.h>
#include <vector>
#include <string>
using namespace std;
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------

string getLongestCommonSubsequence(const  string& a, const string& b)
    {
        vector<vector<int> > max_len;
        max_len.resize(a.size() + 1);
        for(int i = 0; i <= (int)a.size(); i++)
            max_len[i].resize(b.size() + 1);
        for(int i = (int)a.size() - 1; i >= 0; i--)
        {
            for(int j = (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<(int)a.size() && j<(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 __fastcall TForm1::Button1Click(TObject *Sender)
{
string NOP;
string str1,str2;
str1 = Edit1->Text.c_str();
str2 = Edit2->Text.c_str();
NOP = getLongestCommonSubsequence(str1,str2);
String str;
Edit3->Text = NOP.c_str();
}
//---------------------------------------------------------------------------
Вот так это делается. При твоих цифрах (10010101) и (010110110) ответ такой: 010101 - Это НОП короче. Надеюсь помог.
Ответить с цитированием
  (#5 (permalink)) Старый
viktorr viktorr вне форума
Новичок
 
Сообщений: 8
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.05.2010
По умолчанию 22.05.2010, 18:10

Спасиба оч помог (и угадал как раз для чайника) :upset:
Ответить с цитированием
Ads.
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
С помощью какой стандартной компоненты можно нарисовать график из двух массивов qqeeaaddzzcc C++ Builder 5 12.01.2009 23:05
Быстрый Алгоритм сравнения двух массивов AcerExtensa С/С++ 6 21.07.2008 11:38
Создание двух динамических массивов qqeeaaddzzcc С/С++ 6 23.05.2008 17:27
Объединение двух массивов Horror Алгоритмы 6 27.11.2007 18:01
Сравнение двух массивов в Excel'e edgar Visual Basic 2 20.08.2007 17:33
Конкатенация двух численных массивов Amputator Pascal 4 16.04.2006 20:01
TFileStream создание двух динамических массивов Ал-леша C++ Builder 3 01.06.2005 10:38
Как в масиве найти нужную последовательность Rider Вопросы начинающих программистов 3 24.05.2005 18:52
Обработка символьных и числовых массивов в TP Al'varis Вопросы начинающих программистов 1 08.03.2005 18:57
Требуется найти заданную последовательность в строке Pitch Lisp 1 10.10.2004 15:32
Несовместимость указателей двух- и одномерных массивов EiTRoN С/С++ 18 03.06.2004 13:26
Как найти симметричную последовательность на С++ axus Вопросы начинающих программистов 4 28.12.2003 16:50



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов