Kiểm tra mảng tăng dần

Kiểm tra mảng tăng dần hay giảm dần C/C++

Làm sao để kiểm tra mảng tăng dần hay giảm dần? Bài viết này sẽ cung cấp cho các bạn gợi ý ý tưởng giải và lời giải tham khảo. Tuy nhiên, Hiếu khuyến khích các bạn đọc ý tưởng giải và tự làm trước sau đó hãy so sánh với lời giải mẫu của tôi.

Kiểm tra mảng tăng dần
Mảng tăng dần hay giảm dần? Làm sao để kiểm tra dãy số tăng/giảm dần?

Đề bài: Cho dãy số nguyên có N phần tử, yêu cầu kiểm tra dãy số tăng dần hay giảm dần? Như vậy, ta có 3 trường hơp:

  1. Dãy số tăng dần, phần tử phía sau không nhỏ hơn các phần tử phía trước
  2. Dãy số giảm dần, phần tử phía sau không lớn hơn các phần tử phía trước
  3. Dãy số không tăng không giảm

Ý tưởng kiểm tra dãy số tăng dần

Để kiểm tra mảng tăng dần hay không bạn có 2 cách:

  • Bài toán thuận: Nếu dãy có N số, bạn phải đếm có bao nhiêu cặp 2 số liên tiếp a[i] & a[i+1], (0 <= i < N-2) thỏa mãn a[i] <= a[i+1]. Nếu bạn đếm được N – 1 cặp, trả về true. Ngược lại thì trả về false.
    • VD: N = 4, arr[] = 1 2 2 4, ta có 1 <= 2, 2 <= 2, 2 <= 4. Như vậy có (3 = N – 1) cặp thỏa mãn => dãy tăng dần.

Ta có giải thuật như sau:

  • Bài toán nghịch: Nếu thấy một cặp a[i] & a[i+1] bất kỳ mà a[i] > a[i+1] thì trả về false luôn. Ngược lại, trả về true.
    • VD: 1 3 2 4, ta thấy cặp 3 > 2 ở lần duyệt thứ 2 vi phạm, trả về false mà không cần duyệt nữa. Ngược lại, đến cuối mà không xảy ra trường hợp sai thì trả về true.

Ý tưởng của giải thuật này như sau:

Ý tưởng kiểm tra dãy số giảm dần tương tự như trên, mình sẽ không trình bày lại. Để hiểu rõ hơn, chúng ta sẽ cùng đi vào code nhé.

Với trường hợp không tăng không giảm, ta có nhận xét: Mảng không tăng, không giảm đồng thời cả 2 hàm kiểm tra tăng dần, giảm dần đều trả về false.

Tham khảo thêm: Bài tập lập trình C/C++

Hàm kiểm tra dãy số tăng dần

Sử dụng cách kiểm tra đầu tiên:

Với cách kiểm tra theo bài toán nghịch, có vẻ vấn đề dễ dàng hơn một chút:

Hàm kiểm tra dãy số giảm dần

Chúng ta vẫn có 2 cách kiểm tra trên, đây là code hàm kiểm tra dãy số giảm dần:

Full source code kiểm mảng số tăng/giảm

Lưu ý:

  • Hàm sizeof(int) trả về số byte của kiểu int
  • sizeof(a1) trả về tổng kích thước của cả mảng a1, tức bằng số lượng phần tử * sizeof (int) – Vì mảng a1 có kiểu int.
  • Do đó, phép chia sizeof(a1) / sizeof(int) thực chất là tính ra số lượng phần tử của mảng a1.

Kết quả chạy với cách giải quyết bài toán theo hướng thuận. Với trường hợp theo hướng phủ định còn lại, bạn có thể thử. Kết quả đều sẽ như nhau:

Similar Posts

Subscribe
Notify of
guest
2 Bình luận
Inline Feedbacks
View all comments