Bài giảng Kỹ thuật lập trình: Chương 3.1 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

Bài giảng Kỹ thuật lập trình: Chương 3.1 cung cấp cho người đọc những kiến thức như: Kỹ thuật giá trị lính canh; Kỹ thuật đặt biến cờ;...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 Kỹ thuật lập trình: Chương 3.1 - Trường Đại học Ngoại ngữ - Tin học TP.HCM KỸ THUẬT LẬP TRÌNH CƠ BẢN Khoa Công nghệ thông tinTrường Đại học Ngoại ngữ - Tin học TP.HCM (HUFLIT)Nội dung• Kỹ thuật giá trị lính canh• Kỹ thuật đặt biến cờ• Kỹ thuật mảng đánh dấu trạng thái• Kỹ thuật mảng đếm• Kỹ thuật sắp xếp• Kỹ thuật tìm kiếm 2Nội dung• Kỹ thuật vòng lặp không xác định• Kỹ thuật prefix sums• Kỹ thuật sliding window• Kỹ thuật two pointers• Kỹ thuật robot đi trên lưới• Kỹ thuật stack và queue• Kỹ thuật đệ quy 3Các kiến thức đã học• Các câu lệnh • Câu lệnh Tuần tự • Câu lệnh Rẽ nhánh • Câu lệnh Lặp• Cấu trúc dữ liệu • Vô hướng (scalar) • Danh sách (array) • Bảng (table/matrix)• Hàm 4Mục tiêu của kỹ thuật lập trình• Mục tiêu cơ bản • Tổ chức dữ liệu phù hợp, sáng tạo trên những dữ liệu đã học • Định hướng tìm lời giải cho bài toán cơ bản• Để đạt được mục tiêu, chúng ta sẽ • Khai thác các câu lệnh, các cấu trúc dữ liệu, hàm đã học • Điều khiển được từng câu lệnh • Hiểu rõ một số ứng dụng tiềm ẩn của cấu trúc dữ liệu đơn giản 5KỸ THUẬT GIÁ TRỊ LÍNH CANHTính toán bằng vòng lặp• Ý tưởng của tính toán bằng Vòng lặp • Thực hiện nhiều lần cùng một tính toán • Qua mỗi bước lặp, giá trị tính toán sẽ tiệm cận giá trị mục tiêu for (int i=0; iTính toán bằng vòng lặp• Một số vấn đề phát sinh trong vòng lặp • Điều khiển được số lần lặp • Thu nhận giá trị (trạng thái) phát sinh trong vòng lặp• Điều khiển số lần lặp: có 2 phương pháp • Điều khiển số lần lặp dựa trên bộ đếm (counter) Counter-controlled iteration • Điều khiển số lần lặp dựa trên giá trị lính canh (sentinel value) Sentinel-controlled iteration 8Counter-controlled iteration• Bài toán điểm trung bình: Một lớp học có 10 sinh viên làm một bài kiểm tra. Điểm của các bài kiểm tra có giá trị từ 0 đến 10. Hãy xác định điểm trung bình của bài kiểm tra này• Ý tưởng: Điểm trung bình = tổng điểm / số sinh viên • Nhập mỗi điểm, lưu tổng các điểm nhập vào • Thực hiện tính trung bình • In kết quả 9Counter-controlled iteration• Chương trình int total=0; int gradeCounter=1; while (gradeCounterCounter-controlled iteration• Các bước sử dụng Counter-controlled iteration • Bước 1. Xác định số lần lặp tối đa • Bước 2. Dùng một biến counter để đếm số lần lặp của vòng lặp• Mẫu chương trình Counter-controlled iteration int counter=1; while (counterCounter-controlled iteration• Vòng lặp for được thiết kế để triển khai counter- controlled iteration hiệu quả for (int counter=0; counterSentinel-controlled iteration• Bài toán điểm trung bình: Phát triển ứng dụng tính điểm trung bình với số lượng sinh viên tùy ý trong mỗi lần chạy int total=0; int gradeCounter=1; while (gradeCounterSentinel-controlled iteration• Giá trị lính canh Giá trị lính canh (sentinel) là một giá trị đặc biệt (trong ngữ cảnh cụ thể của thuật toán) được dùng để kết thúc một tiến trình (vòng lặp/hàm đệ quy)• Nhận xét • Giá trị lính canh (sentinel): còn gọi là signal value, dummy value • Giá trị lính canh không được trùng với dữ liệu của chương trình • Tùy theo bài toán sẽ có cách chọn giá trị lính canh phù hợp 14Sentinel-controlled iteration• Bài toán điểm trung bình: Phát triển ứng dụng tính điểm trung bình với số lượng sinh viên tùy ý trong mỗi lần chạy• Ý tưởng: • Người dùng nhập tất cả các điểm số mong muốn • Sau đó người dùng nhập sentinel value để xác nhận không còn điểm để nhập • Chương trình phát hiện giá trị sentinel người dùng đã nhập • Chương trình tính điểm trung bình 15Sentinel-controlled iteration• Chương trình int total=0; int gradeCounter=0; int grade = Convert.ToInt32(Console.ReadLine()); while (grade != -1) { total = total + grade; gradeCounter += 1; grade = Convert.ToInt32(Console.ReadLine()); } double average = total / gradeCounter; Console.Write(average); 16Sentinel-controlled iteration • Giá trị sentinel: −??• Nhận xét • Tiến trình sẽ dừng khi gặp giá trị lính canh • Sentinel được dùng trong vòng lặp khi không thể xác định số lần thực hiện 17Sentinel-controlled iteration• Các bước sử dụng Sentinel-controlled iteration • Bước 1. Xác định giá trị lính canh (không được lẫn lộn với giá trị củ ...