PHƯƠNG PHÁP TỔNG QUÁT ĐỂ GIẢI MỘT BÀI TOÁN BẰNG MÁY ...

 XÁC ĐỊNH BÀI TOÁN

1. Khái niệm bài toán

Trong quá trình tổn tại và phát triển, mọi cá nhân luôn phải liên tục giải quyết các bài toán. Cuộc sống là một chuỗi các bài toán mà ta phải đối đầu để giải quyết.

Theo nhiều nhà nghiên cứu thì mọi bài toán đều có thể diễn đạt theo một sơ đồ chung:

A [đến] B

Trong đó:

* A là giả thiết, điều kiện ban đầu hoặc là cái đã cho, đã có khi bắt đầu giải bài toán.

* B là kết luận, mục tiêu cần đạt hoặc là cái phải tìm, phải làm ra khi kết thúc bài toán.

* [đến] là suy luận, giải pháp cần xác định hoặc là một chuỗi các thao tác cần thực hiện, cần thi hành để có được cái phải tìm B từ cái đã có A.

2. Xác định bài toán

Theo sơ đồ trên thì xác định bài toán có nghĩa là xác định A, B và nếu có thể được thì xác định luôn các thao tác được phép sử dụng để đi từ A đến B. (Điều này rất quan trọng nhưng lại thường được hiểu ngầm).

3. Bài toán trên máy tính

Một bài toán trên máy tính cũng mang đầy đủ các tính chất của một bài toán tổng quát đã nói ở trên nhưng có thể được diễn đạt theo một cách nói khác.

* A : là “input” hay còn gọi là thông tin vào.

* B : là “Output” hay còn gọi là thông tin ra.

* [đến] : là chương trình tạo ra từ các lệnh cơ bản của máy cho phép biến đổi từ A thành B

4. Những khó khăn

Để xác định một bài toán trên máy tính ta thường gặp hai khó khăn sau:

* Thông báo về A hay B không đầy đủ và không rõ ràng.

* Thông báo về các điều kiện đặt ra cho cách giải (đến) thường không được nêu ra một cách minh bạch.

5. Một số ví dụ

Bài toán 1 (Bài toán 8 quân hậu)

Hãy tìm các cách đặt 8 quân hậu trên một bàn cờ vua sao cho không có quân hậu nào có thể ăn quân hậu khác.

Xác định bài toán

1. Xác định thông tin vào (INPUT):

— Một bàn cờ vua là một bảng hình vuông gồm 8 hàng và 8 cột:

— Quân hậu là quân có thể ăn được bất kì quân nào nằm trên cùng một hàng, cùng một cột hay cùng một đường chéo.

— Ta có tất cả là 8 quân hậu.

1. Xác định thông tin ra (OUTPUT)

— Các bảng vuông trên đó đã có đánh dấu vị trí của 8 quân hậu sao cho không có quân hậu nào có thể ăn quân hậu khác nghĩa là trên mỗi hàng, mỗi cột, mỗi đường chéo chỉ có thể có một quân hậu. Ví dụ:

— Chỉ ra tất cả các bảng vuông khác nhau thỏa điều kiện của đề bài như bảng vuông ở trên.

Xác định các thao tác chế biến thông tin

— Lần lượt xác định vị trí của một trong 8 quân hậu trên bàn cờ (một ô trong số 64 ô) sao cho:

— Đặt đủ 8 quân hậu.

— Tất cả đều thỏa các điều kiện đã nêu.

Bài toán 2 (Bài toán mã đi tuần)

Cho một bàn cờ có kích thước n X n (n > 3).

Một con mã di chuyển theo luật cờ vua được đặt trong một ô với tọa độ đầu là (x1, y1). Hãy tìm một đường đi với n2 – 1 bước đi sao cho mọi ô trên bàn cờ đều được mã nhảy đến đúng một lần.

Xác định bài toán

1. Xác định thông tin vào (INPUT)

— Một bảng vuông kích thước n x n

— Tọa độ của vị trí thứ nhất của quân má.

— Tám nước đí có thể của quân mã được biểu diễn bởi hình sau:

1. Xác định thòng tin ra (OUTPUT)

— Một bảng vuông trên đó có đãnh dấu vị trí theo thứ tự từ 1 (vị trí đầu) đến n2 (vị trí cuối) của quân mã.

— Từ vị trí k đến vị trí k 4- 1 phải theo đúng luật đi của quân mã (nghĩa là chỉ được sử dụng 1 trong 8 nước đi mô tả ở trên).

— Ví dụ : (n = 5, X1 = 3, y1 = 3 )

23	10	15	4	25
16	5	24	9	14
11	22	1	18	3
6	17	20	13	8
21	12	7	2	19

Xác định các thao tác chế biến thông tin:

– Lần lượt xác định các vị trí của quân mã (từ 2 đến n2 ) sao cho quân mã:

• Di chuyển đúng luật,
• Mỗi ô chỉ được đi một lần.

Bài toán 3

Cho một dãy số nguyên dương

a1, a2, a3,…, an.

Hãy tìm từ dãy trên một dãy con (không nhất thiết phải liên tiếp) tăng và có độ dài là dài nhất.

Xác định bài toán

1. Xác định thông tin vào (INPUT)

— Một dãy số nguyên dương

a1, a2, a3,… an

— Mỗi số được xác định bởi 2 yếu tố là giá trị của số và vị trí (số thứ tự) của số đó trong dãy.

1. Xác định thông tin ra (OUTPUT)

— Một dãy lấy ra từ dãy đã cho:

ai­1, ai2­, ai3,…, aik

(Nghĩa là dãy con thu được sau khi gạch bỏ một số phần từ của dãy đã cho).

— Dãy con này phải có 2 tính chất:

• Tăng

ai­1 < ai2 < ai3,…, < aik

• Có độ dài là dài nhất trong các dãy có thể lấy được.

Xác định các thao tác chế biến thông tin:

— Lần lượt duyệt các phần tử của dãy đã cho.

— Phải quyết định xem phải loại bỏ phần tử nào để dãy còn lại là tăng và dài nhất.

Bài toán 4

Cho 2 số tự nhiên a, b. Tìm ước số chung lớn nhất của chủng.

