Giải thuật

I / Định nghĩa giải thuật : Giải thuật là một hệ thống chặt chẽ và rõ ràng các qui tắc nhằm xác định một dãy các động 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 động tác này ta thu được kết quả mong muốn .

II / Các đặc trưng của giải thuật :
- Tính kết thúc
- Tính rõ ràng , chặt chẽ
- Tính phổ dụng
- Tính hiệu quả

III / Biểu diễn giải thuật :

1 / Phương pháp dùng ngôn ngữ liệt kê các động tác :
Trong đó có các động tác cơ bản :
+ Bắt đầu , thông báo yêu cầu
+ Lệnh gán trị
+ Lệnh thực hiện các phép tính số học , phép tính lô gíc
+ Lệnh kiểm tra điều kiện
+ Lệnh chuyển không điều kiện , lệnh chuyển có điều kiện
+ Lệnh lặp lại
+ Kết thúc

2 / Phương pháp sơ đồ khối :
+Dùng các hình vẽ mô tả các động tác , các mũi tên chỉ thứ tự thực hiện các động tác .


.F.
Bắt đầu Nhóm lệnh
2,3 ...
Điều
kiện

Lệnh 1 Kết thúc .T.



Thí dụ về một số thuật giải thường gặp :

1 / Trao đổi giá trị của 2 biến A và B thông qua biến trung gian C :

B0 Bắt đầu
B1 Nhập giá trị cho A và B
B2 C lấy giá trị của A
B3 A lấy giá trị của B
B4 B lấy giá trị của C
B5 Thông báo kết quả
B6 Kết thúc

2 / Tìm phần tử nhỏ nhất trong dãy số A 1 ,A 2 ,...,A n :

B0 Bắt đầu
B1 Nhập các giá trị N , A 1 ,A 2 ,...,A n
B2 Gán i = 2
B3 Nếu A i < A 1 thì A 1 = A i
B4 Tăng i lên 1 đơn vị
B5 Nếu i<=N thì quay về B3 ( Lệnh lặp )
B6 Nếu i > N thì A 1 nhỏ nhất
B7 Thông báo kết quả
B8 Kết thúc

3 / Duyệt dãy A 1 , A 2 , ... , A n xem có phần tử X hay không :

B0 Bắt đầu
B1 Nhập các giá trị N, A 1 ,A 2 ,...,A n
B2 Gán trị i=1
B3 Nếu i >N thì chuyển sang B6
B4 Nếu A i <> X thì tăng i lên 1 đơn vị , Chuyển về B3
B5 Thông báo kết quả : có X trong dãy A 1 ,A 2 ,...,A n , rồi chuyển sang B7
B6 Thông báo kết quả : Không có X trong dãy A 1 ,A 2 ,...,A n ,
B7 Kết thúc chương trình .

4 / Sắp xếp dãy A 1 ,A 2 ,...,A n , theo thứ tự tăng dần :

B0 Bắt đầu
B1 Nhập N, A 1 ,A 2 ,...,A n
B2 Gán i=1
B3 Gán k=i+1
B4 Nếu A i <= A k thì B6
B5 Thực hiện thuật toán đổi giá trị A i và A j
B6 Tăng j lên 1 đơn vị
B7 Nếu j <= N thì chuyển về B4
B8 Tăng i lên 1 đơn vị
B9 Nếu i < N thì chuyển về B3
B10 Thông báo dãy đã sắp tăng là A 1 ,A 2 ,...,A n .
B11 Kết thúc .



5 / Thuật toán “ Lùa bò vào chuồng “ : Tìm số nguyên dương bé nhất không có trong dãy A 1 ,A 2 ,...,A n .nguyên dương không lớn hơn 32.000

B0 Bắt đầu
B1 Nhập N , A 1 ,A 2 ,...,A n .
B2 Trên trục số đánh dấu các điểm A 1 ,A 2 ,...,A n .
B3 x = 1
B4 Duyệt trên trục số , nếu thấy x là điểm nguyên chưa được đánh dấu thì chuyển sang bước B6
B5 Tăng x lên 1 đơn vị
B6 Thông báo số nguyên dương bé nhất chưa có trong dãy là X
B7 Kết thúc

6 / Thuật toán tìm Ước chung lớn nhất của 2 số nguyên A và B :

