Thuật toán tìm dãy có độ dài lớn nhất

[comeonbaby]

hiz hiz đề bài cho thế này : nhập 1 mảng số nguyên rồi tìm tìm dãy tăng dài nhất và in ra màn hình T_T . (dãy tăng dài nhất là dãy mà nó cứ tăng liên tục ý vd: 3 4 2 5 6 7 2 3 4 : ở đây có 3 dãy ,dãy 1 là 3-4,dãy 2 là 2-7 và dãy 3 là 2-4 suy ra dãy tăng dài nhất là dãy 2-7) .Các bạn giúp mình thuật toán cho bài này với mình không biết cách làm nó.

[rox_rook]

Bài này có trong sách vở rất nhiều, bạn nên vào box giải thuật tìm tài liệu của giải thuật của tác giả Lê Minh Hoàng sẽ có ngay, nhưng thôi mình cũng rảnh nên giúp bạn luôn^^. Bài này là 1 bài tiêu biểu của kĩ thuật quy hoạch động. Nếu dùng quay lùi thì vẫn ra nhưng có lẽ thời gian tính toán sẽ lâu hơn. Giải thuật ở đây mình nêu ra là trong sách vở cả nhưng mình sẽ giải thích theo mình hiểu để cho bạn dễ hiểu :


Xét dãy sau :
Đúng là mãng của C++ bắt đầu tại 0 nhưng chừa lại phần tử đầu tiên là 1 mẹo để tiện cho việc tính toán thôi. Dãy A[] sau có size = 12 nhưng ta chỉ xét 11 phần tử.
A[] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]
1 2 3 8 9 4 5 6 20 9 10

Ta sẽ gán A[0] = -oo, và A[size+1] = +oo ( cái này chỉ là mẹo để tính toán, bạn làm nhiều sẽ có kinh nghiệm thôi)
Bây h ta gọi max_length[i] với ý nghĩa là : độ dài của dãy con tăng dài nhất bắt đầu tại A[i], ta có 2 lưu sau :
- max_length[size+1] = 1, vì nó chỉ có 1 phần tử ( tính qua phải ) vậy thì nó bằng 1.
Ta sẽ dùng 2 vòng lặp để tính các giá trị cho max_length[] :
Lần 1 : ta cứ xét 1 phần tử với phần tại vị trí A[i] đến A[size] tức là giả sử đang xét :
<- ( xét theo chiều mũi tên )
1 2 3 8 9 4 5 6 20 9 10
Thì ta chỉ xét 6 với :
1 2 3 8 9 4 5 6 20 9 10

Bây tính sẽ như sau :
- Nếu mà A[i-1] > A[i] tức là nó không tăng : vậy độ dài giữ nguyên
- Ngược lại thì độ dài tăng lên 1.
- Và điều nữa là độ dài phải là dài nhất tức là khi ta xét ta sẽ thêm điều kiện nếu : dãy con đang xét có phải là tăng dài hơn dãy con trước đó không , nếu dài hơn thì ta giữ lại dãy mới không thì vẫn như nguyên .

1 2 3 8 9 4 5 6 20 9 10

Giả sử đang xét tới dãy con có màu đỏ gồm (A[11], A[10]), xét tới A[9] = 20 vậy điều kiện không thoả điều kiện A[i-1] < A[i] vậy thì ta giữ nguyên giá trị độ dài max_length[] lúc này = 2. Xét tiếp
1 2 3 8 9 4 5 6 20 9 10
Nếu chỉ xét tới
1 2 3 8 9 4 5 6 20 9 10

thì max_length vẫn chưa thay đổi, nhưng nếu xét thêm phần tử A[7] = 5 nữa thì nó sẽ thay đổi vì 3 > 2(^^)
Và cuối cùng là tau sẽ dùng 1 mãng phụ trace[i] để lưu lại dãy con bắt đầu từ bắt đầu từ trace[0] và kết thúc tại A[size+1]
có thể hình dung như sau :
Phần tử 1 : trace[0];
Phần tử 2 : trace[trace[0]]
phần tử 3 : trace[trace[trace[0]]]...

Code bài này cũng đơn giản, bạn đọc xong sẽ hiểu, chịu khó in ra cái bước thao tác của các mãng ( max_length[], và trace[] ) bạn sẽ hiểu kĩ nó hơn.

#include <iostream>
#include <iomanip>

using namespace std;

const static int maxx = 1000;

int array[maxx], 
    max_length[maxx], 
    trace[maxx];
int size;

void EnterData()
{       
    cout << "Enter the length of array: ";
    cin >> size;
    for (int x = 1; x <= size; x++)
    {
        cout << "The element [" << x << "] :"; 
        cin >> array[x];
    }
}

