Bài giảng Cơ sở lập trình Chương 2: Lê Viết Mẫn (Mới nhất)

Thuật toán

v 1.0 - 10/2012

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

chúng ta đã học...

1. Lập trình là gì ?

1.1. Lập trình và ngôn ngữ lập trình

1.2. Lịch sử và các hướng lập trình

1.3. Chương trình và thuật toán

1.4. Các bước trong lập trình

2. C# và .NET

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Giải bài toán trên máy tính

1. Xác định bài toán

2. Thiết kế thuật toán

3. Phân tích thuật toán

4. Cài đặt thuật toán

5. Kiểm tra / Bắt lỗi

[ Sửa lỗi ]

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Nội dung

1. Thuật toán

1.1. Khái niệm

1.2. Các tính chất

1.3. Phát triển thuật toán

2. Mô tả thuật toán

3. Các dạng thuật toán cơ bản

4. Ví dụ

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Thuật toán

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Thuật toán • Một tập các chỉ thị / lệnh đơn giản được xác định rõ ràng để giải

Tính toán và trả ra một hoặc một tập các giá trị ở đầu ra (output)

quyết một bài toán nào đó • Nhận một tập các giá trị ở đầu vào (input) •

• Thuật toán = Logic + Điều khiển • Logic - trả lời câu hỏi “Thuật toán làm gì ? Giải quyết vấn đề gì ? Những yếu tố trong bài toán có quan hệ với nhau thế nào ?...” • Gồm các kiến thức chuyên môn mà bạn phải biết để có thể giải bài toán • Để giải bài toán tính diện tích hình cầu, bạn phải biết công thức tính diện

tích hình cầu

• Điều khiển - trả lời câu hỏi “Giải thuật phải làm như thế nào ?”

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Thuật toán • Có thể được mô tả bằng...

• Ngôn ngữ tự nhiên • Ngôn ngữ lập trình • Mã giả • Lưu đồ

• Cấu trúc dữ liệu - Phương pháp tổ chức dữ liệu • Chương trình = Thuật toán + Cấu trúc dữ liệu

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ - giải p.t bậc nhất

ax + b = 0

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ - giải p.t bậc nhất

ax + b = 0

Nếu a ≠ 0: x = -b/a

Ngược lại, a = 0:

Nếu b = 0: pt có vô số nghiệm

Nếu b ≠ 0: pt vô nghiệm

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ - tìm số lớn nhất

Cho ba số a, b, c. Tìm số lớn nhất trong ba số đó

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ - tìm số lớn nhất

Cho ba số a, b, c. Tìm số lớn nhất trong ba số đó

Bước 1 : Cho Max = a

Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b

Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c

Bước 4 : Trả ra Max là giá trị lớn nhất

Bước 5 : Dừng

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Các câu hỏi về thuật toán • Thuật toán đã giải quyết được bài toán được phát biểu ? • Thuật toán đã được định nghĩa tốt ? • Thuật toán đưa ra được một kết quả ? • Thuật toán kết thúc sau thời gian tính toán hợp lý ?

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Tính chất

Tính kết thúc (tính dừng) •

... quá trình thực hiện thuật toán phải kết thúc sau khi thực hiện một số hữu hạn các bước công việc

Thuật toán tính tổng các số tự nhiên

Bước 1 : Cho s = 0, i = 1

Bước 2 : Cộng thêm i vào s ( s = s + i )

Bước 3 : Tăng i thêm 1 ( i = i + 1 )

Bước 4 : Quay lại bước 2

Bước 5 : Nhận s là kết quả giải bài toán

Bước 6 : Dừng

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Tính chất

Tính xác định •

thuật toán phải rõ ràng, không nhập nhằng, không thể hiểu theo nhiều nghĩa

... nếu trong những điều kiện như nhau thì kết quả thực hiện không phụ thuộc vào đối tượng thực hiện thuật toán •

Thuật toán tìm giá trị lớn nhất

Bước 1 : Cho Max = a

Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b

Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c

Bước 4 : Trả ra Max là giá trị lớn nhất

Bước 5 : Dừng

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Tính chất

... nếu thuật toán được dùng để giải cả một lớp bài toán cùng loại

Tính tổng quát •

Thuật toán tìm giá trị lớn nhất

Bước 1 : Cho Max = a

Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b

Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c

Bước 4 : Trả ra Max là giá trị lớn nhất

Bước 5 : Dừng

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Tính chất

Tính xác định đầu vào - đầu ra •

... nếu xác định rõ các dữ liệu đầu vào và các dữ liệu đầu ra •

đầu vào, đầu ra được xác định càng chính xác thì quá trình xây dựng thuật toán càng thuận lợi và thuật toán càng có chất lượng cao hơn

Thuật toán tìm giá trị lớn nhất

