›
›

Bài giảng Kỹ thuật lập trình - Chương 1: Giải quyết vấn đề bài toán bằng máy tính

pdf 47 trang hapham 1550
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật lập trình - Chương 1: Giải quyết vấn đề bài toán bằng máy tính", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_ky_thuat_lap_trinh_chuong_1_giai_quyet_van_de_bai.pdf

Nội dung text: Bài giảng Kỹ thuật lập trình - Chương 1: Giải quyết vấn đề bài toán bằng máy tính

  1. CHƯƠNG 01: GIẢI QUYẾTVẤN ĐỀ, BÀI TOÁN BẰNG MÁY TÍNH GV: Trần Phước Tuấn EMAIL: tranphuoctuan.khoatoan.dhsp@gmail.com
  2. Nội dung bài học 1. Vấn đề - bài toán 2. Thuật toán - thuật giải 3. Các phương pháp biểu diễn thuật toán 4. Các bước để giải một bài toán trên máy tính 5. Tổng quan về ngôn ngữ lập trình 6. Thể hiện thuật toán bằng ngôn ngữ lập trình Page 2 T.P.Tuấn-Lập Trình C 9/16/2008
  3. 1. Vấn đề - bài toán Khái niệm • Vấn đề thường được dùng với nghĩa rộng hơn bài toán, bài toán là vấn đề mà để giải quyết nó phải liên quan ít nhiều đến tính toán • Pitago chia mọi vấn đề mà con người cần giải quyết thành hai loại: – Theorema: vấn đề cần khẳng định tính đúng – sai – Problema: vấn đề cần tìm giải pháp để để đạt được mục tiêu từ những điều kiện ban đầu nào đó Page 3 T.P.Tuấn-Lập Trình C 9/16/2008
  4. 1. Vấn đề - bài toán Khái niệm • Theo nhiều kết quả nghiên cứu: việc giải quyết vấn đề - bài toán mà Pitago nêu ra đều có thể diễn ra theo một sơ đồ chung: AA BB • Ở đây: –– AA có thể là giả thiết, điều kiện ban đầu –– BB có thể là kết luận, mục tiêu cần đạt –– là suy luận, giải pháp cần xác định Page 4 T.P.Tuấn-Lập Trình C 9/16/2008
  5. 1. Vấn đề - bài toán Khái niệm • Ví dụ 1: Bài toán kiểm tra tính nguyên tố – Cho: Số nguyên dương N – Cần biết: N có là số nguyên tố hay không? • Ví dụ 2: Bài toán quản lý hồ sơ sinh viên – Cho: Hồ sơ gốc của các sinh viên trong trường – Cần biết: Bảng thống kê, phân loại sinh viên theo kết quả học tập Page 5 T.P.Tuấn-Lập Trình C 9/16/2008
  6. 1. Vấn đề - bài toán Khái niệm • Cấu trúc một bài toán: – Thông tin đầu vào (input): cái cho trước – Thông tin đầu ra (output): cái cần tìm • Giải bài toán: là việc xác định tường minh output theo input bằng một quá trình có thể thực hiện một cách hiệu quả Page 6 T.P.Tuấn-Lập Trình C 9/16/2008
  7. 1. Vấn đề - bài toán Một số phương pháp giải quyết vấn đề - bài toán bằng máy tính 1. KĨ THUẬT CHIA ÐỂ TRỊ 2. KĨ THUẬT “THAM LAM” 3. QUY HOẠCH ÐỘNG 4. KĨ THUẬT QUAY LUI 5. KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG Page 7 T.P.Tuấn-Lập Trình C 9/16/2008
  8. 1. Vấn đề - bài toán Chia để trị • Chia bài toán lớn thành những bài toán con (cơ bản) • Giải quyết các bài toán con (cơ bản) thu kết quả dễ dàng • Tổng hợp các kết quả này lại Page 8 T.P.Tuấn-Lập Trình C 9/16/2008
  9. 1. Vấn đề - bài toán Tham lam (heuristic) • Ý tưởng: Trong bàn ăn có nhiều món ăn, ta sẽ chọn món ngon nhất để ăn và ăn cho đến khi nào hết thì chuyển sang món thứ hai và ăn hết món thứ hai, và cứ thế cho đến hết. • Ví dụ: Bài toán rút tiền ATM • Có 3 mệnh giá: 100.000đ,50.000đ, 10.000đ • Số tiền=100.000đ*X1 + 50.000đ*X2+10.000đ*X3 • Hãy chọn X1, X2, X3 tốt • Giải quyết • X1 lớn nhất sao cho X1*100.000đ<=Số tiền • Page 9 T.P.Tuấn-Lập Trình C 9/16/2008
  10. 1. Vấn đề - bài toán Quy hoạch động • Trong kỹ thuật chia để trị, ta chia bài toán lớn thành những bài toán con. Việc giải quyết các bài toán con có thể trùng nhau các bài toán con giải rồi phải giải lại • Kỹ thuật quy hoạch động đưa ra nhằm khắc phục tình trạng này bằng cách lưu lại các kết quả đã giải quyết và sau đó sử dụng lại khi cần mà không cần phải giải lại Page 10 T.P.Tuấn-Lập Trình C 9/16/2008
  11. 1. Vấn đề - bài toán Kỹ thuật quay lui • Là quá trình phân tích đi xuống và quay lui trở lại theo con đường đã đi qua • Ví dụ: Tính n! =n*(n-1)! = Page 11 T.P.Tuấn-Lập Trình C 9/16/2008
  12. 1. Vấn đề - bài toán Tìm kiếm địa phương • Xuất phát từ một phương án nào đó • Áp dụng phép biến đổi trên phương án này để cho một phương án tốt hơn phương án ban đầu • Lặp lại việc biến đổi trên cho đến khi không còn có thể cải thiện được nữa thì dừng lại Page 12 T.P.Tuấn-Lập Trình C 9/16/2008
  13. 2. Thuật toán – thuật giải Thuật toán – khái niệm • Thuật toán là khái niệm cơ sở của toán học và tin học • Thuật toán là một dãy các chỉ thị rõ ràng và có thể thi hành được để hướng dẫn thực hiện hành động nhằm đạt được mục tiêu đặt ra • Thuật toán là sự thể hiện của một phương pháp để giải quyết vấn đề Page 13 T.P.Tuấn-Lập Trình C 9/16/2008
  14. 2. Thuật toán – thuật giải Thuật toán – đặc trưng • Nhập (input). Các thuật toán thường có giá trị đầu vào • Xuất (output). Từ giá trị vào thuật toán cho ra kết quả. • Tính xác định (definiteness). Các bước trong thuật toán phải chính xác rõ ràng. • Tính hữu hạn (finiteness). Thuật toán phải cho ra lời giải (hay kết quả) sau một số bước hữu hạn. • Tính hiệu quả. Tính hiệu quả được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và thời gian sử dụng (khi thực hiện thuật toán trên máy tính). • Tính tổng quát. Thuật toán phải áp dụng được cho tất cả các bài toán cùng dạng, chứ không chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. Page 14 T.P.Tuấn-Lập Trình C 9/16/2008
  15. 2. Thuật toán – thuật giải Thuật toán • Cùng một bài toán có thể có nhiều thuật toán khác nhau để giải • Thuật toán đơn giản, dễ hiểu, có độ chính xác cao, được bảo đảm về mặt toán học, dễ triển khai trên máy, thời gian thao tác ngắn, được gọi là thuthuậậtt totoáánn ttốốii ưuưu Page 15 T.P.Tuấn-Lập Trình C 9/16/2008
  16. 2. Thuật toán – thuật giải Thuật toán • Nghiên cứu thuật toán là một trong những vấn đề quan trọng của tin học • Lý thuyết về thuật toán giải quyết một số vấn đề sau: – Những bài toán nào giải được bằng thuật toán, những bài toán nào không giải được bằng thuật toán – Tìm thuật toán tốt nhất, tối ưu – Triển khai thuật toán trên máy tính Page 16 T.P.Tuấn-Lập Trình C 9/16/2008
  17. 2. Thuật toán – thuật giải Thuật toán – ví dụ Thuật toán giải phương trình bậc hai: AX2 + BX + C = 0 (A 0) -Bước 1 : Tính DELTA = B*B-4*A*C -Bước 2 : So sánh DELTA với số 0 -Bước 3 : Rẽ làm 3 trường hợp : . -Trường hợp DELTA 0 : b b2 4ac X 1,2 2a Page 17 T.P.Tuấn-Lập Trình C 9/16/2008
  18. 2. Thuật toán – thuật giải Thuật toán – các cấu trúc cơ bản 1. Tuần tự: thực hiện hết lệnh này đến lệnh khác 2. Rẽ nhánh: tùy theo dữ liệu đầu vào mà ta quyết định thực hiện câu lệnh gì tiếp theo 3. Lặp: thực hiện lại nhiều lần một số câu lệnh nào đó cho đến khi điều kiện không còn thỏa mãn nữa Page 18 T.P.Tuấn-Lập Trình C 9/16/2008
  19. 2. Thuật toán – thuật giải Thuật giải • Khái niệm thuật toán đã trình bày chính là cánh cửa khép kín cho việc giải các bài toán vì: – Nhiều bài toán không thỏa các đặc trưng cơ bản của thuật toán. – Có nhiều bài toán chưa tìm ra thuật toán hoặc chưa chứng minh được là có thuật toán hay không. – Có những bài toán có thuật toán nhưng khó thực hiện hoặc không thực hiện được Page 19 T.P.Tuấn-Lập Trình C 9/16/2008
  20. 2. Thuật toán – thuật giải Thuật giải • Từ những nhận định trên người ta thấy rằng: cần phải có những đổi mới cho khái niệm thuật toán “Thuật giải” THUẬT GIẢI CŨNG LÀ THUẬT TOÁN NHƯNG MỞ RỘNG CHO CÁC ĐIỀU KIỆN – Tính xác định – Tính đúng đắn Page 20 T.P.Tuấn-Lập Trình C 9/16/2008
  21. 2. Thuật toán – thuật giải Thuật giải – mở rộng tính xác định • Tính xác định thực chất là tính đơn trị của cách giải của một thuật toán và sự rõ ràng tối đa. • Trong thực tế có nhiều bài toán vi phạm tính xác định mà vẫn cho kết qủa. Như vậy thay cho việc xây dựng toàn bộ quá trình giải chỉ cần chỉ ra cách chuyển từ bước i sang bước i+1. • Cách gỉai ngẫu nhiên, đệ quy là mở rộng tính xác định Page 21 T.P.Tuấn-Lập Trình C 9/16/2008
  22. 2. Thuật toán – thuật giải Thuật giải – mở rộng tính đúng đắn • Tính đúng đắn được hiểu là cho kết quả đúng. • Trong thực tế thì số gần đúng là có thể chấp nhận được • Ngoài ra dùng cách giải heuristic đơn giản, độc đáo vẫn có thể cho kết qủa một cách sáng tạo Page 22 T.P.Tuấn-Lập Trình C 9/16/2008
  23. 3. Các phương pháp biểu diễn thuật toán • Ngôn ngữ tự nhiên • Lưu đồ - sơ đồ khối • Mã giả Page 23 T.P.Tuấn-Lập Trình C 9/16/2008
  24. 3. Các phương pháp biểu diễn thuật toán Ngôn ngữ tự nhiên • Liệt kê các thao tác, các chỉ thị bằng ngôn ngữ tự nhiên • Ví dụ: Có 43 que diêm. Hai người chơi luân phiên bốc diêm. Mỗi lượt, mỗi người bốc từ 1 đến 3 que diêm. Người nào bốc cuối cùng sẽ thắng cuộc Page 24 T.P.Tuấn-Lập Trình C 9/16/2008
  25. 3. Các phương pháp biểu diễn thuật toán Ngôn ngữ tự nhiên • Giải thuật để người đi trước luôn thắng cuộc được diễn tả bằng cách liệt kê từng bước như sau: –– BưBướớcc 1:1: Bốc 3 que rồi đợi đối phương đi –– BưBướớcc 2:2: Đối phương bốc (giả sử x que, 0<x<4) –– BưBướớcc 3:3: Đến lượt người đi trước bốc a = (4-x) que. Nếu còn diêm thì quay lại BưBướớcc 22 – Tuyên bố thắng cuộc. KKếếtt ththúúcc Page 25 T.P.Tuấn-Lập Trình C 9/16/2008
  26. 3. Các phương pháp biểu diễn thuật toán Ngôn ngữ tự nhiên – Bài tập 1. Tính điểm trung bình của học sinh gồm các môn Toán, Lý, Hóa. 2. Kiểm tra 2 số a, b giống nhau hay khác nhau. 3. Kiểm tra 1 số a chẵn hay lẻ 4. Giải pt: ax+b=0 5. Giải phương trình bậc 2: ax2 + bx + c = 0 Page 26 T.P.Tuấn-Lập Trình C 9/16/2008
  27. 3. Các phương pháp biểu diễn thuật toán Sơ đồ khối • Là một phương tiện hình học giúp ta diễn tả giải thuật một cách trực quan • Được tạo bởi các kiểu khối cơ bản, nối với nhau bằng các đường có hướng • Thuật ngữ tiếng Anh là Flow Chart Page 27 T.P.Tuấn-Lập Trình C 9/16/2008
  28. 3. Các phương pháp biểu diễn thuật toán Sơ đồ khối bắt đầu điều kiện kết thúc thao tác input Chương trình con output Hướng xử lý Page 28 T.P.Tuấn-Lập Trình C 9/16/2008
  29. 3. Các phương pháp biểu diễn thuật toán Sơ đồ khối – ví dụ Bắt đầu Bắt đầu Bắt đầu Thùng = 0 Lon Số a, Số b a, b 1 Lon Không Thêm 1 Lon vào thùng c = a + b Số a có bằng Số b không? Chưa Thùng = 24 Lon? c Có Bằng Số a bằng Số b Số a không bằng Số b Kết thúc Kết thúc Kết thúc Page 29 T.P.Tuấn-Lập Trình C 9/16/2008
  30. 3. Các phương pháp biểu diễn thuật toán Sơ đồ khối – Bài tập 1. Tính điểm trung bình của học sinh gồm các môn Toán, Lý, Hóa. 2. Kiểm tra 2 số a, b giống nhau hay khác nhau. 3. Kiểm tra 1 số a chẵn hay lẻ 4. Giải pt: ax+b=0 5. Giải phương trình bậc 2: ax2 + bx + c = 0 Page 30 T.P.Tuấn-Lập Trình C 9/16/2008
  31. 3. Các phương pháp biểu diễn thuật toán Mã giả • Ngoài việc sử dụng ngôn ngữ tự nhiên và lưu đồ để biểu diễn thuật toán, người ta còn sử dụng ngôn ngữ tựa pascal, c, được gọi là mã giả • Trong mã giả ta sử dụng cả cấu trúc của ngôn ngữ lập trình và ngôn ngữ tự nhiên Page 31 T.P.Tuấn-Lập Trình C 9/16/2008
  32. 3. Các phương pháp biểu diễn thuật toán Mã giả - ví dụ Biến A,B,C,DELTA,X1,X2 : SốThực ; BắtĐầu Nhập A,B,C; DELTA:=B*B-4*A*C; Nếu DELTA <0 Thi Xuất 'Phương trinh vô nghiệm '; Dừng; Nếu DELTA =0 Thi X1:=(-B/2/A); X2:=X1; Xuất 'Nghiệm kép X1,X2 '; Dừng; Nếu DELTA =0 Thi X1:=(-B-CanBậcHai(DELTA))/2/A; X2:=(-B+CanBậchH(DELTA))/2/A; Xuất 'Nghiệm phân biệt X1,X2 '; Dừng; KếtThúc. Page 32 T.P.Tuấn-Lập Trình C 9/16/2008
  33. 3. Các phương pháp biểu diễn thuật toán Mã giả – Bài tập 1. Tính điểm trung bình của học sinh gồm các môn Toán, Lý, Hóa. 2. Kiểm tra 2 số a, b giống nhau hay khác nhau. 3. Kiểm tra 1 số a chẵn hay lẻ 4. Giải pt: ax+b=0 5. Giải phương trình bậc 2: ax2 + bx + c = 0 SSửử ddụụngng ngônngôn ngngữữ ttựựaa pascalpascal Page 33 T.P.Tuấn-Lập Trình C 9/16/2008
  34. 4. Các bước để giải một bài toán trên máy tính • Bước 1: Xác định vấn đề - bài toán • Bước 2: Lựa chọn phương pháp giải • Bước 3: Xây dựng thuật toán hoặc thuật giải • Bước 4: Cài đặt chương trình • Bước 5: Hiệu chỉnh chương trình • Bước 6: Thực hiện chương trình Page 34 T.P.Tuấn-Lập Trình C 9/16/2008
  35. 4. Các bước để giải một bài toán trên máy tính Bước 1: Xác định vấn đề - bài toán • Phân tích hệ thống nhằm phát biểu chính xác vấn đề, làm rõ yêu cầu của người sử dụng • Đánh giá, nhận định tính khả thi của vấn đề Page 35 T.P.Tuấn-Lập Trình C 9/16/2008
  36. 4. Các bước để giải một bài toán trên máy tính Bước 2: Lựa chọn phương pháp giải • Có nhiều cách khác nhau để giải quyết vấn đề, tùy theo nhu cầu cụ thể mà ta lựa chọn phương pháp thích hợp • Việc lựa chọn phương pháp cũng cần căn cứ vào khả năng xử lý tự động mà ta cần sử dụng Page 36 T.P.Tuấn-Lập Trình C 9/16/2008
  37. 4. Các bước để giải một bài toán trên máy tính Bước 3: Xây dựng thuật toán hoặc thuật giải • Xác định input, output • Xác định các bước thực hiện cơ bản cho dữ liệu đầu vào và đầu ra • Nên áp dụng phương pháp thiết kế có cấu trúc, từ thiết kế tổng thể tiến hành làm mịn dần các bước Page 37 T.P.Tuấn-Lập Trình C 9/16/2008
  38. 4. Các bước để giải một bài toán trên máy tính Bước 4: Cài đặt chương trình • Mô tả thuật giải thành chương trình • Cần nắm vững ngôn ngữ lập trình và thể hiện một cách chính xác thuật toán đã được đưa ra. Page 38 T.P.Tuấn-Lập Trình C 9/16/2008
  39. 4. Các bước để giải một bài toán trên máy tính Bước 5: Hiệu chỉnh chương trình • Cho chương trình chạy thử và hiệu chỉnh những sai sót • Trong bước này ta cần khắc phục hai loại lỗi: – Lỗi cú pháp (có sự hỗ trợ của IDE) – Lỗi ngữ nghĩa (thường khó phát hiện hơn lỗi cú pháp) Page 39 T.P.Tuấn-Lập Trình C 9/16/2008
  40. 4. Các bước để giải một bài toán trên máy tính Bước 6: Thực hiện chương trình • Cho chương trình chạy với những bộ dữ liệu khác nhau để kiểm tra • Lưu ý các trường hợp đặc biệt • Lưu ý các trường hợp người dùng nhập dữ liệu có kiểu không phù hợp với kiểu dữ liệu sử dụng trong chương trình Page 40 T.P.Tuấn-Lập Trình C 9/16/2008
  41. 5. Tổng quan về ngôn ngữ lập trình Con người làm việc Ôi nhiều việc quá VẤN ĐỀ NAN GIẢI PP giải (giải thuật) VẤN ĐỀ TƯƠNG TỰ KẾT QUẢ Page 41 T.P.Tuấn-Lập Trình C 9/16/2008
  42. 5. Tổng quan về ngôn ngữ lập trình Sự hỗ trợ của máy tính Có máy tính Sướng thật, đi làm việc khác thôi! VẤN ĐỀ TƯƠNG TỰ KẾT QUẢ VẤN ĐỀ PP giải NAN GIẢI (giải thuật) Page 42 T.P.Tuấn-Lập Trình C 9/16/2008
  43. 5. Tổng quan về ngôn ngữ lập trình Sự hỗ trợ của máy tính Giải bài toán này thế nào đây? Chương trình biên dịch File Ngôn (Bộ máy của NNLT) ngữ máy (exe, dll, com, ) Source code Cách giải được Kiến thức Kiến thức diễn đạt bằng Chuyên môn về NNLT ngôn ngữ tự nhiên Page 43 T.P.Tuấn-Lập Trình C 9/16/2008
  44. 6. Thể hiện thuật toán bằng ngôn ngữ lập trình Các cấu trúc của thuật toán Các cấu trúc của ngôn ngữ C 1. Tuần tự 1. Dấu ; 2. Rẽ nhánh 2. If, switch case 3. Lặp 3. While, do while, for( , , ) Page 44 T.P.Tuấn-Lập Trình C 9/16/2008
  45. 7. Mối liên hệ giữa các thành phần trong cấu trúc của bài toán và các thành phần nhập xuất trong máy tính Thông tin đầu vào Thông tin đầu ra (input) (output) -Bàn phím:dữ liệu vào thông -Màn hình qua -Máy in -Màn hình Console -File (tập tin) -Windows (các điều khiển: nút lệnh, textbox, ) -Cơ sở dữ liệu Thành phần -Chuột: các điều khiển -Loa tương ứng -File (tập tin) - (nhập xuất) -Cơ sở dữ liệu -Micro -Máy scan -Máy nhận dạng mã vạch - Page 45 T.P.Tuấn-Lập Trình C 9/16/2008
  46. 8. Hãy tìm thuật toán? 1. Cho a,b,c tìm max, min (phát 11. Cơ số 10 2. (10 k) triển cho 4 số, 5 số, ) 12. Cơ số 2 10. (k 10) 2. ax+b=0; 13. Nhập giờ, phút, giây, nhập số 3. ax2+bx+c=0; giây thêm, xuất ra giờ, phút 4. Tháng Quý. giây. 5. Tiền điện. 14. Số nguyên tố 6. Dạng tam giác(nhập a,b,c): 15. Số chính phương Cân, Vuông, Đều, Vuông cân. 16. Phân tích Thừa số nguyên tố. 7. S=1+2+ +n 17. Tổng các ước số của 1 số. 8. Số hạng thứ n của dãy fibonaci 18. Tổng các số nguyên tố < n 9. UCLN, BCNN của 2 số. 19. Tổng các số chính phương < n 10. Rút gọn phân số (nhập tử số, mẫu số). Page 46 T.P.Tuấn-Lập Trình C 9/16/2008
  47. Page 47 T.P.Tuấn-Lập Trình C 9/16/2008