Giới thiệu về thuật toán trong tin học
Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc
nhằm xác định một dãy các thao tác trên những đối tượng, sao
cho sau một số hữu hạn bước thực hiện các thao tác ta đạt được
mục tiêu định trước.
Giới thiệu về thuật toán trong tin
học
1. Khái niệm thuật toán
Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc
nhằm xác định một dãy các thao tác trên những đối tượng, sao
cho sau một số hữu hạn bước thực hiện các thao tác ta đạt được
mục tiêu định trước.
Để giải các bài toán bằng máy tính chúng ta thường phải có
một quan niệm rộng rãi hơn về thuật toán cụ thể là lưu ý đến các
đặc điểm sau:
a) Không cần xác định toàn bộ lời giải, các thao tác
theo từng bước một cách chính xác, đơn vị và rõ ràng.Thay
vào đó chỉ cần chỉ ra một cách chuyển từ một bước giải i tới
bước giải kế tiếp i+1, và tìm cách cắt nhỏ bài toán thành các
bài toán con, đó chính là thuật toán đệ quy rất quan trọng
để giải các bài toán tổng quát.
b) Có nhiều bài toán không có cách giải đúng, hoặc
cách giải đúng không thể chấp nhận được do hạn chế về
thời gian chạy và kích thước bộ nhớ. Nhưng nếu ta chấp
nhận kết quả gần đúng thì có thể tồn tại nhiều cách giải đỡ
phức tạp và có hiệu quả hơn, đó chính là các thuật toán
Heuristic để giải các bài toán gần đúng.
2. Khái niệm bài toán:
Trong phạm vi tin học ta có thể quan niệm bài toán là một
việc nào đó ta muốn máy tính thực hiện. Các bài toán được cấu
tạo bởi 2 thành phần cơ bản Input và Output. Thuật toán cũng có
thể được hiểu là một dãy các thao tác được sắp xếp theo trình tự
xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của
bài toán ta nhận được Output cần tìm.
3. Một số ví dụ:
Bài toán 1:Tìm giá trị lớn nhất của một dãy số nguyên
Xác định bài toán
Input: Số nguyên dương N và dãy N số nguyên a1,a2,...,aN
Output: Giá trị lớn nhất Max của dãy số.
Ý tưởng:
Chọn Max=a1
Lần lượt với i từ 2 đến N, so sánh ai với a1, nếu ai>a1 thì
gán Max=ai
Thuật toán giải được mô tả như sau:
Nhập N>0 và dãy a1,a2,…,aN.
Max a1, i 2;
Nếu i > N thì đưa giá trị Max rồi kết thúc;
Nếu ai > Max thì Max ai
i i + 1 rồi quay lại bước 3.
Bài toán 2: Tìm UCLN của hai số nguyên dương m,n.
Xác định bài toán:
Input : 2 số nguyên dương m,n.
Output : UCLN của 2 số.
Ý tưởng 01: UCLN(m,n)=UCLN(m,m-n) (Giả sử m>n)
Thuật toán giải được mô tả như sau:
Nhập 2 số m,n > 0.
Nếu m=n thì đưa ra UCLN(m,n)=m;
Nếu m > n thì m m-n rồi quay lại bước 2.
Nếu n>m thì n n-m rồi quay lại bước 2.
Đưa ra kết quả UCLN khi một trong m hoặc n=0 (Nếu
m=0 thì UCLN(m,n)=n còn nếu m≠0 thì UCLN(m,n)=m)
Ý tưởng 02: UCLN(m,n) = UCLN(n,m mod n)
Thuật toán giải 02 : dành cho bạn đọc.
Bài toán 3: Cho dãy A gồm N số nguyên a1,a2,…,aN. Sắp xếp
các số hạng để dãy A là trở thành dãy không giảm (tức là số
hạng sau luôn lớn hơn hoặc bằng số hạng trước)
Xác định bài toán:
Input: Dãy A gồm N số nguyên a1,a2,…,aN.
Output: Dãy A đã được sắp xếp trở thành dãy không
giảm
Ý tưởng 01:
Với mỗi cặp số hạng đứng liền kề nhau trong dãy, nếu
số đứng trước lớn hơn số đứng sau thì ta đổi chỗ hai số cho
nhau. Quá trình lặp lại cho đến khi không còn sự đổi chỗ xảy
ra.
Thuật toán giải được mô tả như sau:
Nhập N>0 và dãy a1,a2,…,aN.
MN
Nếu M < 2 thì đưa ra dãy A được sắp xếp rồi kết thúc.
Nếu M ≥ 2 thì M M-1, i 0
i i+1
Nếu i > M thì quay lại bước 3.
Nếu ai > ai+1 thì tráo đổi vị trí ai và ai+1
Quay lại bước 5.
Ý tưởng 02 :
Chia dãy cần sắp xếp thành 2 phần, lấy thành phần giữa X làm
chuẩn để so sánh.
• Tìm một phần tử A ở dãy trên có giá trị lớn hơn X
• Tìm một phần tử B ở dãy dưới có giá trị nhỏ hơn X
• Hoán vị A và B.
• Tiếp tục như vậy cho đến khi ta đạt được dãy trên chỉ
gồm các phần tử nhỏ hơn X, dãy dưới chỉ gồm các phần
tử lớn hơn X.
• Áp dụng thuật toán trên vào dãy trên và dãy dưới (đệ
quy) cho đến khi không chia được nữa.
Thuật toán giải 02: bạn thử mô tả xem sao, đây coi như là
một bài tập nhỏ cho các bạn yêu thích lập trình.
Bài toán 4: Cho dãy A gồm N số nguyên a1,a2,…,aN và một số
X. Hãy xác định xem giá trị của X có nằm trong dãy A không?
Nếu có thì nằm ở đâu ?
Xác định bài toán:
Input: dãy A gồm N số nguyên a1,a2,…,aN và số X.
Output: X có thuộc A không? Nếu có thì nằm ở vị trí nào?
Ý tưởng: So sánh từng phần tử của dãy với X. Nếu có phần tử
ai = X thì đưa ra thứ tự của phần tử thứ i thỏa ai = X.
Thuật toán giải được mô tả như sau :
Nhập N>0 ,dãy a1,a2,…,aN ,và số X
i 1.
Nếu i > N thì kết thúc và đưa kết quả
Nếu i < N thì tiếp tục.
Nếu ai = X thì kết thúc và đưa ra thứ tự của X là i .
Nếu ai ≠ X thì i i + 1 và quay lại bước 5. Vòng lặp
kết thúc khi i > N
4.(nói thêm) Phương pháp tinh chế từng bước trong
lập trình:1
1
Trích từ cuốn “Phương pháp giải các bài toán trong tin học” của Thạc sĩ Trần Đức Huyên (NXBGD
2001)
Ban đầu chương trình được viết bằng những lời tự
nhiên (tiếng Việt chẳng hạn) thể hiện sự phân tích
tổng thể của người lập trình.
Ở từng bước sau, mỗi câu lời được phân tích ra chi
tiết hơn bằng nhiều câu lời khác tương ứng với sự
phân tích một công việc thành những công việc
nhỏ hơn. Mỗi câu lời đó là một sự đặc tả công việc.
Ta nói ở mỗi bước ta đã tinh chế những câu lời đó.
Sự tinh chế được hướng về phía ngôn ngữ lập trình
mà ta sẽ dùng. Nghĩa là, càng ở những bước sau,
các câu lời tự nhiên càng được thay nhiều bằng các
câu lời của ngôn ngữ lập trình.
Một câu lời tự nhiên nếu đơn giản thì ta có thể thay
bằng một vài phát biểu, nếu phức tạp thì ta coi nó
như một thủ tục và tiếp tục tinh chế nó.
Trong qua trình tinh chế đó, ta cần đưa ra những
biểu diến dữ liệu, vì dữ liệu là nguyên liệu của máy
tính. Như vậy cùng với sự tinh chế các công việc,
dữ liệu cũng được tinh chế, phân rã, hay cấu trúc
hóa. Điều này có nghĩa là sự tinh chế các dặc tả
chương trình và dữ liệu là song song.
Phương pháp tinh chế từng bước là một thể hiện
của tư duy giải quyết vấn đề từ trên xuống, trong
đó sự phát triển của các bước là hướng về phía
ngôn ngữ lập trình được dùng. Đáy của sự đi xuống
trong hoạt động phân tích là các phát triển và các
mô tả dữ liệu viết bằng ngôn ngữ lập trình.
Hiểu được phương pháp tinh chế từng bước sẽ
giúp người lập trình có được môt định hướng thể
hiện sự ngăn nắp trên tờ giấy nháp của mình, tránh
khỏi việc phải mò mẫm, thử đi thử lại nhiều lần các
chương trình mang tính trực giác.
