Tiết 20 Bài 6_Giải Bài Toán Trên Máy Tính - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.ppt) (20 trang)

Trang chủ

Giáo án - Bài giảng

Tin học

Tiết 20 Bài 6_Giải bài toán trên máy tính

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (310.29 KB, 20 trang )

Bài toánTìm ước số chung lớn nhất (ƯCLN) của hai sốnguyên dương M và N.Với các giá trị:M = 5;N = 5.UCLN(M,N) = 5M = 8;N = 6.UCLN(M,N) = 2M = 13;N = 17.UCLN(M,N) = 1UCLN(M,N) = 2M = 2006; N = 2018.1. Hãy chỉ ra những ưu điểm của việc giải bàitoán bằng máy tính so với cách giải toán thôngthường?2. Giải bài toán trên máy tính có những bước nào ?Các bước thực hiệnBướ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ỉnhBước 5: Viết tài liệuVí dụ: Xét bài toánTìm ước chung lớn nhất (ƯCLN) của hai số nguyêndương M và NHãy xác định Input và Output của bài toán trên?Ví dụ 2:Cho dãy số A: 2Tìm số k = 6.369301001. Đây là dạng bài toán nào? Cónhững thuật toán nào để giải? Emchọn thuật toán nào? Vì sao?2. Khi lựa chọn hoặc thiết kế thuậttoán cần đảm bảo các tiêu chuẩnnào?BÀI TOÁNCóthểcó nhiềucách giải(thuật toán)Cách 1Cách 2Cách 3...KẾT QUẢ2/ Lựa chọn hoặc thiết kế thuật toána/ Lựa chọn thuật toán :- Một thuật toán chỉ giải được một bài toán, nhưng một bài toán có thể có nhiềuthuật toán để giải. 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 dung lượng bộ nhớ.Ít phức tạp (trình bày dễ hiểu, dễ nhìn).Ví dụ 1:Tìm ước chung lớn nhất của hai số nguyên dươngM, N.Ý tưởng: ta có 2 ý tưởng sau• Nếu M=N thì giá trị chung làUCLN• Chia M cho N lấy dư làR• Nếu M>N thìUCLN(M,N)=UCLN(M-N,N)• Nếu R=0 thìUCLN(M,N)=N• Nếu MN thìB3: Nếu R=0 thìUCLN(M,N)=N rồi kếtthúcM M-N, chuyển sang B2B4: NB2N-M, chuyển sangB4: M N , Nchuyển sang B2R,* Diễn tả thuật toán bằng sơ đồ khối:Nhập M,NNhập M,NĐM=NSĐM>NSNĐưa ra M vàKTChia M cho Nlấy dư RĐR=0MM-NSMNN-M1Đưa ra N vàKTNR2Nên lựa chọn cách giải (thuật toán) nào để viết chươngtrình?Với M=3, N=100Nhập M,NĐM=NSM>NSNN-MĐĐưa ra M vàKTMM-NLầnMN13100239733……94…343135213611KQUCLN(3,100)=1Với M=3, N=100Nhập M,NChia M cho Nlấy dư RĐR=0SMNNRĐưa ra N vàKTLầnMNR1310032100313310KQUCLN(3,100)=1SốlầnthựchiệnThuật toán 1 vàgiá trị tươngứng của (M,N)Thuật toán 2 vàgiá trị tương ứngcủa (M,N)12343,1003,973,943,913,100100,33,1Kết luận: ƯCLN =1…343536…3,12,11,13/ Viết chương trìnhLà lựa chọn cách tổ chức dữ liệu và lựachọn ngôn ngữ lập trình (NNLT) phù hợpvới thuật toán.Có nhiều loại NNLT, vì vậy khi viếtchương trình trong ngôn ngữ nào thì phảituân theo những quy định đó.Program TimUCLN;Var M, N, R:integer;BeginWrite(‘Nhap vao M,N’);Read(M,N);Program TimUCLN;Var M, N, R:integer;BeginWrite(‘Nhap vao M,N’);Read(M,N);While N 0 doWhile MN doBeginIF M>N THENR:=M mod N;M:=M-NM:=N; N:=R;ELSEN:=N-M;Write(‘ uoc chung lon nhatla:’, M);End.end;Write(‘ uoc chung lon nhat la:’, M);End.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ả cũngđúngkhông?Tại saocầnđượcphải cóbướcchỉnh?Kháiniệm:ChươngtrìnhkiểmtrahiệubằngcáchThếchonàothửlà hiệuchạytrên chỉnh?những bộ Input mà người ta đã biết trướcOutput. Các bộ Input-Output này gọi là các Test. Nếucó sai sót người lập trình sửa chương trình rồi thử lại.Quá trình này được gọi là hiệu chỉnh.Ghép nối mỗi mục ở cột bên trái với mục ở cột bên phảiđể thể hiện nội dung tương ứng của từng bước giải bàitoán trên máy tính.1. Xác định bàitoána) Lựa chọn cách tổ chức dữ liệu và ngônngữ lập trình để diễn đạt thuật toán.2. Lựa chọn hoặc b) Thực hiện chương trình với 1 số bộthiết kế thuật toán Input để kiểm tra kết quả.3. Viết chươngtrìnhc) Xác định Input và Output.4. Hiệu chỉnhd) Mô tả 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.5. Viết tài liệue) Lựa chọn thuật toán có thời gian thựchiện nhanh nhất, tốn ít dung lượng bộ nhớvà ít phức tạp nhất.1. Xác định bàitoána) Lựa chọn cách tổ chức dữ liệu và ngônngữ lập trình để diễn đạt thuật toán.2. Lựa chọn hoặc b) Thực hiện chương trình với 1 số bộthiết kế thuật toán Input để kiểm tra kết quả.3. Viết chươngtrìnhc) Xác định Input và Output.4. Hiệu chỉnhd) Mô tả 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.5. Viết tài liệue) Lựa chọn thuật toán có thời gian thựchiện nhanh nhất, tốn ít dung lượng bộ nhớvà ít phức tạp nhất.Bài tập 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.•Thuật toán :- Sơ đồ khốiNhập a và ba=0?Đb=0?ĐPt vsn rồikết thúcSSnghiệm x=-b/arồi kết thúcPt vn rồikết thúcGiải pt: 8x+96=0Pt có nghiệm :x=-12