Đọc truyện cslt 1 chuong 1

cslt 1 chuong 1

Trước Sau

Màu nền

Font chữ

Font size

Chiều cao dòng

Chương 1: nhập môn kĩ thuật lập trình

1.1. Thuật toán

1.1.1. Khái niệm thuật toán

Khái niệm thuật toán là một trong những khái niệm cơ sở của Toán học và Tin học, tuy vậy, khái niệm này vẫn chưa có một định nghĩa thống nhất. Trong từng lĩnh vực khác nhau, có thể hiểu thuật toán theo những cách khác nhau. Trong tài liệu này, khái niệm thuật toán được trình bày một cách rất trực giác theo quan điểm Tin học để sinh viên làm quen và sử dụng được trong khi giải quyết các bài toán đặt ra với Tin học. Đơn giản nhất, ta hiểu: Thuật toán là một bảng hướng dẫn để chỉ ra các công việc phải thực hiện theo một trình tự nào đó đã được xác định để giải quyết một công việc cho trước. Nói cách khác, với những điều kiện ban đầu, một thuật toán sẽ chỉ ra hữu hạn các bước phải tiến hành theo một trình tự duy nhất để đạt được một kết quả đã định trước.

Khái niệm “Thủ tục” được hiểu gần giống như thuật toán nhưng khi nói đến thủ tục, người ta không quan tâm đến kết quả của nó mà chỉ để ý đến trình tự các công việc.

Khi giải các bài toán, thuật toán được hiểu là một bản chỉ ra tập hợp các công việc phải thực hiện theo một trình tự xác định để giải một bài toán hay một lớp bài toán cùng loại. Nó bao gồm một dãy các mệnh lệnh chặt chẽ và rõ ràng xác định trình tự các thao tác trên một số đối tượng là dữ liệu của bài toán. Với một thuật toán, sau một số hữu hạn bước thực hiện sẽ đạt được một kết quả.

Trong một bài toán, các dữ liệu thường có mối quan hệ với nhau tạo thành một cấu trúc của dữ liệu. Mỗi loại cấu trúc dữ liệu sẽ ảnh hưởng trực tiếp đến cách thức thao tác trên dữ liệu. Do vậy, nói đến thuật toán, không thể tách rời thuật toán khỏi dữ liệu và cấu trúc dữ liệu. Có thể thấy điều đó trong hai ví dụ sau:

Ví dụ 1: Cho a, b, c là các hệ số của phương trình bậc hai ax2 + bx + c = 0 (a¹0). Các giá trị a, b, c, ở đây là các phần tử của dữ liệu bài toán. Về mặt hình thức, chúng độc lập với nhau với tư cách bình đẳng nên khi lưu trữ trong bộ nhớ máy tính, người ta thường ghi vào các trường nhớ độc lập, và khi đó gọi là các phần tử dữ liệu không có cấu trúc. Cách thức lưu trữ và xử lí dữ liệu trên máy tính sẽ quyết định dữ liệu đó có phải là có hay không có cấu trúc. Trong các ngôn ngữ lập trình hiện nay, các phần tử dữ liệu không có cấu trúc đều được phân chia thành các loại và mỗi loại đó được ngôn ngữ quy định rõ ràng về cách thức lưu trữ và xử lí trên máy tính. Mỗi loại đó gọi là một kiểu dữ liệu - kiểu dữ liệu cơ sở.

Chẳng hạn, ngôn ngữ Pascal có sử dụng các kiểu dữ liệu cơ sở như: Interger, Byte, Word, Real, Char, String, Boolean, …

Ví dụ 2: Có một bảng dữ liệu về kết quả thi của sinh viên:

Họ và tên

Số báo danh

Ngày sinh

Điểm Toán

Điểm Lí

Điểm Hoá

Vũ Văn Anh

HTC01

01/01/80

9.5

8.0

7.0

Trần Thị Mai

HTC02

08/03/81

8.0

8.5

9.0

Vũ Anh Tuấn

HTC03

19/05/80

10.0

9.5

Các đại lượng: Họ và tên, số báo danh, ngày sinh, điểm Toán, điểm Lí, điểm Hoá là dữ liệu của bài toán liên quan đến từng đối tượng; Thậm chí, ngày sinh lại được cấu thành từ ba thành phần số là ngày, tháng và năm; các dữ liệu này có quan hệ không thể tách khỏi đối tượng phản ánh để tạo thành một bộ dữ liệu của đối tượng đó, những dữ liệu có liên quan với nhau như thế, khi lưu trữ và xử lí trên máy tính, người ta thường tổ chức ghi một bộ thông tin của một đối tượng (bao gồm các phần tử dữ liệu cơ sở) vào một khối gồm các trường nhớ có liên quan đến nhau và gọi là kiểu dữ liệu có cấu trúc. Mỗi dữ liệu kiểu cấu trúc thường được tạo thành từ một tập hợp các dữ liệu kiểu cơ sở có liên quan với nhau.

Với mỗi bài toán, sẽ có một bộ dữ liệu, nó có thể là các dữ liệu cơ sở nhưng cũng có thể là dữ liệu có cấu trúc. Cấu trúc dữ liệu do người sử dụng xác định, nó quyết định thuật toán xử lí và sự lựa chọn ngôn ngữ định trình. Mỗi ngôn ngữ định trình thường chứa sẵn một số cấu trúc tiền định. Việc chấp nhận một ngôn ngữ mô tả tức là chấp nhận các cấu trúc tiền định của ngôn ngữ đó. Nếu sự lựa chọn cấu trúc dữ liệu và ngôn ngữ thích hợp thì việc lập trình sẽ thuận tiện và ngược lại.

1.1.2. Biểu diễn thuật toán

Có nhiều cách để biểu diễn thuật toán, mỗi cách sử dụng một thứ ngôn ngữ và do đó có những ưu, nhược điểm riêng. Hiện nay, thường sử dụng các cách sau:

v Biểu diễn thuật toán bằng ngôn ngữ tự nhiên của con người.

Ví dụ: Thuật toán giải phương trình bậc hai ax2+bx+c = 0 (a≠0)

Bước 1: Xác định dữ liệu a, b, c rồi sang bước 2.

Bước 2: Tính D = b2 - 4ac rồi chuyển sang bước 3.

Bước 3: Kiểm tra điều kiện D >0:

- Nếu thoả mãn thì sang bước 5;

- Nếu ngược lại thì chuyển sang bước 4.

Bước 4: Kiểm tra điều kiện D = 0:

- Nếu thoả mãn thì sang bước 7;

- Nếu ngược lại thì sang bước 9.

Bước 5: Tính X1,2 = (- b ± )/(2a) rồi sang bước 6.

Bước 6: Xác định kết quả: Hai nghiệm là X1 và X2 rồi sang bước 10.

