Bài giảng Hệ thống thông tin: Bài 2 Kỹ thuật thiết kế thuật toán, cung cấp cho người học những kiến thức như: Kỹ thuật tuần tự; Kỹ thuật tổ chức theo cấu trúc; Kỹ thuật đệ quy và lặp; Lựa chọn cấu trúc dữ liệu phù hợp. Mời các bạn cùng tham khảo! | Bài 3 Kỹ thuật thiết kế thuật toán Cơ sở toán học 1 of 59 Các vấn đề Kỹ thuật tuần tự Khái niệm Bài toán Kỹ thuật tổ chức theo cấu trúc Khái niệm Bài toán Kỹ thuật đệ quy và lặp Khái niệm Bài toán Lựa chọn cấu trúc dữ liệu phù hợp Ý tưởng Bài toán Kỹ thuật tuần tự Giải bài toán bằng cách thực hiện tuần tự từng thao tác cho đến khi nhận được kết quả. Kỹ thuật tuần tự Ví dụ 1 Tính n Input n Output T n Chi tiết 1. T 1 2. i 0 3. i i 1 4. T T i 5. if i Kỹ thuật tuần tự Viết lại T 1 i 0 while i Kỹ thuật tuần tự Ví dụ 2 Tìm xâu con dài nhất có các kí tự liên tiếp khác nhau Ví dụ 1 5 52 3 7 8 5 5 6 7 Kỹ thuật tuần tự Input Xâu S Output Xâu X S X là xâu con dài nhất gồm những kí tự liên tiếp khác nhau Chi tiết 1. X d 0 2. Bắt đầu từ kí tự i 1 3. Tìm xâu con gồm các kí tự liên tiếp khác nhau 1. j i 1 while S j S j-1 j j 1 4. if j-i gt d X S d j-i 5. if j Kỹ thuật tuần tự Chi tiết viết lại n len S i 1 d 0 X while i Kỹ thuật tổ chức theo cấu trúc Tổ chức giải quyết bài toán từ trên xuống từ mức tổng quát là ý tưởng giải quyết bài toán cho đến mức chi tiết là các chỉ dẫn đẻ giải quyết công việc đặt ra. Kỹ thuật tổ chức theo cấu trúc Ví dụ 3 Cho a b là các số nguyên có không quá 100 chữ số. Tính c a b. Mức ý tưởng Kí hiệu các chữ số tính từ hàng đơn vị của a và b là và . Nhân lần lượt từng chữ số của b là b0 b1 . bm với a chú ý tới vị trí của chữ số cộng dồn kết quả vào c. Kỹ thuật tổ chức theo cấu trúc Chi tiết thuật toán B1 mức 1 Input 2 số nguyên lớn a b Output c a b Chi tiết c for i 0 i m i tg bi 10i a c c tg Kí hiệu là các phép toán nhân và cộng các số nguyên lớn. Kỹ thuật tổ chức theo cấu trúc Chi tiết thuật toán B1 mức 2 Tổ chức lưu trữ số nguyên lớn vào mảng kiểu vlint xây dựng các thủ tục void nhân byte x vlint a amp vlint kq thực hiện nhân số nguyên a với chữ số x và lưu kết quả vào kq kq x a void cộng vlint x vlint y amp vlint kq thực hiện cộng 2 số nguyên lớn x và y lưu kết quả vào kq kq x y void thêm_10 vlint x int i thực hiện nhân số .
