Bài giảng Nhập môn lập trình: Chương 8 - Trường Đại học Ngoại ngữ - Tin học, TP.HCM

Bài giảng Nhập môn lập trình: Chương 8 Một số kỹ thuật lập trình cơ bản, cung cấp cho người đọc những kiến thức như: Thuật toán tìm kiếm tuyến tính (Linear Search); Thuật toán tìm max/min; Thuật toán hoán vị; Thuật toán Sắp xếp cơ bản ‐ Interchange Sort;... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Nhập môn lập trình: Chương 8 - Trường Đại học Ngoại ngữ - Tin học, TP.HCM Click to edit Master subtitle style MỘT SỐ KỸ THUẬT LẬP TRÌNH  CƠ BẢN Khoa Công nghệ thông tin, HUFLIT NỘI DUNG Thuật toán tìm kiếm tuyến tính (Linear Search) Thuật toán tìm max/min Thuật toán hoán vị Thuật toán Sắp xếp cơ bản ‐ Interchange Sort Thuật toán Tìm kiếm nâng cao Kiểm tra mảng thỏa điều kiện THUẬT TOÁN TÌM KIẾM TUYẾN TÍNH (LINEAR SEARCH) Bài toán Cho dãy số nguyên ( ) và số nguyên x. Hãy tìm kiếm xem x có trong dãy a  hay không Input:  Dòng đầu chứa số n và số x n dòng sau, mỗi dòng là một số nguyên Output: Vị trí của số x trong a (nếu x không có trong a ghi “khong tim thay”) 1. Ý tưởng  Xét từng phần tử  Nếu thì x có trong a  Sau khi chạy mà không có số nào thỏa thì x không có trong dãy a 2. Thuật toán Bước 1: Khởi gán i = 0 Bước 2: So sánh a[i] với giá trị x cần tìm, có 2 khả  năng xảy ra  a[i]  == x , tìm thấy x. Dừng;  a[i]  != x , chuyển sang bước 3 Bước 3: i = i + 1 , xét tiếp phần tử kế tiếp trong  mảng  Nếu i == N , hết mảng. Dừng hoặc kết luận “Không  tìm thấy”;  Ngược lại: lặp lại Bước 2; 3. Ví dụ Cho mảng a có 8 phần tử: 18 5 6 9 10 6 15 1 Giá trị cần tìm:  x = 9 i=0 x=9 18 5 6 9 10 6 15 1 3. Ví dụ i=1 x=9 18 5 6 9 10 6 15 1 i=2 x=9 18 5 6 9 10 6 15 1 3. Ví dụ i=3 x=9 18 5 6 9 10 6 15 1 3. Cài đặt int LinearSearch (int a[], int x) { for (int i = 0; i < a.length; i++) { if (a[i] == x) return i ; //a[i] là phần tử có khóa x } return -1; //tìm hết mảng nhưng không có x } 4. Kết luận Giải thuật tìm kiếm tuyến tính không phụ  thuộc vào thứ tự các phần tử trong danh sách Đây là phương pháp tổng quát nhất để tìm kiếm  trên một danh sách bất kỳ Đối với mảng có thứ tự, thuật toán này chưa  tối ưu vì không tận dụng được tính chất thứ  tự của các phần tử trong mảng THUẬT TOÁN TÌM GIÁ TRỊ  MAX/MIN – HOÁN VỊ 1. Tìm giá trị max Ý tưởng Khởi tạo giá trị max = a1 Lần lượt với i từ 2 đến n, so sánh giá trị số hạng ai với giá trị max, nếu ai > max thì max nhận giá trị mới là ai 1. Tìm giá trị max Sơ đồ flowchart 1. Tìm giá trị max • Thuật toán: Bước 1: Nhận n và dãy a1, a2, …, an ; Bước 2:  max  a1 , i  2; Bước 3:  Nếu i > n thì đưa ra giá trị max rồi  kết thúc; Bước 4:  4.1. Nếu ai > max thì max  ai ; 4.2. i  i +1 rồi quy lại bước 3; 2. Tìm giá trị min Ý tưởng Tương tự như phần Tìm giá trị max Khởi tạo giá trị min = a1 Lần lượt với i từ 2 đến n, so sánh giá trị số hạng ai với giá trị min, nếu ai 3. Hoán vị Cài đặt void swap (int x, int y) { int temp; temp = x; x = y; y = temp; } THUẬT TOÁN SẮP XẾP INTERCHANGE SORT 1. Ý tưởng Xuất phát từ đầu mảng, tìm tất cả các cặp phần  tử không theo thứ tự , triệt tiêu chúng bằng  cách đổi chỗ phần tử này với phần tử tương  ứng trong cặp. Lặp lại xử lý trên với các phần tử tiếp theo  trong dãy 2. Thuật toán Bước 1: Khởi tạo i = 0    //bắt đầu từ đầu dãy Bước 2: j = i + 1; //tìm các cặp phần tử a[j] < a[i], j> i Bước 3: Trong  khi j