Bước 7: Tính nghiệm x=-b/(2a) rồi sang bước 8.

Bước 8: Xác định kết quả: Nghiệm kép = x rồi sang bước 10.

Bước 9: Xác định kết quả: “Phương trình vô nghiệm” rồi sang bước 10.

Bước 10: Kết thúc.

v Biểu diễn thuật toán bằng sơ đồ khối;

Ví dụ: Thuật toán giải phương trình bậc hai nói trên được biểu diễn bằng sơ đồ khối.

(Các quy tắc vẽ sơ đồ khối đã giới thiệu trong giáo trình Tin học đại cương)

v Biểu diễn thuật toán bằng một ngôn ngữ thuật toán.

Ví dụ: Thuật toán giải phương trình bậc hai được biểu diễn bằng ngôn ngữ thuật toán.

- Chọn ngôn ngữ thuật toán để mô tả: Thường chọn PASCAL là ngôn ngữ khá phổ dụng với mọi người.

- Thuật toán:

BEGIN

Read(a,b,c);

Delta:=b*b-4*a*c;

If Delta>0 then

Begin

X1:=(-b-sqrt(Delta))/(2*a);

X2:=(-b+sqrt(Delta))/(2*a);

Write(x1,x2);

End

Else

If Delta=0 then

Begin

X:=-b/(2*a);

Write(x);

End

Else

Write(‘Phương trình Vô nghiệm’);

END.

Chú ý: Việc sử dụng bất kì một ngôn ngữ nào một cách trọn vẹn để mô tả thuật toán sẽ đều bị hạn chế do những quy định ngặt nghèo của chương trình dịch. Vì thế, khi nói mô tả bằng ngôn ngữ Pascal nhưng thực chất chỉ là một ngôn ngữ giả Pascal (hay tựa Pascal) mà thôi, chúng ta có thể thêm bớt một cách linh hoạt, không câu nệ nhiều về cú pháp sao cho tiện lợi cho việc mô tả!

Mỗi cách biểu diễn có những ưu, nhược điểm riêng: Biểu diễn bằng ngôn ngữ tự nhiên thì dễ nhưng không phổ dụng và không sử dụng hết các cấu trúc tiền định của ngôn ngữ lập trình; Biểu diễn bằng sơ đồ khối thì rõ ràng, dễ hiểu nhưng cồng kềnh và nhiều khi không phù hợp với cấu trúc tiền định của ngôn ngữ lập trình; Biểu diễn bằng ngôn ngữ thuật toán thì rất chính xác, thuận tiện nhưng lại gặp khó khăn về ngôn ngữ và việc lựa chọn ngôn ngữ mô tả...

Trong giáo trình này, có thể sử dụng tất cả các cách biểu diễn trên vì mục tiêu của giáo trình này là xây dựng chương trình.

1.1.3. Các cấu trúc cơ bản của thuật toán

Từ lâu, người ta vẫn cho rằng có ba kiểu cấu trúc cơ bản của thuật toán, đó là: Cấu trúc tuần tự (tuyến tính), cấu trúc điều kiện (rẽ nhánh) và cấu trúc lặp (chu trình).

a- Cấu trúc tuần tự là cấu trúc mà tất cả các bước công việc trong thuật toán đều được thực hiện tuần tự, một lần. Hãy thử viết thuật toán tính chu vi và diện tích hình tròn biết bán kính của nó là r và nghiệm lại.

b- Cấu trúc điều kiện là cấu trúc trong thuật toán có việc Kiểm tra một điều kiện để quyết định thực hiện công việc này hay công việc khác tuỳ thuộc điều kiện đó có thoả mãn hay không. Hãy xem việc kiểm tra điều kiện trong thuật toán giải phương trình bậc hai ở trên và kiểm nghiệm lại.

c- Cấu trúc lặp là cấu trúc trong thuật toán có một tập hợp các công việc được thực hiện lặp đi lặp lại nhiều lần. Số lần thực hiện đó gọi là số lần lặp. Nếu trước khi thực hiện vòng lặp, có thể xác định được số lần thực hiện thì gọi là vòng lặp có số lần lặp biết trước, ngược lại (không thể xác định được số lần thực hiện trước khi thực hiện, chỉ xác định được sau khi đã thực hiện xong vòng lặp) thì gọi là vòng lặp với số lần lặp không biết trước. Hãy viết lại thuật toán tính n! và kiểm nghiệm lại.

Tuy vậy, như đã trình bày trong phần 1.1.1., việc xác định cấu trúc thuật toán phụ thuộc ngay cả vào các cấu trúc tiền định có trong ngôn ngữ lập trình. Hiện nay, cấu trúc điều kiện với bản chất là cấu trúc rẽ nhánh, được tách thành hai cấu trúc riêng: Rẽ hai nhánh và Rẽ nhiều nhánh. Đó là nhờ sự xuất hiện thêm một cấu trúc tiền định trong các ngôn ngữ lập trình cấp cao, giúp cho việc lập trình thuận tiện hơn. Hãy xem các lệnh If ... Then và Case ... Of của Pascal, If ... Endif và Do case ... Endcase của FoxPro, if và switch của C, if và case ...end của Delphi ... bạn sẽ thấy: cấu trúc rẽ nhiều nhánh chẳng qua là nhiều cấu trúc rẽ hai nhánh hợp lại, có thể hoàn toàn thay thế cấu trúc rẽ nhiều nhánh bằng các cấu trúc rẽ hai nhánh.

Từ các loại cấu trúc cơ bản, mọi thuật toán, dù phức tạp đến đâu, cũng chỉ là sự tổ hợp của các loại cấu trúc đó.

1.2. Chương trình và ngôn ngữ lập trình

1.2.1. Chương trình

a- Khái niệm về lệnh (statement)

Trong quá trình làm việc với máy tính, khi muốn yêu cầu máy thực hiện một thao tác hay công việc nào đó, người sử dụng phải đưa vào một tập hợp các kí tự (trong giao diện văn bản) hoặc gây một tác động ở một vị trí xác định (trong giao diện đồ hoạ). Khi nhận được tín hiệu này, chương trình xử lí lệnh sẽ phân tích và hiểu được phải thực hiện thao tác gì. Giáo trình “cơ sở lập trình” chỉ xét giao diện văn bản vì giao diện này mang tính bản chất, còn giao diện đồ hoạ có được, chẳng qua là nhờ sự mã hoá lại mà thôi.

Mỗi dãy kí tự khi đưa vào máy với ý định yêu cầu máy thực hiện một thao tác gọi là một lệnh của máy tính điện tử. Bản chất dãy kí tự đó là lời gọi để máy tính cho thực hiện một chương trình hay một đoạn chương trình trong bộ nhớ. Mỗi lệnh sẽ gây ra các phản ứng hoàn toàn xác định đối với máy tính.

