Ktl-icon-tai-lieu

Bài giảng Tin học đại cương, chương 4

Được đăng lên bởi Dang Anh
Số trang: 36 trang   |   Lượt xem: 1341 lần   |   Lượt tải: 2 lần
HỌC VIỆN KTQS
KHOA CÔNG NGHỆ THÔNG TIN

Chương 4. Giải thuật xử lý thông
tin và ngôn ngữ lập trình
Học phần: LẬP TRÌNH CƠ BẢN

Tài liệu tham khảo


2

Giáo trình tin học cơ sở, Hồ Sỹ Đàm, Đào Kiến Quốc, Hồ
Đắc Phương. Đại học Sư phạm, 2004 – Chương 7, 9.

Giải thuật xử lý thông tin và ngôn ngữ lập trình

NỘI DUNG


Khái niệm bài toán và giải thuật



Đặc trưng (yêu cầu) của giải thuật



Các phương pháp diễn đạt giải thuật



Sơ lược về đánh giá giải thuật



Ngôn ngữ lập trình và các mức khác nhau của ngôn ngữ
lập trình



3

Quá trình thực hiện chương trình trên ngôn ngữ bậc cao
Giải thuật xử lý thông tin và ngôn ngữ lập trình

Input

Yêu cầu

KHÁI NIỆM BÀI TOÁN

Output

Cho số tự
nhiên n

n có phải số
nguyên tố hay
không

“có” hay
“không”

Cho hồ sơ
điểm sinh viên

Tìm tất cả các sinh
viên có điểm trung
bình trên 8

Danh sách sv
thoả mãn

Thiết kế hình
học, tải trọng

Tính sức bền

Độ bền

Cho một bài toán nghĩa là cho input,
và yêu cầu để tìm (tính) ra output
4

Giải thuật xử lý thông tin và ngôn ngữ lập trình

KHÁI NIỆM THUẬT TOÁN


Thuật toán (algorithm) là một quá trình gồm một dãy hữu hạn các thao
tác có thể thực hiện được sắp xếp theo một trình tự xác định dùng để
giải một bài toán



Ví dụ : thuật toán Euclid tìm ước số chung lớn nhất của hai số tự
nhiên. Thay vì phải tính toán theo định nghĩa chỉ làm rõ cấu trúc của
USCLN (tích của các ước số chung với số mũ nhỏ nhất) thuật toán
Euclid dựa trên các tính chất sau:

5



USCLN(a,b) = USCLN (b,a))



Nếu a> b, USCLN(a,b) = USCLN (a-b,b)



USCLN(a,a)= a
Giải thuật xử lý thông tin và ngôn ngữ lập trình

THUẬT TOÁN EUCLID
TIM USCLN CỦA HAI SỐ TỰ NHIÊN


Bài toán: Cho hai số m, n tìm d = USCLN(m,n)

1.

Bước 1: Kiểm tra nếu m= n thì về bước 5, nếu không thực hiện tiếp
bước 2

2.

Bước 2: Nếu m> n thì về bước 4 nếu không thực hiện tiếp bước 3

3.

Bước 3: m <n, bớt n đi một lượng bằng m và quay về bước 1

4.

Bước 4: bớt m đi một lượng bằng n và quay về bước 1

5.

Bước 5: Lấy d chính là giá trị chung của m và n. Kết thúc

6

Giải thuật xử lý thông tin và ngôn ngữ lập trình

VÍ DỤ CÁC BƯỚC CỦA THUẬT TOÁN EUCLID

m n
15 21
15 6

m<n
m>n

9

6

m>n

3
3

6
3

m<n
m=n

USCLN(15,21) = 3
7

Giải thuật xử lý thông tin và ngôn ngữ lập trình

CÁC ĐẶC TRƯNG CỦA THUẬT TOÁN


Input



Output



Tính xác định: Sau mỗi bước, bước tiếp theo hoàn toàn xác định.



Tính khả thi: các chỉ dẫn đặt ra đều có thể thực hiện được



Tính dừng: quá trình tính toán luôn phải dừng sau một số hữu hạn bướ...
Chương 4. Giải thuật xử lý thông
tin và ngôn ngữ lập trình
HỌC VIỆN KTQS
KHOA CÔNG NGHỆ THÔNG TIN
Học phần: LẬP TRÌNH CƠ BẢN
Bài giảng Tin học đại cương, chương 4 - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Bài giảng Tin học đại cương, chương 4 - Người đăng: Dang Anh
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
36 Vietnamese
Bài giảng Tin học đại cương, chương 4 9 10 138