void Initialization()
{
    for(int x = 0; x <= size; x++)
    {
        array[x] = 0;
        max_length[x] = 0;
        trace[x] = 0;
    }
    //Thêm 2 phần tử : A[0] = -oo, A[size+1] = +oo
    array[0] = -1000;
    array[size+1] = 1000;
    max_length[size+1] = 1; // Cơ sở Quy hoạch động.
}

void Solving_by_dynamic_programming()
{
    int indice;
    //Xét từ phần tử cuối đi ngược về <---
    for (int x = size; x >= 0; x--)
    {
        indice = size + 1;
        //Xét từ vị trí hiện tại --> đến cuối dãy
        for (int y = x + 1; y <= size + 1; y++)
        {
            //Nếu dãy tăng và có độ dài lớn hơn
            if (array[y] > array[x] && max_length[y] > max_length[indice])
            {
                indice = y;//vì tăng nên ta phải lưu lại vị trí này
            }
            //Khi câu lệnh if trên thoả thì chỗ này sẽ tăng lên cho vị trí đó
            //in ra mãng length[x] bản sẽ hiểu rõ hơn.
            max_length[x] = max_length[indice] + 1;
            trace[x] = indice;//lưu giá trị cuối dãy con đó
        }
    }
}

void Trace_element()
{
    cout << "\n\n";
    cout << "\nThe maximum length: " << max_length[0]-2; //Trừ đi 2 phần tử thêm vào
    cout << "\n\n";
    //Bắt đầu từ vị trí đầu tiên   
    int position = trace[0];
    while (position != size+1)
    {
        cout << "--> array[" << position << "] = " << array[position];
        position = trace[position]; //Truy phần tử kế tiếp
        cout << endl;
    }
}

int main()
{
    Initialization();
    EnterData();
    Solving_by_dynamic_programming();
    Trace_element();
   
    return 0;
} 

[nguyenthanhhungcntt]

hiz hiz đề bài cho thế này : nhập 1 mảng số nguyên rồi tìm tìm dãy tăng dài nhất và in ra màn hình T_T . (dãy tăng dài nhất là dãy mà nó cứ tăng liên tục ý vd: 3 4 2 5 6 7 2 3 4 : ở đây có 3 dãy ,dãy 1 là 3-4,dãy 2 là 2-7 và dãy 3 là 2-4 suy ra dãy tăng dài nhất là dãy 2-7) .Các bạn giúp mình thuật toán cho bài này với mình không biết cách làm nó.

Code của bài toán bạn yêu cầu đây:

    #include<conio.h>    #include<stdlib.h>    #include<stdio.h>    #include<iostream.h>    #define duongvocung 3200    #define amvocung -3200    int n,i,j,l[100],a[100];    static int k,max,jmax;    // k danh dau vi tri phan tu bat dau cua day con tang lon nhat    // n la do dai cua day    //l la mang chua do dai lon nhat cua tung phan tu khi tinh tu  cuoi day    // a la mang chua cac  phan tu     void nhap(){     clrscr();     cout<<"Dynamic prigramming\n";     cout<<"\n";      cout<<"\n";      cout<<"\n";      cout<<"\n";    cout<<"Tim day con tang dai nhat cua mot day\n\n\n\n\n\nSo phan tu cua day la:";    cin>>n;    cout<<"\n\n\n\n\n";    cout<<"Nhap cac phan tu cua day:\n";    for(i=1;i<=n;i++)    cin>>a[i];    }     //////////////////////////////////////////    /// day la ham tim do dai day con tang lon nhat    void tinh_f()    {    a[n+1]=duongvocung;//a[n+1]=3200 phan tu duong vo cung    l[n+1]=1;//do dai phan tu duong vo cung la 1    a[0]=amvocung;//a[0]=-3200 phan tu am vo cung    for(i=n;i>=0;i--)    {    jmax=n+1;    for(j=n+1;j>=i+1;j--)    if(a[i]<a[j]&&l[j]>=l[jmax])        {        jmax=j;    l[i]=l[j]+1;     }      }       }       ///////////////////////////////////////////////////////////////////////       // ham xemday()in ra day ban da nhap       void xemday(){      for(i=1;i<=n;i++)      cout<<" "<<a[i];      }      ////////////////////////////////////////////////      //ham tim_max() in ra do dai day con tang lon nhat          void tim_max(){      int t=0;      max=l[1];      for(i=1;i<=n;i++)        if(max<=l[i]){        max=l[i];        k=i;    }    for(i=k;i<=n;i++)     if(max-l[i]==t&&a[i]>=a[k])    {    cout<<" "<<a[i];    t++;    }     }///////////////////////////////////////////////////////////////////    void main(){    nhap();    cout<<"day ban da nhap:\n";    xemday();    cout<<"\n";    tinh_f();    cout<<"day ket qua la:\n";    tim_max();    getch();}

[thangtcnb]