Ví dụ: Trong ngôn ngữ PASCAL, dãy kí tự: Writeln(‘Wel come to PASCAL!’) được gọi là một lệnh - lệnh hiển thị dữ liệu ra màn hình, khi đó máy sẽ hiển thị ra màn hình dãy kí tự: Wel come to PASCAL!

b- Khái niệm về chương trình (Program)

Sau khi có thuật toán, phải mô tả thuật toán cho máy tính bằng một ngôn ngữ mà máy có thể hiểu được. Bản mô tả thuật toán đó gọi là một chương trình. Chương trình cho máy tính là một tập hợp hữu hạn các lệnh viết bằng một ngôn ngữ nào đó, mà người dùng và máy có thể hiểu được. Mỗi một lệnh sẽ tương ứng với một hay một số thao tác trong thuật toán đã được xây dựng trước.

c- Khái niệm về lập trình

Lập trình, theo nghĩa chung, là một công việc của con người, bao hàm rộng và mang tính thiết kế toàn diện, từ việc tìm thuật toán, chọn ngôn ngữ định trình thích hợp và soạn thảo chương trình. Công việc này tạo ra một chương trình cho máy tính. Nếu chọn ngôn ngữ định trình là một ngôn ngữ máy thì sau lập trình, ta đã có một chương trình có thể thực hiện (EXEcute); Ngược lại, nếu chọn ngôn ngữ thuật toán để mã hoá thuật toán thì sau lập trình, ta sẽ có một chương trình nguồn, muốn có một chương trình có thể thực hiện, ta phải chạy chương trình dịch để dịch chương trình nguồn đó ra chương trình đích.

Theo nghĩa hẹp, lập trình chỉ bao gồm một công việc là thảo ra chương trình bằng một ngôn ngữ nào đó sau khi đã có thuật toán. Đó chính là việc mã hoá thuật toán thành một chương trình, có thể chọn ngôn ngữ lập trình là ngôn ngữ máy hay ngôn ngữ thuật toán.

1.2.2. Ngôn ngữ lập trình (Programming Language)

Có thể sử dụng nhiều loại ngôn ngữ khác nhau để viết trình cho máy tính điện tử. Các ngôn ngữ được sử dụng trong viết trình gọi là ngôn ngữ lập trình. Người ta chia các ngôn ngữ lập trình thành ba loại: Ngôn ngữ máy, ngôn ngữ kí hiệu và ngôn ngữ thuật toán.

· Ngôn ngữ máy

Mỗi loại máy tính ra đời, nhà chế tạo đã xây dựng ngay bên trong máy một ngôn ngữ cơ sở dựa trên một tập lệnh rất đơn giản và nghèo nàn được quy định bởi các đặc tính kĩ thuật của các mạch điện tử trong máy. Với ngôn ngữ này, máy tính có thể hiểu được ngay mà không cần có sự can thiệp trung gian của việc dịch hay thông dịch - gọi là ngôn ngữ máy, đó chính là ngôn ngữ sơ cấp nhất. Ngôn ngữ máy là một ngôn ngữ lập trình với những đặc điểm chính là:

- Các lệnh đều trực tiếp can thiệp vào các mạch điện tử của máy tính;

- Mỗi lệnh máy chỉ quy định phải làm một phép toán (hay thao tác) sơ cấp đơn giản như: cộng, trừ, nhân, chia, so sánh hai đại lượng với nhau;

- Mỗi lệnh máy đều có hai phần: Phần mã phép toán chỉ phép toán phải thực hiện và phần địa chỉ ghi địa chỉ của các ô nhớ chứa các toán hạng hay địa chỉ cụ thể trong RAM chứa kết quả sau khi thực hiện phép toán;

- Mỗi mã phép toán hay địa chỉ đều phải được viết hoàn toàn bằng các chữ số hệ 2 là 0 và 1 để có thể đưa vào bộ nhớ trong của máy. Tuy nhiên, khi viết hay hiển thị chương trình, không nên dùng số hệ 2 vì lệnh sẽ dài, khó đọc và khó nhớ. Trong giao tiếp bằng ngôn ngữ máy, người ta dùng số hệ 16 hay số hệ 8 thay vì trực tiếp dùng số hệ 2 vì viết số của hai hệ này gọn, dễ nhớ và rất dễ dàng đổi sang hệ 2 nhờ một kênh đổi số có sẵn trong thiết kế của bất kì máy tính nào.

Viết chương trình bằng ngôn ngữ máy là một việc làm thủ công, tẻ nhạt, mất nhiều thời gian, dễ nhầm lẫn. Đã vậy, các chương trình lập cho loại máy này không dùng được cho loại máy khác. Điều đó làm chậm nhịp độ ứng dụng kĩ thuật tính toán điện tử vào các lĩnh vực của đời sống kinh tế – xã hội.

· Ngôn ngữ kí hiệu

Ngôn ngữ kí hiệu là một ngôn ngữ lập trình thuộc lớp trung gian giữa ngôn ngữ máy và ngôn ngữ thuật toán, gọi là ngôn ngữ trong. Trong ngôn ngữ kí hiệu, mã lệnh và địa chỉ lệnh được ghi bằng kí hiệu chứ không ghi bằng các chữ số 0 và 1 như ở ngôn ngữ máy. ASSEMBLER là đặc trưng của loại ngôn ngữ này.

· Ngôn ngữ thuật toán

Với những nhược điểm của việc viết trình bằng ngôn ngữ máy, các chuyên gia tin học đã nỗ lực cải tiến việc lập trình cho máy tính. Người ta tìm cách xây dựng các ngôn ngữ lập trình rất dễ đọc, dễ hiểu gần gũi với ngôn ngữ tự nhiên của con người, đó là một hệ thống những quy ước không phụ thuộc vào từng máy cụ thể. Những ngôn ngữ đó gọi là ngôn ngữ thuật toán.

Trong số các ngôn ngữ thuật toán, có những ngôn ngữ phù hợp với phương pháp lập trình cấu trúc, chẳng hạn: ngôn ngữ C, PASCAL, FORTRAN ...; có ngôn ngữ phù hợp với phương pháp lập trình hướng đối tượng, chẳng hạn: C++, JAVA, DELPHI...; có những ngôn ngữ chuyên để giải quyết các bài toán quản trị cơ sở dữ liệu, chẳng hạn: VISUAL FOXPRO, SQL, ACCESS, ... . Người học lập trình thường bắt đầu từ việc học lập trình cấu trúc.

