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

Thảo luận trong 'Thuật toán' bắt đầu bởi haihung_9x, 17 Tháng tư 2011.

  1. Offline

    haihung_9x

    • Friends

    • Chém gió đỉnh cao
    Số bài viết:
    353
    Đã được thích:
    271
    Điểm thành tích:
    220
    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.
    Mã:
    #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]<<" "; 
        } 
    }  
    KunMinziwithyou thích bài này.
  2. Offline

    trsa

    • Thành Viên Mới

    Số bài viết:
    180
    Đã được thích:
    15
    Điểm thành tích:
    0
    void tim(int *M, int n, int m){
    for(int i=0; i<n;i++)
    for(int j=0;j<m;j++)
    {
    if(M==M[j])
    cout<<M;
    }
    }

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

    lyvinhr00m

    • cụ lý

    Số bài viết:
    1.234
    Đã được thích:
    930
    Điểm thành tích:
    900


    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)
  4. Offline

    trsa

    • Thành Viên Mới

    Số bài viết:
    180
    Đã được thích:
    15
    Điểm thành tích:
    0
    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
    Mã:
    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ì
    lyvinhr00m thích bài này.

Chia sẻ trang này

Advertising: Linux system admin | nukeviet | nukeviet 4 | Upload ảnh miễn phí