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

Đề tài: Tìm dãy số tăng dần dài nhất mà các số không xếp liên tiếp

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

    Angry Tìm dãy số tăng dần dài nhất mà các số không xếp liên tiếp

    Chào tất cả các bạn, tui mới zô cong dong c, tại vì mới học c . bây giờ đang "cháy não" bởi một thuật toán, nghĩ "xiêu vẹo tâm can" mà vẫn ko giải ra. Ai bik thuật toán này chỉ giùm. Đề bài là
    "Cho một dãy số nguyên được nhập từ bàn phím, tìm chuỗi số nguyên theo chiều tăng dần trong dãy số đã cho(không tự ý xếp lại dãy), có số lượng số nhiều nhất, và không cần fải là những số đi liền kề nhau.

    ví dụ:
    dãy số nhập vào:
    1 2 3 9 16 27 4 5 11 13 25 26 48 49

    dãy số dài nhất xuất ra là:
    1 2 3 4 5 11 13 25 26 48 49

    ai bik thuat toan chi dum, neu co code thi hay wa!

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

    Bài này có liên quan nhiều đến Min yên ngựa và Max đỉnh núi đây
    Ngu ý của mình là thế này:
    Mấu chốt ở các điểm Min yên ngựa: giả sử ta có các yên ngựa ở các vị trí : p1,p2,p3... nằm rải rác trong dãy
    C++ Code:
    1. 1)Ta khởi hành từ 1 yên ngựa vị trí p .
    2.  Tạo 1 mảng result để nhét kết quả;
    3.  top=p // Max đỉnh núi tạm thời
    4.  Cho i chạy từ p đến hết dãy
    5.     Nếu a[i]>=top thì:
    6.        dem++;
    7.        top=a[i];
    8.        Đẩy a[i] vào result;
    9.  // Kết thúc với 1 yên ngựa, ta có chiều  dài dãy tăng tương ứng với nó là "dem"
    10.  // Và dãy tương ứng của yên ngựa là result
    11. 2. Cứ thế ta duyệt hết các yên ngựa, rồi so sánh các độ dài tương ứng với mỗi yên ngựa sẽ ra kết quả
    @ : Code chưa chính xác đâu, khoan hãy đọc . Hix hix

    Ặc, mà cách trên đi từ Yên ngựa đầu --> cuối dãy : Hình như ko dc chính xác rùi bạn ui.

    Nó ko lắp ghép tương quan đc yên ngựa sau với yên ngựa trước. @@ :(

    Á, nghĩ ra cách giải quyết vấn đề rùi .

    Thuật toán vẫn vậy. Bổ sung thêm :
    Từ mỗi yên ngựa :
    Ta chạy tới trước (làm các công việc như trên) ;
    min=a[p]; // Min tạm thời .
    Chạy từ yên ngựa lui sau :
    Kiểm tra a[i] <= min thì:
    dem++;
    min=a[i];
    đẩy a[i] vào result;


    Hoàn chỉnh đây :
    C++ Code:
    1. 1)Ta khởi hành từ 1 yên ngựa vị trí p .
    2.  Tạo 1 mảng result để nhét kết quả;
    3.  top=a[p] // Max đỉnh núi tạm thời
    4.  bottom=a[p] // Min tạm thời
    5.  dem=1; // Độ dài của dãy tương ứng
    6.  1.1) Cho i chạy từ p+1 đến hết dãy (Nhớ kiểm tra nhỡ p= cuối dãy thì khỏi chạy)
    7.     Nếu a[i]>=top thì:
    8.        dem++;
    9.        top=a[i];
    10.        Đẩy a[i] vào result;
    11.  1.2) Cho j chạy từ p-1 đến đầu dãy (Nhớ kiểm tra nhỡ p = đầu dãy thì khỏi chạy)
    12.     Nếu a[j]<=bottom thì:
    13.        dem++;
    14.        bottom=a[j];
    15.        đẩy a[j] vào result;
    16.  // Kết thúc với 1 yên ngựa, ta được ĐỘ DÀI =dem tương ứng dãy tăng "tạm thời" theo nó
    17.  // mảng result lưu các phần tử của dãy đấy
    18. //( Nó sẽ có dạng Yên ngựa-> Tăng -> Max -> Giảm tụt xuống Yên ngựa-> Giảm -> min)
    19. ___________________
    20. 2)Cứ thế ta duyệt hết các yên ngựa, rồi so sánh các độ dài tương ứng với mỗi yên ngựa sẽ ra kết quả
    21. // Dãy dài nhất thì ta SORT nó 1 phát là được kết quả hoàn chỉnh rồi in nó ra ngoài
    Đã được chỉnh sửa lần cuối bởi aydada : 22-11-2011 lúc 09:07 PM. Lý do: Làm liền bài viết

  3. #3
    Ngày gia nhập
    12 2009
    Nơi ở
    The country of happiness
    Bài viết
    182

    bạn tìm đọc ebook DSAP của tác giả Lê Minh Hoàng đã được giới thiệu rất nhiều trên forum , trong phần "Quy hoạch động" có nói rất kỹ về bài toán này.
    Trích dẫn Nguyên bản được gửi bởi Wazi Armstrong Xem bài viết
    Ôi skill của mình đã đạt đến hàng tuyệt đỉnh
    Không chỉ ăn, tắm, đi lại có thể code
    Mà giờ đã mình có thể code cả khi ngủ. Code tạm vào buffer của não, lúc nào dậy chỉ việc viết ra một cách trôi chảy không lưỡng lự.
    PS: Nếu ngủ dài rảnh rảnh có thể debug luôn, dậy chỉ việc build ?
    Trích dẫn Nguyên bản được gửi bởi vietanh8286 Xem bài viết
    Lập trình viên giỏi là lập trình viên có vợ

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

    cám ơn nhiều nha các bạn. Phù.

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

    Trích dẫn Nguyên bản được gửi bởi tiendaotd Xem bài viết
    bạn tìm đọc ebook DSAP của tác giả Lê Minh Hoàng đã được giới thiệu rất nhiều trên forum , trong phần "Quy hoạch động" có nói rất kỹ về bài toán này.
    Ui thank tiền bối nhìu nhìu.
    Cái ngu ý kia của mình vẫn còn sót nên phải xem tài liệu để rút ra thôi

  6. #6
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Mặc định Tìm dãy số tăng dần dài nhất mà các số không xếp liên tiếp

    Bài cơ bản n=1000
    http://vn.spoj.pl/problems/LIQ/
    Bài nâng cao n=30.000
    http://vn.spoj.pl/problems/LIS/
    Các bạn submit cho xôm tụ

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

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

  1. Bài tập C Viết chương trình nhập liên tiếp các số thực
    Gửi bởi Koldeady trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 14-12-2013, 11:15 AM
  2. tổng liên tiếp lớn nhất của mảng
    Gửi bởi Creepy trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 25-11-2013, 05:33 PM
  3. Tìm dãy con liên tiếp có tổng lớn nhất
    Gửi bởi doantai1988 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 8
    Bài viết cuối: 19-08-2012, 11:16 AM
  4. tìm 3 số liên tiếp có tích nhỏ nhất và 3 số liên tiếp có tổng lớn nhất trong dãy số thực
    Gửi bởi starter trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 19
    Bài viết cuối: 11-06-2011, 11:36 AM
  5. Cách tìm dãy số 0 liên tiếp dài nhất
    Gửi bởi gnourt2 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 08-06-2007, 09:56 PM

Tags của đề tài này

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