Bước 1 : Cho Max = a

Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b

Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c

Bước 4 : Trả ra Max là giá trị lớn nhất

Bước 5 : Dừng

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Tính chất

Tính hiệu quả •

... nếu cho ra kết quả đúng trong mức chi phí ít nhất về thời gian, không gian

Thuật toán tìm giá trị lớn nhất

Bước 1 : Cho Max = a

Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b

Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c

Bước 4 : Trả ra Max là giá trị lớn nhất

Bước 5 : Dừng

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Phát triển thuật toán • Xác định đầu vào (Input) • Xác định các bước xử lý (Process) • Xác định đầu ra (Output) • Vẽ biểu đồ HIPO • Xác định các chương trình con (Module)

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Xác định đầu vào • Chúng ta cần dữ liệu gì ? • Chúng ta lấy dữ liệu đó như thế nào ? • Dữ liệu tồn tại ở dạng nào ?

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Xác định đầu ra • Những kết quả nào chương trình phải trả ra cho người sử

dụng ?

• Kết quả phải được trả ra ở dạng nào ?

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Xác định các bước xử lý • Cách xử lý dữ liệu để đạt được kết quả có ý nghĩa ? • Áp dụng công thức gì ?

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Vẽ biểu đồ HIPO

Hierarchy of Inputs Processes & Outputs

Bài toán

Đầu vào

Xử lý

Đầu ra

C.t. con

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Xác định các c.t. con • Cách nào để chia các vấn đề lớn thành các vấn đề nhỏ hơn, dễ

quản lý hơn ?

• Các chương trình con cần những đầu vào nào ? • Các xử lý nào là cần thiết cho mỗi chương trình con ? • Đầu ra nào là được chờ đợi tại mỗi chương trình con ?

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Mô tả thuật toán

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ngôn ngữ tự nhiên ax + b = 0

Nếu a ≠ 0: x = -b/a

Ngược lại, a = 0:

Nếu b = 0: pt có vô số nghiệm

Nếu b ≠ 0: pt vô nghiệm

• Sử dụng ngôn ngữ thường ngày (tiếng mẹ đẻ) • Dễ trình bày vấn đề • Dài dòng, không trình bày rõ cấu trúc thuật toán, khó hiểu

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Mã giả

ax + b = 0

If a ≠ 0 then x = -b/a

else a = 0:

If b = 0 then pt có vô số nghiệm

If b ≠ 0 then pt vô nghiệm

• Dùng kết hợp ngôn ngữ tự nhiên với các cú pháp của một/nhiều

ngôn ngữ lập trình nào đó

• Diễn tả được cấu trúc thuật toán, dễ viết • Phụ thuộc vào ngôn ngữ lập trình

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Lưu đồ • Còn được gọi là sơ đồ khối • Sử dụng các khối hình để thể hiện một bước công việc / thao

tác nào đó

• Thứ tự thực hiện các công việc được chỉ định bằng các cạnh có

hướng nối liền các khối với nhau

• Trình bày thuật toán bằng hình vẽ trực quan, dễ nhìn, dễ hiểu

và dễ thấy được tổng thể của thuật toán

• Độc lập ngôn ngữ

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ - lưu đồ p.t bậc nhất

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ngôn ngữ lưu đồ

Thực hiện công việc A

Vào / ra dữ liệu

Bắt đầu hay kết thúc một thuật toán

Một phép kiểm tra B, tùy thuộc vào trạng thái của B là đúng hay sai mà rẻ nhánh thích hợp

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Các dạng thuật toán cơ bản

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Thuật toán tuần tự

entry

statement 1

;

{

statement 2

;

statement 3

statement n

;

}

exit

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ 1

Tính tiền lương công nhân nếu biết lương căn bản và số ngày công

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ 1

Tính tiền lương công nhân nếu biết lương căn bản và số ngày công

Đầu vào : lương căn bản, số ngày công

Đầu ra : tiền lương công nhân

Xử lý : tính theo công thức Lương = Lương căn bản * Ngày công

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ 1

Tính tiền lương công nhân nếu biết lương căn bản và số ngày công

Begin

Nhập LCB, NC

Lương = LCB * NC

In Lương

End

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Thuật toán lựa chọn

entry

true false expression

true

e s a f

expression statement statement_1 statement_2

Dạng 1

Dạng 2

exit

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ 2

Cho ba số a, b, c. Tìm số lớn nhất trong ba số đó

Bước 1 : Cho Max = a

Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b

Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c

Bước 4 : Trả ra Max là giá trị lớn nhất

Bước 5 : Dừng

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Begin

Nhập a, b, c

Max = a

b > Max

false

true

Max = b

c > Max

false

true

Max = c

In Max

End

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ 3

Nhập vào số nguyên n. Kiểm tra nếu n > 0 thì tăng n lên 1 đơn vị. Xuất kết quả ra màn hình

