Một số giải thuật trên mảng 1 chiều | Môn Lập trình căn bản - Đại học Cần Thơ

lOMoAR cPSD| 58097008
MỘT SỐ GIẢI THUẬT TRÊN MẢNG 1 CHIỀU
1. Nhập mảng A có n phần tử từ bàn phím
Nhập số phần tử thực tế n i= 0..n-1
Nhập phần tử A[i] Ví dụ: int main(){ int A[100],n; scanf(“%d”,&n); for(i=0;i<=n-1;i++) scanf(“%d”,&A[i]); return 0; }
2. Duyệt qua mảng A gồm n phần tử
Duyệt nghĩa là i qua mảng A thăm mỗi phần tử úng 1 lần. Giải thuật như sau: i= 0..n-1 Xử lý phần tử A[i]
Ví dụ 1: Hiển thị mảng A lên màn hình i= 0..n-1
Hiển thị A[i] int main(){ int A[100],n; //Nhập mảng A từ bàn phím // .... // Hiển thị mảng for(i=0;i<=n-1;i++) printf(“%d ”,A[i]); return 0; }
Ví dụ 2: Hiển thị các số lẻ trong mảng A có n phần tử: i= 0..n-1
Nếu A[i] là số lẻ thì hiển thị A[i]
Ví dụ 3: Tính tổng giá trị các phần tử của mảng A gồm n số S=0 i= 0..n-1 S=S+A[i]
Ví dụ 4: Sao chép mảng A sang mảng B lOMoAR cPSD| 58097008 i= 0..n-1 B[i] = A[i];
3. Tìm kiếm phần tử X trong mảng A gồm n phần tử
- Giả sử ban đầu X không có trong mảng A, đặt biến Found=0;
- i=0; //Bắt đầu từ vị trí đầu tiên
Lặp trong khi (i vẫn là 1 vị trí hợp lệ AND Tìm chưa thấy X trong mảng A) - Nếu X==A[i] Tìm thấy - Ngược lại i=i+1
Các phát biểu trên có thể biểu diễn bằng ngôn ngữ giả như sau: Found=0; i=0; Lặp trong khi (i Nếu X==A[i] Found=1; Ngược lại i=i+1; //…
Nếu Found ==1 thì tìm thấy X trong A ở vị trí i
Ngược lại, không tìm thấy X trong A và i=n
4. Đảo ngược mảng A gồm n số
Chẳng hạn mảng A gồm n=5 phần tử: Vị trí 0 1 2 3 4 A 5 6 7 8 9
Ý tưởng ở đây là tìm vị trí giữa của mảng A, coi vị trí này như là 1 trục đối xứng; sau đó tiến
hành đổi chỗ giá trị của từng phần tử bên trái trục với phần tử tương ứng bên phải. i= 0.. n -1 2
Đổi chỗ A[i] và A[n-i-1]; 2/3
Lưu ý: Để đổi chỗ 2 giá trị x, y bất kỳ ta dùng 1 biến trung gian t: t=x; x=y; y=t;
5. Sắp xếp mảng A gồm n số: i=0..n -2 lOMoAR cPSD| 58097008 j=i+1..n -1
Nếu (A[i]>A[j]) Đổi chỗ A[i] và A[j]
6. Trả về giá trị lớn nhất trong mảng A gồm n phần tử:
- Gọi giá trị lớn nhất cần tìm là Max; ban đầu Max = A[0]
- Lần lượt xét từng phần tử còn lại, nếu Max < phần tử đang xét thì đặt lại Max chính là phần tử đang xét Giải thuật như sau: Max = A[0] i=1..n -1
Nếu (Max < A[i]) thì Max = A[i]
Max chính là kết quả cần tìm