Việc tiếp cận các ngôn ngữ thuật toán trong lập trình cấu trúc được tiến hành theo trình tự: Bắt đầu là tìm hiểu bộ kí tự của ngôn ngữ, sau đó sẽ tìm hiểu hệ thống từ khoá (keywords) là các từ cố định với nghĩa và cách dùng bất biến. Tập hợp từ khoá của ngôn ngữ thuật toán là một tập con rất nhỏ của một ngôn ngữ tự nhiên (thường là tiếng Anh) với sự phân định chính xác về ngữ nghĩa. Song song với việc tìm hiểu các từ khoá là nghiên cứu các đại lượng sử dụng trong ngôn ngữ. Các đại lượng là một yếu tố để mô tả dữ liệu (hằng, biến, ...) trong máy tính. Trên cơ sở các đại lượng, người ta xây dựng tập hợp các phép toán thực hiện được trên mỗi kiểu dữ liệu của các đại lượng đó. Cuối cùng là đi tìm hiểu các mẫu lệnh, đó là các quy định máy móc rất khắt khe về cú pháp để viết một câu lệnh. Một lệnh được gọi là cho phép khi nó được xây dựng dựa trên các yếu tố của ngôn ngữ theo đúng quy định của cú pháp.

Mỗi ngôn ngữ thuật toán đều có một chương trình dịch làm nhiệm vụ dịch các chương trình viết bằng ngôn ngữ thuật toán (gọi là chương trình nguồn hay chương trình gốc) thành một chương trình tương ứng viết bằng ngôn ngữ máy (gọi là chương trình đích). Tuỳ theo cách dịch và chạy chương trình, các ngôn ngữ thuật toán được chia thành hai loại là Thông dịch (Interpreter) hay Biên dịch (compiler). Trình biên dịch sẽ dịch toàn bộ chương trình nguồn thành chương trình đích rồi mới thực hiện chương trình đích; Ngôn ngữ thông dịch thì dịch lệnh nào thực hiện ngay lệnh đó, lần sau thực hiện phải dịch lại do đó tốc độ rất chậm và luôn cần chương trình dịch đi kèm. Muốn lập trình bằng ngôn ngữ thuật toán, phải hiểu cách dịch nghĩa sang ngôn ngữ máy của chương trình dịch, đó chính là cách thực hiện (tác động) mỗi lệnh viết bằng ngôn ngữ thuật toán.

1.3. Thiết kế một chương trình máy tính

1.3.1. Kĩ thuật thiết kế trên xuống (top-down design)

Lập trình cho máy tính điện tử là một công việc trí tuệ có tính thiết kế toàn diện, từ việc hình thành thuật toán, đánh giá thuật toán, thiết kế chương trình, chọn ngôn ngữ lập trình và viết trình. Với các bài toán nhỏ, thuật toán đơn giản thì quá trình trên không phức tạp và tốn ít công sức nhưng với các bài toán phức tạp, có quy mô lớn, thông tin vào - ra nhiều, thuật toán phức tạp thì hai khâu hình thành thuật toán và thiết kế chương trình quả là tốn rất nhiều công sức. Một chương trình viết ra được đánh giá là hay hay dở phụ thuộc phần lớn vào hai khâu trên. Tuy nhiên, thuật toán sẽ quyết định chương trình, việc thiết kế chương trình chịu ảnh hưởng chủ yếu và trực tiếp của việc thiết kế thuật toán.

Trong thiết kế thuật toán, với các bài toán lớn, người ta thường thực hiện phân rã bài toán theo mô hình tổ chức phân cấp (giống cấu trúc hình cây): Một bài toán lớn được chia ra thành những bài toán nhỏ, mỗi bài toán nhỏ lại chia thành nhiều bài toán nhỏ hơn, .... Cứ như thế cho đến khi có được các bài toán nhỏ khá đơn giản mà ta đã biết cách giải quyết (bài toán mức cơ sở), không cần phân rã tiếp nữa. Cuối cùng thì thực hiện xây dựng thuật toán cho từng bài toán nhỏ ở mức cơ sở ấy. Việc thiết kế như trên gọi là sử dụng kĩ thuật thiết kế trên - xuống (top-down design). Có thể mô tả cấu trúc phân cấp đó như sau:

Trong kĩ thuật thiết kế trên – xuống, người ta phân tích toàn bộ bài toán một cách tổng quát, xuất phát từ dữ liệu và mục tiêu đặt ra để đề cập tới những vấn đề chủ yếu, rồi sau đó mới đi dần vào giải quyết những phần việc cụ thể một cách chi tiết theo kiểu cụ thể hoá dần dần.

Khi thuật toán sử dụng kĩ thuật thiết kế trên - xuống thì chương trình cũng được thiết kế theo nguyên tắc trên - xuống vì chương trình chính là ảnh của thuật toán nhờ quá trình mã hoá bằng một ngôn ngữ lập trình nào đó. Thể hiện của nó như sau:

- Mỗi bài toán cơ sở được định trình bằng một chương trình hay một đoạn chương trình tương đối độc lập, gọi là một modul chương trình. Trong các ngôn ngữ lập trình hiện nay, mỗi modul này chính là một chương trình con thể hiện bằng một thủ tục hay một hàm;

- Ngoài các modul chương trình được thiết kế để giải quyết và xử lí các bài toán cơ sở, trong hệ thống các chương trình con còn một số modul khác để tạo các chức năng riêng biệt và tạo giao diện người dùng giúp cho việc thao tác với chương trình được thuận tiện;

- Sự liên kết và điều hành một số chương trình con để thực hiện bài toán lớn hơn (cấp cao hơn) được thực hiện bằng một chương trình khác, gọi là chương trình mẹ. Một chương trình có thể là mẹ của chương trình này nhưng lại là con của chương trình khác. Trong mỗi bộ chương trình giải bài toán, có một chương trình mẹ không là con của một chương trình nào, gọi là chương trình chính, đó chính là chương trình điều hành tổng thể để thực hiện bài toán đã đặt ra.

Sử dụng kĩ thuật thiết kế trên - xuống giúp cho việc giải bài toán được định hướng rõ ràng, tránh sa đà ngay vào các chi tiết vụn vặt làm rối công việc. Trong lập trình, kĩ thuật này là cơ sở cho việc lập trình có cấu trúc mạch lạc, khúc chiết, dễ kiểm soát.

Hiện nay, việc giải quyết các bài toán lớn thường được nhiều người cùng thực hiện. Phương pháp thiết kế trên - xuống cho phép tách bài toán thành nhiều phần độc lập tương đối, tạo điều kiện cho các thành viên thực hiện phần việc của mình mà không chịu ảnh hưởng của các thành viên khác.

Việc phân rã một bài toán lớn thành nhiều bài toán nhỏ tương đối độc lập là một việc làm phức tạp cần phải được phân tích thiết kế một cách kĩ càng. Hiện nay nó được đánh giá là quan trọng hơn cả việc lập trình. Chính vì vậy, phân tích, thiết kế giải thuật đã trở thành một ngành khoa học đã và đang được các nhà khoa học đặc biệt quan tâm.

