Bai tap Pascal

BÀI TOÁN
VÀ
THUẬT TOÁN
Xét các yêu cầu sau :
Giải phương trình bậc hai ax2+bx+c=0
Viết một dòng chữ ra màn hình máy tính.
Quản lý các cán bộ trong một cơ quan.
Tìm ước chung lớn nhất của hai số nguyên dương a và b.
Xếp loại học tập các học sinh trong lớp.
I. KHÁI NiỆM BÀI TOÁN
Trong TIN HỌC
Trong TOÁN HỌC
Yêu cầu 1 và 4 được xem là bài toán
Tất cả các yêu cầu trên đều được xem là bài toán
Trong các yêu cầu trên, yêu cầu nào được xem như là một bài toán?
Khái niệm bài toán trong
Tin học?
Bài toán là việc nào đó ta muốn máy tính thực hiện.
TOÁN HỌC?
Các yếu tố cần quan tâm khi giải một bài toán
 Trong Tin học, để phát biểu một bài toán, ta cần trình bày rõ Input và Output của bài toán đó.
CÁC THÀNH PHẦN CƠ BẢN CỦA BÀI TOÁN
CÁC VÍ DỤ
VD1 : Giải phương trình bậc hai
ax2 + bx + c = 0 (a ≠ 0).
Input : Các số thực a,b,c (a ≠ 0)
Output : Số thực x thỏa : ax2+bx+ c = 0

VD2 : Tìm giá trị nhỏ nhất của các số trong một dãy số.
Input : Các số trong dãy số.
Output : Giá trị nhỏ nhất trong dãy số.
VD3 : Tìm ước chung lớn nhất của hai số nguyên dương a và b.
Input :
Output :

VD4 : Xếp loại học tập các học sinh trong lớp.
Input :
Output :
UCLN của a và b.
Hai số nguyên dương a và b.
CÁC VÍ DỤ (tt)

?
?
?
?
Bảng điểm của học sinh.
Bảng xếp loại học tập.
Nêu một bài toán và chỉ rõ Input, Output của bài toán đó?
Xem thêm các ví dụ trong SGK/24, 25
TÓM LẠI
Một bài toán được cấu tạo bởi 2 thành phần cơ bản :

Input (Các thông tin đã có)
Output (Các thông tin cần tìm từ Input)
II. KHÁI NiỆM THUẬT TOÁN
Hướng dẫn các thao tác cho máy thực hiện để tìm ra lời giải
Bài toán
Input
Output
Bằng cách nào?
Giải bài toán
Thuật 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 một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ Input của bài toán này, ta nhận được Output cần tìm.
BÀI TOÁN
Thuật toán để giải một bài toán là :
Một dãy hữu hạn các thao tác.
Các thao tác được sắp xếp theo một trình tự xác định.
Sau khi thực hiện dãy thao tác đó, từ Input ta tìm được Output của bài toán.
MÔ TẢ CÁC THAO TÁC
TRONG THUẬT TOÁN
Có 2 cách mô tả
Liệt kê
Dùng sơ đồ khối
Nêu ra tuần tự các thao tác cần tiến hành
Dùng một số biểu tượng thể hiện các thao tác
Giải toán thông thường:
Nếu a = 0 thì () không phải là pt bậc nhất.
+ Neáu b = 0 thì () voâ số nghieäm.
+ Neáu b ≠ 0 thì () voâ nghieäm.
Nếu a ≠ 0 thì () có nghiệm x = -b/a.
a) LIỆT KÊ

LIỆT KÊ :
Bước 1 : Nhập a, b.
Bước 2 : Nếu a = 0 thì quay lại bước 1, ngược lại thì qua bước 3.
Bước 3 : Gán cho x giá trị -b/a, rồi qua bước 4.
Bước 4 : Đưa ra kết quả x và kết thúc.
VD : Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0 ()
: Thể hiện các thao tác so sánh
b) DÙNG SƠ ĐỒ KHỐI
Trong sơ đồ khối, người ta dùng một số biểu tượng thể hiện các thao tác như :
: Thể hiện các phép tính toán
: Quy định trình tự thực hiện các thao tác
: Thể hiện các thao tác nhập, xuất dữ liệu
VD: Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0
Nhập a, b
a = 0
x ?-b/a
Sai
Đưa ra x và kết thúc

Bước 1 : Nhập a, b.
Bước 2 : Nếu a = 0 thì quay lại bước 1, ngược lại thì qua bước 3.
Bước 3 : Gán cho x giá trị -b/a, rồi qua bước 4.
Bước 4 : Đưa ra kết quả x và kết thúc.
SƠ ĐỒ KHỐI
LIỆT KÊ
III. VÍ DỤ VỀ THUẬT TOÁN
1.Bài toán 1 :

Cho dãy số gồm N số sau (N = 5):
11 6 20 4 8
Tìm giá trị NHỎ NHẤT của dãy số trên ?
a) XÁC ĐỊNH BÀI TOÁN
Input : Số nguyên dương N và dãy N số nguyên a1,….,aN.
Output: Giá trị bé nhất (Min) của dãy số
b) Ý TƯỞNG
Khởi tạo giá trị Min = a1
Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Min, nếu Min>ai thì Min nhận giá trị mới là ai
HƯỚNG DẪN:
Gọi Min là giá trị nhỏ nhất cần tìm.
Gán Min bằng giá trị phần tử đầu tiên của dãy.

