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

Thêm vào BST

Báo xấu

11
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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

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

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