1.3.2. Kĩ thuật chương trình con

a- Khái niệm:

Trong lập trình, thường gặp những đoạn chương trình được lặp đi lặp lại nhiều lần ở những chỗ khác nhau (có thể khác nhau một vài số liệu). Để tránh tình trạng viết đi, viết lại nhiều lần những đoạn chương trình này, ta nên chuyển những đoạn chương trình đó thành một chương trình để khi cần thì có thể gọi nó thay vì phải viết lại chương trình trên, chương trình đó gọi là chương trình con.

Ngoài ra, khi viết chương trình giải quyết các bài toán lớn, phức tạp, chương trình thường rất dài, gồm hàng trăm, hàng nghìn dòng lệnh. Đọc và kiểm soát các chương trình này thường rất khó khăn. Vì vậy, để đơn giản trong quá trình gỡ rối, sửa đổi, bổ sung... chương trình, ta nên phân rã chương trình theo kĩ thuật thiết kế trên - xuống. Trong việc này, có một lưu ý rằng: Các chương trình con càng độc lập về dữ liệu, về biến thì càng thuận lợi cho việc kiểm soát khi viết hoặc hiệu chỉnh chương trình.

Khi đã có đủ hệ thống các chương trình con cần thiết bao gồm cả các chương trình con để tạo giao diện người dùng, để kết hợp các chương trình con đó trong việc xử lí bài toán đặt ra, phải xây dựng các chương trình điều hành, khi cần chương trình con nào thì gọi các chương trình con đó để thực hiện. Chương trình gọi đến chương trình con được gọi là chương trình mẹ và ở mức cao nhất, chương trình mẹ là chương trình chính.

Mô hình tổ chức một chương trình con như ở sơ đồ dưới đây.

Hiện nay, trong các ngôn ngữ lập trình thông dụng, thường sử dụng hai loại chương trình con là hàm và thủ tục. Trong mỗi ngôn ngữ lập trình (xét các ngôn ngữ thuật toán), bao giờ cũng có một số thủ tục và hàm chuẩn được xây dựng sẵn và lưu trữ trong thư viện chương trình mẫu của ngôn ngữ. Các hàm và thủ tục này chủ yếu dùng để xử lí các thao tác đơn giản và cơ sở trong xử lí dữ liệu. Khi cần, người viết trình chỉ cần gọi hàm hay thủ tục thông qua tên của nó theo đúng quy định cú pháp của ngôn ngữ. Điều đó giúp cho lập trình viên giảm bớt công sức và thời gian lập trình.

Ngoài các thủ tục và hàm chuẩn, người lập trình có thể tự xây dựng một số thủ tục và hàm để thực hiện một số công việc nào đó phục vụ việc giải bài toán. Các thủ tục và hàm này gọi là thủ tục và hàm của người dùng.

Trong các thủ tục và hàm người dùng, thường có các thành phần:

· Dấu hiệu để xác định chương trình này là chương trình con thủ tục hay hàm;

· Xác định tên thủ tục/hàm. Tên này dùng để gọi nó trong chương trình mẹ nên bắt buộc phải có;

· Xác định các tham số hình thức là các biến coi là dữ liệu ban đầu để thủ tục/ hàm đó xử lí. Các tham số này có thể có hoặc không;

· Xác định các biến cục bộ là các biến trung gian mà thủ tục/hàm đó dùng đến khi xử lí dữ liệu ban đầu. Các tham số này có thể có hoặc không và chỉ có ý nghĩa trong chính chương trình con này;

· Các lệnh của thủ tục/hàm để xử lí dữ liệu ban đầu;

· Dấu hiệu kết thúc thủ tục/hàm.

Khi chương trình mẹ gọi đến chương trình con (hàm/thủ tục), nó phải gửi các giá trị xác định cho các biến là tham số hình thức của chương trình con đó nếu nó có tham số hình thức, các giá trị xác định đó gọi là các tham số thực sự. Quá trình đó gọi là truyền tham số cho chương trình con.

Chương trình con chỉ thực hiện được khi các tham số hình thức đã nhận một bộ dữ liệu cụ thể nhờ việc truyền tham số từ chương trình mẹ. Việc truyền tham số cho chương trình con thường thông qua hai con đường:

Một là, sử dụng biến chung (public), tức là cả chương trình mẹ và chương trình con đều sử dụng chung một hay một số biến nào đó. Cách này thường khó kiểm soát giá trị của biến này, hay gây nhầm lẫn nên ít dùng.

Hai là: sử dụng tham số hình thức. Các tham số trong chương trình con là các biến độc lập với chương trình chính, kể cả chúng có cùng tên nhưng chỉ có hiệu lực trong chương trình con. Khi kết thúc chương trình con thì các biến này được giải phóng và không ảnh hưởng gì đến chương trình mẹ. Khi đó việc truyền tham số được thực hiện nhờ đẩy tham số thực sự trong lời gọi chương trình con.

b- Thủ tục (Procedure)

Thủ tục là một loại chương trình con dùng để thực hiện một số thao tác xử lí nào đó trong bài toán. Mỗi thủ tục được bắt đầu bằng từ khoá để xác định đó là thủ tục, thường là từ Procedure, với kiến trúc cơ bản như sau:

Procedure <tên thủ tục>[(biến 1, biến 2,...)]

[Khai báo các biến cục bộ]

<Các lệnh>

Trong đó:

Tên thủ tục: là tên một chương trình được đặt theo quy tắc của mỗi ngôn ngữ. Tên này dùng để gọi thủ tục nên buộc phải có.

Các biến 1, 2, ... là các tên biến gọi là tham số hình thức dùng làm dữ liệu ban đầu của thủ tục;

Các biến cục bộ: là các biến trung gian cần thiết cho việc xử lí dữ liệu ban đầu của thủ tục, những biến cục bộ chỉ có ý nghĩa ở chính trong thủ tục này.

Khi chương trình chính gọi một thủ tục qua tên cùng với các tham số thực sự (nếu có), thì các tham số hình thức trong thủ tục sẽ nhận lần lượt các giá trị của các tham số thực sự rồi thực hiện thủ tục như một chương trình bình thường. Sau khi thực hiện xong thủ tục, điều khiển lại trả về chương trình chính để thực hiện lệnh tiếp theo lệnh vừa gọi đến thủ tục trên.

Có một đặc điểm cần phải biết đến là: Thủ tục sẽ không được tham gia vào các biểu thức.

Ví dụ: Chương trình Pascal để tính diện tích tam giác bằng một trong nhiều cách có sử dụng một số thủ tục.

{Chuong trinh nhieu chuc nang}

Program Tinh_DT_tam_giac_bang_nhieu_cach;