Đầu vào : số nguyên n

Đầu ra : giá trị của n

Xử lý : kiểm tra n > 0, nếu đúng tăng n lên 1

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ 3

Nhập vào số nguyên n. Kiểm tra nếu n > 0 thì tăng n lên 1 đơn vị. Xuất kết quả ra màn hình

Begin

Nhập n

n > 0

false

true

n = n + 1

In n

End

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ 4

Nhập vào số nguyên n. Kiểm tra nếu n chẵn xuất ra màn hình câu “n chẵn”, ngược lại xuất “n lẻ”

Đầu vào : số nguyên n

Đầu ra : giá trị của n

Xử lý : kiểm tra n chẵn hoặc lẻ thì xuất ra dòng tương ứng

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ 4

Nhập vào số nguyên n. Kiểm tra nếu n chẵn xuất ra màn hình câu “n chẵn”, ngược lại xuất “n lẻ”

Begin

Nhập n

n % 2 = 0

false true

In “n chẵn” In “n lẻ”

End

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Thuật toán lặp

statement_1

false condition false statement condition

true

statement_2 true

true statement condition

statement_3

Dạng 1

Dạng 2

Dạng 3

false

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ 5

Nhập vào điểm thi ( ∈ [0..10]). Nếu nhập sai thì yêu cầu nhập lại

Đầu vào : số nguyên n ∈ [0..10]

Đầu ra :

Xử lý : nếu n ∉ [0..10] thì yêu cầu nhập lại

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ 5

Nhập vào điểm thi ( ∈ [0..10]). Nếu nhập sai thì yêu cầu nhập lại

Begin

Nhập n

n ∉ [0..10]

true

false

End

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Ví dụ 6

Tính tổng S = 1 + 2 + ... + n (với n > 0). Nhập n vào từ bàn phím

Đầu vào : số nguyên n (n > 0)

Đầu ra : S

Xử lý : i = i + 1 và S = S + i

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Begin

Nhập n

S = 0 i = 1

i > n

true

false

S = S + i i = i + 1

In S

End

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Cảm ơn sự chú ý Câu hỏi ?

Thuật toán Lê Viết Mẫn - lvman@hce.edu.vn

Bài giảng Cơ sở lập trình: Chương 2 - Lê Viết Mẫn

Chủ đề:

Thuật toán

chúng ta đã học...

Giải bài toán trên máy tính

Nội dung

Thuật toán

Thuật toán • Một tập các chỉ thị / lệnh đơn giản được xác định rõ ràng để giải

Thuật toán • Có thể được mô tả bằng...

Ví dụ - giải p.t bậc nhất

Ví dụ - giải p.t bậc nhất

Ví dụ - tìm số lớn nhất

Ví dụ - tìm số lớn nhất

Các câu hỏi về thuật toán • Thuật toán đã giải quyết được bài toán được phát biểu ? • Thuật toán đã được định nghĩa tốt ? • Thuật toán đưa ra được một kết quả ? • Thuật toán kết thúc sau thời gian tính toán hợp lý ?

Tính chất

Tính chất

Tính chất

Tính chất

Tính chất

Phát triển thuật toán • Xác định đầu vào (Input) • Xác định các bước xử lý (Process) • Xác định đầu ra (Output) • Vẽ biểu đồ HIPO • Xác định các chương trình con (Module)

Xác định đầu vào • Chúng ta cần dữ liệu gì ? • Chúng ta lấy dữ liệu đó như thế nào ? • Dữ liệu tồn tại ở dạng nào ?

Xác định đầu ra • Những kết quả nào chương trình phải trả ra cho người sử

Xác định các bước xử lý • Cách xử lý dữ liệu để đạt được kết quả có ý nghĩa ? • Áp dụng công thức gì ?

Vẽ biểu đồ HIPO

Xác định các c.t. con • Cách nào để chia các vấn đề lớn thành các vấn đề nhỏ hơn, dễ

Mô tả thuật toán

Ngôn ngữ tự nhiên ax + b = 0

Mã giả

Lưu đồ • Còn được gọi là sơ đồ khối • Sử dụng các khối hình để thể hiện một bước công việc / thao

Ví dụ - lưu đồ p.t bậc nhất

Ngôn ngữ lưu đồ

Các dạng thuật toán cơ bản

Thuật toán tuần tự

;

{

;

;

}

Ví dụ 1

Ví dụ 1

Ví dụ 1

Thuật toán lựa chọn

Ví dụ 2

Ví dụ 3

Ví dụ 3

Ví dụ 4

Ví dụ 4

Thuật toán lặp

Ví dụ 5

Ví dụ 5

Ví dụ 6

Cảm ơn sự chú ý Câu hỏi ?

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi