Chương 1 TÔNG QUAN VÈ cơ SỞ LẬP TRÌNH Chương này bao gồm các kiến thức về thuật toán, tính chất thuật toán, sơ đồ khối và các khái niệm về chương trình và ngôn ngữ lập trình. Đồng thời chương này còn bao gồm cả việc giới thiệu về các phương pháp lập trình và các kỹ thuật thiết kế chương trình như kỹ thuật chương trình con và kỹ thuật đệ quy. Khái niệm Thuật toán là một tập hữu hạn các bước lệnh đã được xác định theo một thứ tự nhất định để theo đó máy tính có thể thực hiện được một cách tự động nhằm mục đích giải một bài toán hay một nhiệm vụ nào đó. Thông thường các lệnh ở các bước chính là các phép vào thông tin, phép xử lý hoặc ra thông tin.
Thuật toán phải được thể hiện rõ ràng trong các bước của nó và khi thuật toán được thực hiện thông qua dãy hữu hạn các bước thì phải đảm bảo dừng và cho ra kết quà theo mong muốn của người sử dụng.1: Viết thuật toán giải phương trinh bậc hai ax2+bx+c=0 (aoO) Bước 1: Nhập các giá trị của 3 hệ số a, b, c Bước 2: Nếu a=0 thì 2. Yêu cầu đầu vào không đảm bảo. Chuyển đến bước 4 Bước 3: Trường hợp a khác 0 thì 3. Tính giá trị D = b2 - 4ac 5 3.
Phương trình có hai nghiệm phân biệt X] và x2 3. Giá fri của hai nghiệm được tính theo công thức sau 3. Chuyển đến bước 4. Phương trình có nghiệm kép x0 3.
Giá trị của nghiệm kép là „ -b x°~ 2a 3. Chuyển đến bước 4 3. Phương trình vô nghiệm. đến bước 4 Bước 4: Kết thúc 1.
Tính chất của thuật toán Trong khuôn khổ giáo trình một số tính chất cơ bản sẽ được giới thiệu bao gồm: ■ Tính xác định: Tính chất này có nghĩa là các bước của thuật toán phải rõ ràng, chính xác, không gây nên sự nhập nhằng, đa nghĩa. Thực hiện đúng các bước của thuật toán thì với một bộ dữ liệu vào, chỉ cho duy nhất một bộ kết quả ra. Ví dụ: Ở ví dụ giải phương trình bậc 2 nói trên, việc tính D = b2-4ac và phân chia các trường hợp của D để đảm bảo rằng trong mọi trường 6 hợp của D thì thuật toán luôn có câu trả lời kết quả tương ứng (Có 2 nghiệm riêng biệt; có nghiệm kép; hay vô nghiệm). ■ Tính dừng: Tính chất này có nghĩa là khi áp dụng thuật toán cho một bộ dữ liệu cụ thể thì sau hữu hạn bước thực hiện sẽ cho kết quà và kết thúc.
Tính dừng là một trong các tính chất dễ bị vi phạm khi trình bày các bước của thuật toán. Điều đó có nghĩa là khi thực hiện hết các bước của thuật toán, người sử dụng sẽ nhận được kết quả mong muốn. Tuy nhiên, có những thuật toán mà khi thực thi nó sẽ “chạy mãi không dừng” (hay còn gọi là “lặp vô tận”) thì chúng sẽ được gọi là thuật toán “vi phạm tính dừng”. Ví dụ: Viết thuật toán để tính tổng các sổ nguyên dương lẻ < n (n nhập từ bàn phím).
Thuật toán như sau: Bước 1. Nếu i = n+1 thì sang Bước 8, ngược lại sang Bước 5 Bước 5. Quay lại bước Bước 4. In ra s Rõ ràng, thuật toán kết thúc khi giá trị của i vượt quá n, nhưng điều kiện "i=n+l" không phải lúc nào cũng đạt được.
Vì nếu n là số chẵn thì n+1 là một số lẻ thì sau một số hữu hạn bước, i sẽ bằng n+1. Tuy nhiên, nếu n là một số lẻ thì n+l là một số chẵn nên không đạt được i= n+1. Hay nói cách khác thuật toán sẽ không dừng. 7 ■ Tính phổ dụng: Tính chất này có nghĩa ỉà thuật toán không chỉ giải cho một bài toán mà giải cho một lớp các bài toán và có thể làm việc trên các dữ liệu khác nhau.
■ Tính đúng: Tính chất này có nghĩa là sau khi thực hiện tất cả các bước của thuật toán theo đúng trình tự, ta phải được kết quả mong muốn với mọi bộ dữ liệu đầu vào. Kết quả đó được kiểm chứng bằng yêu cầu của bài toán. ■ Tính khả thi: Tính chất hày thể hiện ưên ba yêu cầu sau: - Kích thước phải đủ nhỏ. Một thuật toán sẽ có tính hiệu quả bằng 0 nếu lượng bộ nhớ mà nó yêu cầu vượt quá khà năng lưu trữ của hệ thống máy tính.
- Thuật toán phải được máy tính thực hiện trong thời gian cho phép. Ví dụ như xếp thời khóa biểu thì không thể cho máy tính chạy lâu tới mức mà việc xếp thời khóa biểu chỉ có thể áp dụng cho các kì tiếp theo. - Thuật toán phải dễ hiểu và dễ cài đặt. Khái niệm Đổ thể hiện thuật toán người ta có thể dùng nhiều phương pháp để biểu diễn, ví dụ như cách viết ở trên (mục 1.1) được gọi là phương pháp liệt kê theo các bước.
Ngoài ra, một trong các phương pháp thể hiện thuật toán thường được dùng là sơ đồ khối. Vậy, sơ đồ khối là cách thể hiện thuật toán bàng các hình khối hình học nối với nhau bằng các đường đi có hướng. Ở đây, chúng ta quy ước trong sơ đồ khối sử dụng các hình khối như sau: 8 Khối kiểm tra điều kiện Hướng thực hiện Khối vào ra 1. Các dạng cấu trúc cơ bản của sơ đồ khối Sơ đồ khối thể hiện thuật toán thường được thể hiện ở 3 dạng cơ bản như sau: • Sơ đồ khối dạng tuần tự: Là sơ đồ khối thể hiện thuật toán gồm n khối mà khi thực hiện thuật toán với một bộ dữ liệu cụ thể sẽ lần lượt thực hiện từ khối đầu tiên đến khối cuối cùng theo thứ tự viết của nó.
• Sơ đồ khối dạng rẽ nhánh: Là sơ đồ khối thể hiện thuật toán gồm n nhánh mà khi thực hiện thuật toán với một bộ dữ liệu cụ thể sẽ thực hiện một trong n nhánh mà thôi.1: Vẽ sơ đồ khối thể hiện thuật toán để giải bài toán giải phương trình bậc hai nói trên.1: Sơ đồ khối giải phương trình bậc hai ax2+bx+c=0 (aoO) • Sơ đồ khối dạng chu trình: Là sơ đồ khối thể hiện thuật toán gồm n khối mà khi thực hiện thuật toán với một bộ dữ liệu cụ thể sẽ có một số khối lặp đi lặp lại nhiều lần phụ thuộc vào một điều kiện nào đó vẫn thỏa mãn.2: Cho một dãy A gồm N số nguyên khác nhau ab a2, aN. Tìm và in ra chỉ số I và giá trị aj, mà ai chia hết cho k (k nguyên, và nhập từ bàn phím) hoặc thông báo không có số hạng nào của dãy A mà chia hết cho k. Trên thực tế, sơ đồ khối dùng để giải bài toán nào đó có thể được sử dụng một cách hỗn hợp với 3 dạng cơ bản nói trên. Nghĩa là trong sơ đồ 10; khối, có thể đoạn khối này là tuần tự, đoạn khác là rẽ nhánh, và đoạn khác nữa là chu trình, hoặc trong đoạn khối rẽ nhánh lại chứa đoạn khối rẽ nhánh, hoặc trong đoạn khối chu trình lại chứa chu trình v.
Sơ đồ khối thể hiện bài toán ờ ví dụ 1.2 11 Giả mã (Pseudo Code) Mặc dù sơ đồ khối thể hiện rất rõ quá trình xử lý Tuy nhiên, để có thể chuyển hóa từ sơ đồ thành ngôn ngữ lập trình là việc không hề dễ dàng. Vì thế, khi thể hiện thuật toán bằng cách thức giả lập mã, cách viết này sẽ minh họa dưới dạng sử dụng các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Điều này giúp cho việc vừa tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán. Ví dụ một đoạn giả mã của thuật toán giải phưoìig trình bậc hai Neu delta > 0 thì làm các việc: X1 =(-b-sqrt(delta))/(2 *a) x2=(-b+sqrt(delta))/(2*a) In ra màn hình: phương trình có hai nghiệm là X] và x2 Ngược lại Neu delta = 0 thực hiện: In ra kết quả: phương trình có nghiệm kép là -b/(2*a) Ngược lại {delta < 0 } In ra kết quả: phương trình vô nghiệm 1.
CHƯƠNG TRÌNH VÀ NGÔN NGỮ LẬP TRÌNH 1. Khái niệm chương trình Chương trình là một tập hợp các lệnh để thể hiện một thuật toán giải quyết một bài toán hay một nhiệm vụ nào đó. Trong đó, lệnh chính là một chỉ thị cho máy tính để theo đó máy tính có thể thực hiện một cách tự động. Ví dụ như việc viết các dòng lệnh để máy tính có thể giải phương trình bậc 2: ax2 + bx +c =0 (a#0) một cách tự động mà không cần có sự can thiệp của con người trong quá trình xử lý.
Ngôn ngữ lập trình Ngôn ngữ lập trình là ngôn ngữ để viết chương trình. Có nhiều loại ngôn ngữ lập trình khác nhau mà sự liên quan của chúng phụ thuộc vào kiến trúc và hoạt động của máy tính. Có thể phân chia chúng thành các mức: • Ngôn ngữ máy: Là ngôn ngữ chương trình được viết ở dưới dạng nhị phân hoặc ở dạng hexa, mà máy tính có thể hiểu được một cách trực tiếp và thực hiện được. Tuy nhiên, nó không thuận lợi cho con người trong việc hiểu và viết chương trình.
• Họp ngữ: Là ngôn ngữ cấp thấp mà con người có thể sử dụng được để viết chương trình. Điểm không thuận lợi của ngôn ngữ này là chúng phụ thuộc chặt chẽ vào kiến trúc của máy tính. • Ngôn ngữ lập trình bậc cao: Là ngôn ngữ mà câu lệnh của nó gần gũi với ngôn ngữ tự nhiên. Chúng có tính độc lập, nghĩa là không phụ thuộc vào một loại máy cụ thể nào.
Ngôn ngữ lập trình phải bao gồm các yếu tố sau đây: • Tập các ký tự; Tập hợp từ vựng. • Tập hợp các quy tắc ngữ pháp và quy tắc viết các lệnh. Đối với các chương trình viết bằng họp ngữ hoặc ngôn ngữ lập trình bậc cao thì chúng cần có một chương trình dịch tương ứng để dịch chúng sang ngôn ngữ máy. Chương trình dịch cho hợp ngữ gọi là hợp dịch (dịch từ ngôn ngữ cấp thấp ra ngôn ngữ máy).
Để dịch chương trình viết bằng ngôn ngữ lập trình bậc cao sang ngôn ngữ máy gồm có trình biên dịch (dịch từ ngôn ngữ bậc cao sang ngôn ngữ cấp thấp) và hợp dịch (dịch tiếp ra ngôn ngữ máy). Quy trình giải bài toán trên máy tính điện tử Việc giải bài toán trên máy tính điện tử thường được tiến hành qua các bước sau đây: 13 • Bước 1: Xác định bài toán: Phải xác định mục đích của bài toán, xác định dữ liệu vào, xác định cách xử lý và dữ liệu đưa ra.