B0 Bắt đầu
B1 Nhập 2 số nguyên A và B
B2 Gán A = A , B =  B 
B3 Nếu A =0 và B=0 thì B9
B4 Nếu A=0 và B <>0 thì B10
B5 Nếu B=0 và A <>0 thì B11
B6 Gán dư của phép chia A cho B vào biến D ( D = A mod B )
B7 Nếu D = 0 thì chuyển sang B10
B8 Gán A = B ; B = D ; D = A mod B chuyển về B7
B9 Thông báo UCLN không tồn tại , chuyển về Bkt
B10 Thông báo kết quả : Ước số chung lớn nhất là số B , chuyển về Bkt
B11 Thông báo kết quả : Ước số chung lớn nhất là số A
Bkt Kết thúc

7 / Thuật toán tìm số nguyên tố :

B0 Bắt đầu
B1 Nhập số N
B2 Nếu N=2 hoặc N=3 thì chuyển sang B8
B3 Gán i=-1
B4 Nếu (N mod 2 =0) hoặc (N Mod 3 =0) thì chuyển sang B 9
B5 Tăng i lên 6 đơn vị
B6 Nếu (N mod i <> 0) và (N mod (i+2) <>0) và ( i*i <= N ) chuyển sang B 5
B7 Nếu i*i <= N thì chuyển sang B 9
B8 Thông báo : N là số nguyên tố , chuyển tới B10
B9 Thông báo : N là hợp số
B10 Kết thúc chương trình

Biểu diễn thuật toán : Tìm ước chung lớn nhất của 2 số nguyên bằng sơ đồ khối




A :=  A  Bắt Đầu
B :=  B 




A=0 và B=0 .T. Không có
UCLN



.T.
A<>0 và B=0 UCLN là A




.T. UCLN là B
B<>0 và A=0






D := A mod B



.T.
D = 0 Kết thúc





A := B
B := D
D := A mod B





8 / Thuật toán tìm căn bậc 2 của số không âm A :
B0 Bắt đầu
B1 Nhập số không âm A và sai số cho phép 
B2 X 0 = 1 ( X là giá trị gần đúng đầu tiên của căn bậc 2 của A )
B3 X = X 0
B4 X o = ( X + A/X ) / 2
B5 Kiểm tra :  X 0 - X  <  thì chuyển sang B6 còn không thì chuyển về bước B3
B6 Thông báo căn bậc hai của A là X 0
B7 Kết thúc
9 / Tìm nghiệm gần đúng của một đa thức F(x) bằng thuật toán chia đôi :
B0 Bắt đầu
B1 Nhập các hệ số của đa thức và độ sai số cho phép 
B2 Nhập 2 giá trị A và B sao cho F(A) <0 và F(B) >0
B3 Nếu  B - A  <  thì chuyển tới B10
B4 X = ( A+B )/2
B5 Tính F(X)
B6 Nếu F(X) >0 thì B = X , chuyển về B3
B7 Nếu F(X) <0 thì A=X , chuyển về B3
B8 Nếu F(X) = 0 thì Chuyển tới B10
B10 Thông báo nghiệm là X
B11 Kết thúc
10 / Thuật toán Greedy Algorithm với bài toán tô màu

Bài toán : Cho tập n điểm gọi là tập G , các điểm này được đánh số từ 1 đến N và được nối với nhau bởi một số đoạn thẳng . Hãy tô màu cho các điểm theo nguyên tắc : 2 điểm có đoạn thẳng nối chúng phải tô bằng 2 màu khác nhau . Nêu cách tô màu cho các điểm sao cho càng dùng ít màu càng tốt .
Gợi ý xây dựng thuật toán : Cần tổ chức 2 tập : Tập điểm đã tô màu D và tập điểm chưa tô màu C .Mỗi lần có 1 đỉnh được tô màu thì kết nạp thêm đỉnh đó vào D , tập C loại trừ đỉnh đó . Dùng màu 1 tô cho đỉnh 1 . Số lượng lớn nhất các màu đã dùng là MD=1. Chọn đỉnh i chưa tô màu , cho tập màu T là rỗng , tìm tất cả các đỉnh k nối với i , nếu đỉnh k đã được tô màu thì ghi lại màu của đỉnh k vào tập màu T , so T với tập màu đã dùng TMD gồm các màu từ 1 tới MD , nếu có màu của TMD không thuộc T thì chọn nó làm màu của đỉnh i , ngược lại phải chọn màu MD+1 làm màu cho đỉnh i ; tăng MD lên 1 đơn vị ; thoát khỏi việc chọn màu cho đỉnh i . Quá trình tiếp tục cho đến khi tất cả các đỉnh đều được tô màu

