bài toán
thuât toán
Bài 4
Harder and harder
Computer
Study
informatics
VÀ
.
BÀI TOÁN
I
THUẬT TOÁN
II
Computer
Study
informatics
Harder and harder
Computer
Study
informatics
Harder and harder
I. BÀI TOÁN
1. Khái niệm
- Bài toán là một việc nào đó mà ta muốn máy tính thực hiện.
2. Thành phần
Trong tin học, để phát biểu một bài toán, ta cần trình bày Input và Output của bài toán đó.
3. Ví dụ
XÁC ĐỊNH Input VÀ Output CỦA CÁC BÀI TOÁN SAU
I. BÀI TOÁN
Harder and harder
3. Ví dụ
Bài 1: Cho số nguyên dương A. Hãy xuất ra màn hình A là số chẵn hay lẻ?
Computer
Study
informatics
Input : Số nguyên A (A>0)
Output : A là số chẵn hay lẻ
Bài 2: Cho 2 số nguyên dương A và B. Hãy xuất ra màn hình UCLN của 2 số.
Input : Số nguyên A,B (A,B>0)
Output : UCLN(A,B)
Harder and harder
Computer
Study
informatics
TỪ INPUT LÀM THẾ NÀO ĐỂ TÌM RA OUTPUT??
BÀI TOÁN
Input
Output
CÁCH GIẢI BÀI TOÁN
HƯỚNG DẪN CÁC THAO TÁC CHO MÁY THỰC HIỆN ĐỂ TÌM LỜI GIẢI
???
THUẬT TOÁN
Harder and harder
Computer
Study
informatics
II. THUẬT TOÁN
1. Khái niệm
BÀI TOÁN
Input
Output
THUẬT TOÁN
Thao tác 1 -> Thao tác 2 -> … -> Thao tác n
-> Thuật toán để giải 1 bài toán là 1 dãy hữu hạn các thao tác được sắp xếp theo 1 trình tự xác định sao cho sau khi thực hiện dãy thao tác dó, từ Input bài toán này, ta nhận được Output cần tìm
II. THUẬT TOÁN
2. Cách biểu diễn
Có 2 cách biểu diễn
Liệt kê
Dùng sơ đồ khối
Nêu tuần tự các thao tác cần tiến hành
Dùng một số hình khối thể hiện thao tác
Harder and harder
Computer
Study
informatics
II. THUẬT TOÁN
2. Cách biểu diễn
Bài toán: Nhập số nguyên dương A. Hãy xuất ra màn hình xem A là số chẵn hay lẻ?
Bước 1: Nhập số nguyên A.
Bước 2: Nếu A = 0 thì quay lại bước 1, ngược lại sang bước 3.
Bước 3: Nếu A chia hết cho 2 thì A là số chẵn, ngược lại A là số lẻ. Qua bước 4.
Bước 4: Xuất kêt quả ra màn hình và kết thúc.
LIỆT KÊ
Harder and harder
Computer
Study
informatics
II. THUẬT TOÁN
2. Cách biểu diễn
SƠ ĐỒ KHỐI
Bài toán: Nhập số nguyên dương A. Hãy xuất ra màn hình xem A là số chẵn hay lẻ?
Thực hiện thao tác so sánh, kiểm tra điều kiện
Thực hiện thao tác tính toán
Thực hiện thao tác nhập / xuất dữ liệu
Quy trình thực hiện các thao tác
Harder and harder
Computer
Study
informatics
Harder and harder
Computer
Study
informatics
SƠ ĐỒ KHỐI
Harder and harder
Computer
Study
informatics
3. TÍCH CHẤT CỦA THUẬT TOÁN
3 TÍCH CHẤT
Tính dừng: Thuật toán phải kết thúc sau 1 số hữu hạn các bước
Tính xác định: Sau một thao tác thì hoặc kết thúc hoặc có đúng 1 thao tác để thực hiện bước tiếp theo.
Tính đúng đắn: Thuật toán kết thúc phải nhận được Output
VD: Cho dãy các thao tác sau:
Bước 1: Xóa bảng
Bước 2: Vẽ đường tròn
Bước 3: Quay lại bước 1
Có phải thuật toán không? Tại sao?
3. TÍCH CHẤT CỦA THUẬT TOÁN
-> Không phải thuật toán vì vi phạm tính dừng
Harder and harder
Computer
Study
informatics
TỔNG KẾT
Harder and harder
Computer
Study
informatics
I. BÀI TOÁN
1. Khái niệm
2. Thành phần
3. Ví dụ
II. THUẬT TOÁN
1. Khái niệm
2. Cách biểu diễn
3. Tính chất
I. BTVN
1. Ôn tập lại kiến thức buổi học
2. Làm bài số 2,4,6,7 SGK trang 44
3. Chuẩn bị cho tiết bài tập tiếp theo
TIẾT HỌC KẾT THÚC
CẢM ƠN CÁC EM ĐÃ NHIỆT TÌNH THAM GIA!