Lần lượt so sánh Min với các phần tử tiếp theo trong dãy. Tại mỗi vị trí so sánh :
+ Nếu Min lớn hơn giá trị phần tử cần so sánh trong dãy thì lấy giá trị của phần tử đó gán lại cho Min.

- Khi so sánh đến phần tử cuối cùng trong dãy số thì Min sẽ mang giá trị nhỏ nhất của dãy.
Gán i = 2
11 6 20 4 8
Min
Min=11
Min=6
Min=4
Giá trị nhỏ nhất: 4
Biến i lưu trữ vị trí tiếp theo mà Min sẽ so sánh
+ Tăng i lên 1 đơn vị
LIỆT KÊ
Bước 1 : Nhập N và dãy a1,., aN.
Bước 2 : Đặt Min ? a1, i ? 2;
Bước 3 : Nếu i<=N thì thực hiện bước 4, nếu không thì chuyển đến bước 5.
Bước 4 :
4.1. Nếu Min > ai thì đặt Min ? ai.
4.2. Tăng i một đơn vị rồi quay về bước 3
Bước 5 : Đưa ra Min rồi kết thúc.
SƠ ĐỒ KHỐI :
Mô phỏng thuật toán Min
5
2
1
3
0
5
6
8
9
11
12
10
4
7
-3
-3
-3
-3
-3
-9
0
0
2.Bài toán 2 :

Tìm giá trị LỚN NHẤT của một dãy số với Input và Output như sau:
Input : Số nguyên dương N và dãy N số
a1,...,aN.
Output : Giá trị lớn nhất (Max) của dãy số.


Mô tả thuật toán để giải bài toán này theo cả 2 cách liệt kê và dùng sơ đồ khối.
III. VÍ DỤ VỀ THUẬT TOÁN
(tt)
a) XÁC ĐỊNH BÀI TOÁN
Input : Số nguyên dương N và dãy N số nguyên a1,….,aN.
Output: Giá trị lớn nhất (Max) của dãy số
b) Ý TƯỞNG
Khởi tạo giá trị Max = a1
Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai>Max thì Max nhận giá trị mới là ai
VÍ DỤ ÁP DỤNG
Cho dãy số gồm N số sau (N = 5):
11 6 20 4 8
Tìm giá trị LỚN NHẤT của dãy số trên ?
HƯỚNG DẪN:
Gọi Max là giá trị l?n nhất cần tìm.
Gán Max bằng giá trị phần tử đầu tiên của dãy.

Lần lượt so sánh Max với các phần tử tiếp theo trong dãy. Tại mỗi vị trí so sánh :
+ Nếu Max nh? hơn giá trị phần tử cần so sánh trong dãy thì lấy giá trị của phần tử đó gán lại cho Max.

- Khi so sánh đến phần tử cuối cùng trong dãy số thì Max sẽ mang giá trị l?n nhất của dãy.
Gán i = 2
11 6 20 4 8
Max
Max=11
Max=11
Giá trị l?n nhất: 20
Biến i lưu trữ vị trí tiếp theo mà Max sẽ so sánh
+ Tăng i lên 1 đơn vị
Max=20
Max=20
LIỆT KÊ
Bước 1 : Nhập N và dãy a1,., aN.
Bước 2 : Đặt Max ? a1, i ? 2;
Bước 3 : Nếu i >N thì chuyển đến bước 5.
Bước 4 :
4.1. Nếu ai > Max thì đặt Max ? ai.
4.2. i ? i + 1 rồi quay về bước 3
Bước 5 : Đưa ra Max rồi kết thúc.
SƠ ĐỒ KHỐI :
Nhập N và dãy a1,., aN
Max? a1 ,i ? 2
i >N?
ai >Max?
Max ? ai
i ? i+1
Đưa ra Max rồi kết thúc
Đúng
Sai
Đúng
Sai
Mô phỏng thuật toán Max
5
2
5
3
5
4
7
5
7
6
7
7
15
8
9
15
15
11
15
12
10
15
III. VÍ DỤ VỀ THUẬT TOÁN
(tt)
3.Bài toán 3 :







Mô tả thuật toán để giải bài toán này theo cả 2 cách liệt kê và dùng sơ đồ khối.
Kiểm tra tính nguyên tố của một số nguyên dương:
Input : ?
Output : ?
a) XÁC ĐỊNH BÀI TOÁN
Input :?
Output:?
N là một số nguyên dương
N là nguyên tố hay không nguyên tố
b) Ý TƯỞNG
Nếu N = 1 thì N không là số nguyên tố
Nếu 1Nếu N>=4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố
Vậy nếu có bất kỳ một ước số
khác 1 và chính nó
thì kết luận N không là nguyên tố.
LIỆT KÊ
Bước 1 : Nhập s? nguyên dương N ;
Bước 2 : Nếu N = 1 thì thông báo N không là nguyên tố rồi kết thúc;
Bước 3 : Nếu N < 4 thì thông báo N là nguyên tố rồi kết thúc;
Bước 4 : i ? 2;
Bước 5 : Nếu i > [ ] thì thông báo N là nguyên tố rồi kết thúc;
Bước 6: Nếu N chia hết cho i thì thông báo N không là nguyên tố rồi kết thúc;
Bước 7: i ? i + 1 rồi quay lại bước 5.


