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.
Đề 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:
- 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
- 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
- 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:
dem = 0; Lặp qua từng cặp số a[i], a[i+1]: nếu a[i+1] >= a[i]: tăng dem return dem == N - 1;
- 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:
Lặp qua từng cặp số a[i], a[i+1]: nếu a[i] > a[i+1]: trả về false Trả về true
Ý 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:
// Kiểm tra theo kiểu bài toán thuận bool IsGrow1(int a[], int n) { int dem = 0; for (int i = 0; i < n-1; i++) { if (a[i + 1] >= a[i]) dem++; } if (dem == n - 1) return true; else return false; }
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:
// Kiểm tra theo kiểu bài toán ngịch bool IsGrow2(int a[], int n){ for(int i = 0; i < n-1; i++){ if(a[i] > a[i+1]) return false; } return true; }
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:
// Kiểm tra theo kiểu bài toán thuận bool IsDESC1(int a[], int n) { int dem = 0; for (int i = 0; i < n-1; i++) { if (a[i + 1] <= a[i]) dem++; } if (dem == n - 1) return true; else return false; } // Kiểm tra theo kiểu bài toán ngịch bool IsDESC2(int a[], int n){ for(int i = 0; i < n-1; i++){ if(a[i] < a[i+1]) return false; } return true; }
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.
#include <stdio.h> // Kiểm tra theo kiểu bài toán thuận bool IsASC1(int a[], int n) { int dem = 0; for (int i = 0; i < n - 1; i++) { if (a[i + 1] >= a[i]) dem++; } if (dem == n - 1) return true; else return false; } // Kiểm tra theo kiểu bài toán ngịch bool IsASC2(int a[], int n) { for (int i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) return false; } return true; } // Kiểm tra theo kiểu bài toán thuận bool IsDESC1(int a[], int n) { int dem = 0; for (int i = 0; i < n - 1; i++) { if (a[i + 1] <= a[i]) dem++; } if (dem == n - 1) return true; else return false; } // Kiểm tra theo kiểu bài toán ngịch bool IsDESC2(int a[], int n) { for (int i = 0; i < n - 1; i++) { if (a[i] < a[i + 1]) return false; } return true; } void check(int a[], int n){ if(IsASC1(a, n)){ printf("nDay so tang dan!"); }else if(IsDESC1(a, n)){ printf("nDay so giam dan!"); }else{ printf("nDay so khong tang khong giam!"); } } int main() { int a1[] = {1, 3, 5, 7, 7}; int a2[] = {4, 3, 2, 1, 1, 1}; int a3[] = {1, 3, 2, 4, 5, 6}; check(a1, sizeof(a1)/ sizeof(int)); check(a2, sizeof(a2)/ sizeof(int)); check(a3, sizeof(a3)/ sizeof(int)); }
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:
Day so tang dan! Day so giam dan! Day so khong tang khong giam!
Để lại một bình luận