Thuật toán tìm dãy con chung dài nhất..

[haihung_9x]

Sau đây là thuật toán tìm dãy con chung dài nhất. Nhưng nó vẫn còn sai nghĩa là tìm không hết các phần tử của dãy con chung dài nhất ( chưa xuất được dãy con chung dài nhất). Bạn nào kiểm tra dùm coi.

Vidu: nhập vào 2 dãy:
dãy a: 1,5,9,6,7,10,15,19
dãy b: 2,5,6,7,16,19,20,21

thì thuật toán của mình chỉ xuất được 6,7. Đúng phải là 5,6,7,19 mới đúng.

#include <iostream> 
using namespace std; 

void Nhap(int a[], int n) 
{ 
    for (int i = 0; i<n; i++) 
        cin>>a[i]; 
} 

void xuat(int a[], int n) 
{ 
    for (int i = 0; i<n; i++) 
        cout<<a[i]<<" "; 
} 

void Tim(int a[], int n, int x, int c[], int &t)
{
    t = 0;
    for (int i = 0; i<n; i++)
        if (a[i] == x)
        {
            c[t] = i;
            t++;
        }
}
int DayConChung(int a[], int n, int b[], int m, int &max)
{
    int k, j, l, spt, vt, t;
    int c[100];
    max = 0;
    for (int i = 0; i < n; i++)
    {
        Tim(b,m,a[i],c,t);
        for (l = 0; l < t; l++)
        {
            k = c[l];
            spt = 0;
            j = i;
            while ((j<n) && (k<m))
            {
                if (b[k] == a[j])
                {
                    spt++;
                    j++;
                    k++;
                }
                else
                    break;
            }
            if (spt>max)
            {
                vt = i;
                max = spt;
            }
        }
    }
    return vt;
}  
void main() 
{ 
    
    int a[100], b[100]; 
    int n,m, max; 
    cout<<"Nhap so phan tu cho day A: ";cin>>n;
    cout<<"Nhap gia tri cho day A"<<endl;
    Nhap(a,n); 
    cout<<"Nhap so phan tu cho day B: ";cin>>m;
    cout<<"Nhap gia tri cho day B"<<endl;
    Nhap(b,m); 
    xuat(a,n);cout<<endl;
    xuat(b,n);cout<<endl;
    int vt; 
    vt = DayConChung(a,n,b,m,max); 
    if (max == 0) 
        cout<<"Khong co day con chung"; 
    else 
    { 
        cout<<"Day con chung dai nhat la: "; 
        for (int i = 0; i<max; i++) 
            cout<<a[vt+i]<<" "; 
    } 
}

--------------------------------------------------
Xem các chủ đề cùng chuyên mục:

• Nhập một mảng, Trong khi nhập mảng được sắp xếp tăng dần 19/07/2009
• Nhập 1 chuỗi. Các chữ thường => hoa, các chữ hoa => thường rồi xuất ra 21/07/2009
• Bài Tập Hàm-Số Hoàn Hảo 21/05/2009
• tính tổng ma trận đê!!! 10/05/2009
• ".:'Định Nghĩa Giai Thừa':." 26/05/2009
• Nhập 1 dãy số nguyên, sau đó in ra các giá trị và chỉ số lớn hơn x 19/07/2009
• Liên quan đến ma trận. 14/05/2009
• Tính tần suất tập hai đây(ko giống như dùng con trỏ đâu) 14/05/2009
• Muốn học tốt C va C++ thì vào đây!!!! 14/05/2009
• Bài Tập Hàm-Tổ hợp 21/05/2009

+1 EXP

[trsa]

void tim(int *M, int n, int m){
for(int i=0; i<n;i++)
for(int j=0;j<m;j++)
{
if(M[i]==M[j])
cout<<M[i];
}
}

chừng đó là nó in kqua ok rồi

[lyvinhr00m]

void tim(int *M, int n, int m){
for(int i=0; i<n;i++)
for(int j=0;j<m;j++)
{
if(M[i]==M[j])
cout<<M[i];
}
}

chừng đó là nó in kqua ok rồi

Mình không bik là cách này đúng không, nhưng theo mình học trên lớp thì hình như không phải

VD: cho 2 day
a=(3,5,1,3,5,5,3)
b=(1,5,3,5,3,1)
Thì sẽ in ra kết quả là:
(5,3,5,3)or (1,3,5,3)or (1,5,5,3)

[trsa]

kết quả theo chuong trình trên là nguyên dãy a. nếu muốn lấy phần tử ko trùng thì chỉ cần thêm lệnh sau

int giao(int*&M1,int &n1,int*&M2,int&n2)
{    int *M3, d,i,j;
	for( i=1;i<=n1;i++)
	   for( j=1;j<=n2;j++)
             {
	      if(M1[i]==M2[j])
	        for(d=0;d<=i+j;d++)
	            M3[d]=M1[i];
                    break;     
              }
      return M3[d];
}
void boptutrung(int*&M,int &n)
{     int dem,i,j;
          for(i=0;i<n;i++)
             {   dem=i;
                  for(j=i+1;j<n;j++)
                    {
                       if(M3[i]==M3[j])
                           break;
                       else
                          dem=dem+1; 
                      }
                   if(dem==n-1) cout<<M1[i];
               }
}

hàm main gọi 2 hàm trên.

với chương trình này thì kết quả là (3,5,1).
Mình chưa chạy, bạn chạy thử đi, có lỗi gì thì nói hì