Từ 1 tới 1 trên tổng số 1 kết quả

Đề tài: Bài toán về mảng con.

  1. #1
    Ngày gia nhập
    08 2008
    Bài viết
    28

    Mặc định Bài toán về mảng con.

    Đề bài này ở trong mục Kinh nghiệm ngành IT -> 33 câu hỏi phỏng vấn của Google nhưng mình thấy nó hay và cho vào mục này hợp hơn.
    Bài 25 . Cho một dãy số A gồm n số thực: A[1], ...., A[n]. Một dãy con của A là một dãy liên tục các phần tử của A. Ví dụ: dãy A[2], A[3], ...., A[25] là một dãy con của A. Tìm một thuật toán chạy trong thời gian O(n) để in ra dãy con có tổng lớn nhất của A. (Chú ý là A có thể lẫn lộn các số âm, dương.)
    PHP Code:
    #include <iostream.h>
    #include <conio.h>
    int Max 0  ;              // luu lai tong lon nhat
    int index1index2 ;     // de luu lai vi tri cua mang con.
    void DoLeftint *, int int);
    void DoRightint *, int int);
    /* Duyet tu trai sang phai */
    void DoLeftint *aint leftint right)
      {
        
    int sumleft ;
        
    int i left;
        for( 
    lefti<= righti++ )
           {                      
             if( 
    sumleft a[i] <= ) break ;
             
    sumleft += a[i];
           }
        if( 
    sumleft Max )
           {
               
    Max sumleft;
               
    index1 left;
               
    index2 1;
           }
        if( 
    i+<= right DoLeftai+1right);
        if( 
    ileft DoRight(a,left,i-1) ;
      }

    /*  Duyet nguoc lai tu phai qua trai  */
    void DoRightint *aint leftint right)
      {
        
    int sumright ;
        
    int i right;
        for( 
    right>= lefti-- )
           {                      
                 if( 
    sumright a[i] <= ) break ;
                 
    sumright += a[i];
           }
        if( 
    sumright Max )
           {
               
    Max sumright;
               
    index1 i+1;
               
    index2 right;
           }
        if ( 
    <= left ) return ;               // Day la dieu kien dung
        
    DoRight(a,left,i-1) ;
        if( 
    i+<= right DoLeftai+1right);
      }

    int main()
     {
      const 
    6;
      
    int a[N] = { 8, -108, -2,9,-};
      
    DoLefta05);
      
    cout << " Mang con co tong cac phan tu lon nhat la ";
      
    cout << " a[" << index1 <<"..." << index2 << "]\n";
      
    cout << " Tong = " << Max;
      
    getch();
      return 
    ;
     } 
    Bài này mình dùng đệ quy. Ý tưởng thế này:
    Ví dụ 1 dãy a[10] = { 1, 2, -1, -5, 4, 2, 3, -8, -1, 2 }
    Đầu tiên kiểm tra từ trái qua phải: 1 >0 ; 1+2 > 0 ; 1+2 + (-1) >0 ; 1+2+(-1)+(-5) < 0 . Đến đây dừng lại chia làm 2 mảng con:
    Mảng 1: { 1, 2, -1 } ;
    Mảng 2: { 4, 2, 3, -8, -1, 2 }
    => Mảng con có tổng lớn nhất hoặc là mảng con của mảng 1 hoặc là mảng con của mảng 2.
    Đối với mảng thứ 2 phải lặp lại công việc như vậy giống như mảng a ban đầu.
    Đối với mảng 1 ta làm tương tự như vậy nhưng duyệt từ bên phải sang.
    Kết hợp duyệt từ phải qua trái rồi từ trái qua phải cuối cùng ta tìm được mảng con có tổng các phần tử lớn nhất.
    Từ mảng 1 tìm được mảng { 1, 2 }
    Từ mảng 2 tìm được 2 mảng { 4, 2, 3, -8 } và {2}
    Cuối cùng được mảng { 4, 2, 3 }

    Còn một bài nữa cũng khá hay mọi người thử nghĩ xem ( mình nghĩ là khó hơn )
    Bài 7. Cho một array A các ký tự trong một bộ ký tự nào đó, và một tập S của vài ký tự. Viết một function chạy trong thời gian tuyến tính,trả về sub-array nhỏ nhất của A chứa tất cả các ký tự trong S.
    Đã được chỉnh sửa lần cuối bởi aMember : 10-08-2008 lúc 08:57 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