Xác định bài toán

1. Xác đinh thông tin vào (INPUT):

— Hai số tự nhiên a, b.

1. Xác định thòng tin ra (OUTPUT):

— Số tự nhiên d thỏa

• d là ước của a và d là ước của b
• d lớn nhất trong tập các ước chung của a và b.

Xác đinh các thao tóc chế biến thờnỉi tin

— Xây dựng một dãy hữu hạn các thao tác cho phép tính được d từ a và b.

Ví dụ :

a = 16,

b = 24,

d = 8

6. Một số nhận xét quan trọng

Qua các ví dụ trên ta thấy một số nhận xét quan trọng sau đây:

— Việc xác định bài toán là rất quan trọng nó ảnh HƯỚNG rất lớn đến cách thức và chất lượng của viêc giải quyết bài toán.

— Một bài toán cho dù dược diễn đạt bằng thông báo chính xác đến đâu đi chăng nữa cũng phải giả định là phần lớn thông tin về A và B tiềm ẩn trong đầu người giải. Thông báo về A hoặc B chỉ là biểu tượng gợi nhớ đến các thông tin tiềm ẩn đó.

— Bước đầu tiên để xác định một bài toán là phải phát biểu lại bài toán một cách chính xác theo ngòn ngữ của riêng mình vì đó chính là cách ta tiếp cận bài toán, hiểu bài toán.

— Bước kế tiếp là tìm hiểu các thòng tin Input A và thông tin Output B, tìm các mối liên hệ giữa chúng.

— Nên xét một vài trường hợp cụ thể để thông qua đó hiểu được cả bài toán và cũng thông qua đó thấy rõ được các thao tác cần phải tiến hành. Thực tế cho thấy có những bài toán trong tin học chỉ có thể mô tả được thông qua các ví dụ.

2. TÌM CẤU TRÚC DỮ LIỆU

BIỂU DIỄN BÀI TOÁN

1. Khái niệm ban đầu

Máy tính điện tử được phát minh như một thiết bị nhầm làm dễ dàng và tiến hành nhanh các tính toán phức tạp và lớn. Trong nhiều ứng dụng, khả năng lưu trữ và truy cập lượng thông tin lớn giữ vai trò quan trọng và được xem như là đặc trưng chính của nó, và khả nâng tính toán trở thành ít quan trọng trong nhiều trường hợp. Trong thực tế, thông tin cần xử lí là trừu tượng. Thông tin cung cấp cho máy tính điện tử (MTĐT) gồm một tập hợp dữ liệu về bối cảnh thực đã được mã hóa. Nói rõ hơn, tập hợp này được xem như thích đãng cho vấn đề định sẵn. Từ đó có thể đưa vào máy tính và tính ra kết quả cần tìm.

Khi giải một bài toán ta cần phải định nghĩa tập hợp dữ liệu để biểu diễn tình trạng cụ thể. Việc lựa chọn này tùy thuộc vào vấn đề phải giải quyết. Sau đó là việc lựa chọn cách biểu diễn thông tin này. Thông thường việc lựa chọn này phải tùy thuộc vào các thao tác cần thực hiện trên dữ liệu.

Ví dụ:

— Nếu chỉ cần thao tác cộng (+) thì cách tốt nhất để biểu diễn một số n là n que hoặc dùng số La Mã. Qui tắc cộng với sự biểu diễn này là khá đơn giản và tự nhiên trong khi đó phép biểu diễn dùng số Ả Rập đòi hỏi các quy tắc ít hiển nhiên hơn.

— Tuy nhiên, trường hợp trên bị đảo ngược khi ta xét đến việc cộng các số lớn hoặc khi xét phép nhân hoặc phép chia. Việc phân tích các thao tác trên thành các thao tác đơn giản được thực hiện dễ dàng trong phép biểu diễn hằng số Ả Rập mà nguyên tắc giá trị dựa trên vị trí các chữ số.

– Mọi người đều biết là MTĐT biểu diễn mọi dữ liệu bằng các chữ số nhị phân (bit). Phép biểu diễn này ít thích hợp cho con người vì cần khá nhiều bit, song nó lại khá thích hợp cho các mạch điện tử vì hai trị 0 và 1 có thể được biể diễn một cách dễ dàng và tin cậy được với sự có hay vắng mặt cảu dòng điện, từ trường hoặc điện tích.

2. Các câu trúc dữ liệu thường dùng

– Trong ngôn ngữ PASCAL ta có sơ đồ các kiểu dữ liệu như sau:

DATA TYPE gồm có SIMPLE TYPE và STRUCTURE TYPE.

SIMPLE TYPE gồm BASIC TYPE (BOOLEAN, INTEGER, REAL, CHAR) và USER DEFINED TYPE (SUB_RANGE, ENUMERATED)

STRUCTURE TYPE gồm ARRAY, SET, RECORD, STRING, FILE

BOOLEAN : Kiểu logic chỉ có thể nhận một trong hai giá trị TRUE hoặc FALSE

INTEGER : Kiểu số nguyên (-32768 .. 32767)

REAL : Kiểu số thực (2.9 X 10-39..1.7x 1038 )

CHAR : Kiểu kí tự (chữ viết, chữ số,..)

SUB RANGE : Kiểu miền con cùa một kiểu sơ cấp. Ví dụ:

TYPE

Chu_hoa = ’A’ .. ’Z’ ;

Chu_thuong = ’a’ ..’z’ ;

Tuoi_tho = 0 .. 200 ;

* ENUMERATED : Kiểu liệt kê được định nghĩa bằng cách liệt kê tất cả các phần tử có thể có.

Ví dụ :

TYPE

Thu = (ChuNhat, ThuHai, ThuBa, ThuTu, ThuNam, ThuSau, ThuBay);

Color = (Red, Blue, Green, White, Black);

Trui cay = (Cam, Xoai, Man, Nho);

*     * ARRAY : Kiểu mảng gồm một tập hợp các phần tử cùng thuộc một kiểu dữ liệu cơ sở được xác định bởi chỉ số.

Ví dụ:

TYPE

A = ARRAY [Kiểu chỉ số] OF [Kiểu cơ sở] ;