Bài của bạn nguyenthanhhung bị sai rồi. Bạn coi lại xem, khi mình chạy chương trình cho ra như thế này.
Dynamic prigramming




Tim day con tang dai nhat cua mot day





So phan tu cua day la:10





Nhap cac phan tu cua day:
1
2
1
2
1
3
5
7
3
6
day ban da nhap:
1 2 1 2 1 3 5 7 3 6
day ket qua la:
1 2 3 5 7

Đáng ra dãy xuất ra phải là: 1 3 5 7

[thangtcnb]

Bạn rõ_rock cũng sai luôn. Mình đã test và cho ra kq như sau:
Enter the length of array: 10
The element [1] :1
The element [2] :2
The element [3] :1
The element [4] :3
The element [5] :4
The element [6] :5
The element [7] :1
The element [8] :2
The element [9] :1
The element [10] :2



The maximum length: 4

--> array[1] = 1
--> array[2] = 2
--> array[4] = 3
--> array[5] = 4
--> array[6] = 5


Đáng lẽ dãy ở đây phải là: 1 3 4 5

[rox_rook]

Oops ^^! Đọc đề không kĩ ! sorry !Nếu đề bài như trên thì đơn giản hơn nhiều
Fixed

#include <iostream>
#include <fstream>

using namespace std;
class Array
{
    public :
        Array();
       ~Array();
        void search_longest_segment();
        friend ostream &operator << (ostream &, const Array &);
        friend istream &operator >> (istream &, Array &);
   
    private :
        int *ptr;
        int position, max_length;
        int size;
};

Array::Array():size(10)
{
    ptr = new int[size + 1];
    for(int x = 0; x < size; x++){
        *(ptr + x) = 0;
    }
    ptr[size] = 10000;//khởi tạo phần tử lính canh
    position = 0;          
    max_length = 1;
}

Array::~Array()
{
    delete[] ptr;
}

istream &operator >> (istream &input, Array &obj)
{
    cout << "Size of array : ";
    input >> obj.size;
    for (int x = 0; x < obj.size; x++){
        cout << "The element [" << x << "] :"; 
        input >> obj.ptr[x];
    }
    return input;
}

ostream &operator << (ostream &output, const Array &obj)
{
    output << "Maximum length of sub-segment : " << obj.max_length << endl;
    output << "End position : " << obj.position << endl;
    for (int x = obj.position; x >= (obj.position - obj.max_length + 1); x--){
        output << "The element [" << x << "] :" << obj.ptr[x] << endl; 
    }
    return output;
}

void Array::search_longest_segment()
{
    int count = 1;    
    for(int x = position; x < size; x++){
        if(ptr[x+1] > ptr[x]){ //Nếu dãy tăng 
            count++;             //tăng độ dài
            if(count >= max_length){ //nếu lớn hơn độ dài trước đó
                max_length = count;
                position = x + 1;
            }
        }
        else{//Dãy không tăng, cập nhật lại biếm đếm
            count = 1;
            position = x; //Bắt đầu từ vị trí x
        }
    }
}

int main()
{
    Array problem;
    cin >> problem;
    problem.search_longest_segment();
    cout << problem;

    return 0;
} 

[nguyenthanhhungcntt]

Bài của bạn nguyenthanhhung bị sai rồi. Bạn coi lại xem, khi mình chạy chương trình cho ra như thế này.
Dynamic prigramming




Tim day con tang dai nhat cua mot day





So phan tu cua day la:10





Nhap cac phan tu cua day:
1
2
1
2
1
3
5
7
3
6
day ban da nhap:
1 2 1 2 1 3 5 7 3 6
day ket qua la:
1 2 3 5 7

Đáng ra dãy xuất ra phải là: 1 3 5 7

Không sai đâu bạn ạ
bạn đã hiểu nhầm định nghĩa 1 dãy con rồi.Theo mình hiểu thì bạn hiểu là dãy con là 1 dãy mà các phần tử của chúng phải liền nhau. Còn theo mình hiểu là dãy con là dãy mà các phần tử trong day theo đúng tứ tự trong dãy mẹ mà không nhất thiết phải liền nhau. Nếu hiểu theo cách của bạn thì có lẽ code còn dễ hơn rất nhiều.thanks

[thangtcnb]

Ặc ặc, bạn dùng chương trình nào để biên dịch vậy. Mình dùng VC6.0 để biên dịch thì nó báo tới 47 errors.
Với lại hàm của bạn mình ko hiểu rõ chỗ này.

Array::Array():size(10)
{
    ptr = new int[size + 1];
    for(int x = 0; x < size; x++){
        *(ptr + x) = 0;
    }
    ptr[size] = 10000;//khởi tạo phần tử lính canh
    position = 0;          
    max_length = 1;
}

Bạn có thể giải thích rõ hơn được ko???

[thangtcnb]