SƠ ĐỒ KHỐI :
Nhập N
N=1?
N<4?
i2
N chia hết cho i?
i>[ ]?
N
Thông báo N là nguyên tố rồi kết thúc
Thông báo N không là nguyên tố rồi kết thúc
Đúng
Đúng
Sai
Sai
Đúng
Sai
Đúng
Sai
Mô phỏng thuật toán kiểm tra tính nguyên tố
Với N = 29 ([ ] = 5)
29 là số nguyên tố
29/2
29/3
29/4
29/5
Không
Không
Không
Không
Mô phỏng thuật toán kiểm tra tính nguyên tố
45/2
45/3
Không
Chia hết
45 không là số nguyên tố
Với N = 45 ( [ ] = 6)
CÁC TÍNH CHẤT CỦA
THUẬT TOÁN
Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác
CÁC TÍNH CHẤT CỦA
THUẬT TOÁN (tt)
Tính xác định: Sau khi thực hiện một thao tác thì:
Hoặc thuật toán kết thúc
Hoặc có đúng một thao tác xác định để được thực hiện tiếp theo
CÁC TÍNH CHẤT CỦA
THUẬT TOÁN (tt)
Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.
CÁC THUẬT NGỮ CHÍNH
Là việc nào đó ta muốn máy tính thực hiện
Các thông tin đã có (các giả thiết)
Các thông tin cần tìm từ Input (kết luận)
*Một dãy hữu hạn các thao tác.
*Các thao tác được sắp xếp theo một trình tự xác định.
*Sau khi thực hiện dãy thao tác đó, từ Input ta tìm được Output của bài toán.
Dùng các biểu tượng qui ước để thể hiện các thao tác trong thuật toán
Bài toán
Input
Output
Thuật toán
Sơ đồ khối
Ghi nhớ
Xuất Min
Nhập dãy N
Thực hiện lệnh
(Phép gán, phép tính)
Điều Kiện
Đúng
Sai
Ta cần diễn tả thuật toán bằng một ngôn ngữ sao cho máy tính có thể hiểu và thực hiện được, ngôn ngữ đó gọi là ngôn ngữ lập trình. Kết quả diễn tả thuật toán như vậy gọi là chương trình.
LƯU Ý
TÌM MAX TRONG N SỐ
5
1
4
7
6
3
15
8
MAX
5
5
7
7
15
15
1
2
3
4
5
6
7
8
9
10
9
2
6
4
5
21
22
30
31
33
1
10
5
9
6
10
6
8
30
6
7
6
21
1
a­giua < k
<=> 9 < 21
Dau = Giua+1
2
Giua > K
<=> 30 > 21
Cuoi=Giua-1
3
KẾT THÚC !!!
6
1
5
3
7
8
10
7
12
4
6
1
5
3
7
8
10
7
12
4
6
1
5
3
7
8
10
7
12
4
6
1
5
3
7
8
10
7
12
4
6
1
5
3
7
8
10
7
12
4
6
1
5
3
7
8
10
7
12
4
MÔ PHỎNG THUẬT TOÁN TRÁO ĐỔI (Exchange Sort)
6 1 5 3 7 8 10 7 12 4
1 6 5 3 7 8 10 7 12 4
1 5 6 3 7 8 10 7 12 4
1 5 3 6 7 8 10 7 12 4
1 5 3 6 7 8 7 10 12 4
1 5 3 6 7 8 7 10 4 12
Ví dụ
Cho dãy A gồm các số:
3, 5, 23, 8, 2, 9, 4, 6, 11, 98, 7.
Với khoá k= 4.
1
2
4
3
4
4
4
5
4
6
4
7
4
Vậy chỉ số cần tìm là i= 7.
Ví dụ
Cho dãy A gồm các số:
3, 5, 23, 8, 2, 9, 4, 16, 11, 98, 7.
Với khoá k= 6.
1
6
2
3
6
4
6
5
6
6
6
7
6
8
6
9
6
10
6
11
6
Vậy không có hạn nào của dãy A
Có giá trị bằng k.
K=45
54 12 32 84 78 45 25 34 49
XUẤT i=6
!
K=13
54 12 32 84 78 45 25 34 49
XUẤT THÔNG BÁO DÃY A
KHÔNG CÓ PHẦN TỬ NÀO BẰNG K
?
!
K = 2 và N = 10
A
5
7
1
4
2
9
8
11
25
51
1
5
_
2
_
3
_
4
_
Với i = 5 thì a5 = 2
K = 6 và N = 10
A
I
5
7
1
4
2
9
8
11
25
51
1
2
3
10
4
5
6
7
8
9
11
Với mọi i từ 1 đến 10 không có ai có giá trị bằng 6