Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
Bảng giá phần mềm
Educations Software

Đại Lý - Chi Nhánh

Bản tin điện tử
 
Hỗ trợ trực tuyến
Hỗ trợ kỹ thuật
(Bùi Văn Khoa)
Trang thông tin hỗ trợ khách hàng
 
Đăng nhập/Đăng ký
Bí danh
Mật khẩu
Mã kiểm traMã kiểm tra
Lặp lại mã kiểm tra
Ghi nhớ
 
Quên mật khẩu | Đăng ký mới
 
Xem bài viết theo các chủ đề hiện có
  • Hoạt động của công ty (700 bài viết)
  • Sản phẩm mới (215 bài viết)
  • Dành cho Giáo viên (549 bài viết)
  • Lập trình Scratch (3 bài viết)
  • Mô hình & Giải pháp (156 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (127 bài viết)
  • Hỗ trợ khách hàng (486 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (242 bài viết)
  • Học tiếng Việt (183 bài viết)
  • Thông tin khuyến mại (79 bài viết)
  • Download - Archive- Update (289 bài viết)
  • Các Website hữu ích (70 bài viết)
  • Cùng học (92 bài viết)
  • Thông tin tuyển dụng (55 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (78 bài viết)
  • School@net 15 năm (154 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (124 bài viết)
  • Khám phá phần mềm (122 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (36 bài viết)
  • Phần mềm cho em (13 bài viết)
  • ĐỐ VUI - THƯ GIÃN (363 bài viết)
  • Các vấn đề giáo dục (1210 bài viết)
  • Bài học trực tuyến (1037 bài viết)
  • Hoàng Sa - Trường Sa (17 bài viết)
  • Vui học đường (275 bài viết)
  • Tin học và Toán học (220 bài viết)
  • Truyện cổ tích - Truyện thiếu nhi (180 bài viết)
  • Việt Nam - 4000 năm lịch sử (97 bài viết)
  • Xem toàn bộ bài viết (8179 bài viết)
  •  
    Thành viên có mặt
    Khách: 10
    Thành viên: 0
    Tổng cộng: 10
     
    Số người truy cập
    Hiện đã có 54206082 lượt người đến thăm trang Web của chúng tôi.

    Bài toán dãy con tăng – giảm dài nhất

    Ngày gửi bài: 04/11/2009
    Số lượt đọc: 4431

    1. Bài toán dãy con tăng – giảm dài nhất

    Bài toán tìm dãy con tăng-giảm dài nhất được phát biểu như sau: cho một dãy số nguyên (hoặc 1 dãy số, một xâu ..) gồm n phần tử. Hãy tìm một dãy con gồm các phần tử của dãy ban đầu (giữ nguyên thứ tự) sao cho các phần tử của dãy con đó tạo thành một dãy tăng-giảm dần và dài nhất có thể được. Các phần tử của dãy con dài nhất tìm được (nghiệm của bài toán) không nhất thiết phải là các phần tử liên tiếp trong dãy ban đầu. Vì việc tìm một dãy con tăng dài nhất cũng tương tự như việc tìm một dãy con giảm dài nhất nên chúng ta sẽ chỉ xem xét bài toán tìm dãy con dài nhất. Các kiến thức tương tự cũng sẽ được áp dụng cho bài toán tìm dãy con giảm dài nhất.

    Bài toán tìm dãy con tăng dài nhất là một trong các bài toán được nghiên cứu nhiều trong các lĩnh vực như toán học, thuật toán, lý thuyết vật lý.

    Ví dụ: Dãy ban đầu gồm các phần tử: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.

    Dãy con tăng dài nhất sẽ là: 0, 2, 6, 9, 13, 15.

    Có thể thấy rằng nghiệm của bài toán không là duy nhất, trong ví dụ trên chúng ta có hai nghiệm khác là: 0, 4, 6, 9, 11, 15 và 0, 2, 6, 9, 11, 15.

    Cách tiếp cận đầu tiên và không hiệu quả đối với bài toán này là duyệt qua các tập con của dãy ban đầu và kiểm tra các điều kiện: dãy tăng và dài nhất. Với một dãy n phần tử bạn sẽ cần duyệt hết 2n tập con của dãy và điều này là không thể dù với những giá trị n khá nhỏ. Cách tiếp cận đúng đắn với bài toán này là sử dụng kỹ thuật qui hoạch động.

    Trong bài báo này tôi sẽ trình bày với các bạn 3 thuật toán qui hoạch động để giải quyết bài toán LIS-LDS với độ phức tạp thời gian giảm dần.

    2.Sắp xếp mảng với hàm qsort() trong C/C++

    Trước hết là việc thực hiện sắp xếp một mảng (chúng ta sẽ cần dùng tới kiến thức này ở thuật toán thứ nhất) bằng hàm qsort() của C/C++. Để sắp xếp một mảng các phần tử có kiểu bất kỳ chúng ta chỉ cần cài đặt một hàm so sánh thứ tự giữa hai phần tử đó và gọi tới hàm qsort() (cài đặt thuật toán Quick sort) được cung cấp sẵn bởi C/C++.

    Ví dụ để sắp xếp một mảng số nguyên ta cần khai báo hàm so sánh hai số nguyên như sau:

    int cmp_function(const void *x, const void *y)

    {

    return (*(int*)(x)) - *((int*)(y)); // chuyển các con trỏ x và y thành con trỏ int *

    }

    Sau đó khi cần sắp xếp mảng a có n phần tử chúng ta sẽ gọi hàm qsort() theo cú pháp sau:

    qsort(a, n,sizeof(int), cmp_function); // sizeof(int) là kích thước 1 phần tử của mảng a.

    Việc cung cấp hàm so sánh để có thể làm việc với các kiểu dữ liệu khác dành lại cho các bạn độc giả như một bài tập nhỏ.

    3.Bài toán tìm dãy con chung (LCS) của hai dãy

    Đây là một bài toán khá phổ biến trong tin học, nhất là khi chúng ta học về qui hoạch động. Mục đích của bài toán là đi tìm dãy con chung (gồm 1 số phần tử) của hai dãy ban đầu có độ dài lớn nhất. Gọi hay dãy ban đầu là a gồm n phần tử và b gồm m phần tử (đánh chỉ số từ 0), chúng ta sẽ sử dụng các mảng hai chiều ret[][] và path[][] để lưu độ dài lớn của dãy con tìm được và giá trị truy hồi (mảng path) để tính ngược lại dãy con kết quả theo công thức sau:

    Mỗi phần tử ret[i][j] sẽ là độ dài xâu con lớn nhất tương ứng với các dãy ban đầu a[0..i-1] và b[0..j-1], ban đầu các phần tử của mảng ret[][] sẽ được khởi tạo bằng 0.

    Giá trị độ dài dãy con LCS lớn nhất được lưu tại biến ret[n][m] và đường đi sẽ được tính lại dựa trên giá trị của các biến path[i][j].

    Để tìm hiểu kỹ hơn về thuật toán cho bài toán LCS các bạn có thể tham khảo trên các bài báo của tạp chí “Tin học và Nhà trường” các số trước đây.

    Ở đây tôi xin đưa ra cài đặt cụ thể với ngôn ngữ C++ và dữ liệu demo cho bài toán LCS như sau:

    #include

    using namespace std;

    const int MAXMN = 100;

    int ret[MAXMN][MAXMN];

    int path[MAXMN][MAXMN];

    int lcs(int a[], int n, int b[], int m);

    void print_lcs(int a[], int i, int j);

    int main()

    {

    int a[] = {1, 8, 2, 3, 18, 2, 6, 9};

    int n = sizeof(a)/sizeof(int);

    int b[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};

    int m = sizeof(b)/sizeof(int);

    cout << lcs(a, n, b, m) << endl;

    print_lcs(b, n, m);

    system("pause");

    return 0;

    }

    int lcs(int a[], int n, int b[], int m)

    {

    int i, j;

    int v;

    memset(ret, 0, sizeof(ret));

    for(i=1;i<=n;++i)

    for(j=1;j<=m;++j)

    {

    if(a[i-1]==b[j-1])

    {

    v = ret[i-1][j-1] + 1;

    path[i][j] = 0; // DIAG

    }else if(ret[i-1][j]>ret[i][j-1])

    {

    v = ret[i-1][j];

    path[i][j] = 1; // UP

    }else

    {

    v = ret[i][j-1];

    path[i][j] = 2; // LEFT

    }

    ret[i][j] = v;

    }

    return ret[n][m];

    }

    void print_lcs(int a[], int i, int j)

    {

    if(i==0||j==0)

    return;

    if(path[i][j]==0)

    {

    print_lcs(a, i-1, j-1);

    cout << a[i-1] <<" ";

    }else

    if(path[i][j]==1)

    print_lcs(a, i-1, j);

    else

    print_lcs(a, i, j-1);

    }

    Cài đặt trên của bài toán LCS có 2 vòng lặp chính nên dễ thấy độ phức tạp thuật toán là T(n, m) = O(n*m).

    4.Thuật toán 1: tìm dãy LIS-LDS dựa vào bài toán LCS

    Chúng ta sẽ xem xét thuật toán thứ nhất cho bài toán, thuật toán này dựa trên ý tưởng sau: nếu a là dãy ban đầu và b là kết quả của việc sắp xếp dãy a thì LIS của dãy a chính là LCS của dãy a và dãy b.

    Cụ thể với cài đặt của bài toán LCS ở phần 3 chúng ta sẽ có thêm các hàm sau phục vụ cho việc tìm LIS của mảng a:

    int cmp_function(const void *x, const void *y)

    {

    return (*(int*)(x)) - *((int*)(y));

    }

    int get_lis1(int a[], int n)

    {

    int * b = new int[n];

    int i;

    for(i=0;i

    b[i] = a[i];

    qsort(b, n,sizeof(int), cmp_function);

    return lcs(a, n, b, n);

    }

    Để in ra nghiệm của bài toán chúng ta gọi tới hàm print_lcs() với các tham số là mảng a và n như sau: print_lcs(a, n, n);

    Do thuật toán sắp xếp Quick sort có độ phức tạp là O(nlogn) và thuật toán cho bài toán LCS cho hai mảng a, b có độ phức tạp là O(n*n) = O(n2) nên thuật toán 1 có độ phức tạp là O(n2).

    5.Thuật toán 2: tìm dãy LIS-LDS với độ phức tạp O(n2)

    Chúng ta sẽ xem xét một thuật toán qui hoạch động tốt hơn cho bài toán LIS, lần này chúng ta sẽ sử dụng một mảng 1 chiều d[] để lưu độ dài dãy LIS của mảng a theo công thức truy hồi sau:

    d[i] lưu giá trị LIS của mảng a[0..i], ban đầu d[i] = 1 với mọi i, nghiệm của bài toán sẽ là giá trị max của mảng d sau khi đã tính toán xong cho các giá trị i=0..n-1.

    Để có thể tìm lại được nghiệm chúng ta dùng một mảng prev[] để dánh dấu mỗi điểm mà d[i] = d[j] + 1, khi đó prev[i] = j, ban đầu các phần tử của mảng prev[] đều bằng -1. Việc in nghiệm được thực hiện bằng 1 hàm đệ qui dựa trên giá trị của mảng prev[] và vị trí cuối cùng của nghiệm (phần tử cuối cùng của dãy LIS tìm được) được lưu ở biến lasti.

    Cài đặt cụ thể bằng C++ như sau:

    #include

    using namespace std;

    const int MAXN = 100;

    int a[] = {9,2,5,3,7,11,8,10,13,2}; // data array

    int prev[MAXN];

    int lasti = 0;

    int get_lis0(int a[], int n);

    void print_lis(int a[], int n, int lasti);

    int main()

    {

    int n = sizeof(a)/sizeof(int);

    int i;

    cout << "Mang ban dau:
    ";

    for(i=0;i

    cout << a[i] << " ";

    cout << "
    So phan tu cua LIS:" << get_lis2(a, n) << endl;

    print_lis(a, n, lasti);

    system("pause");

    return 0;

    }

    int get_lis2(int a[], int n)

    {

    int * d = new int [n]; // hold max lis length of i location

    int i, j;

    int temp;

    for(i=0;i

    {

    prev[i] = -1;

    d[i] = 1;

    }

    for(i=1;i

    {

    // recalculate d[i];

    temp = d[i];

    for(j=i-1;j>=0;--j)

    if(a[i]>a[j]&&d[j]+1>temp)

    {

    prev[i] = j;

    temp = d[j]+1;

    }

    d[i] = temp;

    }

    temp = d[0];

    for(i=0;i

    if(d[i]>temp)

    {

    lasti = i;

    temp = d[i];

    }

    return temp;

    }

    void print_lis(int a[], int n, int lasti)

    {

    if(prev[lasti]!=-1)

    print_lis(a, n, prev[lasti]);

    cout << a[lasti] << " ";

    }

    Đoạn thực hiện chính của thuật toán là vòng lặp for với biến i và vòng lặp for với biến j nên độ phức tạp của thuật toán là T(n) = O(n2). Tuy nhiên có thể thấy rõ là thuật toán thứ hai này nhanh hơn và hiệu quả hơn về bộ nhớ so với thuật toán thứ nhất.

    6.Thuật toán 3: tìm dãy LIS-LDS với độ phức tạp O(nlogn)

    Chúng ta sẽ xem xét thuật toán tốt hơn cho bài toán LIS với độ phức tạp O(nlogn). Thuật toán sử dụng mảng d[] để lưu các phần tử của nghiệm (chính là LIS tìm được ở mỗi bước), d[k] sẽ là giá trị nhỏ nhất của dãy LIS gồm k phần tử tìm được ở một bước của bài toán, một mảng ind[] sẽ được sử dụng để lưu chỉ số của các phần tử của mảng d[] trong mảng a[] ban đầu, một mảng lasti[] sẽ được sử dụng để lưu giá trị nhỏ hơn đứng ngay trước a[i] trong mỗi bước của thuật toán.

    Ví dụ với mảng ban đầu a[] = {9, 2, 5, 3, 7, 11, 8, 10, 13, 6} chúng ta sẽ có:

    Tiếp theo chúng ta sẽ có:

    Có thể thấy nghiệm trong trường hợp này là 2, 3, 7, 8, 10, 13. Thuật toán sẽ có một vòng lặp với biến i chạy từ phần tử đầu tiên của mảng ban đầu cho tới hết, mỗi bước chúng ta sẽ sử dụng thuật toán tìm kiếm nhị phân để tìm vị trí của phần tử a[i] trong mảng d, sau đó cập nhật lại các giá trị của các phần tử trong mảng ind và lasti. Cụ thể thuật toán được cài đặt như sau:

    #include

    using namespace std;

    const int MAXN = 100;

    int get_lis3(int a[], int n);

    void print(int i);

    int last;

    int ind[MAXN]; // backtrack array

    int lasti[MAXN]; // backtrack array

    int a[] = {9, 2, 5, 3, 7, 11, 8, 10, 13, 6}; // data array

    int main()

    {

    int n = sizeof(a)/sizeof(int);

    cout << "Do dai LIS tim duoc:" << get_lis3(a, n) << endl;

    cout << "Nghiem:
    ";

    print(last);

    system("pause");

    return 0;

    }

    int get_lis3(int a[], int n)

    {

    // mang d: luu mang gia tri cua day LIS/LDS

    // mang ind: luu vi tri cua cac phan tu d[i] trong mang a

    // mang lasti: luu vi tri phan tu nho hon dung ngay truoc a[i]

    int i, l, r, m, len, index;

    int * d = new int [n];

    d[0] = a[0];

    len = 1;

    ind[0] = 0;

    lasti[0] = -1;

    last = 0;

    for (i=1; i

    if (a[i] > d[len-1]) {

    index = len;

    last = i;

    len += 1;

    } else {

    l = 0;

    r = len-1;

    while(l<=r)

    {

    m = l+(r-l)/2;

    if(d[m]>=a[i])

    r = m-1;

    else

    l = m+1;

    }

    if (d[l] >= a[i])

    index = l;

    else

    index = r;

    }

    d[index] = a[i];

    ind[index] = i;

    if(index==0)

    lasti[i] = -1;

    else

    lasti[i] = ind[index-1];

    }

    delete []d;

    return len;

    }

    void print(int i)

    {

    if(lasti[i]==-1)

    {

    cout << a[i] << " ";

    return;

    }

    print(lasti[i]);

    cout << a[i] << " ";

    }

    Vòng lặp chính của thuật toán chạy với n bước, mỗi bước thực hiện tìm kiếm nhị phân trên mảng d có không quá i phần tử nên thuật toán sẽ có độ phức tạp T(n) = O(nlogn). Đây là thuật toán hiệu quả nhất cho bài toán LIS-LDS.

    Mặc dù đã hết sức thận trọng và xem xét kỹ lưỡng các ví dụ đưa ra trong bài viết, tuy vậy vẫn có thể không tránh khỏi các sai sót, rất mong nhận được sự đóng góp ý kiến của các bạn độc giả. Mọi góp ý, thắc mắc xin gửi về địa chỉ email: tuannhtn@yahoo.com.

    School@net (Theo THNT)



     Bản để in  Lưu dạng file  Gửi tin qua email


    Những bài viết khác:



    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 1407 - Nhà 17T2 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Điện thoại: (04) 62511017 - Fax: (04) 62511081
    Email: school.net@hn.vnn.vn


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.