B = ARRAY [1.. 100] OF Integer ; C = ARRAY [1.. 10, 1.. 20] OF Boolean ;

* RECORD : Kiểu bản ghi gôm một tập hợp các phần tử thuộc các kiểu dữ liêu khác nhau.

Ví dụ:

TYPE

Hocsinh = RECORD

HoTen : String [30] ;

Lop : 1.. 12 ;

Truong : String [30] ;

DiemTB : Real ;

Ketqua : Boolean ;

END ;

* SET : Kiểu tập hợp gồm một số các đối tượng có cùng kiểu cơ sở.

Ví dụ:

TYPE

Chucai = SET OF CHAR ;

Chuso = SET OF 0.. 9 ;

* STRING : Kiểu chuối gồm một dãy các kí tự.

Ví dụ:

TYPE

Tên chuỗi = STRING [Chiều dài chuỗi].

* FILE : Kiểu Tệp gồm một tập hợp các dữ liệu có liên quan với nhau và có cùng kiểu được nhóm lại thành một đãy và được lưu trữ trên đĩa.

Ví dụ:

TYPE

Tep = FILE OF integer ;

Bai = TEXT ;

3. Các lưu ý khi chọn cấu trúc dứ liệu

Khi lựa chọn cấu trúc dử liêu để biểu diễn một bài toán ta nên dựa vào các tiêu chuẩn sau đày:

— Cấu trúc dữ liệu phải biểu diễn được đầy đủ các thông tin nhập và xuất của bài toán.

— Cấu trúc dữ liệu phải phù hợp với các thao tác của thuật toán mà ta lựa chọn để giải quyết bài toán.

— Cấu trúc dữ liệu phải phù hợp với điều kiện cho phép của ngôn ngữ lập trình và MTĐT đang sử dụng.

4. Các ví dụ

Bài toán 1 (Bài toán 8 quân hậu)

— Bàn cờ là một bảng vuông 8×8 , nên rõ ràng cấu trúc mảng (ARRAY) là thích hợp để biểu diễn.

— Theo luật cờ vua, một quân hậu ăn được mọi quân khác nằm cùng hàng, hoặc cùng cột hoặc trên cùng đường chéo trên bàn cờ. Vậy ta suy ra mỗi cột có thể chứa một và chỉ một quân hậu. Do đó để đơn giản ta ký hiệu quân hậu ở cột i là i. Như vậy tham biến i trở thành chỉ số cột và việc lựa chọn được tiến hành trên tám giá trị của chỉ số hàng j.

— Để tìm dữ liệu biểu diễn tám quân hậu trên bàn cờ, cách chọn thoạt tiên là dùng mảng vuông để biểu diễn bàn cờ, nhưng xem kỹ thấy cách biểu diễn đó dẫn tới các thao tác cồng kềnh trong việc thử quyền sử dụng các quân hậu ở các vị trí. Điều đó hết sức không hay vì thao tác trên lại phải thực hiện nhiều lần. Do đó ta sẽ chọn cách biểu diễn sao cho thao tác trên dễ bao nhiêu hay bấy nhiêu. Cách tốt nhất là biểu diễn các thông tin thực sự nổi bật và được sử dụng một cách càng trực tiếp càng tốt. Trong trường hợp của bài toán này thì đó không phải là vị trí các quân hậu mà là phải chăng đã có một quân hậu trên mỗi hàng và các đường chéo (Ta đã biết rằng đúng một quân hậu đã được đặt trên mỗi cột k, với 1 < k < i). Điều đó dẫn tới cách chọn các biến như sau:

Var x : array [1 .. 8] of Integer;

a : array [1 .. 8] of Boolean;

b : array [b1 .. b2] of Boolean;

c : array [c1 .. c2] of Boolean;

Trong đó

x[i] biểu diễn vị trí của quân hậu trong cột thứ i;

a|j] = True có nghĩa là không có quân hậu nào nầm trên hàngj;

b[k] = True có nghĩa là không có quân hậu nào nằm trên đường chéo thứ k;

c[k] = True có nghĩa là không có quân hậu nào nằm trên đường chéo thứ k;

Các chỉ số của b và C đều tính toán được, do đó việc chọn các giới hạn chỉ số b1, b2, c1, c2 cũng được quyết định theo; ta lưu ý rằng trên một đường chéo thì mọi ô có cùng tổng số các tọa độ i + j, và trên một đường chéo thì hiệu số các tọa độ i — j là không đổi. Cụ thể là:

b1 = 2, b8 = 16

c1 = -7, c8 = 7

Với cách chọn cấu trúc dữ liệu biểu diễn bài toán như trên thì :

* Câu lệnh đặt quân hậu sẽ là như sau:

X [i] := j;

A [j] := False;

B [i + j] := False;

C [i — j] := False;

* Câu lệnh cất quân hậu sẽ là:

a [j] := True;

b [i + j] := True;

c [i — j] := True;

* Điều kiện an toàn của ô (i, j) có thể đặt quản hậu được biểu diễn bởi biểu thức logic:

a [j] and b [i + j] and C [i — j] .

Bài toán 2 (Đài toán mã di tuẩn)

— Ta có thể biểu diễn bàn cờ bằng một ma trận gọi là dd. Đồng thời ta đưa ra một kiểu dữ liệu để chỉ các giá trị chỉ số.

Type chỉ số = 1.. n;

Var dd : array [chỉ số, chỉ 8ố] of integer;

— Ta quyết định chọn biểu diễn của mỗi ô trên bàn cờ bởi một số nguyên chứ không phai một giá trị Boolean để chỉ ô bị chiếm, vi rằng ta còn muốn giữ lại dấu vết của các ô bị chiếm theo tuần tự. Qui ước như sau là một cách chọn lựa hiển nhiên:

dd[x, y] := 0 : ô (x, y) chưa được thăm đến.

dd[x, y] := i : ô (x, y) đã được thăm ờ nước thứ ỉ (1 < ỉ < n2).

— Để tìm cấu trúc dữ liệu để biểu diễn 8 nước đi có thể của con mã ta phân tích như sau:

