Thuật toán tìm số chẵn lớn nhất nhỏ hơn mọi giá trị lẻ có trong mảng
Bài toán: Cho mảng một chiều các số nguyên. Hãy viết hàm tìm số chẵn lớn nhất nhỏ hơn mọi giá trị lẻ có trong mảng. Nếu mảng không tồn tại số lẻ nào thì in ra số -1.
Ví dụ:
- Input:
|
1 |
3 4 5 6 7 9 8 |
- Output:
|
1 |
So chan lon nhat nho hon tat ca cac so le la: 2 |
Ý tưởng tìm số chẵn lớn nhất nhỏ hơn mọi giá trị lẻ trong mảng
- Ý tưởng là chúng ta sẽ tìm ra số lẻ
mincó giá trị nhỏ nhất trong mảng. Vậy sốmin - 1chính là số chẵn lớn nhất nhỏ hơn mọi giá trị lẻ trong mảng. Nếu ta không tìm được số lẻ nào trong mảng thì ta sẽ trả về giá trị -1.
Xây dựng hàm tìm số lẻ min có giá trị nhỏ nhất trong mảng
- Đầu tiên ta nên khởi tạo biến min có giá trị thật lớn để có thể tìm được giá trị lẻ nhỏ nhất trong mảng. Tốt nhất là nên dùng một hằng số lớn hơn kiểu int.
- Ta tiến hành duyệt tất cả các phần tử trong mảng nếu phần tử
a[i]vừa mang giá trị lẻ vừa bé hơn giá trịminthì ta gánmin = a[i]. - Sau khi duyệt tất cả các phần nếu giá trị
minvẫn bằng giá trị khởi tạo tức là mảng không có phần tử lẻ. Ta tiến hành trả về giá trị -1. Nếu không thì ta trả về giá trịmin- 1. - Lưu ý nếu ta khởi tạo
min = 0thì ta không thể tìm được giá trị lẻ nhỏ nhất trong mảng được. Cùng hai xem đoạn code sau:
|
1 2 3 4 5 6 7 8 |
int a[5] = { 3, 4, 5 , 6, 9 }; int min = 0; for(int i=0;i<5;i++){ if(a[i] < min && a[i]%2==1 ) min = a[i]; } cout<<"Min la: "<<min; return 0; |
|
1 |
Min la: 0 |
Nhưng nếu khởi tạo giá trị min lớn thì có thể khắc phục được lỗi trên
|
1 2 3 4 5 6 7 8 9 |
int a[5] = { 3, 4, 5 , 6, 9 }; int min = 10000 ; for(int i=0;i<5;i++){ if(a[i] < min && a[i]%2==1 ) min = a[i]; } cout<<"Min la: "<<min; return 0; } |
|
1 |
Min la: 3 |
Code tham khảo
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<iostream> #include<math.h> using namespace std; const long MAX = 1000000000; void NhapMang(int a[], int n) { for (int i = 0; i < n; i++) { cout << "Nhap a[" << i << "]: "; cin >> a[i]; } } int Fun(int a[], int n) { long min = MAX; for (int i = 0; i < n; i++) { if (a[i] < min && a[i] % 2 == 1) min = a[i]; } if( min == MAX ) return -1; else return min - 1; } int main() { int a[100]; int n; cout << "Nhap vao n: "; cin >> n; NhapMang(a, n); if (Fun(a, n) == -1) cout << "Mang khong co phan tu le"; else cout << "So chan lon nhat nho hon tat ca cac so le la: " << Fun(a, n); system("pause"); return 0; } |
Sau khi chạy chương trình trên ta nhận được kết quả:
|
1 2 3 4 5 6 7 |
Nhap vao n: 5 Nhap a[0]: 3 Nhap a[1]: 4 Nhap a[2]: 5 Nhap a[3]: 6 Nhap a[4]: 9 So chan lon nhat nho hon tat ca cac so le la: 2 |
Bài viết mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !
