Giáo án bài 6 giải bài toán trên máy tính năm 2024

Nội dung Text: Bài giảng Tin học 10 bài 6: Giải bài toán trên máy tính

1. BÀI GIẢNG ĐIỆN TỬ MÔN: TIN HỌC 10 03/06/14 1
2. Bài toán là gì? Bài toán là một công việc mà con người muốn máy tính thực hiện.  Thuật toán là gì? Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.
3. Máy tính làm một công việc Có phải máy tính hay giải một bài toán là do con thông minh và làm người đã đưa vào trong máy được mọi công việc các cách thức làm việc để kể cả việc giải hướng dẫn cho máy thực hiện toán? công việc. Việc giải toán trên máy Để giải bài toán trên tính được máy tính ta thường thực hiện tiến hành theo 5 bước. như thế nào?
4. § 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH Việc giải bài toán trên máy tính thường có 5 bước : Bước 1: Xác định bài toán Bước 2 : Lựa chọn hoặc thiết kế thuật toán Bước 3 : Viết chương trình Bước 4 : Hiệu chỉnh Bước 5: Viết tài liệu.
5. 1/ Xác định bài toán : ?Vớ ịnh toán là xác ịnh Input và Output Xác iđmột bài toán thì trướcđtiên cần phải xác định hai của u tố toán. ết, đó là hai yếu tố nào? yếbài cần thi • Input: Những dữ kiện, giảcủa ết, toán ệu đã có. Phải xác định input và output thi bài số li • Output: Kết quả cần tìm, kết luận cần chỉ ra.
6. Ví dụ1 : Xét bài toán sau Tìm ước chung lớn nhất (ƯCLN) của hai số nguyên dương M và N ? Hãy xác định Input và Output của bài toán trên? Input : Hai số nguyên dương M và N; Output: ƯCLN(M, N). Khi đã xác định được input và output ta sẽ lựa chọn hoặc thiết kế thuật toán cho bài toán.
7. Có thể Cách 1 có nhiều BÀI TOÁN KẾT QUẢ cách giải Cách 2 (thuật toán) Cách 3 ...
8. 2/ Lựa chọn hoặc thiết kế thuật toán a/ Lựa chọn thuật toán : Một bài toán có thể có nhiều thuật tóan để giải nhưng mỗi thuật toán chỉ giải được cho một bài toán. Vì vậy ta phải chọn thuật toán tối ưu trong các thuật toán đã có. Một thuật toán tối ưu phải có các tiêu chuẩn sau : Thời gian thực hiện nhanh. Ít tốn bộ nhớ. Trình bày dễ hiểu, dễ nhìn. b/ Diễn tả thuật toán : Có 2 cách diễn tả một thuật toán  Diễn tả bằng cách liệt kê.  Diễn tả bằng sơ đồ khối.
9. Ví dụ 1:Tìm ước chung lớn nhất của hai số nguyên dương M, N. Ý tưởng: ta có 2 ý tưởng sau: • Nếu M=N thì giá trị chung • Chia M cho N lấy dư là là UCLN R • Nếu M>N thì • Nếu R=0 thì UCLN(M,N)=UCLN(M-N,N) UCLN(M,N)=N • Nếu M
10.  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
11. * Diễn tả thuật toán bằng sơ đồ khối: Nhập M,N Nhập M,N Chia M cho N Đ Đưa ra M và lấy dư R M=N KT S Đ Đưa ra N và Đ R=0 KT M>N M M-N S S M N N N-M N R 1 2 Nên lựa chọn cách giải (thuật toán) nào để viết chương trình?
12. 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
13. Với M=3, N=100 Nhập M,N Chia M cho N Lần M N R lấy dư R Đ 1 3 100 3 Đưa ra N và R=0 KT 2 100 3 1 S M N 3 3 1 0 N R KQ UCLN(3,100)=1
14. Số lần Thuật toán 1 và giá Thuật toán 2 và giá trị thực trị tương ứng của tương ứng của (M,N) hiện (M,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 2,1 36 1,1 37 Kết luận: ƯCLN = 1
15. 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 chương trình trong ngôn ngữ nào thì phải tuân theo những quy định đó.
16. Program TimUCLN; Program TimUCLN; Var M, N, R:integer; Var M, N, R:integer; Begin Begin Write(‘Nhap vao M,N’); Write(‘Nhap vao M,N’); Read(M,N); Read(M,N); While N 0 do While MN do Begin IF M>N THEN R:=M mod N; M:=M-N M:=N; N:=R; ELSE end; N:=N-M; Write(‘ uoc chung lon nhat la:’, M); Write(‘ uoc chung lon nhat End. la:’, M); End.
17. 4/ Hiệu chỉnh : ?Khi ta giải một bài toán có phải lúc nào kết quả Khái niđúngChương Tại sao cầnkiểmi tra bằng hiệu cũng ệm: không? trình được phả có ước cáchỉnh? Thạy thử trên nhchng bộ Input mà người ch cho chế nào là hiệu ữ ỉnh? ta đã biết trước Output. Các bộ Input-Output này gọi là các Test. Nếu có sai sót người lập trình phải sửa chương trình rồi thử lại. Quá trình này được gọi là hiệu chỉnh.
18. Ví dụ 2: Để kiểm chứng tính đúng đắn của chương trình giải pt bậc hai ax2 +bx +c =0, ta sử dụng vài bộ số Input để thấy rõ bước hiệu chỉnh của bài toán. Bài toán này có Input là gì? Input là bộ ba số a,b,c. a=1,b= -3,c=2 ; ∆ =1>0(chương trình đưa ra hai nghiệm). a=1,b= -4,c=4; ∆ =0 (chương trình đưa ra một nghiệm). a=1,b=3,c=4; ∆= -7
19. Bước hiệu chỉnh giúp cho người lập trình thấy những sai sót để sửa sai, giúp cho kiểm tra tính đúng đắn của chương trình để có được một chương trình hoàn chỉnh. 5/ Viết tài liệu : Mô tả chi tiết toàn bộ bài toán, thuật toán, thiết kế chương trình, kết quả thử nghiệm và hướng dẫn sử dụng.
20. Ví dụ 3: Bài toán: viết thuật toán giải pt bậc nhất ax+b=0 và sử dụng vài bộ Input để kiểm chứng tính đúng đắn của chương trình. Xác định bài toán : - Input : các hệ số a,b - Output : các kết luận về nghiệm của pt. Ý tưởng : nghiệm của bài toán phụ thuộc vào các số a và b như sau: -Nếu a=0 : +Nếu b=0 :kết luận pt có vô số nghiệm; +Nếu b≠ 0 : kết luận pt vô nghiệm; -Nếu a ≠ 0 : kết luận pt có một nghiệm x = -b/a.