Cho một cặp tọa độ xuất phát (x, y) thì có 8 chỗ lần lượt có thể lấy làm tọa độ mã nhảy đến (u, v). Chúng được đãnh số từ 1 đến 8 như trong hình. Một phương pháp đơn giản đế thu được u, V từ X, y là cộng thêm các chênh lệch về tọa độ chừa sẵn trong một mảng các cặp chênh lệch, hoặc trong hai mảng của từng chênh lệch. Giả sử các mảng đó là a và b ta gán giá trị như sau:

a m := 2 ; b [1] := 1 ;

a [2] := 1 ; b [2] := 2 ;

a [3] := – 1 ; b [3] := 2 ;

a [4] := – 2 ;  b [4] := 1 ;

a [5] := – 5 ; b [5] := – 1 ;

a [6] := 1 ; b [6] := – 2 ;

a [71 := 1 ; b [7] := – 2 ;

a [8] := 2 ; b [8] := – 1 ;

— Còn một chi tiết nữa không thể bỏ qua đó là : Một biến [u, v] chỉ tồn tại được nếu cả hai u và V đều nằm trong các giới  hạn 1.. n Vậy ta nên xây dựng tập S : = [1.. n] và điều kiện đi được của con mã là

For j := 1 to 8 do

Begin

u := X + a Ịj] ;

V := y + b UI ;

If (u in S) and (v in S) and dd [u, v] = 0

then

Begin

dd [u, v] := i ;

X := u ; y := V ;

Try (i + 1) ;

X := u – a Ịj] ;

y := V – b Ịj] ;

dd [u, v] := 0 ;

end ;

end ;

§3. TÌM THUẬT TOÁN

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 qui 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.

2. Các đặc trưng của thuật toán

a/ Tính xác định

Ở mỗi bước của thuật toán, các thao tác phải hết sức rõ ràng. Không thể gây nên sự nhập nhằng, lẫn lộn, tùy tiện. Nói cách khác là trong cùng một điều kiện, hai bộ xử lí cùng thực hiện một bước của thuật toán thì phải cho cùng một kết quả.

b/ Tính hữu hạn dừng

Một thuật toán bao giờ cũng phải dừng lại sau một số hữu hạn bước.

c/ Tính đúng đắn

Sau khi thực hiện tất cả các lệnh của thuật toán ta phải được kết quả mong muốn, kết quả đó thường được xác định theo định nghĩa có trước.

d/ Tính phổ dụng

Thuật toán có thể giải bất kì bài toán nào trong cùng một lớp các bài toán, có nghĩa là thuật toán có thể làm việc với các dữ liệu khác nhau, trong một miền xác định và luôn dẫn đến kết quả mong muốn.

d/ Tính có đại lượng vào và ra

Khi bắt đầu, một thuật toán bao giờ cũng nhận các đại lượng vào mà ta thường gọi là dữ liệu vào, các dữ liệu vào thường lấy từ một tập xác định cho trước.

Sau khi kết thúc, một thuật toán bao giờ cũng cho ta một số đại lượng ra tùy theo chức năng mà thuật toán đảm nhiệm, chúng thường được gọi là dữ liệu ra.

f/ Tính hiệu quả

— Tính hiệu quả của một thuật toán được đãnh giá dựa trên các tiêu chuẩn sau:

* Dung lượng bộ nhớ cần có.

* Số các phép tính cần thực hiện.

* Thời gian cần thiết để chạy.

* Có dễ hiểu đối với con người không.

* Có dễ cài đặt trên máy không.

3. Mở rộng khái niệm thuật toán

Để có thể 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.

Ví dụ 1 (Bài toán Euclide)

Tìm ước số chung lớn nhất của hai số nguyên dương m và n. Ta cổ thuật toán Euclide dược diễn tả bằng lưu đồ như sau:

Ví dụ 2 (Bài toán sàng Eratosthenes)

Tim tất cả các số nguyên tố trong các số nguyên từ 1 đến N.

(N lớn hơn hoặc bằng 3 )

Ta có thuật toán Eratosthenes như sau:

Ví dụ 3 (Bài toán 8 quân hậu)

Hãu tìm cách đặt 8 quân hậu trên một bàn cờ vua sao cho không có quân hậy nào có thể ăn quân hậu khác.

Ta dùng thuật toán Đệ qui có quay lui dựa trên phương pháp thử và sai như sau:

Ví dụ 4 (Bài toán mã đi tuần)

Cho một bàn cờ có kích thước n x n. Một con mã di chuyển theo luật cờ vua được đặt trong một ô với tọa độ đầu là (x1y1). Hãy tìm một dường đi với n2-1 bước đi sao cho mọi ô trên bàn cờ đề được mã nhảy đến đúng một lần.

Ta dùng thuật toán Đệ qui có quay lui dựa trên phương pháp thử và sai như sau:

Ví dụ 5

Cho 2 dãy số nguyên dương a1, a2,…, an

b1, b2,…, bm

sao cho a1 + a2 + … + an = b1 + b2 + … + bm

Hãy lập một bảng số a [1.. n, 1.. m] gồm các số nguyên dương thỏa mãn:

— Tổng các số ở hàng i bhng ai

— Tổng các số ở cột j bàng aj

Ta sử dụng thuật toán Heuristic “GREEDY” (Tham ăn) như sau:

§4. LẬP TRÌNH

1. Khái niệm

