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

Đề tài: Xuất ra các dãy con ko giảm

  1. #1
    Ngày gia nhập
    03 2007
    Nơi ở
    Việt Nam
    Bài viết
    8

    Mặc định Xuất ra các dãy con ko giảm

    Anh em có ai làm giúp mình bài này đi, khó hiểu lắm "Nhập vào một mảng và: a.xuất ra các dãy con ko giảm. b.Tìm dãy con ko giảm có chiều dài lớn nhất. c.Tìm dãy con ko giảm có tổng lớn nhất."
    các bạn co thể giải thích cho mình đoạn code chi tiết nhé. Cám ơn rất nhiều!
    Học! học nữa! học mãi...!
    Học không nổi nữa đi ngủ!

    Kiến thức là nguồn tài nguyên vô tận,
    Chia sẽ về kiến thức giúp chúng ta tiến lại gần nhau!

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Hix suy nghĩ chút nào , 1 dãy con không giảm thì là dãy con tăng , nhưng mà vẫn đề là dãy con này được tính từ hướng nào . Cứ default là từ đầu đến cuối trước nè .

    Như vậy bây giờ chỉ là vấn đề tìm một dãy con tăng nữa thôi , thuật toán tìm dãy con tăng hình như là có rồi còn không thì cậu cứ nghĩ đơn giản như thế này :
    Duyệt từ đầu đến cuối nếu mà giá trị thứ i+1 < i thì in dãy từ lúc duyệt đến i đấy . sao đó duyệt tiếp từ i+1 đến hết .

    cứ mỗi lần tìm ra dãy đó thì lưu vào một mảng , với câu a thì xuất hết ra , với câu b thì strlen(A) tìm max rồi in ra, còn câu c thì tính tổng rồi coi thằng nào lớn nhất .

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

    virusvn có viết 1 bài giải thích về vấn đề này:
    http://05dbb.13.forumer.com/viewtopic.php?t=277
    Với đề là tìm các phần tử không giảm dài nhất (hoặc xóa ít nhất các số để tạo thành dãy không giảm dài nhất).
    Tuy không đưa code C lên, nhưng giải thích khá dễ hiểu, bạn tự viết code nhé. Không phải là không muốn share, mà mấy bài này làm khi mượn máy người ta - lúc đó nghèo ko có USB, nên giờ ko còn code, thông củm.

  4. #4
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Uhm bài khá hay đấy ,đi sâu hơn câu hỏi của knowlege nhiều . Tuy nhiên nếu đi theo kiểu xóa ít nhất các số để tạo thành dãy ko giảm dài nhất thì sẽ hay hơn .

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

    Đây là bài toán cơ bản của phương pháp quy hoạch động thôi mà: Tìm dãy con không giảm dài nhất của N phần tử cho trước.
    Các làm rất đơn giản
    Code:
    Gọi F[i] là độ dài dãy không giảm dài nhất từ phần từ a[1] đến a[i]
    Khi đo, F[i] được tính bằng công thức:
    F[i] = F[j] + 1 với j = 1..i-1; a[i] >= a[j] và F[j] là lớn nhất.
    Có thể tìm được F[j] bằng 1 vòng lặp, nếu không tìm thấy thì F[i] = 1
    Độ phức tạp thông thường là O(N^2), nếu cải tiến bằng cách chia nhị phân tìm kiếm j hoặc dùng cấu trúc Interval Tree thì độ phức tạp còn lại là O(N*log(2, N)). Sau khi tìm được F[i] với mọi i = 1..N rồi thì cứ dựa vào công thức trên mà truy vết thôi.
    Bài toán này là bài toán đầu tiên mà sách thuật toán nào nói về quy hoạch động cũng nói đến.
    Với những câu sau thì chỉ cần cải tiến rất nhỏ từ thuật toán trên là được.

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

  1. Sách Mới Xuất Bản Giảm GIá 10%
    Gửi bởi billgatevn25 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: 16-10-2012, 05:10 PM
  2. Weezo: Truy xuất dữ liệu từ xa cực kỳ đơn giản
    Gửi bởi vietsnets2 trong diễn đàn Software (Phần mềm) | Ebooks
    Trả lời: 0
    Bài viết cuối: 03-01-2012, 07:52 AM
  3. Bài tập C Đêm số lần xuất hiện của kí tự(không đơn giản)
    Gửi bởi amen_boy trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 21
    Bài viết cuối: 02-12-2011, 10:31 AM
  4. Làm thế nào để xuất ảnh ra các định dạng ảnh từ giao diện đã vẽ!!!
    Gửi bởi vuduyhien trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 17-02-2011, 10:03 AM
  5. Giải bài hợp ngữ nhập xuất
    Gửi bởi buitrungkien 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: 10-09-2009, 03:03 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