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

Đề tài: mảng con dài nhất

  1. #1
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    703

    Mặc định mảng con dài nhất

    cho 1 mảng A,yêu cầu tìm mảng con dài nhất
    ví dụ A=23 -8 -10 0 67 68 3 15 5 12 thì kết quả sẽ là -8 -10 0 3 5 12
    các bạn cùng suy nghĩ nhá,lưu ý là không dùng thuật tóan vét cạn được với những test lớn cỡ 200 phần tử,mình xin gợi ý cách làm của mình là quy về đồ thị.

  2. #2
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Trích dẫn Nguyên bản được gửi bởi tanglung117 Xem bài viết
    lưu ý là không dùng thuật tóan vét cạn được với những test lớn cỡ 200 phần tử
    Sao không dùng qui hoạt động.
    Mà bạn post bài lên là để thảo luận giải thuật hả?
    Không biết ghi gì luôn ...

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

    cho 1 mảng A,yêu cầu tìm mảng con dài nhất
    ví dụ A=23 -8 -10 0 67 68 3 15 5 12 thì kết quả sẽ là -8 -10 0 3 5 12
    các bạn cùng suy nghĩ nhá,lưu ý là không dùng thuật tóan vét cạn được với những test lớn cỡ 200 phần tử,mình xin gợi ý cách làm của mình là quy về đồ thị.
    Vẫn chưa thấy yêu cầu bài toán, tính chất của dãy dài nhất là gì ?

  4. #4
    Ngày gia nhập
    01 2008
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi tanglung117 Xem bài viết
    cho 1 mảng A,yêu cầu tìm mảng con dài nhất
    ví dụ A=23 -8 -10 0 67 68 3 15 5 12 thì kết quả sẽ là -8 -10 0 3 5 12
    các bạn cùng suy nghĩ nhá,lưu ý là không dùng thuật tóan vét cạn được với những test lớn cỡ 200 phần tử,mình xin gợi ý cách làm của mình là quy về đồ thị.
    Quy hoạch động được không bạn
    Code:
     #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();
    }
    Time

  5. #5
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    703

    to rox_rook :thành thật xin lỗi nha,tên bài viết lẽ ra phải là "dãy con tăng dài nhất",giờ thì chắc bạn đã hiểu đề bài.
    To nthung giải thuật của bạn là đúng,song rất tiếc mình chưa biết gì về C++ mà chỉ rành về C ,nhưng nói chung tư tưởng đúng thì phần cài đặt không vấn đề gì.
    Sau đây là giải thuật của mình :
    gọi n là số phần tử của mảng ,khi đó mình quy về đồ thị n đỉnh như vậy trọng số trên 1 cạnh (i,j) sẽ là c[i][j]=1,nếu a[i]<=a[j] && i<j.
    else c[i][j]=0;
    sử dụng thuật toán Floyd để tìm đường đi dài nhất giữa mọi cặp đỉnh --> kết quả.

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

    Mặc định mảng con dài nhất

    hay lắm tanglung

  7. #7
    Ngày gia nhập
    10 2011
    Bài viết
    29

    Em thấy bài này cần gì phải quy hoạch động với đồ thị ạ, mình chỉ cần cho duyệt cả mảng rồi so sánh lần lượt các phần tử cạnh nhau a[i-1] và a[i], nếu a[i-1]<a[i] thì vẫn ở trong mảng con, nếu a[i-1]>a[i] thì sẽ hết mảng con, ta lại so sánh độ dài với mảng con tăng dài nhất đã biết, rồi tiếp tục chạy. Thế này đơn giản hơn còn gì ạ? Với lại Floyd của anh G.Perelman có thời gian O(n^3) còn quy hoạch động hình như là O(nlgn) em không nhớ rõ lắm, còn cách duyệt tuần tự thì chỉ có O(n) thôi ạ.
    Em mới học, có gì sai mọi người thông cảm

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

  1. Sửa máy tính, cài đặt windows, phần mềm tại nhà nhanh nhất, rẻ nhất, hiệu quả nhất …
    Gửi bởi hopluccc 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: 08-07-2013, 02:07 PM
  2. Trả lời: 12
    Bài viết cuối: 25-10-2012, 02:48 AM
  3. Bài tập C++ NHập mảng một chiều gồm n phần tử kết thúc nhập khi nhập một chữ cái
    Gửi bởi thienthanoze trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 15
    Bài viết cuối: 09-07-2012, 10:10 PM
  4. Bài tập C++ Viết phương trình nhập vào 1 chuỗi số.Hãy nhập vào 1 số.Đếm xem có bao nhiêu chữ số bạn vừa nhập
    Gửi bởi namtuocdn trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 16-10-2011, 10:39 AM
  5. Bài tập C++ Nhập mảng 1 chiều, nếu phần tử nhập trùng nhau thì bắt nhập lại
    Gửi bởi danielh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 09-07-2011, 03:35 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