Lập trình là dùng một ngôn ngứ máy tính cụ thể nồo đó (ví dụ I ’itHcal) để diỗn tả thuật toán, cấu trúc dữ liệu thành các câu lệnh để mriy tính có thể thực hiện được và giải quyết đúng bài toán mà người l(q» trình mong muốn.

2. Kĩ năng lập trình

Kĩ năng lập tringh là kĩ năng cài đặt thành công các thuật toán bằng một ngôn ngữ lập trình. Đã gọi là kĩ năng thì chỉ có thể có được thông qua rèn luyện tích cực.

Kinh nghiệm cho thấy một thuật toán hay nhưng do cài đặt vụng về, lộn xộn khi chạy trên máy tính có thể cho kết quả rất tồi tệ.

3. Phát triển chương trình bằng cách tinh chế từng bước

Tinh chế từng bước là một phương pháp khoa học, có hệ thống giúp ta phân tích các thuật toán và cấu trúc dữ liệu từ đó viết thành chương trình.

Muốn lập trình giỏi không phải chỉ cần nắm vững ngôn ngữ lập trình là đủ.

Vấn đề cốt yếu là biết phương pháp phát triển dần dần để chuyển các ý tưởng ra thành chương trình hoàn chỉnh.

4. Phương pháp tinh chế từng bước

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 (tiếng Việt) càng được thay nhiều bằng các câu lời của ngôn ngữ lập trình (ví dụ Pascal)

— Một câu lời tự nhiên nếu đơn giản thì có thể thay bằng một vài phát biểu, còn nếu nó tỏ ra phức tạp thì có thể coi nó là một thủ tục, và ta tiếp tục tinh chế nó.

— Trong quá trình tinh chế đó, ta cần phải đư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 đặ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.

5. Các ví dụ

Ví dụ 1 (Bài toán Euclide)

Tìm ước số chung lớn nhất của hai số nguyên dương m và n.

Theo thuật toán Euclide đã trình bày trong §3 ta tinh chế chương trình như sau:

Bắt đầu

Nhập m, n, lưu m vào a, lưu n vào b

While m khác n

If M > n then thay m bởi m — n

else thay n bởi n — m

Xuất UCLN của a, b là m

Kết thúc

Chương trình có thể được viết hoàn chỉnh như sau

Program UCLN ;

Var m, n : integer ; a, b : integer ;

Begin

Writeln (’Xin cho biet m, n’) ;

Readln (m, n) ; a := m ; b := n ;

While m < > n do

if M > n then m := m — n

else n := n — m;

Writeln (’UCLN cua’ , a, b, ’la’ , m) ;

Readln ;

End.

Ví dụ 2 (Bài toán Sàng Eratosthenes)

Tìm tất cả các số nguyên tố trong các số nguyên từ 1 đến N (N lớn hơn hoặc bằng 2).

Theo thuật toán Eratosthenes trong §3 ta có thể tinh chế chương trình như sau.

TINH CHẾ LẦN I

– Lấy 2 tập

NT = [] (Để chứa các số nguyên tố tìm được)

S = [2,.. N] (Tập các số cần xét)

– Tìm số đầu tiên trong s đưa vào NT.

– Loại bỏ khỏi s các bội số của số nguyên tố vừa tìm được (sàng lọc)

– Số đầu tiên còn lại của s là số nguyhn tft Tiếp tục quá trình cho đến khi s = [ ]

– Xuất NT

TINH CHẾ LẦN 2

Bắt đầu

NT := [ ] ;

S := [2… N] ;

Repeat

Tìm số đầu tiên trong S

NT := NT + [S0]

Loại khỏi S các bội của S0

Until S = [ ]

Xuất NT ;

Kết thúc.

TINH CHẾ LẲN 3 (Chương trình hoàn chỉnh)

Program ERATOSTHENES ;

Const

N = 100 ;

Type

Nguyen = 1.. N ;

Var

NT, S:Set of Nguyen ;

S0 , I : Integer ;

Begin

NT := [ ] ;

S := [2.. N] ;

S0 := 2 ;

Repeat

While n0t (S0 in S) do

S0 :=S0+1 ;

NT := NT + [S0] ;

I := SO ;

While I =< N do

Begin

S := S – [I]

I := I + S0 ;

End ;

Until S = [];

For I := 1 to N do

If I in NT then writeln (I) ;

Readln ;

End

Rõ ràng là cấu trúc dữ liệu tập hợp Set of Nguyen tuy dễ hiểu nhưng rất cồng kềnh và làm máy chạy rất chậm chạp, ta có thể dùng mảng Boolean linh hoạt hơn như sau:

TINH CHẾ LẦN 4 (Dùng mảng Boolean)

Program ERATOSTHENES Const N = 1000 ;

Var a : array [1.. n] of Boolean ;

i, j : integer ;

Begin

a [1] := False ;

For i := 2 to N do a [i] := true ;

For i := 2 to (N div 2) do For j : = 2 to (N div i) do

a [i * j] := False ;

For i := 1 to N do

If a [i] then write (i : 4) ;

Writeln ;

End.

Trong ngôn ngữ PASCAL, nếu dừng mảng Boolean thì ta bị giới hạn N nhỏ hơn hoặc bằng 10000. Để có thể chạy với số lớn hơn ta không dùng mảng lưu như sau.

TINH CHẾ IẢN 5 (Không dùng Mảng, tập hợp)

Program Eratosthenes ;

Var i, j, k, n : integer ;

Begin

Repeat

Write (‘N =  ’) ; Readln (N) ;

Until n >= 2 ;

Write (*2*) ;

For i := 3 to N do Begin

K := 0 ;

For j := 2 to Trunc [Sqrt (i)] do If (i mod j) = 0 then K := 1 ;

If K = 0 then write (i) ;

End ;

End.

Ví dụ 3 (Bài toán 8 quân hậu)

Hãy tìm cách đặt 8 quân hậu trên một bàn cờ vua sao cho không có quân hậu nào có thể ăn quân hậu khác.

Theo thuật toán đệ quy có quay lui dựa trên phương pháp thử và sai đã trình bày ở §3 ta có chương trình Pascal như sau.

TINH CHẾ LẦN 1

Program EIGHT_QUEEN;

Var a, x : array [1.. 8] of integer;

b:array [2.. 16] of integer;

c:array [-7, 7] of integer;

i:integer;

Procedure print;

Var j : integer;

Begin

For j := 1 to 8 do write (x [j] : 4);

Writeln;

Readln;

End;

Procedure Try (i : integer);

Var j : integer ;

Begin

if i > 8 then print else

For j:= 1 to 8 do

if (a [j] = 0) and (b [i + j] = 0) and

(c [i – j] = 0) then

Begin

x [i] := j;

a U] := 1;

b [i + j]:= 1;

c [i – j]:= 1;

Try (i + 1);

c [i – j]:= 0;

b [i + j]:= 0;

a [j] := 0;

end;

end;

Procedure Init;

Var j : integer;

Begin

Fiilchar (a, sizeof (a), 0);

