BÀI TOÁN và THUẬT TOÁN

Chia sẻ: Phan Hong Thai Thai | Ngày: | Loại File: PPT | Số trang:22

0
510
lượt xem
177
download

BÀI TOÁN và THUẬT TOÁN

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

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ủ đề:
Lưu

Nội dung Text: BÀI TOÁN và THUẬT TOÁN

  1. CHƯƠNG TRÌNH TIN HỌC LỚP 10 Chương I Bài 4. BÀI TOÁN và             THUẬT TOÁN GV: Đặng Bá Sáu 1
  2. I. BÀI TOÁN • Xét các yêu cầu sau : 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? xem là bài toán đều được xem là bài toán GV: Đặng Bá Sáu  2
  3. Khái niệm bài toán trong  Tin học? Bài toán là việc nào đó ta  muốn máy tính thực hiện. GV: Đặng Bá Sáu  3
  4. 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Ữ - Giả thiết Đưa vào máy           Input thông  tin gì      TOÁN HỌC? - 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 đó. GV: Đặng Bá Sáu  4
  5. CÁC VÍ DỤ VD1 : Giải phương trình bậc hai 2 ax + 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ố. GV: Đặng Bá Sáu 5
  6. 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.  Input    : ?ảng điểm của học B  Output  : ?ảng xếp loại học tập. sinh. B GV: Đặng Bá Sáu 6
  7. Nê mộ    o và hỉ õ u  tbàit án  c r   I ,Out  ủa   o nput  putc bàit án  đó? Xem thêm các ví dụ trong SGK/24, 25 GV:ĐặngBá      Sáu  7
  8. 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) 8 GV: Đặng Bá Sáu
  9. II. THUẬT TOÁN 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 GV: Đặng Bá Sáu  9
  10. 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ải n 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ác thao xác định sắ xế sau khi thự một trình tự tác được 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. GV: Đặng Bá Sáu  10
  11. 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 GV: Đặng Bá Sáu  11
  12. a) LIỆT KÊ VD : Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0 (q) 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.  Nế ua ≠ 0 thì (( ) có • Bước 4 : Đưa ra kết quả nghiệm x = -b/a. x và kết thúc. GV: Đặng Bá Sáu 12
  13. b) DÙNG SƠ ĐỒ KHỐI  Trong sơ đồ khối, người ta dùng một số 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 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 GV: Đặng Bá Sáu 13
  14. VD: Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0 LIỆT KÊ SƠ ĐỒ KHỐI N haäp    a,b • Bước 1 : Nhập a, b. • Bước 2 : Nếu a = 0 thì quay lại bước 1, ngược Ñ uùn   =  a  0 g lại thì qua bước 3. • Bước 3 : Gán cho x Sai giá trị -b/a, rồi qua bước 4.  x  ­ a   = b/ • Bước 4 : Đưa ra kết quả x và kết thúc. Ñ öa  x  keát ra  vaø   GV: Đặng Bá Sáu  14 thuùc
  15. LƯU Ý 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. GV: Đặng Bá Sáu  15
  16. III. VÍ DỤ VỀ THUẬT TOÁN 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 ? GV: Đặng Bá Sáu  16
  17. H Ö Ô ÙNG   AÃN: D - Goïi M i laø giaù trò nhoû n Min nhaát caàn tìm. - Gaùn M i baèng giaù trò n Min=6 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 M i n 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. GV: Đặng Bá Sáu  17
  18. SƠ ĐỒ KHỐI : N haäp    daõy  1, , N vaø  a …   aN  M i =  1  i = 2   n  a , Sai Ñ öa  M i ra  n  i<=N   roàikeát     Ñ uùng thuùc Sai M i >  i n  a Ñ uùng M i =  i n  a      i   i= +1 GV: Đặng Bá Sáu  18
  19. LIỆT KÊ  GV: Đặng Bá Sáu  19
  20. 4. VÍ DỤ VỀ THUẬT TOÁN (tt) Bài toán 2 :  Tìm giá trị LỚN NHẤT của một dãy số với Input và  Output như sau: • Input    : Số nguyên dương N và dãy N số  a1,...,aN. • Output : Giá trị lớn nhất (Max) của dãy số. Mô tả thuật toán để giải bài toán này theo cả 2  cách liệt kê và dùng sơ đồ khối. GV: Đặng Bá Sáu  20
Đồng bộ tài khoản