Rõ ràng thuật toán trên đã tìm mọi khả năng tốt nhất để gán màu cho 1 đỉnh . Song lời giải theo thuật toán này chưa tối ưu ( Chưa là lời giải tốt nhất ) vì việc chọn màu tốt nhất cho 1 đỉnh i chưa chắc bảo đảm có lợi cho việc chọn màu của các đỉnh tiếp sau i
Sau này chúng ta sẽ đề cập tới một thuật toán khác có tính tối ưu để giải bài toán tô màu này .
11 / Tìm kiếm nhị phân trên mảng đã được sắp thứ tự
B0 Bắt đầu
B1 Nhập số X và dãy A gồm N phần tử
B2 Gán đầu := 1 ; cuối := N
B3 Kiểm tra đầu <= cuối nếu sai thì chuyển về B 8
B4 giữa := ( đầu + cuối ) div 2
B5 Nếu X > A[giữa] thì đầu := giữa +1
B6 Nếu X < A[giữa] thì cuối := giữa -1
B7 Nếu X= A[giữa] thì cuối := -1
B8 Nếu cuối = -1 thì thông báo có X trong mảng ,còn ngược lại thì thông báo không có X trong mảng
B9 Kết thúc .

12 / Sắp xếp gọn từng Băng với thao tác đổi chỗ trực tiếp 2 phần tử :

Bài toán : Cho dãy số gồm N số , chỉ gồm số 1,2,3 (1<=N<=1000). Một thao tác đổi chỗ giữa 2 phần tử của dãy là trao đổi trực tiếp giá trị 2 phần tử này cho nhau .Bằng số ít nhất các thao tác đổi chỗ , hãy sắp dãy thành dãy không giảm .

Gợi ý :
Đếm số số 1 của dãy là s1 , số số 2 là s2 ; đặt T2=s1+1,T3 = s1+ s2 + 1 , gọi dãy từ vị trí 1 đến vị trí T2-1 là băng 1, từ T2 đến T3-1 là băng 2 , còn lại từ T3 đến N là băng 3
Muốn có phương án sắp tốt nhất , ta chia các thao tác thành 3 loại có thứ tự ưu tiên :
Loại 1 : Thao tác tốt : đổi số 1 ở băng 2 cho số 2 ở băng 1 , hoặc đổi số 1 ở băng 3 cho số 3 ở băng 1
Loại 2 : Thao tác bắt buộc : xảy ra trong hoàn cảnh không còn cách giải quyết khác nữa : Thí dụ như ở băng 2 không còn số 1 , chỉ còn số 1 ở băng 3 , trong trường hợp này đành phải đổi số 2 ở băng 1 cho số 1 ở băng 3 ; hoặc như ở băng 3 không còn số 1 , chỉ còn số 1 ở băng 2 , trong trường hợp này đành phải đổi số 3 ở băng 1 cho số 1 ở băng 2 ;
Loại 3 : Thao tác cuối cùng : Là những thao tác còn lại , phải hoàn thành nốt,mang tính hiển nhiên về cách thức thực hiện , thứ tự thực hiện không ảnh hưởng sự tối ưu . Thí dụ : Khi đã xếp xong Băng 1 , do độ dài các băng đã tính toán sẵn nên có bao nhiêu số 3 trong băng 2 thì cũng còn bấy nhiêu số 2 trong băng 3 .Mặt khác thứ tự trong 1 băng không quan trọng nên có thể thực hiện các thao tác đổi chỗ hoàn toàn tuỳ ý cho các cặp (số 3 trong băng 2 - số 2 trong băng 3 )

B0 Bắt đầu
B1 Nhập N và dãy A(N) ;
B2 i := 1
B3 Nếu i > S1 thì về B11
B4 Nếu (A[i] = 1 ) thì i:=i+1 và về B3
B5 Tĩm vị trí số 1 trong băng 2 gọi là vị trí x (không có thì x=0)
Tĩm vị trí số 1 trong băng 3 gọi là vị trí y (không có thì y=0)
B6 Nếu x=0 và y = 0 thì B11
B7 Nếu A[i] =2 thì B9
B8 Nếu A[i] =3 thì B10
B9 Nếu x>0 thì (đổi A[i] và A[x] ; tăng i := i+1 ; về B3 ) còn không ( x=0 , y>0) thì (đổi A[i] với A[y]; tăng i := i+1 ; về B3 )
B10 Nếu y>0 thì (đổi A[i] và A[y] ; tăng i := i+1 ; về B3 ) còn không ( y=0 , x>0) thì (đổi A[i] với A[x]; tăng i := i+1 ; về B3 )
B11 (Đã xong băng 1), i = T2
B12 Nếu i>T2-1 thì tới B15
B12 Nếu A[i]=2 thì i:=i +1 và về B12
B13 Tìm vị trí số 2 trong băng 3 , gọi vị trí này là z
B14 Đổi A[i] và A[z] ; tăng i := i+1 , về B12
B15 Hiện dãy đã xếp tăng
B16 Kết thúc