Fillchar (b, sizeof (b), 0);

Fiilchar (c, sizeof (c), 0);

End;

Begin [Chương trình chính]

Init;

Try (1) ;

End.

Sau khi chạy chương trình trên, một trong các kết quả có thể thấy trên màn hình là:

1

5

8

6

3

7

2

4

Ứng với một lời giải sau trên bàn cờ:

Muốn tránh dùng đệ quy ta có thể dùng vòng lạp Repeat như sau :

Xét cột đầu:

j := 1 ; i = 0;

Thử cột

Repeat

i := i + 1 (xét một hàng)

Antoan := a [i] and b [i + j] and C [i + j];

Until antoan or (i = 8)

Đặt quân hậu vào ô (i, j);

X [i] := i;

a [i] := False; b [i + j] := False;

c [i – j] := False;

Xét cột kế

j := j + 1; i := 0 Đã xong với cột cuối j > 8 Đã quay lại qua cột đầu j < 1 Quay lại

j : = j — 1; [xét lại cột trước]

if j > = 1 then

Begin

Loại quân hậu ở ô (i, j) {i = X [j]}

if i = 8 then Begin

j = j — 1

if j > = 1 then

Bỏ quân hậu ỏ ô (i, j) {i = X [j]}

end;

end;

end;

Bỏ quân hậu ở ô (i j);

i := x[j];

a [i] := True; b [i + j] := True; C [i — j] := True

Và chương trình PASCAL hoàn chỉnh là:

TINH CHẾ LẦN 2 (Không dùng Đệ Qui)

Program EIGHT QUEEN;

Const

HAU = ’Q’;

OTRONG = ’#’;

Var

x : array [1.. 8] of integer; antoan : boolean;

a : array [1.. 8] of Boolean; i, j : integer

b : array [2.. 16] of Boolean;

c : array [-7.. 7] of Boolean;

Begin {Khởi tạo tình trạng ban đầu}

For i := 1 to 8 do a [i] := True;

For i := 2 to 16 do b [i] := True;

For i := -7 to 7 do C [i] := True;

j := 1

i := 0

Repeat

Repeat

i := i + 1

antoan := a [i] and b [i 4- j] and C [i – j];

Until antoan or (i = 8);

If antoan then

Begin {Đặt quân hậu vào}

X [j] := i;

a [i] := False; b [i + j] := False;

c [i — j] := False;

j := j + 1; (xét cột kế)

1 := 0;

End;

Else

Begin {Quay lại}

j := j — 1; {cột trước}

if j > = 1 then

Begin {Bỏ quân hậu đi}

i := x[j];

a [i] := True;

b [i + j] := True;

c [i – j] := True;

if i = 8 then

Begin

j := i — 1; {Quay thèm một cột} if j > = 1 then Begin

i := x [j];

a [i] := True; b [i + j] := True;

c [i – j] := True;

End;

End;

End;

End;

Until (j > 8) or (j < 1);

If j < 1 then Writeln (’VO NGHIEM’);

Else

For i := 1 to 8 do

Begin

For j := 1 to 8 do

if x [j] := i then write (HAU)

else write (OTRONG);

Wrriteln;

End;

End.

Ví dụ 4 (Bài toán mã đi tuần)

Cho một bàn cờ có kích thước n x n. Một con mã di chuyển theo luật cờ vua được đặt trong một ô với tọa độ ban đầu là (xx, yx). Hãy tìm một đường đi với n2– 1 bước đi sao cho      mọi ô trên bàn cờ đều được mã nhảy đến đúng một lần

Theo luật toán Đệ quy có quay lui dựa trên phương pháp thử và sai đã trình bày ở §8 ta có chương trình PASCAL như sau:

Program Knightour;

Const

a : array [a.. 8] of integer = (2, 1, – 1, – 2, – 2, – 1, 1, 2);

b : army [1.. 8] of integer = (1, 2, 2, 1, – 1, – 2, – 2, – 1);

n := 5; nsq := 25;

Type

Index = 1.. n;

Var

q : Boolean;

dd : Array [index, index] of integer;

S: Set of Index;

x, y : Integer;

Procedure Init;

Begin

Fillchar (dd, sizeof (dd), 0);

§5. CHẠY THỬ, THAY ĐỔI, KIỂM TRA CHƯƠNG TRÌNH

1. Chạy thử

Một chương trình đã viết xong chưa chắc đã chạy được trên máy tính để cho ra kết quả mong muốn.

Kĩ năng tìm lỗi, sửa lỗi, điềuu chỉnh, viết lại chương trình cũng là một kĩ năng quan trọng của người lập trình.

Quá trình rèn luyện kĩ năng này phải bắt đầu trong việc tìm lỗi và sửa chữa lỗi của chính mình.

2. Phân loại lỗi và cách sửa chữa

Lỗi về thuật toán: điều chỉnh lại thuật toán, thậm chí có thể loại bỏ thuật toán sai, tìm thuật toán khác nghĩa là làm lại từ đầu.

Lỗi về trình tự: phải xem lại thuật toán, phân tích lại từ trên xuống để đặt lại cho đúng với thuật toán.

Lỗi về cú pháp: viết lại cho đúng với cú pháp của ngôn ngữ lập trình mà mình đang sử dụng. (Các phần mềm ngôn ngữ hiện nay đều có phần tiện ích giúp đỡ tìm kiếm lối cú pháp và hướng dẫn sửa chữa).

3. Xây dựng các bộ Test

Có nhiều chương trình rất khó kiểm tra tính đúng đắn. Nhất là các chương trình tìm kiếm lời giải tối ưu, vì chúng ta chưa biết kết quả đúng là thế nào ? Vì vậy việc tìm lỗi rất khó khăn.

Để tháo gỡ các khó khăn trên, ta nên viết các chương trình cho nhập dữ liệu bằng Files thay vì bằng bàn phím (Vì mỗi lần sửa chữa trong khi chạy thử lại phải gõ bàn phím lại từ đầu).

Thông thường ta dùng các thủ tục có dạng sau để đọc các Files chứa các bộ Test.

Procedure Read data;

Var S : String;

f : Text;

X : Biến chứa dữ liệu;

Begin

Writen (‘Xin cho biet ten File’);

Readln (S);

Assign (f, S);

Reset (f);

Read (f,x);

Clowe (f);

End;

Khi tự mình phải làm các bộ Test để thử chương trình của chính mình ta nên lưu ý các điều sau:

• Nên khởi đầu bằng các bộ Test nhỏ nhưng chứa các giá trị đặc biệt (Vì kinh nghiệm cho thấy đây là chỗ dễ bị lỗi nhất).
• Làm nhiều các bộ Test nhưng phải đa dạng tránh lặp đi lặp lại các bộ Test tương tự.
• Nên kết thúc bằng các bộ Test có kích thước lớn để kiểm tra tính chịu dựng của chương trình.

Thông qua các bộ Test để điều chỉnh chương trình sửa chữa các lỗi khó thấy khi lập trình.

Phải ghi nhớ rằng một chương trình chạy qua được một số bộ test không có nghĩa là chương trình đó đã đúng. Bởi vì có thể là ta chưa xây dựng được bộ Test để chỉ ra cái sai của nó.

Nếu được, nên tìm cách chứng minh tính đúng đắn của chương trình (Việc này đôi lúc rất khó).

4. Thay đổi chương trình

Một chương trình đã viết xong, đã chạy tốt, đã giải được bài toán mà ta mong muốn điều đó chưa có nghĩa là quá trình lập trình đã kết thúc. Ta thường phải sửa đổi nó theo một hướng nào đó để đáp ứng một yêu cầu mới (Ví dụ tổng quát hóa vấn đề lên…). Chính ở đây phương pháp tinh chế từng bước tỏ ra có hiệu quả. Những câu lời tự nhiên ở những bước tinh chế đầu sẽ giúp ta dễ thấy được những chỗ cần sửa trong chương trình cũ, giúp ta thừa HƯỚNG những lao động phân tích, thiết kế và chứng minh đã làm lúc trước.

Vậy phương pháp tinh chế từng bước có ý nghía đối với khả năng duy trì của chương trình.

Cũng vậy, phương pháp tinh chế từng bước còn giúp tăng cường tính phổ dụng của chương trình, nghĩa là sự chuyển đổi chương trình sang một môi trường khác ví dụ như sang một ngôn ngữ, lập trình khác hay một hệ thống máy tính khác.

Ví dụ (Bài toán 8 quân hậu tổng quát)

Tìm tất cả các cách đặt 8 quản hậu lên bàn cờ sao cho không có quân nào ăn nhau.

Trở lại với bước tinh chế thứ 2 của bài toán 8 quân hậu ở 4, ta thấy cần có 2 sửa đổi sau:

* Khi đã đặt được quân hậu cuối cùng vào bàn cờ, thì ta sẻ in lời giải đó ra, nhưng khống kết thúc chương trình. Mà ta sẽ thực hiện một sự quay lại để tìm một lời giải khác.

* Chương trình sẽ ngừng khi sự quay lại đã quá cột đầu.

Chương trình có dạng phác họa như sau:

Xét cột đầu

Repeat

Thử cột;

if an toàn then Begin

Đặt quân hậu vào;

Xét cột kế;

if cột kế vượt quá cột cuối cùng then

Begin

In ra lời giải;

Quay lại;

end;

end;

Else quay lại

Until đã quay lại quá cột đầu.

Chỉ cần đến đây là ta đã có thể viết lại thành chương trình hoàn chỉnh vì những câu trả lời tự nhiên đề đã được phân giải thành Pascal ở chương trình trước. Chương trình 8 quân hậu tổng quát như sau

Program EIGHTQUEEN;

Const

HAU = ’Q’;

OTRONG = ‘#’

Var

x : array [1.. 8] of integer;

a : array [1.. 8] of Boolean;

b : array [2.. 16] of Boolean;

c : array [-7.. 7] of Boolean;

i, j, Stt, ii, jj : integer; antoan, quaylui : Boolean;

Begin

Stt := 0; {Số thứ tự của một tình thế}

For i := 1 to 8 do a [i] := true;

For i := 2 to 16 do b [i] := true;

For i := —7 to 7 do C [i] := true;

{Tình trạng ban đầu} j := 1; {Xét cột đầu}

i := 0;

Repeat

Quay lui := False ; {Chưa cần quay lui}

Repeat

i := i+1 ; {thử một cột}

antoan := a[i] and b[i+j] and c[i — j] ;

Until antoan or (i = 8) ;

if antoan then

Begin {Đạt quân hậu vào}

x[j] := 1;

a[i] := False; b[i + j] := False; c[i – j] := False;

j := j + 1; {xét cột kế}

i := 0;

if j > 8 then {Đã quá cột cuối cùng}

Begin

Stt := Stt + 1;

Writeln (’Tinh the thu’, Stt : 3,);

For ii := 1 to 8 do

Begin

Write (ii : 3, ’ ’);

For jj := 1 to 8 do

if x [jj] = ii then

Write (HAU) else write (OTRONG);

Writeln ;

end ; {In ra một lời giải}

Readln ;

Quay lui := true;

{Quay lại tìm một lời giải khác}

End;

End;

if (not antoan) or quaylui then

Begin

j := j – 1

if j >= 1 then

Begin {Gỡ quân hậu ra}

o := x [j];

a[i] := True; b[i + j] := True; c[i – j] := True;

if i = 8 then

Begin {Quay lạỉ thêm một cột nữa} j := j – 1; if j > = 1 then

Begin {Lại gỡ quân hậu ra}

i := x[j];

a[i] := True; b[i+j] := True; c[i—j] := True;

end;

end;

end;

end;

Until (j < 1) ; {Đã quay lại quá cột đầu}

End.

5. Tiêu chuẩn của chương trình

Thế nào là một chương trình tốt ?

Một chương trình tốt cần phải thỏa mãn bốn tính chất sau :

1. a) Tính tin cậy:

Một chương trình tin cậy là một chương trình chạy đúng như dự định.

Muốn một chương trình tin cậy, ta phải:

– Có một giải thuật đúng.

– Thể hiện một cách đúng đắn giải thuật thành chương trình (Cài đặt đúng).

