Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 18 kết quả

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

  1. #1
    Ngày gia nhập
    11 2007
    Bài viết
    154

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

    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ó.

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,918

    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.
    PHP Code:

    #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<= sizex++)
        {
            
    cout << "The element [" << << "] :"
            
    cin >> array[x];
        }
    }

    void Initialization()
    {
        for(
    int x 0<= sizex++)
        {
            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>= 0x--)
        {
            
    indice size 1;
            
    //Xét từ vị trí hiện tại --> đến cuối dãy
            
    for (int y 1<= size 1y++)
            {
                
    //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;


  3. #3
    Ngày gia nhập
    11 2006
    Bài viết
    6

    Trích dẫn Nguyên bản được gửi bởi comeonbaby Xem bài viết
    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:


    C++ Code:
    1.     #include<conio.h>
    2.     #include<stdlib.h>
    3.     #include<stdio.h>
    4.     #include<iostream.h>
    5.     #define duongvocung 3200
    6.     #define amvocung -3200
    7.     int n,i,j,l[100],a[100];
    8.     static int k,max,jmax;
    9.     // k danh dau vi tri phan tu bat dau cua day con tang lon nhat
    10.     // n la do dai cua day
    11.     //l la mang chua do dai lon nhat cua tung phan tu khi tinh tu  cuoi day
    12.     // a la mang chua cac  phan tu
    13.      void nhap(){
    14.      clrscr();
    15.      cout<<"Dynamic prigramming\n";
    16.      cout<<"\n";
    17.       cout<<"\n";
    18.       cout<<"\n";
    19.       cout<<"\n";
    20.     cout<<"Tim day con tang dai nhat cua mot day\n\n\n\n\n\nSo phan tu cua day la:";
    21.     cin>>n;
    22.     cout<<"\n\n\n\n\n";
    23.     cout<<"Nhap cac phan tu cua day:\n";
    24.     for(i=1;i<=n;i++)
    25.     cin>>a[i];
    26.     }
    27.  
    28.     //////////////////////////////////////////
    29.     /// day la ham tim do dai day con tang lon nhat
    30.     void tinh_f()
    31.     {
    32.     a[n+1]=duongvocung;//a[n+1]=3200 phan tu duong vo cung
    33.     l[n+1]=1;//do dai phan tu duong vo cung la 1
    34.     a[0]=amvocung;//a[0]=-3200 phan tu am vo cung
    35.     for(i=n;i>=0;i--)
    36.     {
    37.     jmax=n+1;
    38.     for(j=n+1;j>=i+1;j--)
    39.     if(a[i]<a[j]&&l[j]>=l[jmax])
    40.         {
    41.         jmax=j;
    42.     l[i]=l[j]+1;
    43.  
    44.     }
    45.       }
    46.        }
    47.        ///////////////////////////////////////////////////////////////////////
    48.        // ham xemday()in ra day ban da nhap
    49.  
    50.       void xemday(){
    51.       for(i=1;i<=n;i++)
    52.       cout<<" "<<a[i];
    53.       }
    54.       ////////////////////////////////////////////////
    55.       //ham tim_max() in ra do dai day con tang lon nhat
    56.           void tim_max(){
    57.       int t=0;
    58.       max=l[1];
    59.       for(i=1;i<=n;i++)
    60.         if(max<=l[i]){
    61.         max=l[i];
    62.         k=i;
    63.     }
    64.     for(i=k;i<=n;i++)
    65.  
    66.     if(max-l[i]==t&&a[i]>=a[k])
    67.     {
    68.     cout<<" "<<a[i];
    69.     t++;
    70.     }
    71.  
    72.     }
    73. ///////////////////////////////////////////////////////////////////
    74.     void main(){
    75.     nhap();
    76.     cout<<"day ban da nhap:\n";
    77.     xemday();
    78.     cout<<"\n";
    79.     tinh_f();
    80.     cout<<"day ket qua la:\n";
    81.     tim_max();
    82.     getch();
    83. }

  4. #4
    Ngày gia nhập
    12 2007
    Bài viết
    25

    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

  5. #5
    Ngày gia nhập
    12 2007
    Bài viết
    25

    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

  6. #6
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,918

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

    Oops ^^! Đọc đề không kĩ ! sorry !Nếu đề bài như trên thì đơn giản hơn nhiều
    Fixed
    PHP Code:
    #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 positionmax_length;
            
    int size;
    };

    Array::Array():
    size(10)
    {
        
    ptr = new int[size 1];
        for(
    int x 0sizex++){
            *(
    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 0obj.sizex++){
            
    cout << "The element [" << << "] :"
            
    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>= (obj.position obj.max_length 1); x--){
            
    output << "The element [" << << "] :" << obj.ptr[x] << endl
        }
        return 
    output;
    }

    void Array::search_longest_segment()
    {
        
    int count 1;    
        for(
    int x positionsizex++){
            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 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;


  7. #7
    Ngày gia nhập
    11 2006
    Bài viết
    6

    Trích dẫn Nguyên bản được gửi bởi thangtcnb Xem bài viết
    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
    Đã được chỉnh sửa lần cuối bởi nguyenthanhhungcntt : 26-12-2007 lúc 07:55 AM.

  8. #8
    Ngày gia nhập
    12 2007
    Bài viết
    25

    Ặ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.
    Code:
    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???

  9. #9
    Ngày gia nhập
    12 2007
    Bài viết
    25

    Trích dẫn Nguyên bản được gửi bởi nguyenthanhhungcntt Xem bài viết
    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?

  10. #10
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,918

    Ừ ! 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 :
    PHP Code:
     for(int x positionsizex++){
            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ì :
    PHP Code:
    Array::Array()//:size(10)
    {
        
    size 10; ( Để nó ở đây )
        
    ptr = new int[size 1];
        for(
    int x 0sizex++){
            *(
    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 !
    PHP Code:
    #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 0sizex++){
            
    cout << "The element [" << << "] :"
            
    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 << endl;
        
    cout << "End position : " << position << endl;
        for (
    int x position 1>= (position max_length 1); x--){
            
    cout << "The element [" << << "] :" << ptr[x] << endl
        }
    }

    void Search_longest_segment()
    {
        
    int count 1;    
        for(
    int x positionsizex++){
            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 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;


Các đề tài tương tự

  1. Trunh tâm dịch thuật CNN đơn vị dịch thuật uy tín nhất Việt Nam
    Gửi bởi ntoantb896 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 27-11-2012, 02:21 PM
  2. Giảm thuế thu nhập doanh nghiệp năm 2011, miễn thuế thu nhập cá nhân đến hết năm 2012
    Gửi bởi tailanh8423 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 28-05-2012, 01:10 PM
  3. Lập trình C Xin thuật toán Thuật toán ma trận con có tổng lớn nhất
    Gửi bởi Contrai21 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-03-2012, 09:10 AM
  4. Bài tập C++ Viết chương trình nhập số lượng hàng hóa, giá cả, thuế, xuất ra tổng giá, thuế, tổng cộng
    Gửi bởi seit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 04-03-2011, 09:04 AM
  5. Hướng dẫn kê khai thuế thu nhập cá nhân, thuế doanh nghiệp 0903034381
    Gửi bởi thngxanhcty trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 19-05-2010, 02:33 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn