Bài giảng Tin học Lớp 10 - Bài 6: Giải bài toán trên máy tính - Trường THCS & THPT Mỹ Hòa Hưng

Nội dung text: Bài giảng Tin học Lớp 10 - Bài 6: Giải bài toán trên máy tính - Trường THCS & THPT Mỹ Hòa Hưng

1. Tröôøng THCS & THPT MYÕ HOØA HÖNG CHAØO MÖØNG QUÍ THAÀY COÂ DÖÏ GIÔØ GV: Phaïm Thò Bích Lieãu 1
2. Caâu 3. Chương trình dịch dùng để làm gì ? A. Diễn đạt các thao tác của thuật toán B. Biểu diễn thuật toán bằng sơ đồ khối C. Là chương trình dịch từ các ngôn ngữ khác nhau ra ngôn ngữ máy D. Dùng để diệt Virus 3
3. CHƯƠNG TRÌNH TIN HỌC LỚP 10 Tuần: 8 oOo PPCT Tiết: 16 5
4. XÁC ĐỊNH BÀI TOÁN LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN VIẾT CHƯƠNG TRÌNH HIỆU CHỈNH 5 VIẾT TÀI LIỆU 7
5. 1. XÁC ĐỊNH BÀI TOÁN VD: Tìm ước số chung lớn nhất của hai số nguyên dương M và N Khái niệm ƯCLN? Các cách tìm ƯCLN? 9
6. Cách 1 có nhiều cách giải BÀI TOÁN Cách 2 KẾT QUẢ (thuật toán) Cách 3 . . . 11
7. 2. LỰA CHỌN HOẶC THIẾT KẾ THUẬT TOÁN a. Lựa chọn thuật toán - Mỗi thuật toán chỉ giải được cho một bài toán, nhưng có thể có nhiều thuật toán khác nhau cùng giải một bài toán. ➔Vì vậy ta phải chọn thuật toán tối ưu để giải bài toán. - Tiêu chuẩn thuật toán tối ưu là: » Thời gian thực hiện nhanh. » Ít tốn bộ nhớ. » Trình bày dễ hiểu, dễ nhìn. 13
8. VD: Tìm ƯCLN của hai số nguyên dương M, N. Ý tưởng: ta có 2 ý tưởng sau: • Chia M cho N lấy dư là • Nếu M=N thì giá trị chung là R UCLN • Nếu R=0 thì • Nếu M>N thì UCLN(M,N)=N UCLN(M,N)=UCLN(M-N,N) • Nếu R khác 0 thì gán N • Nếu M<N thì cho M, gán R cho N UCLN(M,N)=UCLN(M,N-M) • Tiếp tục chia M cho N. 15
9. VD. Diễn tả thuật toán bằng cách dùng sơ đồ khối Lượt 1 2 3 NhậpM= 25, M N ,N= 10 M 25 15 5 5 N 10 10 10 5 Đ 2515M55 = ===N10105 ?? ?? ĐƯưCLNa ra (25,10)M và kết = 5 thúc S Đ M15525 > > >10 >10 N10 ?? MM << 15M25 N1010 S NN <=- N10 - -M5 17
10. 3. VIẾT CHƯƠNG TRÌNH - Là lựa chọn cách tổ chức dữ liệu và lựa chọn ngôn ngữ lập trình (NNLT) phù hợp với thuật toán. - Có nhiều loại NNLT, vì vậy khi viết Kể tên các ngôn chương trình trongngữ ngôn lập trình?ngữ nào thì phải tuân theo những quy định đó. 19
11. 4. HIỆU CHỈNH Sau khi viết xong, chương trình cần phải được thử bằng một số Input tiêu biểu. Nếu phát hiện sai sót thì phải sửa chương trình rồi thử lại.Khi ta giải một bài toán có lúc kết quả cũng đúng không? Tại sao cần phải có bước hiệu chỉnh? Thế nào là hiệu chỉnh? 21
12. 5. VIẾT TÀI LIỆU - Mô tả chi tiết về bài toán, thuật toán, chương trình và kết quả thử nghiệm - Hướng dẫn cách sử dụng chương trình - Người sử dụng có thể đề xuất những khả năng hoàn thiện thêm 23
13. CỦNG CỐ Câu 2: Mục đích của việc hiệu chỉnh là : a. Xác định lại Input và Output của bài toán. b. Phát hiện và sửa sai sót. c. Mô tả chi tiết bài toán. d. Để tạo ra một chương trình mới. 25
14. BÀI TẬP VỀ NHÀ Hãy viết thuật toán giải phương trình bậc nhất ax + b = 0 và đề xuất các bộ Test tiêu biểu 27
15. ❖ Thuật toán : * Diễn tả thuật toán bằng cách liệt kê : B1:Nhập M,N B1: Nhập M, N B2: Nếu M=N thì giá trị B2: Chia M cho N lấy chung là UCLN rồi kết thúc dư là R B3:Nếu M>N thì B3: Nếu R=0 thì M M-N, chuyển sang B2 UCLN(M,N)=N rồi kết thúc B4: N N-M, chuyển sang B2 B4: M N , N R, chuyển sang B2 31
16. Lần M N Với M=3, N=100 1 3 100 2 3 97 Nhập M,N 3 3 94 Đ M=N Đưa ra M và KT S Đ 34 3 1 M>N M M-N S 35 2 1 N N-M 36 1 1 KQ UCLN(3,100)=1 33
17. Số Thuật toán 1 và Thuật toán 2 và lần giá trị tương giá trị tương ứng thực ứng của (M,N) của (M,N) hiện 1 3,100 3,100 2 3,97 100,3 3 3,94 3,1 4 3,91 Kết luận: ƯCLN = 1 34 3,1 35 35 2,1