Uses Crt;

Var

a,b,c,p,dientich:Real;

chon:integer;

Procedure ba_canh;

Begin

Write('Nhap canh thu nhat: ');Readln(a);

Write('Nhap canh thu hai: ');Readln(b);

Write('Nhap canh thu ba: ');Readln(c);

p:=(a+b+c)/2;

dientich:=SQRT(p*(p-a)*(p-b)*(p-c));

Writeln('Dien tich tam giac=',dientich:10:3);

End;

Procedure hai_canh_va_goc;

Var

goc:real;

Begin

Write('Nhap canh thu nhat: ');Readln(a);

Write('Nhap canh thu hai: ');Readln(b);

Write('Nhap do lon goc xen giua(tinh bang do):');Readln(goc);

dientich:=a*b*SIN(goc/180*pi)/2;

Writeln('Dien tich tam giac=',dientich:10:3);

End;

Procedure mot_canh_va_duong_cao;

Var

duongcao:real;

Begin

Write('Nhap canh thu nhat: ');Readln(a);

Write('Nhap duong cao tuong ung: ');Readln(duongcao);

dientich:=a*duongcao/2;

Writeln('Dien tich tam giac=',dientich:10:3);

End;

{Chương trình chính}

Begin

While true do

Begin

ClrScr;

Writeln(' Bam phim so tuong ung ');

Writeln('De chon cach can tinh dien tich tam giac');

Writeln(' *********************************');

Writeln('1 - Biet chieu dai ba canh.');

Writeln('2 - Biet chieu dai hai canh va goc xen giua.');

Writeln('3 - Biet chieu dai mot canh va duong cao tuong ung.');

Writeln('4 - Thoat khoi chuong trinh.');

Readln(chon);

If chon=1 then ba_canh;

If chon=2 then hai_canh_va_goc;

If chon=3 then mot_canh_va_duong_cao;

If chon=4 then exit;

If NOT ((chon=1) or (chon=2) or (chon=3) or (chon=4)) then

Writeln('Chon khong hop le!');

Readln;

End;

End.

c- Hàm (Function)

Hàm là một chương trình con dùng để tính một đại lượng nào đó có kiểu dữ liệu đơn giản, vô hướng (số, kí tự, xâu kí tự, logic, ...). Khi chương trình chính gọi một hàm thì phải có ít nhất một lệnh gán giá trị cho tên của hàm. Một hàm được bắt đầu bằng từ khoá, thường là từ Function và được kiến trúc cơ bản như sau:

Function <tên hàm>[(biến 1, biến 2,...)] <Kiểu kết quả của hàm>

[Khai báo các biến cục bộ]

<Các lệnh>

<Xác định các giá trị trả về chương trình mẹ>

Trong đó: Các thành phần có nghĩa tương tự trong phần thủ tục; Giá trị trả về chương trình mẹ là giá trị mà chương trình mẹ sẽ nhận được sau khi gọi hàm. Vì lí do này, các hàm sẽ phải có một kiểu dữ liệu của kết quả hàm và có thể tham gia vào các biểu thức.

Ví dụ: Trong Pascal, chương trình giải phương trình bậc hai, dùng một hàm để tính Delta:

Program Giai_PT_bac2;

Var

a,b,c,x1,x2:real;

Function delta(a1,b1,c1:real):real;

Begin

delta:=SQR(b1)-4*a1*c1;

End;

{Phan chuong trinh chinh}

Begin

Write('Nhap he so a=');readln(a);

Write('Nhap he so b=');readln(b);

Write('Nhap he so c=');readln(c);

If a=0 then

Begin

Writeln('Day khong la PT bac 2. Bam ENTER de ket thuc!');

Readln;

Exit;

End;

If delta(a,b,c)<0 then

Writeln('Phuong trinh vo nghiem')

Else

Begin

x1:=(-b+SQRT(delta(a,b,c)))/(2*a);

x2:=(-b-SQRT(delta(a,b,c)))/(2*a);

Writeln('Phuong trinh co nghiem');

Writeln('X1=',x1:10:3,' X2=',x2:10:3);

Readln;

End;

End.

Chú ý: Sau này, sẽ nghiên cứu ngôn ngữ C với một đặc điểm riêng là C không sử dụng thủ tục mà chỉ có hàm, do vậy các từ khoá Procedure và Function không cần dùng!

1.3.3. Kĩ thuật đệ quy

Một đối tượng được gọi là đệ quy nếu nó lại bao hàm chính nó hoặc nó được định nghĩa thông qua nó.

Ví dụ: Có thể định nghĩa n! là tích của n với (n-1)!

Một thuật toán được gọi là đệ quy nếu trong thân nó có lời gọi đến chính nó.

Ví dụ: Thuật toán đệ quy để tính n! :

- Theo định nghĩa đệ quy:

n! =

