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

Chia sẻ: Hoang Duc | Ngày: | Loại File: PPT | Số trang:54

Thêm vào BST

Báo xấu

511
lượt xem 76
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác. Ta cần diễn tả thuật toán bằng một ngô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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng về thuật toán

BAØI TOAÙN VAØ THUAÄT TOAÙN
I. KHÁI NiỆM BÀI TOÁN Xét các yêu cầu sau : • 1. Giải phương trình bậc hai ax2+bx+c=0 2. Viết một dòng chữ ra màn hình máy tính. 3. Quản lý các cán bộ trong một cơ quan. 4. Tìm ước chung lớn nhất của hai số nguyên dương a và b. 5. Xếp loại học tập các học sinh trong lớ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án
Khái niệm bài toán trong Kh Tin học? Bài toán là việc nào đó ta muốn máy tính thực hiện.
Các yếu tố cần quan tâm khi giải một bài toán TOÁN HỌC TIN HỌC THUẬT NGỮ Input Đưa vào máy - Giả thiết TOÁN HỌìC? thông tin g - Kết luận Cần lấy ra Output thông tin gì  Trong Tin học, để phát biểu một bài toán, ta cần trình bày rõ Input và Output của bài toán đó.
CAÙC THAØNH PHAÀN CÔ BAÛN CA CUÛA BAØI TOAÙN OUTPUT INPUT Caùc thoâng tin caàn Caùc thoâng tin tìm töø 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êu một bài toán và chỉ rõ Input, Output của bài toá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ÁI NiỆM THUẬT TOÁN II. 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ÁN Input 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ác thao 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ác
VD: 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= g lại thì qua bước 3. 0 • Bước 3 : Gán cho x Sai giá trị -b/a, rồi qua x  -b/a bước 4. • Bước 4 : Đưa ra kết quả x và kết thúc. Ñöa ra x vaø keát thuùc
III. VÍ DỤ VỀ THUẬT TOÁN III. V 1.Bài toán 1 : Cho dãy số gồm N số sau (N = 5): 11 6 20 4 8 Tìm giá trị NHỎ NHẤT của dãy số trên ?
a) XÁC ĐỊNH BÀI TOÁN a) X • Input : Số nguyên dương N và dãy N số nguyên a1,….,aN. • Output: Giá trị bé nhất (Min) của dãy số
b) Ý TƯỞNG b) • Khởi tạo giá trị Min = a1 • Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Min, nếu Min>ai thì Min nhận giá trị mới là ai
HÖÔÙNG DAÃN: Min - Goïi Min laø giaù trò nhoû nhaát caàn tìm. Min=6 - Gaùn Min baèng giaù trò phaàn töû ñaàu tieân cuûa 11 6 20 4 8 daõy.i = 2 Gán Min=11 Min=4 - Laàn löôït so saùnh Min vôùi caùc phaàn töû tieáp Giaù trò nhoû theo trong daõy. Taïi moãi nhaát: 4 vò trí so saùnh : Biến i lưu trữ vị trí + Neáu Min lôùn hôn giaù tiếp theo mà Min sẽ trò Tăng i lên 1 đcaàn so saùnh + phaàn töû ơn vị so sánh trong daõy thì laáy giaù trò cuûa phaàn töû ñoù gaùn laïi cho Min.
LIỆT KÊ LI  Böôùc 1 : Nhaäp N vaø daõy a1,…, aN.  Böôùc 2 : Ñaët Min  a1, i  2;  Böôùc 3 : Neáu i ai thì ñaët Min  ai. 4.2. Taêng i moät ñôn vò roài quay veà böôùc 3