+ Trả lời chủ đề
Results 1 to 2 of 2

Chủ đề: Dãy con chung không liền kề dài nhất

  1. #1
    Senior Member itoa's Avatar
    Gia nhập
    03-2010
    Bài viết
    184
    Cảm ơn
    89
    Được cảm ơn 65 lần trong 47 bài
     

    Dãy con chung không liền kề dài nhất

    Dãy C = c1, c2, ..., ck là dãy con không liền kề của dãy A = a1, a2, ..., am nếu C có thể nhận được bằng cách chọn một dãy các phần tử không liền kề của A, nghĩa là tìm dược dãy các chỉ số i1, i2, ..., ik sao cho:

    1 ≤ i1, i2, ..., ik ≤ m;
    i1 < i2 - 1, i2 < i3 - 1, ..., ik - 1 < ik - 1;
    c1 = ai1, c2 = ai2, ck = aik.

    Ta gọi độ dài của dãy số là số phần tử của nó.

    Cho hai dãy:
    A = a1, a2, ..., am

    B = b1, b2, ..., bn

    Dãy C được gọi là dãy con chung không liền kề của hai dãy A và B nếu như nó vừa là dãy con không liền kề của A, vừa là dãy con không liền kề của B.

    Yêu cầu

    Cho hai dãy số A và B. Hãy tìm dãy con chung không liền kề dài nhất của hai dãy đã cho.
    Vd: a[] = 1 9 7 3 4 6 5 7 3 9 9 9
    b[] = 4 9 2 4 7 5 8 9 6 3 9 1
    => c[] = 9 4 5 9 9

  2. #2
    Senior Member itoa's Avatar
    Gia nhập
    03-2010
    Bài viết
    184
    Cảm ơn
    89
    Được cảm ơn 65 lần trong 47 bài
     
    PHP Code:
    #include <iostream>
    #include <conio.h>
     
    using namespace std;
    //dung quy hoach dong do phuc tap 0(m*n)

    /*ki hieu Xi = <x1,x2,...,xi>.
    f[i][j] la do dài cua dãy con chung không lien ke dài nhat 
    cua hai dãy a[i] và b[j]. */
    void lnacs(int mint nint *aint *b,  int **f)
    {
        for (
    int i 1<= mi++)
        {
            for (
    int j 1<= nj++)
                if (
    a[i] == b[j])
                   
    f[i][j] = f[2][2] + 1;

                else
                    if (
    f[1][j] >= f[i][1])
                       
    f[i][j] = f[1][j];
                    else
                        
    f[i][j] = f[i][1];

        }
     }
     
     
    int main()
    {
        
    //khoi tao, cap phat bo nho
        
    int mn, *a, *b, **f, *kq;
        
    freopen("data.txt","r",stdin); //doc tu file
        
    cin>>m>>n;
        
    = new int[1];
        
    = new int[1];
        
    = new int*[2];
        
    kq = new int[1];
        
        for (
    int i = -1<= mi++)
            
    f[i] = new int[1];
     
         for (
    int i = -1<= mi++)
             for (
    int j = -1<= nj++)
                 
    f[i][j] = 0;

              
        
    a[0] = b[0] = 0;
        for (
    int i 1<= mi++)
            
    cin>>a[i];
        for (
    int i 1<= ni++)
            
    cin>>b[i];
    //
        
    lnacs(mnabf);
        
    //in de kt mang f
           
    for (int i 0<= mi++)
            {
                 for (
    int j 0<= nj++)
                 
    cout<<f[i][j]<<" ";
                 
    cout<<endl;
            }
            
    //truy vet tim day con chung
        
    int k 1;
        
    int i mint j n;
        while (
    >= && >= 1)
        {
              if (
    a[i] == b[j])
              {
                       
    kq[k] = a[i];
                       
    1;
                       
    1;
                       
    1;
              }
              else
                  if (
    f[i][j] == f[i][1])
                     
    1;
                  else
                      
    1;
        }
        
    cout<<endl<<endl;
        for (
    int i 1>= 1i--)
            
    cout<<kq[i]<<" ";              
      
        
    cout<<endl;
        
    cout<<f[m][n];
        
    getch(); 
        
    //giai phong bo nho
        
    delete []a;
        
    delete []b;
        
    delete []kq;
        for (
    int i = -1<= mi++)
            
    delete []f;
        return 
    0;


+ Trả lời chủ đề

Thông tin chủ đề

Users Browsing this Thread

Hiện có 1 người đang xem chủ đề này. (0 thành viên và 1 khách)

     

Những thành viên đã đọc chủ đề này : 1

You do not have permission to view the list of names.

Các quyền đăng bài

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts