intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:62

12
lượt xem
5
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:
Lưu

Nội dung Text: 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

  1. 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
  2. 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
  3. THUẬT TOÁN TÌM KIẾM TUYẾN TÍNH (LINEAR SEARCH)
  4. 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”)
  5. 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
  6. 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;
  7. 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
  8. 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
  9. 3. Ví dụ i=3 x=9 18 5 6 9 10 6 15 1
  10. 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 }
  11. 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
  12. THUẬT TOÁN TÌM GIÁ TRỊ  MAX/MIN – HOÁN VỊ
  13. 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
  14. 1. Tìm giá trị max Sơ đồ flowchart
  15. 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;
  16. 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
  17. 3. Hoán vị Cài đặt void swap (int x, int y) { int temp; temp = x; x = y; y = temp; }
  18. THUẬT TOÁN SẮP XẾP INTERCHANGE SORT
  19. 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
  20. 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 
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2