zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng Lập trình C++: Chương 1 - Trần Phước Tuấn

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:47

Báo xấu

85
lượt xem 6
download

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

Chương 1 của bài giảng Lập trình C++ trình bày 6 nội dung cơ bản như sau: Vấn đề - bài toán, thuật toán - thuật giải, các phương pháp biểu diễn thuật toán, các bước để giải một bài toán trên máy tính, tổng quan về ngôn ngữ lập trình, thể hiện thuật toán bằng ngôn ngữ lập trình. Mời các bạn cùng tham khảo.

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 Lập trình C++: Chương 1 - Trần Phước Tuấn

CHƯƠNG 01: GIẢI QUYẾT VẤN ĐỀ, BÀI TOÁN BẰNG MÁY TÍNH GV: Trần Phước Tuấn EMAIL: tranphuoctuan.khoatoan.dhsp@gmail.com
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
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
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: AB • Ở đây: – A có thể là giả thiết, điều kiện ban đầu – B 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
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
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
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
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
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đ
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
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
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
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
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
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à thuật toán tối ưu Page 15 T.P.Tuấn-Lập Trình C 9/16/2008
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
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 : vô nghiệm; -Trường hợp DELTA = 0 : B X1  X 2   2* A -Trường hợp DELTA > 0 : b  b 2  4ac X 1,2  2a Page 17 T.P.Tuấn-Lập Trình C 9/16/2008
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
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
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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.