Bài giảng về thuật toán

Tính dừng: Thuật toán phải kếtthúc sau một số hữu hạn lầnthực hiện các thao tác. Ta cần diễn tả thuật toán bằng mộtngôn ngữ sao cho máy tính có thểhiểu và thực hiện được, ngôn ngữ đógọi là ngôn ngữ lập trình. Kết quảdiễn tả thuật toán như vậy gọi làchương trình.
Nội dung trích xuất từ tài liệu:
Bài giảng về thuật toán BAØI TOAÙN VAØTHUAÄT TOAÙN I.KHÁINiỆMBÀITOÁN Xétcácyêucầusau:•1. Giảiphươngtrìnhbậchaiax2+bx+c=02. Viếtmộtdòngchữramànhìnhmáytính.3. Quảnlýcáccánbộtrongmộtcơquan.4. Tìmướcchunglớnnhấtcủahaisốnguyên dươngavàb.5. Xếploạihọctậpcáchọcsinhtronglớp. Trong TOÁN HỌC Trong TIN HỌC  Trong các yêu cầu trên, yêu cầu Yêu cầu 1 và 4 được Tất cả các yêu cầu trên nào được xem như là một bài toán? đều được xem là bài toán xem là bài toánKháiniệmbàitoántrongKh Tinhọc?Bàitoánlàviệcnàođótamuốnmáytínhthựchiện.Cácyếutốcầnquantâmkhigiải mộtbàitoán TOÁNHỌC TINHỌC THUẬTNGỮ Input Đưavàomáy-Giảthiết TOÁN HỌìC? thôngting-Kếtluận Cầnlấyra Output thôngtingìTrongTinhọc,đểphátbiểumộtbàitoán,tacần trìnhbàyrõInputvàOutputcủabàitoánđó.CAÙCTHAØNHPHAÀNCÔBAÛNCA CUÛABAØITOAÙN OUTPUT INPUT CaùcthoângtincaànCaùcthoângtin tìmtöøInput ñaõcoù CÁC VÍ DỤ VD1 : Giải phương trình bậc hai ax2 + bx + c = 0 (a ≠ 0). Input : Các số thực a,b,c (a ≠ 0) Output : Số thực x thỏa : ax2+bx+ c = 0 VD2 : Tìm giá trị nhỏ nhất của các số trong một dãy số. Input: Các số trong dãy số. Output : Giá trị nhỏ nhất trong dãy số. CÁC VÍ DỤ (tt)VD3 : Tìm ước chung lớn nhất của hai số nguyên dương a và b. Input: ? số nguyên dương a và b. Hai ? Output: UCLN của a và b.VD4 : Xếp loại học tập các học sinh trong lớp. ?ảng điểm của học Input: B Output: ?ảng xếp loại học tập. sinh. B Nêumộtbàitoánvàchỉrõ Input,Outputcủabàitoán đó?Xem thêm các ví dụ trong SGK/24, 25 TÓM LẠI Một bài toán được cấu tạo bởi 2 thành phần cơ bản : Input(Các thông tin đã có) Output (Các thông tin cần tìm từ Input)II.KHÁINiỆMTHUẬTTOÁNII.KH Bài toán Bằng cách nào?Input Output Giải bài toán Thuật toán Hướng dẫn các thao tác cho máy thực hiện để tìm ra lời giải BÀI TOÁN THUẬT TOÁNInput Output (Thao tác 1 Thao tác 2 ... Thao tác n) Thuật toán để giải một bài toán là : Thuột toán hữugiảin cácbài toán là một dãy • Mậ t dãy để hạ một thao tác. hữu hạn các thao tác được sắp xếp theo • C trình tự xác đị ợc sắ xế sau khi thự mộtác thao tác đưnh saopcho p theo một c trình tự thao ịnh. hiện dãy xác đtác đó, từ Input của bài toán này, ta nhận được Output cần tìm. • Sau khi thực hiện dãy thao tác đó, từ Input ta tìm được Output của bài toán. MÔ TẢ CÁC THAO TÁC TRONG THUẬT TOÁN Nêu ra tuần tự cácthao tác cần tiến hành Liệt kê Có 2 cách mô tả Dùng sơ đồ khối Dùng một số biểu tượng thể hiện các thao tác a) LIỆT KÊ VD : Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0 () Giải toán thông thường: LIỆT KÊ : Nế u a = 0 thì () không • Bước 1 : Nhập a, b. phải là pt bậc nhất. • Bước 2 : Nếu a = 0 thì + Neáu b = 0 thì () quay lại bước 1, ngược lại voâ số nghieäm. thì qua bước 3. + Neáu b ≠ 0 thì () • Bước 3 : Gán cho x giá voâ nghieäm. trị -b/a, rồi qua bước 4. • Bước 4 : Đưa ra kết quả Nế ua ≠ 0 thì () có nghiệm x = -b/a. x và kết thúc.b) DÙNG SƠ ĐỒ KHỐI sơ đồ khối, người ta dùng một số Trong biểu tượng thể hiện các thao tác như : : Thể hiện các thao tác nhập, xuất dữ liệu : Thể hiện các phép tính toán : Thể hiện các thao tác so sánh : Quy định trình tự thực hiện các thao tácVD: Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0 SƠ ĐỒ KHỐI LIỆT KÊ Nh a ä p• Bước 1 : Nhập a, b. a, b• Bước 2 : Nếu a = 0 thìquay lại bước 1, ngược Ñuùn a= glại thì qua bước 3. 0• Bước 3 : Gán cho x Saigiá trị -b/a, rồi qua x  -b/abước 4.• Bước 4 : Đưa ra kếtquả x và kết thúc. ...