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

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

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

Thêm vào BST
Báo xấu
16
lượt xem 6
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

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 Kỹ thuật lập trình: Chương 3.1 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

  1. KỸ THUẬT LẬP TRÌNH CƠ BẢN Khoa Công nghệ thông tin Trường Đại học Ngoại ngữ - Tin học TP.HCM (HUFLIT)
  2. 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 2
  3. Nộ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 3
  4. Cá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 4
  5. Mụ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 5
  6. KỸ THUẬT GIÁ TRỊ LÍNH CANH
  7. Tí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; i
  8. Tí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 8
  9. Counter-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ả 9
  10. Counter-controlled iteration • Chương trình int total=0; int gradeCounter=1; while (gradeCounter
  11. Counter-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 (counter
  12. Counter-controlled iteration • Vòng lặp for được thiết kế để triển khai counter- controlled iteration hiệu quả for (int counter=0; counter
  13. Sentinel-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 (gradeCounter
  14. Sentinel-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 14
  15. Sentinel-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 15
  16. Sentinel-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); 16
  17. Sentinel-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 17
  18. Sentinel-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ủa dữ liệu chương trình) • Bước 2. Mỗi lần lặp, kiểm tra giá trị lính canh, để xác định vòng lặp kết thúc • Mẫu chương trình Sentinel-controlled iteration int sentinel = ...; while (data != sentinel) { ... } 18
  19. Giá trị lính canh • Giá trị lính canh với cấu trúc dữ liệu Khi quyệt qua một cấu trúc dữ liệu, chúng ta có thể đặt giá trị lính canh (sentinel) ở đầu hay ở cuối của cấu trúc dữ liệu để yêu cầu vòng lặp tự động dừng khi đã duyệt xong cấu trúc dữ liệu ... • Cài đặt int n = ...; a[n] = sentinel; i=0; while (a[i] != sentinel) { ... } ... 19
  20. Giá trị lính canh • Bài toán: Cho mảng số nguyên 𝑎𝑎 = 𝑎𝑎0 , 𝑎𝑎1 , … , 𝑎𝑎 𝑛𝑛−1 , (1 ≤ 𝑛𝑛 ≤ 108 ) và số nguyên 𝑥𝑥. Kiểm tra xem mảng 𝒂𝒂 có chứa giá trị 𝒙𝒙 không? Nếu có xuất ra "Yes", ngược lại xuất ra "No" int[] a={4, 6, 8, 2, 5, 0}; int n = 5; int x=2; int sentinel = x; a[n] = x; int i=0; while (a[i] != sentinel) i++; if (i
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

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