– Sau khi đã dịch chương trình, phải tiến hành thử chương trình: Cho những dữ liệu mẫu vào, chạy thử chương trình và kiểm tra lại kết quả.

Tuy nhiên việc chạy thử chương trình chỉ giúp phát hiện một số lỗi, chứ không phải tất cả. Vì vậy khi viết chương trình xong phải kiểm tra tính đúng đắn của nó. Điều này dẫn đến sự ra đời của lí thuyết chứng minh chương trình.

– Một quan niệm quan trọng trong việc lập trình là : Thiết kế chương trình song song với chứng minh chương trình. Nghĩa là trong quá trình xây dựng chương trình ta luôn phải kiểm tra và chứng minh đúng đắn của các bước:

1. b) Tính uyển chuyển:

– Chương trình cần phải để sửa đổi.

– Trong quá trình sử dụng một chương trình, những nhược điểm của nó dần dần bộc lộ. Đồng thời những yêu cầu đối với chương trình cũng có thể có những thay đổi so với thiết kế ban đầu.

– Nếu ta viết đi viết lại chương trình từ đầu thì sẽ tốn rất nhiều công tác. Tốt hơn, hiển nhiên, là sửa chữa lại chương trình đã có. Một chương trình tốt phải có tính chất để sửa đổi, nhằm giúp tiết kiệm công sức của người lập trình trong quá trình phát triển chương trình.

– Trong lĩnh vực xây dựng phần mềm, người ta thường nói : Chương trình có chu trình sống gồm các giai đoạn:

• Thiết kế.
• Thi công.
• Sử dụng.
• Sửa đổi.

1. c) Tính trong sáng:

– Chương trình phải viết cho dề đọc, dế hiểu.

– Chương trình phải tạo thuận lợi cho việc bào trì bao gồm:

– Sửa sai.

– Cải tiến.

– Biến đổi.

– Để có một chương trình trong sáng, ta cần chú ý về : các tên của biến, kiểu, chương trinh con, … phải có tính gợi nhớ, viết dưới dạng cấu trúc, sử dụng nhiều chú thích.

Một chương trình không trong sáng thường mắc các sai tóm:

• Các danh hiệu quá vắn tắt,
• Các phát biểu viết không chọn lựa,
• Không tạo dạng cấu trục.

Một chương trình như vậy không những sẽ khó đọc, khó hiểu khi kiểm tra mà còn có thể dẫn đến nhiều lỗi sai khó phát hiện.

1. d) Tính hữu hiệu:

Hữu hiệu là chạy nhanh và ít tốn bộ nhớ, nghĩa là ít tốn không gian và thời gian.

Để có một chương trình hữu hiệu, quan trọng nhất là có một giải thuật hữu hiệu. Sau đó, cán có những khéo léo nhất định, khi lập trình

Tuy nhiên, yêu cầu hữu hiệu nhiều khi làm cho chương trình trở nên rối rắm, khó hiểu, khi sửa đổi. Những nhà lập trình cấu trúc khẳng định, tiêu chuẩn hữu hiệu không quan trọng bằng 3 tiêu chuẩn trên.

Ngày xưa, khi ngành lập trình còn thô sơ, người ta thường chú trọng các mẹo vặt để nâng tính hữu hiệu (chạy nhanh, ít tốn bộ nhớ). Do đó, chương trình khó đọc, tối tăm. Ngày nay, với sự phát triển của phần cứng (máy chạy rất nhanh, có bộ nhớ lớn). Yêu cầu hữu hiệu không còn đặt ra quá nặng như trước nữa.

Một chương trình không phải chỉ là một tập các mệnh lệnh người giao cho máy mà còn là một tập các thông tin giao tiếp giữa người với người.

6. Kết luận.

Quá trình xây dựng chương trình là một chuỗi các bước tinh chế.

Ở mỗi bước, một công việc được phản rn lhni nhiều công viêc con. Mỗi sự tinh chế cho một mô tả công việc có thể được đi kèm bởi một tinh chế cho mô tả của dữ liệu – là cái tạo nên phương tiện liên lạc giữa các công việc. Sự tinh chế mô tả của chương trình và của các cấu trúc dữ liệu phải tiến hành đồng thời.

Mức độ của tính module đạt được theo cách này sẽ quyết định tính hÁt. dế dàng hay khó khốn trong việc làm thích ứng một chương trinh . An nửa đổi hay mở rộng về mục đích hay về môi trường thực thi (ngôn Itgiì, máy tính).

Trong quá trình tinh chế từng bước, mối cách biểu diễn tự nhiên của bài toán đang xét cần được sử dụng càng lâu càng tốt. Hướng phát triển của sự biểu diễn trong quá trình tinh chế được quyết định bởi ngôn ngữ lập trình mà ta dùng. Ngôn ngữ lập trình phải cho phép, chúng ta diễn tả một cách tự nhiên nhất và rõ ràng nhất các cấu trúc , tin chương trình và dữ liệu. Đồng thời nó cũng phải cho phép hướng dẫn quá trình tinh chế bằng cách trình bày những đặc tính căn bản và những nguyên lí cấu trúc tự nhiên đối với máy tính mà chương trình chạy trên đó.

Mỗi sự tinh chế dẫn đến một số các quyết định thiết kế, dựa trên một tập các tiêu chuẩn thiết kế.

Ví dụ:

• Tính hữu hiệu.
• Sự tiết kiệm bộ nhớ.
• Tính trong sáng.
• Tính cấu trúc.

Người lập trình phải được rèn luyện để có ý thức về các quyết dịnh liên quan và biết khảo sát nghiêm túc cũng như từ bỏ các lời giải nguy cả khi chúng là đúng.

Người lập trình phải học cách cân nhắc mọi phương tiện của từng lời giải theo tiêu chuẩn đó. Đặc biệt là phải biết từ bỏ những quyết định ta có, và đi ngược lên, nếu cần thiết, trở lại đỉnh.

Cần phải từ bỏ niềm tin tưởng ngây thơ ràng lập trình là dễ, các ngôn ngữ lập trình là đủ mạnh và các máy tính là đủ nhanh.

Chia sẻ:

• Twitter
• Facebook

Thích Đang tải...

Có liên quan