Không sai đâu bạn ạ
bạn đã hiểu nhầm định nghĩa 1 dãy con rồi.Theo mình hiểu thì bạn hiểu là dãy con là 1 dãy mà các phần tử của chúng phải liền nhau. Còn theo mình hiểu là dãy con là dãy mà các phần tử trong day theo đúng tứ tự trong dãy mẹ mà không nhất thiết phải liền nhau. Nếu hiểu theo cách của bạn thì có lẽ code còn dễ hơn rất nhiều.thanks

Mình chỉ hiểu theo đề bài thôi. Chính xác là đề bài là tìm dãy con tăng thì khi bạn xuất ra phải là dãy con của dãy mẹ và dãy con phải là dãy tăng. Mình không hiểu làm như thế nào là đơn giản. Bạn có thể hướng dẫn rõ hơn được ko?

[rox_rook]

Ừ ! thangtcnb hiểu đúng rồi đó ! Đúng là cách của bạn nguyênthanhhungcntt không sai nhưng lại sai nếu đề bài chính là ví dụ mà comeonbaby đưa ra
Mình dùng TC, Visual 2005 và Dev-cpp. Do mình không có VC6 nên ko debug được. Mà do mình xài class nên nhìn nó rối răm, để mình sữa lại cho đơn giản.
Trả lời luôn cho bạn :

ptr[size] = 10000;//khởi tạo phần tử lính canh

Thực ra chỗ này là gán cho nó 1 giá trị + vô cực thôi ( có thể thêm header file #include<limits> )
sữa thành INT_MAX cũng được. Còn tại sao mình dùng lính canh thì bạn để ý câu lệnh này sẽ hiểu :

 for(int x = position; x < size; x++){
        if(ptr[x+1] > ptr[x]){ //Nếu dãy tăng 

Lúc x = size nó sẽ so sánh với ptr[size+1], vậy nếu không có phần tử lính canh thì ta phải thêm 1 câu lệnh điều kiện gì đó ( đại khái giải quyết 1 ngoại lệ này, vậy thì mình dùng lính canh để cho đỡ xét thôi )

Array::Array():size(10)

Cái này là bộ khởi tạo ( gọi là initializer ) ý nói thằng dấu 2 chấm sau constructor á. Nếu khởi tạo cho thành viên có thuộc tính const thì bắt buộc phải dùng nó, nhưng nếu không phải const thì cũng không sao. Mình để vậy cho gọn thôi còn nếu không thì :

Array::Array()//:size(10)
{
    size = 10; ( Để nó ở đây )
    ptr = new int[size + 1];
    for(int x = 0; x < size; x++){
        *(ptr + x) = 0;
    }
    ptr[size] = 10000;//khởi tạo phần tử lính canh
    position = 0;          
    max_length = 1;
} 

Đây mình viết lại không dùng class cho bạn dễ đọc, nếu bạn còn gì thắc mắc mình sẽ giải thích. Thân !

#include <iostream>
#include <fstream>
#include <limits>//for INT_MAX

using namespace std;

void Read_input_from_user_and_Initialization();
void Search_longest_segment();
void Print_result();
void Reclaim_memory();

int *ptr;
int position, 
    max_length,
    size;
    
int main()
{
    Read_input_from_user_and_Initialization();
    Search_longest_segment();
    Print_result();
    Reclaim_memory();

    system("pause");
    return 0;
}  

void Read_input_from_user_and_Initialization()
{
    cout << "Size of array : ";
    cin >> size;
    ptr = new int[size + 1];
    for (int x = 0; x < size; x++){
        cout << "The element [" << x << "] :"; 
        cin >> ptr[x];
    }
    
    ptr[size] = INT_MAX;//kho+?i ta.o pha^`n tu+? lính canh
    position = 0;          
    max_length = 1;
}

void Print_result() 
{
    cout << "\nMaximum length of sub-segment : " << max_length - 1 << endl;
    cout << "End position : " << position << endl;
    for (int x = position - 1; x >= (position - max_length + 1); x--){
        cout << "The element [" << x << "] :" << ptr[x] << endl; 
    }
}

void Search_longest_segment()
{
    int count = 1;    
    for(int x = position; x < size; x++){
        if(ptr[x+1] > ptr[x]){ //Ne^'u dãy ta(ng 
            count++;             //ta(ng ?o^. dài
            if(count >= max_length){ //ne^'u lo+'n ho+n ?o^. dài tru+o+'c ?ó
                max_length = count;
                position = x + 1;
            }
        }
        else{//Dãy không ta(ng, ca^.p nha^.t la.i bie^'m ?e^'m
            count = 1;
            position = x; //Ba('t ?a^`u tu+` vi. trí x
        }
    }
}

void Reclaim_memory()
{
    delete[] ptr;
    ptr = NULL;
}