KỸ THUẬT LẬP TRÌNH (p3)

Mối liên hệ giữa thuật toán và cấu trúc dữ liệu Kiểu con trỏ trong C Sử dụng kiểu array trong C Kiểu xâu kí tự trong C Sử dụng struct trong C.Thuật toán (giải thuật) là một quy tắc để với những dữ liệu ban đầu đã cho, tìm được lời giải sau một khoảng thời gian hữu hạnBài toán
Nội dung trích xuất từ tài liệu:
KỸ THUẬT LẬP TRÌNH (p3)KỸ THUẬT LẬP TRÌNH NỘI DUNG Thuật toán Kiểu dữ liệu và cấu trúc dữ liệu THUẬT TOÁN Mối liên hệ giữa thuật toán và cấu trúc dữ liệu VÀ CẤU TRÚC DỮ LIỆU Kiểu con trỏ trong C Sử dụng kiểu array trong C Kiểu xâu kí tự trong C Sử dụng struct trong C 0 1KHÁI NIỆM THUẬT TOÁN CÁC ĐẶC TRƯNG CỦA THUẬT TOÁNThuật toán (giải thuật) là một quy tắc để với những dữ Tính kết thúc (tính dừng)liệu ban đầu đã cho, tìm được lời giải sau một khoảng Tính xác địnhthời gian hữu hạn Tính phổ dụng Bài toán Tính hiệu quả • Thực hiện nhanh Thuật toán • Tiêu phí ít tài nguyên máy tính (bộ nhớ) Dữ liệu vào Kết quả ra Máy tính 2 3CÁC ĐẶC TRƯNG CỦA THUẬT TOÁN TIÊU CHUẨN ĐÁNH GIÁ THUẬT TOÁN Thuật toán tìm UCLN của hai số nguyên dương Lựa chọn thuật toán nào cho bài toán? 1. Nhập vào hai số nguyên dương a, b Tiêu chuẩn 1: Thuật toán đơn giản, dễ hiểu, dễ cài đặt 2. So sánh hai số, chọn số nhỏ nhất gắn cho UCLN Tiêu chuẩn 2: Thuật toán sử dụng tiết kiệm tài nguyên 3. Nếu một trong hai số a, b không chia hết cho UCLN thì thực máy tính (dung lượng không gian nhớ, thời gian) hiện bước 4, ngược lại thì thực hiện bước 5 4. Giảm UCLN một đơn vị và quay lại bước 3 5. In UCLN. Kết thúc ? Các đặc trưng của thuật toán trên 4 5NGÔN NGỮ THUẬT TOÁN NGÔN NGỮ THUẬT TOÁN Ngôn ngữ dùng để mô tả thuật toán Ngôn ngữ liệt kê từng bước ? Tại sao phải dùng ngôn ngữ diễn đạt thuật toán • Thuật toán: Euclid ? Đặc điểm của ngôn ngữ diễn đạt thuật toán • Vào: m,n nguyên dương (m > n) • Ngôn ngữ liệt kê từng bước (Ngôn ngữ tự nhiên) • Ra: gcd là ước chung lớn nhất của m và n • Sơ đồ khối r: số nguyên dương • Ngôn ngữ “giả code”: Tựa Pascal, tựa C, … Bước 1. Nhập vào m, n – Các bước trong chương trình nên được đánh số thứ tự Bước 2. Nếu m, n >0 thì chuyển sang bước 3, ngược lại thì thông báo “Dữ liệu vào không hợp lệ” và kết thúc thuật toán – Có thể bỏ qua phần khai báo dữ liệu, thay vào đó là đặc tả cấu trúc dữ liệu trước khi viết giải thuật Bước 3. Nếu m > n thì chuyển sang bước 4. Ngược lại, hoán chuyển giá trị của m, n Mô tả thuật toán Bước 4. Nếu n = 0 thì gcd = m, in giá trị của gcd và kết thúc. Ngược lại, • Thuật toán: chuyển sang bước 5. • Vào (Input): Bước 5. Tính r là phần dư của phép chia m cho n • Ra (Output): Bước 6. Gán giá trị của n cho m và của r cho n. Quay lại bước 4. 6 7NGÔN NGỮ THUẬT TOÁN NGÔN NGỮ THUẬT TOÁN Sơ đồ khối Thuật toán Euclid Bắt đầu Nút thao tác Lệnh Nhập m, n Thông báo ...