{

1 khi n = 0

n.(n-1)! khi n ≥ 1

- Dưới dạng một hàm, viết như sau:

Function Giai_thua(n)

If n = 0 then Giai_thua:=1

Else Giai_thua:=n*Giai_thua(n-1)

Return

Nhìn vào thuật toán và chương trình, ta thấy, có một lời gọi đến chính nó trong mệnh đề else của lệnh if, thế nhưng, mỗi lần gọi đến hàm Giai_thua thì n sẽ giảm đi 1; Quá trình đệ quy sẽ dừng khi n=0.

Trong lập trình, đệ quy là một kĩ thuật đặc biệt để chỉ hiện tượng tại một lệnh của chương trình con lại gọi đến chính chương trình con đó.

Ví dụ: Chương trình Pascal để tính tích P=1x2x3x...xn = n!

Cách 1: Không sử dụng kĩ thuật đệ quy

Program Tinh_giai_thua_KDQ;

Uses Crt;

Var

N:Integer;

Function Giai_thua:Longint;

Var

I:Integer;

P:Longint;

Begin

P:=1;

If N>0 then

For i:=1 to n do P:=P*I;

Giai_thua:=P;

End;

{Hết chương trình con, bắt đầu chương trình chính}

Begin

ClrScr;

Write(‘Nhap so n=’);Readln(n);

Writeln(‘N!=’,Giai_thua);

Readln;

End.

Cách 2: Sử dụng kĩ thuật đệ quy

Program Tinh_giai_thua_DQ;

Uses Crt;

Var

N:Integer;

Function Giai_thua(n:Integer):Longint;

Begin

If N=0 then Giai_thua:=1 Else

Giai_thua:=N*Giai_thua(n-1);

End;

{Hết chương trình con,

bắt đầu chương trình chính}

Begin

ClrScr;

Write(‘Nhap so n=’);Readln(n);

Writeln(‘N!=’,Giai_thua(n));

Readln;

End.

Phương pháp này có ưu điểm là rất ngắn gọn song thường tốn thời gian thực hiện và tốn bộ nhớ vì việc đệ quy sẽ sử dụng bộ nhớ xếp chồng Stack (vào trước ra sau) để chứa kết quả trung gian. Phải rất thận trọng để lường trước việc kết thúc quá trình đệ quy. Trong ví dụ trên, nếu có phép gán:

k:=giai_thua(-1);

thì sẽ khởi động một quá trình đệ quy rất dài vì sẽ xử lí sai với tham số âm, trong khi hoàn toàn có thể xử lí rất tiết kiệm bộ nhớ và thời gian bằng các lệnh chu trình.

Nói chung, trong lập trình, người ta thường không thích sử dụng kĩ thuật đệ quy. Khi đó phải khử đệ quy trong chương trình nhờ việc sử dụng kĩ thuật Stack.

1.4. Trình tự giải bài toán trên máy tính

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

Đối với người làm tin học, xác định bài toán là việc tìm hiểu toàn bộ nội dung bài toán, bao gồm:

- Xác định mục đích giải bài toán;

- Xác định dữ liệu ban đầu của bài toán;

- Xác định yêu cầu về các thông tin kết quả sau khi giải bài toán.

1.4.2. Xác định cấu trúc dữ liệu của bài toán

Với các dữ liệu ban đầu của bài toán đã được xác định ở bước 1, phải xác định được các dữ liệu cho trước có thể tạo thành dữ liệu có cấu trúc hay không, nếu có thì có thể tách ra thành nhóm dữ liệu sao cho mỗi nhóm sẽ tương ứng với một loại cấu trúc dữ liệu nào đó và nên sử dụng các cấu trúc nào thì hợp lí. Các kiểu cấu trúc dữ liệu đã được giới thiệu trong giáo trình về “Cấu trúc dữ liệu và giải thuật”.

1.4.3. Tìm cách giải và xây dựng thuật toán

Trong bước này, phải xác định xem bài toán có lời giải hay không? Nếu có, thì chọn lấy một cách giải tốt nhất. Sau khi chọn xong cách giải bài toán, tiến hành xây dựng thuật toán theo kiểu thiết kế trên - xuống để tạo ra các modul nhỏ trên cơ sở các cấu trúc dữ liệu đã lựa chọn. Đây là công việc khó khăn nhất trong quá trình giải bài toán vì nó mang tính kiến trúc toàn diện. Thuật toán có thể được mô tả bằng nhiều cách như đã giới thiệu ở trên.

1.4.4. Viết chương trình

Căn cứ vào thuật toán đã xây dựng ở bước 3, ta tạo mã nguồn (viết trình bằng một ngôn ngữ phù hợp với loại bài toán và khả năng của loại máy tính sẽ sử dụng). Trong viết trình, nên lợi dụng tối đa khả năng của các chương trình con.

1.4.5. chạy thử và hiệu chỉnh

Đây là bước xác định xem chương trình có lỗi hay không, nếu có lỗi thì phải hiệu chỉnh lại. Lỗi chương trình có thể thuộc về lỗi ngữ pháp, lỗi ngữ nghĩa hay lỗi thuật toán. Lỗi ngữ pháp là lỗi sử dụng sai cú pháp và yêu cầu của ngôn ngữ, thường dễ phát hiện trong quá trình dịch chương trình; Lỗi ngữ nghĩa là lỗi làm sai kết quả của phép xử lí (ví dụ lỗi tràn số) mặc dù vẫn đúng ngữ pháp, lỗi này thường được phát hiện trong quá trình chạy chương trình; Lỗi thuật toán là lỗi do sai thuật toán (ví dụ công thức tính toán sai, vòng lặp hay đệ quy vô hạn), thường khó phát hiện, yêu cầu người lập trình phải tự phát hiện lỗi trong thuật toán. Trong bước chạy thử, cần phải chuẩn bị trước các bộ dữ liệu khác nhau với các kết quả đã biết trước để kiểm định, các bộ dữ liệu này phải mang tính đặc trưng và quét hết các khả năng có thể xảy ra của bài toán trong quá trình sử dụng.

1.4.6. Giải bài toán

Giải bài toán chính là bước dùng chương trình sau khi đã được chạy thử và hiệu chỉnh để giải bài toán với dữ liệu thực tế. Trong quá trình này phải tiến hành đánh giá các tính năng của chương trình để một lần nữa hiệu chỉnh hoặc bảo trì chương trình.

1.4.7. Đánh giá kết quả

Việc đánh giá kết quả của quá trình giải bài toán là đánh giá hiệu quả và tính hợp lí của các thông tin kết quả do chương trình cung cấp và xem có phù hợp với mục tiêu giải bài toán hay không.

1.4.8. Hướng dẫn và bảo trì

Khi chương trình được viết cho nhiều người dùng, thì người lập trình phải viết tài liệu hướng dẫn sử dụng chương trình để cung cấp cho người dùng cùng với chương trình dịch. Hiện nay, đa số các chương trình đã có ngay trong nó dịch vụ hỗ trợ người dùng theo từng ngữ cảnh tại thời điểm máy đang hoạt động. Ngoài ra, còn phải có các chuyên gia giỏi về xử lí tình huống để giúp đỡ người dùng. Các chuyên gia này, một mặt đáp ứng nhu cầu thực tế của người dùng, mặt khác, đây là bộ phận cung cấp các thông tin phản hồi giúp người thiết kế hệ thống kịp thời điều chỉnh để nâng cấp sản phẩm của mình thành các phiên bản mới.

1.5. Số có độ chính xác hữu hạn

Phần “biểu diễn thông tin trong máy tính” ở giáo trình “Tin học đại cương” đã giới thiệu một cách sơ lược về nguyên tắc biểu diễn thông tin trong bộ nhớ của máy tính. Tuy vậy, có một vấn đề mới nảy sinh, đáng phải quan tâm, khác với tư duy toán học thông thường khi làm thủ công - đó là vấn đề độ chính xác của các số khi được lưu trữ ở bộ nhớ máy tính.

Với tất cả các loại máy tính, các thông tin số đều được lưu trữ trong các trường nhớ chuẩn có độ dài xác định và cố nhiên là hữu hạn. Bản chất hữu hạn đó buộc máy tính chỉ có khả năng xử lí các thông tin số có số chữ số cố định và giá trị nằm trong một phạm vi nào đó. Ta gọi những số đó là số có độ chính xác hữu hạn. Đây là đặc điểm rất quan trọng cần phải lưu ý trong quá trình xử lí thông tin bằng máy tính.

Để đơn giản, ta có thể xét một tập hợp các số nguyên dương được tạo thành từ 2 chữ số hệ thập phân làm ví dụ. Tập hợp này chỉ gồm 100 số: 00, 01, 02, 03, ..., 99. Vì hạn chế đó mà nó không thể biểu diễn được các số quá lớn hoặc quá nhỏ (>99 và <0), các phân số, các số vô tỉ, ...

Trong tư duy toán học thông thường, các phép toán tổng, hiệu và tích của hai số nguyên luôn là một số nguyên, còn trong máy tính với đặc điểm sử dụng số có độ chính xác hữu hạn, ở ví dụ trên, các phép toán sau sẽ thực hiện sai:

70 + 80 = 150 (quá lớn)

05 – 10 = -5 (số âm)

20 x 20 = 400 (quá lớn)

07 : 02 = 3.5 (không nguyên)

Các kết quả trên đều không thuộc phạm vi biểu diễn, và nghĩa là không thể thực hiện đúng trên máy tính.

Cũng lại thấy, các tính chất kết hợp, tính chất phân phối trên số có độ chính xác hữu hạn cũng khác với đại số thông thường. Chẳng hạn:

50 + (60 – 30) khác với (50 + 60) – 30

Tràn số ở đây

5 x ( 50 – 40) khác với 5 x 50 – 5 x 40 !

Nếu bạn đã làm quen với ngôn ngữ lập trình Pascal thì sẽ càng thấy rõ điều này. Chẳng hạn, số nguyên kiểu integer được lưu trữ ở 2 bytes với mã bù 2, do vậy sẽ có phạm vi biểu diễn từ -32768 đến 32767, ta xét đoạn chương trình sau:

Var i: integer;

Begin

i := 32767;

i := i + 1;

writeln(“i1 = ”, i);

i := i + 1;

write(“i2= ”, i);

readln;

End.

thì giá trị của i được đưa ra ở lệnh writeln sẽ là i1 = -32768 và ở lệnh write sẽ là i2 = -32767. Thế nhưng, trong đại số thông thường thì hoàn toàn không phải như vậy.

Bạn sẽ hoàn toàn ngạc nhiên khi bạn gán cho một biến số thực x nào đó một số nhưng khi quay lại so sánh x với chính số đó thì máy tính xác định x không bằng chính số đó. Có thể thấy điều đó trong ví dụ sau ở Pascal:

Var

x:Real;

Begin

x:=1.1;

If x=1.1 then Write(‘TRUE’) Else Write(‘FALSE’);

Readln;

End.

Trong đại đa số các trường hợp, bạn sẽ được câu trả lời là FALSE. Và điều đó là hoàn toàn có thể lí giải được bằng lí luận về số có độ chính xác hữu hạn.

Trong khi xây dựng thuật toán, người ta thường không để ý đến giá trị của các kết quả được tính toán mà chỉ để ý đến cách làm, trình tự công việc, tính tối ưu và độ phức tạp khi tính toán. Thế nhưng, khi xây dựng chương trình để máy tính thực hiện thuật toán giúp con người, vấn đề độ chính xác hữu hạn của số lại trực tiếp ảnh hưởng tới kết quả tính toán của máy tính. Vì thế, trong các ngôn ngữ lập trình, nhất là với các ngôn ngữ thuật toán, người ta phải để ý đến kiểu dữ liệu cùng với phạm vi biểu diễn của chúng và đánh giá trước miền kết quả của các phép tính sẽ được thực hiện khi viết trình để chọn được kiểu dữ liệu tương ứng cho phù hợp với bài toán thực tế. Chẳng hạn, trong Pascal, khi tính n!, nếu ta xác định chỉ chạy với các số n khá nhỏ thì có thể xác định kết quả là số kiểu interger, lớn hơn nữa thì có thể xác định kết quả là số kiểu longint, thậm chí kiểu real, double,... . Việc này, chỉ có con người mới có thể xác định được.

Xin được lưu ý thêm rằng, trong nhiều trường hợp, người lập trình không có ý thức rõ ràng về vấn đề này. Ta có thể thấy ngay điều đó trong một ví dụ rất đơn giản mà nhiều người vướng phải, ví dụ giải phương trình bậc 2:

Nếu xác định Delta là biến kiểu REAL và kiểm tra điều kiện có nghiệm kép được viết là:

If Delta=0 Then Write(‘Nghiệm kép x = ‘, -b/(2*a));

thì rất sai vì rất nhiều giá trị của Delta khác 0 (hai khoảng 0<delta<2,9x10-39 và - 2,9x10-39 <Delta <0) sẽ đều được máy xác định là 0 và do đó gây ra sai lầm về mặt thuật toán. Trong khi rèn luyện về kĩ năng lập trình, ta có thể “tạm tha thứ” cho những sai sót đó để đạt được những điều lớn hơn nhưng vẫn phải biết sự có mặt của các trường hợp đó để xử lí các vấn đề thực tế về sau.

Với bản chất hữu hạn của bộ nhớ máy tính, trong quá trình xử lí dữ liệu số, phải thường xuyên quan tâm đến dữ liệu, xem có vượt quá phạm vi biểu diễn của máy tính hay không, dữ liệu có phù hợp không? Nếu không, có thể nhận được một kết quả sai không ngờ tới.

bài tập và Câu hỏi ôn tập chương 1

1. Khái niệm về thuật toán, các cách biểu diễn thuật toán. Sự liên quan giữa thuật toán và dữ liệu?

2. Các cấu trúc cơ bản của thuật toán? Lấy một ví dụ minh hoạ cho tất cả các cấu trúc trên.

3. Khái niệm chương trình và mối quan hệ giữa các ngôn ngữ lập trình?

4. Những điểm cần nắm vững đối với một ngôn ngữ lập trình cấp cao? Chỉ ra cách tiếp cận một ngôn ngữ lập trình mới trong kĩ thuật lập trình cấu trúc?

5. Nội dung của kĩ thuật thiết kế trên - xuống và ý nghĩa của nó?

6. Khái niệm chương trình con và mối quan hệ với kĩ thuật trên - xuống?

7. Cấu trúc chung của một chương trình con?

8. Khái niệm đệ quy trong chương trình, ưu và nhược của kĩ thuật đệ quy?

9. Các bước để giải một bài toán trên máy tính và ý nghĩa của từng bước?

10. Cấu trúc bộ nhớ trong của máy tính và cách lưu trữ thông tin số trong bộ nhớ máy tính?

11. Tìm hiểu hai bảng mã ASCII, UNICODE và cách lưu thông tin kí tự trong bộ nhớ của máy tính.

12. Khái niệm về số có độ chính xác hữu hạn và những hạn chế trong xử lí dữ liệu số của máy tính?

13. ý nghĩa của việc nghiên cứu vấn đề số có độ chính xác hữu hạn và những điều cần lưu ý về vấn đề này đối với người lập trình?

Bạn đang đọc truyện trên: Truyen2U.Pro

Trước Sau