Bài giảng Kỹ thuật lập trình - Bài 5: Các thuật toán trên Array - Lê Gia Minh

Nội dung text: Bài giảng Kỹ thuật lập trình - Bài 5: Các thuật toán trên Array - Lê Gia Minh

1. Kỹ thuật lập trình Các thuật toán trên Array
2. Nội dung ¡ Thuật toán tính tổng số - tích số ¡ Thuật toán đếm ¡ Thuật toán tìm phần tử theo một tiêu chuẩn tìm kiếm ¡ Thuật toán tìm phần tử lớn-nhỏ nhất ¡ Thuật toán sắp xếp.
3. Tính Tổng - Tích Tính tổng S =A[0] Tích tích : P = + A[1] + +A[n- A[0]*A[1]* *A[n-1] 1] P = 1; S = 0; Lặp i=0 N-1 làm Lặp i=0 N-1 làm P = P * A[i] ; S = S + A[i] ; Cuối lặp Cuối lặp
4. Tính Tổng – Tích thỏa điều kiện Tính tổng S =A[0] Tích tích : P = + A[1] + +A[n- A[0]*A[1]* *A[n-1] 1] P = 1; S = 0; Lặp i=0 N-1 làm Lặp i=0 N-1 làm Nếu A[i] thỏa DK Nếu A[i] thỏa DK P = P * A[i] ; S = S + A[i] ; Cuối lặp Cuối lặp
5. Một số ví dụ ¡ Nhập vào K(nguyên dương) tính : l A = tổng các số lẻ nhỏ hơn hay bằng K l B = tích các phần tử là bội số của 3 và nhỏ hơn hay bằng K. l C = tổng các phần tử là số nguyên tố trong mãng mà nhỏ hơn hay bằng K
6. Thuật toán tìm số MAX và MIN Min=Max=A[0]; Lặp i=1 N-1 làm Nếu (A[i]>Max) Max = A[i]; Nếu (A[i]<Min) Min = A[i]; Cuối lặp
7. Thuật toán Đếm Count = 0 ; Lặp i=0 N-1 làm Nếu A[i] thỏa DK Count++; Cuối lặp
8. Một số ví dụ ¡ Nhập vào một số N, một mãng số thực A gồm N phần tử và một số thực X – Trả lời các câu hỏi sau : l X có bằng với một số nào đó trong A l X có lớn hơn tất cả các số trong A l X có nhỏ hơn một số nào đó trong A
9. Một số ví dụ (tt) ¡ Nhập vào một số N, một mãng số thực A gồm N phần tử và một số thực X – Trả lời các câu hỏi sau : l Mảng có sắp thứ tự tăng ? l Mảng có sắp thứ tự giảm ? l Mảng có sắp thứ tự ?
10. Thuật tóan sắp xếp Lặp i=0 N-2 Lặp j=i+1 N-1 Nếu (A[i] > A[j]) swap(A[i],A[j]) Bubble Sort
11. Thuật tóan tìm kiếm ¡ Tìm kiếm tuyến tính ¡ Tìm kiếm có phần tử cầm canh ¡ Tìm kiếm nhị phân
12. Search Algorithm- Tuyến tính ¡ Vét cạn(Exhautive) – đơn giản for(I = 1 to N) if (A[i] == X ) return i ; ¡ Tìm kiếm có phần tử cầm canh(sentinel) Làm giảm số lần so sánh trong vòng lặp bằng cách thêm phần tử lính canh H K A I S D E A G S Phần tử cần tìm S N
13. Compare Sentinel and Not START START 1 i 1 i > = i : N A[i] : X = (i+1) i N+1 i : N N*2 lần so < lần so sánh Found Found Not Found sánh END END
14. Tìm kiếm nhị phân 1. Found = false 2. First =1 3. Last = N 4. While ((First A[Mid]) 9. First = Mid + 1 10. Else 11. Found = true
15. Bài tập ¡ Liệt kê các số âm trong mảng một chiều. ¡ Liệt kê các vị trí chẵn lớn nhất trong mảng 1 chiều số nguyên. ¡ Liệt kê các giá trị trong mảng một chiều số nguyên có chử số đầu tiên là số lẻ. ¡ Liệt kê các giá trị trong mảng một chiều số nguyên có tòan chử số là số lẻ. ¡ Viết lại hàm tìm kiếm nhị phân bằng đệ quy