Từ đầu cần khẳng định ý định của snow khi viết bài này là mong muốn snow và các bạn sẽ cùng nhau tạo ra 1 loạt bài viết về các thuật toán cơ bản, về các kĩ năng lập trình cơ bản, về những CTDL cơ bản, về các kinh nghiệm lập trình của bản thân. Trong lập trình mà nói đây là những thứ rất quan trọng và mỗi người sẽ có những kinh nghiệm cũng như những “miếng” riêng rất hay. Vậy snow rất mong các bạn và snow sẽ cùng post lên nhưng hiểu biết và kinh nghiệm của mình để cùng nhau học hỏi và hi vọng đây sẽ là 1 bài tut tốt cho các bạn newbie cho cả snow và các bạn. Và snow tự nhận là mình ko giỏi và cần học hỏi nhiều, nên rất mong nhận được góp ý cũng như được học hỏi từ các bạn
Vì là bài viết dựa trên những gì snow được học, từng gặp, từng làm, từng đọc và bản thân snow là người không giỏi hệ thống lại vấn đề nên rất mong các mod nếu có thể thì chỉnh sửa lại cho có hệ thống hơn và cũng rất mong các mod sẽ post lên những kinh nghiệm của mình ...
Cũng chẳng biết phải bắt đầu như thế nào nên snow đành đem cái “khẩu hiệu” nổi tiếng của Niklaus Wirth ra làm lời đầu tiên cho mình :
Data Structures + Algorith = Programs (Cấu trúc dữ liệu + Giải thuật = Chương trình).
Thật ra mà nói khi snow chọn IT thì cũng chỉ là sự tình cờ(tại thấy là ngành “oách” nhất hiện tại... greenbiggrin.gif ), lúc đó đối với snow công việc lập trình là cái chi chi đó rất “ghê gớm” và cao siêu. Và với hiểu biết hạn hẹp của mình vào lúc đó snow tưởng tượng ra rất nhiều chuyện buồn cười về công việc lập trình cũng như về các lập trình viên. Chẳng hạn như muốn viết ra 1 chương trình thì người ta phải ngồi đó và viết vào máy từng mã nhị phân 0,1... y chang như mấy người điện tín viên gõ và nhận mã morse ( greenbiggrin.gif thật ra đây là công việc của trình biên dịch hoặc trình thông dịch chứ đâu phải của lập trình viên). Sau này có học rồi, tiếp xúc rồi mới thấy nó khác hẳn với suy nghĩ của mình. Nó không quá khó nhưng cũng không quá dễ, vấn đề là nó đòi hỏi bạn phải nắm được kiểu tư duy của nó.
Về mặt nào đó học lập trình giống như việc bạn học thêm 1 thứ ngôn ngữ mới, 1 thứ tư duy mới (có 1 câu danh ngôn rất hay về việc học ngoại ngữ mà snow thấy nó cũng có phần nào đúng với việc học lập trình “Học thứ tiếng của 1 dân tộc là học các tư duy của dân tộc đó”). Cũng vậy, khi bạn học lập trình là thật ra giống như bạn đang học nói chuyện với máy, học cách ra lệnh cho nó làm những gì mà bạn muốn. Vì vậy, nếu lời nói của bạn “trong sáng, dễ hiểu” đối với máy thì nó sẽ chạy tốt, còn ngược lại thì...... greenbiggrin.gif
Có người từng nói với snow: “Muốn lập trình tốt thì đầu tiên phải học cách... ngu như máy trước, rùi mới lập trình tốt được!”. Ý người đó muốn nói là lập trình viên phải hiểu được những giới hạn cũng như những khả năng của máy tính thì mới có thể lập trình tốt được. Nếu bạn ko nắm rõ thì những gì bạn viết ra đôi khi là
Mission Impossible với 1 cái máy tính và khi đó nó sẽ trở nên “ngu”.
1. Những yêu cầu với 1 chương trình máy tính
Đầu tiên ta cần biết lập trình là viết ra những chương trình nhằm giúp máy tính giải quyết những bài toán, những yêu cầu nào đó trong thực tế cho ta. Vì vậy có 1 số yêu cầu nhất định cho việc viết chương trình:
+Đúng đắn: chương trình phải đáp ứng được những yêu cầu được đặt ra.
+Chính xác
+Tin cậy: bảo đảm cùng 1 dữ liệu nhập vào thì kết quả trả ra luôn luôn giống nhau
+Tổng quát: người lập trình viên phải có khả năng nhìn thấy tất cả mọi khả năng có thể của dữ liệu nhập vào và chương trình phải làm việc tốt được với mọi dữ liệu nhập vào.
+An toàn: chương trình phải làm việc tốt ngay cả trong những điều kiện bất thường xảy ra, hạn chế việc chương trình bị “chết” trong quá trình chạy vì nhiều nguyên nhân như dữ liệu nhập vào không phù hợp, lỗi truy cập...vv... (hình như việc này ngay cả Microsoft cũng...ko làm được vì Widows cứ bị hư hoài à...).
+Hiệu quả: Chương trình phải tiết kiệm tài nguyên ở mức thấp nhất có thể, chạy nhanh nhất ở mức có thể...
+Dễ : nâng cấp, sửa chữa.
2.Thiết kế chương trình:
a. Các xu hướng thiết kế:
Hiện nay có 2 xu hướng chính được chọn lựa trong việc thiết kế chương trình máy tính đó là : hướng thủ tục và hướng đối tượng
a.1.Hướng thủ tục(MP):
Thông qua 1 quá trình phân tích nhất định, lập trình viên sẽ tách bài toán hay yêu cầu ban đầu thành những bài toán con, yêu cầu con đơn giản hơn và giải quyết từng thứ 1. Việc này sẽ giúp bạn thực hiện được các bài toán phức tạp 1 cách dễ dàng. Bởi vì viết tổng thể cả 1 bài toán phức tạp là 1 việc làm rất khó và gần như Mission Impossible, nhưng chia nhỏ nó ra thành từng phần nhỏ hơn để giải quyết rùi gắn từng phần riêng đó lại là lựa chọn dễ dàng và khôn ngoan hơn. Việc này còn giúp cho chương trình của bạn dễ đọc, dễ bảo quản và dễ sửa chữa hơn.
Vd: yêu cầu đặt ra là bạn phải viết 1 chương trình dọc dữ liệu từ 1 file chứa các thông tin về số nhân viên, thông tin của từng nhân viên của 1 công ty, xử lí và trả lại thông tin về lương sẽ trả tháng này của từng nhân viên.
Như vậy nếu bạn để y nguyên như vậy mà làm sẽ rất khó và khi có sai sót bạn sẽ rất khó dò lỗi trong 1 khối chương trình gộp chung như vậy. Vì vậy bạn sẽ tách quá chương trình ra 1 số quá trình đơn giản hơn như sau:
Xử lí việc đọc file
Xứ lí thông tin đọc được từ file
Xử lí việc thông báo kết quả.
Từ các quá trình này bạn có thể tách thêm các quá trình con nữa nếu cần.
Như vậy khi xảy ra lỗi trong lập trình thì việc tìm lỗi và sữ chữa sẽ dễ dàng hơn cho bạn. Chẳng hạn khi lỗi thuộc về việc đọc file thì bạn chỉ cần dò tìm nó trong đoạn thủ tục bạn viết dùng để đọc file.
a.2.Hướng đối tượng(OOP): đây là 1 hướng thiết kế mới và gần với thực tế hơn phương pháp hướng thủ tục nhưng đương nhiên đòi hỏi ở bạn nhiều việc để làm và suy nghĩ hơn. 1 cách cơ bản mà nói thì hướng đối tượng nhìn vấn đề với 1 “con mắt khác” so với hướng thủ tục.
a.3 Khác như thế nào???
Nếu như ở hướng thủ tục bạn nhìn chương trình như “1 đống những công việc nhỏ cần phải làm tuần tự”. Thì khác 1 chút ở hướng đối tượng bạn nhìn theo hướng “1 đống những dữ liệu cần được tách riêng và xử lí” (đây là cảm nhận và cách hiểu riêng của snow về 2 hướng lập trình này...).
Vậy tại sao nói hướng đối tượng gần với thực tế hơn hướng thủ tục???
Đơn giản là vì trong thực tế mọi thứ tồn tại vốn dưới dạng các đối tượng (dữ liệu) khác nhau và các đối tượng đó tương tác với nhau chứ ko phải là các thủ tục.
Vd: bạn có thể hình dung như thế này. Cũng với ví dụ tính lương ở trên.
+Bây giờ giả sử tất cả các nhân viên đó đều thuộc về 1 công ty và có những chức vụ khác nhau. Như vậy nếu nhìn theo hướng thủ tục bạn sẽ chỉ thấy việc phải xử lí riêng cho từng loại nhân viên thuộc từng chức vụ 1 và việc này hơi “rối mù“ 1 chút trong chương trình và dễ gây nhầm lẫn cũng như sẽ khó cho việc sửa chữa, nâng cấp về sau nếu như xuất hiện thêm những chức vụ mới.
+Nhưng nếu bạn nhìn theo hướng đối tượng bạn sẽ thấy rằng đầu tiên ở đây có chung 1 loại đối tượng lớn nhất là “nhân viên”. Tiếp theo từ “nhân viên” ta có thể tách ra những đối tượng con của nó là “công nhân”, “trưởng phong”, “thư kí”, “giám đốc”, mỗi 1 đối tượng con sẽ có chung các đặc điểm của đối tượng cha và có riêng các đặc tính riêng của nó. Như vậy khi có thêm chức vụ thì bạn chỉ đơn giản thêm vào 1 đối tượng con mới chứ ko cần sửa lại đoạn mã đã viết ban đầu.
Nhưng bạn phải hiểu đối tượng trong hướng đối tượng ko chỉ đơn giản là “dữ liệu” mà mỗi đối tượng ngoài dữ liệu còn mang trong nó những thủ tục, hành vi của riêng đối tượng đó và đối tượng tương tác với các đối tượng khác thông qua các hành vi này. Và các đối tượng giống nhau sẽ có cùng những hành vi giống nhau. Đây là tính đóng gói của hướng đối tượng.
Ngoài ra hướng đối tượng còn có tính thừa kế nghĩa là tất cả những kiểu đối tượng con dẫn xuất từ cùng 1 kiểu đối tượng cha sẽ được thừa kế những “đặc tính” di truyền của cha (về dữ liệu cũng như hành vi...).
Một tính chất quan trọng khác của hướng đối tượng là tính đa hình, nghĩa là cùng 1 hành vi nhưng đối tượng sẽ có cách “xử sự” khác nhau với từng loại đối tượng khác nhau tuỳ theo định nghĩa của bạn về hành vi của đối tượng đối với từng loại đối tượng khác nhau...
b.Các phương pháp thiết kế:
Ở đây cũng có 2 phương pháp thiết kế chính là từ trên xuống (Top-down) và từ dưới lên (Bottom-up)
b.1.Top-down:
Đây là phương pháp thiết kế mang tính đi sâu vào tổng quát trước. Ở từng tầng của phương pháp thiết kế này chức năng tổng quát nhất được đem ra làm tên gọi, sau đó bạn phát triển những tầng tiếp theo nhỏ hơn của chức năng đó. Và cứ tiếp tục phân tầng như vậy cho tới khi các chức năng đã được đơn giản ở mức có thể thực hiện dễ dàng và hiệu quả.
b.2.Bottom-up:
Ngược lại với kiểu thiết kế top-down là kiểu bottom-up. Kiểu này được sử dụng chủ yếu khi bạn cần xây dựng chương trình từ những thứ đã có sẵn. Như vậy bạn chỉ cần tìm các thành phần cần thiết từ những thứ đã có. Một ví dụ đơn giản là khi bạn sử dụng các hàm đã có sẵn và được hỗ trợ của ngôn ngữ lập trình để xây dựng 1 ứng dụng đơn giản nào đó.
3.Các cấu trúc điều khiển cơ bản:
Dù chương trình của bạn có được xây dựng phức tạp như thế nào, có ứng dụng những giải thuật cao siêu tới đâu thì thực chất 2 thành phần cơ bản nhất xây dựng ra chúng vẫn chỉ là dữ liệu và các cấu trúc điều khiển. ở đây snow nói về các cấu trúc điều khiển cơ bản:
+Cấu trúc điều khiển tuần tự:
các toán tử, hàm, câu lệnh, dữ liệu được xử lí theo nguyên tắc tuần tự: trái sang phải, trên xuống dưới. Bạn phải nắm rõ sự tuần tự này và cả các thay đổi của dữ liệu trong thứ tự làm việc của chương trình nếu muốn đảm bảo chương trình sẽ chạy đúng.
+Cấu trúc điều kiện:
Bao gồm những toán tử, hàm, câu lệnh, dữ liệu chỉ được thực hiện hoặc xử lí khi 1 điều kiện nào đó được thỏa mãn.
+Cấu trúc lặp:
Gồm những toán tử, hàm, câu lệnh, dữ liện sẽ được xử lí lặp lại 1 số hữu hạn lần nào đó. Bạn phải chú ý khi sử dụng cấu trúc lặp để tránh tạo ra những cấu trúc lặp vô hạn sẽ dẫn đến việc treo máy. Vì vậy yêu cầu đầu tiên khi sử dụng cấu trúc lặp là điều kiện dừng của vòng lặp phải đúng đắn. Bạn còn phải lưu ý tính nhớ và sự thay đổi của dữ liệu trong vòng lặp để đảm bảo cho chương trình chạy đúng.
+Ngoài 3 cấu trúc cơ bản trên còn 1 kiểu lập trình rất cần thiết cho 1 số bài toán, đó là kiểu đệ qui. Đôi khi đây là “điều không thể tránh khỏi” khi bạn “đụng” vào những bài toán có bạn chất là đệ qui.
1 thủ tục đệ qui sẽ gọi lại bản thân nó tại 1 nơi nào đó bên trong thủ tục đó nếu 1 điều kiện dừng nào đó ko được thoả. Cũng giống như cấu trúc lặp, khi sử dụng đệ qui bạn phải đảm bảo điều kiện dừng cho nó. Nhưng bạn cần lưu ý là đệ qui sẽ chiếm 1 số khá lớn tài nguyên bộ nhớ do mỗi 1 lần đệ qui, các mã lệnh sẽ được “quăng” vào stack của bộ nhớ và lưu lại đó cho tới khi được xử lí. Như vậy đệ qui càng nhiều lần thì bộ nhớ sẽ “nặng” và ảnh hưởng tới hiệu quả của các chương trình khác. Trong 1 số trường hợp bạn có thể khử đệ qui bằng cách sử dụng các vòng lặp, stack hoặc queue...
1 ví dụ đơn giản về đệ qui trên C:
Chẳng hạn để tính 1 giai thừa n!, bạn có thể sử dụng 1 hàm đệ qui như sau:
int Giai_thua(int n)
{
if(n==1)
return 1;
return n*Giai_thua(n-1);
}
Nhưng cũng có thể sử dụng vòng lặp để giải quyết:
int Giai_thua(int n)
{
int result=1;
for(int i=2; i<=n; i++)
result *= i
return result;
}
4. Tổng quát về trình biên dịch và thông dịch của ngôn ngữ lập trình:
Ở đây snow chỉ nói sơ sơ những gì snow hiểu về trình biên dịch và thông dịch để giúp các bạn khỏi thắc mắc xem “nó làm ăn ra sao???”. Và đây cũng được coi là những hiểu biết sơ đẳng nhất mà bạn cần biết khi lập trình:
Như snow đã từng đề cập ở trên, việc lập trình ngày nay ko phải là cái kiểu ngồi dịch từng mã nhị phân như “cái thuở ban đầu lưu luyến ấy” nữa. Ngày nay các lập trình viên tạo ra các chương trình bằng việc lập trình bằng 1 ngôn ngữ nào đó và đem biên dịch bằng trình biên dịch của ngôn ngữ đó trước khi chạy chương trình, hoặc vừa chạy vừa dịch(chạy tới đâu dịch tới đó) nếu là trình thông dịch.
2 chương trình trên thực chất có thể coi là trung gian giao tiếp giữa người lập trình viên và máy tính. Hiểu nó bạn sẽ hiểu “Ê, tại sao tui viết cái lệnh toàn tiếng Anh hông hà mà mấy cái máy nó hiểu hay vậy???”. Thiệt ra thì máy đâu có hiểu mấy cái “tiếng Anh nửa mùa” mà bạn viết. Nó chỉ hiểu mã nhị phân 0,1 của những gì bạn viết ra đã được trình biên dịch hoặc thông dịch dịch lại cho nó “nghe” thôi. Nhưng giữa 2 chương trình thông dịch và biên dịch có những khác biệt nhất định dù chúng có cùng nhiệm vụ là “dịch” lại cho máy “nghe” những gì bạn “nói” với nó.
4.1 Trình biên dịch:
Toàn bộ mã chương trình mà bạn viết sẽ được trình này dịch ra hợp ngữ (assembly) để chuyển thành chỉ thị máy. Trong quá trình này có thể bao gồm quá trình tiền xử lí, biên dịch từng đoạn nhỏ của chương trình, kiểm tra lỗi, kiểm tra kiểu của các biến..., lắp ráp lại thành chương trình cuối cùng để máy có thể thực thi.
4.2 Trình thông dịch:
Khác với trình biên dịch, trình thôn dịch không dịch cùng lúc toàn bộ mã chương trình mà nó dịch từng dòng mã lệnh thành những chỉ thị mà máy có thể thực thi ngay. Từng lệnh sẽ được dịch và được thi hành ngay trong khi dịch chứ ko phải dịch xong tất cả, ráp nối lại rồi mới chạy như trình biên dịch. Nhưng đây cũng có thể là điểm bất lợi của trình thông dịch vì cùng 1 câu lệnh như nhau bạn có thể phải dịch lại nhiều lần ở nhiều thời điểm khác nhau. Trong khi ở trình biên dịch bạn sẽ chỉ phải dịch 1lần, khi cần thì trỏ vào đoạn mã chương trình đã được dịch trước đó.
Như đã nói trước đó, trong bài này snow cũng chỉ đề cập tới 1 số vấn đề và khái niệm cơ bản nhất nhằm giúp những bạn mới làm quen với lập trình có được cái nhìn tổng quát về lập trình. Một số vấn đề hơi “cao” sẽ được đề cập nhưng cũng chỉ thoáng qua, rùi ta sẽ quay lại sau nói rõ ràng hơn ở những bài sau cũng nằm trong loạt bài này. (tới lúc đó rất mong các “cao thủ” ra tay trợ giúp ...)
1.Một cái nhìn khái quát về việc lập trình và các loại ngôn ngữ lập trình:
Thật ra mà nói thì snow cũng không rành về các loại ngôn ngữ lập trình nhiều lắm cho mấy. Nhưng đã từng là 1 người phải dọ dẫm tập đi (và hiện nay vẫn còn tiếp tục...dọ dẫm tiếp...), nên snow biết vào lúc ban đầu những người học lập trình luôn thắc mắc về việc nên chọn loại ngôn ngữ lập trình nào, và các loại ngôn ngữ thì thật sự có bản chất ra sao và 1 chương trình được lập trình bằng 1 ngôn ngữ lập trình như thế nào (toàn là những vấn đề to tát, tối thui và rối nùi để có thể hiểu dễ dàng...). Và câu hỏi lớn nhất luôn luôn tồn tại là: “Lập trình thật ra là làm cái gì ở trỏng???”
Và ở trên forum này của HVA lâu lâu snow lại bắt gặp các câu hỏi của các bạn còn hơi bị “mới lạ” với lập trình nghe rất “lạ tai” nhưng thật ra nếu đứng từ góc độ của các bạn ấy (những người có thể là chỉ mới nghe nói về lập trình lần đầu) thì ta sẽ không thấy “lạ” nữa: “Lập trình là gì vậy?”, “Ngôn ngữ lập trình có giúp gì cho tui trong việc làm web ko?”, “Nên học loại ngôn ngữ lập trình nào?”... Những ai đã đang và học lập trình, làm những công việc liên quan tới lập trình thoạt nghe có thể phì cười vì những câu hỏi “chất phác” và “ngô nghê” này nhưng chỉ cần 1 thoáng nhớ lại bản thân mình vào “cái thuở ban đầu” thì ta sẽ thấy dễ thông cảm...
Vậy ở đây snow xin được nói những hiểu biết của mình (dù là hơi hạn hẹp) về các loại ngôn ngữ lập trình cũng như công việc lập trình nhằm giúp các bạn phần nào đỡ “thắc mắc” hơn...
a.Thế nào là lập trình?
Nói từ kinh nghiệm của bản thân snow thì hồi trước snow nghĩ về công việc lập trình rất khác (như ở bài trước đã nói qua...). Và ngày nay theo snow nghĩ công việc lập trình đã thay đổi 1 cách sâu sắc so với những giai đoạn đầu. Và hơn nữa ngày nay bản chất của lập trình đã len lỏi vào rất sâu rộng trong cuộc sống, và phát triển thành rất nhiều loại, nhiều kiểu lập trình khác nhau tùy theo mục đích...
Chẳng hạn thắc mắc như của HVTF đã được squallanh giải thích ở trên. Thật ra thì LVH quote câu nói của squallanh cũng đúng, có điều ý của squallanh nói ở đây “programmer” nghĩa là những người lập trình viên thiên về ứng dụng (những lập trình viên này ít gặp cá vấn đề đòi hỏi tới AI - Trí Tuệ Nhân Tạo...). Còn AI vốn dành cho các lập trình viên thiên về nghiên cứu...
Bạn có thể hiểu, nếu như ngày xưa công việc lập trình xuất hiện chỉ nhằm để: “Làm sao cho cái cục sắt toàn dây điện và bóng đèn lab này chịu chạy và chịu tính toán là hay rùi!!!”. Nghĩa là ngày xưa mục tiêu đưa ra cho việc lập trình bị giới hạn trong 1 số lượng nhu cầu rất ít và nhắm vào 1 số công việc chủ yếu đòi hỏi việc tính toán, tạo ra những hệ điều hành đơn giản để vận hành được máy tính...vv... và thời gian đó lập trình vốn là công việc của giới “chuyên gia” và nghiên cứu toán học. Và cũng do việc phát triển các ngôn ngữ lập trình và các công cụ lập trình vào thời đó cón rất ít và ít ứng dụng rộng rãi trong cuộc sống nên lập trình ít gặp trong cuộc sống. Nhưng vào ngày nay khi các ngôn ngữ và các công cụ lập trình đã được phát triển, các nhu cầu, các mục tiêu lập trình khác nhau đã được phát triển thì lập trình đã len lỏi vào khắp mọi ngõ ngách trong cuộc sống và ai thì cũng có thể lập trình cho những thứ gì đó mà mình cần thông qua những công cụ phù hợp nào đó ứng với nhu cầu mình cần.
Chẳng hạn như 1 người làm văn phòng đã sử dụng Ms Excel để lập bảng tính lương, in ra kết quả lương của các nhân viên thì thật ra trong quá trình đó cô ấy đã ít nhiều có “đụng” tới lập trình rùi đó (thông quá các hàm để tính toán...).
Hơn nữa ngày nay lập trình không chỉ đơn giản là ở trong ngành phần mềm hay lập trình hệ thống nữa, nói chung bạn có thể gặp lập trình trong những lĩnh vực sau:
+Hệ thống: bao gồm thiết lập giao thức để các phần cứng chịu làm việc với nhau, giao thức để con người và máy tính làm việc với nhau, phân phối các tiến trình làm việc trong máy tính, nhận biết phần cứng (các driver cho phần cứng...), thiết lập hệ thống mạng, điều khiển việc truy cập giữa các tài nguyên trên mạng, điều khiển các thiết bị mạng
+Tri thức: Giúp máy tính có thể “suy nghĩ” thay cho con người trong một số vấn đề quá thiên về tính toán, hoặc những chương trình chuyên sâu giải quyết về một số lĩnh vực đặc biệt nào đó (expert system), trả lời câu hỏi thông qua 1 số thông tin được nhập về 1 tình huống nào đó...
+Ứng dụng: Bao gồm rất nhiều mặt, không chỉ đơn giản là phần mềm, mà còn bao gồm cả lập trình web, thiết lập ra những chương trình hoặc những ứng dụng cần thiết trong cuộc sống, giải trí...
+Hệ thống thông tin: Bao gồm việc thiết lập, xây dựng cơ sở dữ liệu, xây dựng 1 kho thông tin có sẵn để khi cần thì máy tính hoặc user có thể “lấy” được...
.......(còn nhiều nhiều nữa, nhưng có thể là snow ko biết hết...)
Và bạn đừng nhầm lẫn cho rằng những lĩnh vực lập trình trên hổng có “dính dáng” gì tới nhau (hông dám đâu, “đụng đầu” nhau côm cốp luôn đó...). Ví dụ như bạn viết một ứng dụng giúp user có thể nhập các yêu cầu tìm kiếm rùi máy tính sẽ trả ra kết quả (chẳng hạn như 1 từ điển điện tử) thì khi đó ứng dụng của bạn sẽ lại phải làm việc trên 1 cơ sở dữ liệu nào đó (như vậy là kết hợp hệ thống thông tin và ứng dụng...).
Như vậy nói chung là bạn có thể thấy lập trình ngày nay đã “vươn vòi bạch tuộc” tới rất nhiều ngóc ngách trong cuộc sống, và 1 lúc nào đó bạn có nhu cầu “làm cái gì đó” để cho máy tính nhận những thiết lập nào đó từ bạn để đáp ứng yêu cầu nào đó của bạn thì tức là bạn đang lập trình rùi đó...
b.Tổng quan về các loại ngôn ngữ lập trình:
Như snow từng nói, vào “thuở ban đầu lưu luyến ấy” thì lựa chọn duy nhất để con người làm cho máy tính chạy là “chịu khó” ngồi đó rùi mã hoá từng bit 0,1 đưa vào máy tính nhằm giúp nó chạy. Họ làm được điều này dựa trên những sơ đồ luận lúy logic mà họ đã thiết lập cho máy tính. Bạn nên hiểu thật ra máy tính có cách “suy nghĩ” khác với bạn là do đối với nó thì mọi chuyện cuối cùng đều chỉ được về đúng (1) hoặc sai (0) để giải quyết (bao gồm cả tính toán trên các con số). Chứ máy tính ko thể nào có cái kiểu suy nghĩ phức tạp tới nỗi “nói không là có, nói có là không” hoặc xử lí thông tin dựa trên nhiều loại “tín hiệu” như con người.
+Người đầu tiên lập trình trên máy tính kiểu 0,1 này là 1 người phụ nữ tên là EVA (í! Xí lộn, tên là ADA...) “nghe đồn” là một nữ toán học, vào năm “nào đó” (“nào đó” vì hổng nhớ rõ là năm nào) đã đưa cho chiếc máy tính đầu tiên (to cỡ 1 cái nhà kho)1 “cuộn giấy” đã được đục lỗ để nó đọc và hiểu được những gì nó cần làm...
+Đương nhiên là “nói chuyện” với máy cái kiểu này thì hơi “mệt” thật (bạn thử nói chuyện với ai đó mà chỉ toàn dùng “đúng” hoặc “sai” xem...). Nên sau đó người ta tạo ra 1 loại ngôn ngữ lập trình cấp thấp tên là Assembly. Assembly giúp cho con người nói chuyện “dễ thở” với máy tính hơn 1 chút bằng việc cho phép con người dùng 1 số lệnh (là những từ tiếng Anh đơn giản, vắn tắt), các toán tử, 1 số cấu trúc lặp, di chuyển trên vùng ghi mã chương trình trong bộ nhớ để thực thi. (“nghe đồn” ngôn ngữ này làm việc trực tiếp với các thanh ghi và bộ nhớ rất nhiều, bạn phải nắm rỏ mô hình stack của bộ nhớ...).
+Mặc dù “dễ thở” hơn nhưng Assembly vẫn còn rất “chua chát” với các lập trình viên (nhất là những người mới học lập trình. Vụ này snow cũng chỉ mới “nghe đồn” vì chưa học qua Assembly nhưng học kì tới này định đăng kí học phần này, hi vọng là sẽ không đến nỗi “địa ngục” như người ta nói...). Nên sau đó người ta đưa ra một thế hệ ngôn ngữ lập trình mới, đó là ngôn ngữ lập trình bậc trung. Loại ngôn ngữ này cung cấp cho bạn 1 số kiểu dữ liệu cơ bản (số nguyên, số thực, kí tự, chuỗi kí tự), các kiểu dữ liệu tự định nghĩa, các cấu trúc lặp, cấu trúc điều kiện, đệ qui... Việc này đã giúp lập trình viên dễ thở hơn rất nhiều. Bởi vì nếu như trong Assembly bạn phải làm việc với các ô nhớ trong mô hình stack của bộ nhớ thông qua các thanh ghi, phải tự thiết lập và quản lí việc lặp thông qua lệnh JUMP nhảy trên bộ nhớ...vv... và khi có lỗi thì việc dò tìm là rất dễ “nổi khùng”. Thì giờ đây với ngôn ngữ bậc trung bạn sẽ được giải thoát khỏi những công việc “nhàm chán” và “khô khan” đó. Việc cung cấp 1 số kiểu dữ liệu cơ bản cũng giúp cho bạn làm việc và tính toán dễ dàng hơn, trong khi các kiểu dữ liệu tự định nghĩa giúp bạn có thể tạo ra các kiểu dữ liệu gần với nhu cầu thực tế hơn. Các cấu trúc lặp đã có hẳn cú pháp và mô hình chuẩn cũng giúp bạn nhiều hơn. Các cấu trúc điều kiện và rẽ nhánh được cung cấp... Nói chung, ngôn ngữ lập trình bậc trung giúp cho việc lập trình được trừu tượng hoá hơn, chương trình dễ đọc hơn...
+Sau đó với nhu cầu ngày càng tăng, dẫn tới sự ra đời của ngôn ngữ bậc cao. Trong ngôn ngữ bậc cao đã có thêm 1 số kiểu dữ liệu định sẵn và mang tính định kiểu rất mạnh và là 1 ngôn ngữ có cấu trúc (1 ví dụ nổi tiếng của loại ngôn ngữ này là Pascal). Trong loại ngôn ngữ này, các kiểu dữ liệu được phân định và quản lí rất chặt chẽ tạo ra sự an toàn về mặt dữ liệu. Cú pháp có cấu trúc và đòi hỏi sự tuân thủ nghiêm túc cấu trúc giúp cho việc xây dựng chương trình trên loại ngôn ngữ này trở nên “trong sáng, dễ đọc” đối với lập trình viên và giúp ít phạm sai sót hơn và việc debug tìm lỗi lập trình dễ dàng hơn... Nhưng cũng chính vì tính quá chặt chẽ của mình mà các loại ngôn ngữ bậc cao khiến cho 1 số “quyền năng” của lập trình viên bị hạn chế và lập trình viên sẽ ko còn được “tự do, tự tung tự tác” như trước đây nữa (có đôi khi việc tự do là cần thiết...). Cũng như việc chạm vào hệ thống trong loại ngôn ngữ này trở nên khó khăn hơn...
Nhưng cũng không loại trừ một số loại ngôn ngữ mang cả 2 tính chất “tự do, mềm dẻo”của ngôn ngữ bậc trung, lại vừa mang tính có cấu trúc và kiểm soát chặt chẽ của ngôn ngữ bậc cao (C/C++ là một ví dụ cho kiểu ngôn ngữ “lai” này).
Trong giai đoạn phát triển ngôn ngữ bậc cao này đã xuất hiện thêm 1 khái niệm lập trình mới mẻ, đó là lập trình hướng đối tượng (OOP), snow đã trình bày sơ lược về khái niệm lập trình này ở bài trước, và ngay lập tức khái niệm lập trình này được “tích hợp” vào 1 số ngôn ngữ lập trình bậc cao như C/C++, Pascal, JAVA...
+Hiện nay đã phát triển thêm 1 thế hệ ngôn ngữ mới, đó là thế hệ ngôn ngữ thứ tư. Trong thế hệ ngôn ngữ này đã có sự “phân luồng” rõ rệt. Mỗi một ngôn ngữ thuộc thế hệ thứ tư được tạo ra là nhằm đi sâu vào phục vụ 1 mục đích lập trình cụ thể. Nó sẽ có sẵn những kiểu dữ liệu, những hàm, những khái niệm cơ bản hoặc sâu sa để giúp cho lập trình viên làm ít công việc hơn, chỉ cần quan tâm đến dữ liệu nhập và các thành phần cần thiết. Cũng như làm việc trên những cơ sở đã được xây dựng sẵn. Thường thì theo snow biết các hệ ngôn ngữ này có “tích hợp” sẵn 1 mô hình cơ sở dữ liệu nào đó... Một vài ví dụ cho thế hệ ngôn ngữ này là SQL (Structure Query Language) phục vụ cho việc xây dựng và truy cập cơ sở dữ liệu theo kiểu sử dụng các câu truy vấn (query) và ứng dụng mô hình cơ sở dữ liệu quan hệ. Một ví dụ khác là ngôn ngữ lập trình PROLOG của lĩnh vực Tri Thức. Theo snow biết ngôn ngữ này được xây dựng dựa trên Logic hơp giải và giúp cho lập trình viên làm việc dễ dàng với các vấn đề trí tuệ nhân tạo liên quan tới logic hoá...
+Ngoài ra những loại ngôn ngữ snow đề cập ở trên vốn chỉ liên quan tới phần mềm trong khi hiện nay còn có sự tồn tại và phát triển của các ngôn ngữ liên quan tới mạng máy tính, web như HTML, PHP, ASP (hix hix, cái này thú thật là snow chưa tìm hiểu... nếu có “cao thủ” nào biết thì xin bổ sung vào để cho các bạn có nhu cầu có cái nhìn khái quá về chúng...).
Như đã nói từ bài trước, bài này snow sẽ nói về các kiểu dữ liệu, các cấu trúc dữ liệu cơ bản...
Chắc các bạn còn nhớ, từ bài đầu tiên snow đã đem cái “slogan” này của Niklaus Wirth ra “che đạn” cho mình:
Data structures + Algorithms = Programs (Cấu trúc dữ liệu + Giải thuật = Chương trình)
Đây là 1 câu nói nổi tiếng vì nó rất ngắn gọn nhưng đã nói lên tất cả bản chất của việc lập trình. Về mặt nào đó bạn có thể tưởng tượng chương trình của bạn sau khi được lập trình xong, được biên dịch thành chương trình thực thi rùi thì khi đó đối với người sử dụng (users) “nó” sẽ chẳng khác gì 1 cái “hộp đen” cả. Tất cả những gì users có thể làm với chương trình mà bạn viết ra là “quăng” cho nó vài dữ liệu, chọn vài tùy chọn (mà bạn cho phép họ chọn), hoặc được phép nhập cho nó vài hàm “linh tinh” với các đối số nào đó (đương nhiên việc này còn tùy việc bạn có “cho phép” hay ko???). Và sau đó cái mà cái “hộp đen” đó trả ra cho users cũng chỉ là dữ liệu, nhớ nhé, chỉ dữ liệu mà thôi. Và còn cái dzụ “nó” làm việc như thế nào thì đối với họ sẽ là cả 1 “bí ẩn” (trừ khi bạn “thành thật” cho họ biết nó làm việc như thế nào mà thôi... Cảm thấy “đã” chưa nào???).
Nó (“hộp đen”-chương trình) làm sao mà hay dzạ??? Vì bên trong nó có chứa những giải thuật do bạn thiết lập, những giải thuật này lại làm việc trên các dữ liệu, chỉ đơn giản là thế...
Như vậy 2 thứ cơ bản cấu thành nên 1 chương trình máy tính chỉ là dữ liệu và giải thuật mà thôi. Nhưng bạn đừng có nhầm lẫn mà “tưởng bở” nha, chỉ có 2 nhưng bàn về 2 thứ này 1 hồi là bạn sẽ nổ đom đóm mắt và quay mòng mòng đó (hi hi, “hù con nít” chút chơi.....).
Bây giờ snow sẽ cho bạn thấy sự “hay ho” của cấu trúc dữ liệu đối với 1 chương trình máy tính.
1.Khái quát về kiểu dữ liệu và cấu trúc dữ liệu trong lập trình:
a.Một chút xíu về kiểu dữ liệu trong kiến trúc máy tính:
Nếu để ý thì chắc bạn còn nhớ ở bài trước snow có nói tất cả những gì máy tính hiểu chỉ là 2 con số: đúng (1), sai (0). Vậy chắc bạn sẽ thắc mắc: “Vậy tại ra làm sao mà tui nhập cho nó 1 con số tiền tỉ nó vẫn tính được mà đâu có sai đâu??? Nó mà sai thì chắc... hix hix... tui sạt nghiệp luôn quá...”. Vâng, hồi đầu khi mới học về máy tính đây thực sự cũng là 1 câu hỏi lớn đối với snow (Thậm chí bạn tin ko??? Có lần snow nằm mơ thấy mình đi hỏi cái PC của mình chuyện này luôn đó...).
Thật ra trên cơ bản mà nói 1 con số bạn nhập vào là 100.000 chẳng hạn thì đối với bạn nó là 100 ngàn, nhưng snow đảm bảo với bạn máy tính sẽ chẳng có “ấn tượng” gì lắm với con số đó của bạn ngoài 1 dãy số nhị phân 0,1 liên tiếp được chứa trong 1 ô nhớ có số byte ứng với kiểu dữ liệu mà bạn đã chọn dùng để chứa con số đó.
“Vậy tại sao nó vẫn tính toán được và vẫn trả ra con số thập phân đúng như vậy???”.
Ở đây có 1 thứ “chen ngang” giữa bạn và máy tính. Có 1 thứ giúp bạn nói “tiếng người”, máy nói “tiếng máy” nhưng máy vẫn hiểu người và người vẫn hiểu máy. Đó là vì các hệ máy tính vốn đã được định nghĩa những cách biểu diễn dữ liệu và 1 số kiểu dữ liệu cơ sở. Ngoài ra còn phải nói tới kích thước “từ” của máy tính và kích thước của các thanh ghi trong bộ xử lí. (nói thoáng qua thôi nghen, chứ nói rõ về mấy thứ này không chừng mình bị “lạnh” như mấy cái máy tính luôn đó).
Đại khái thì bạn cứ hiểu như vầy, dữ liệu của bạn được biểu diễn trên máy chỉ là 0,1 nhưng theo những qui tắc nhất định nào đó của từng kiểu dữ liệu (số nguyên, phân số, số chấm động...) và mỗi kiểu dữ liệu sẽ được thiết kế riêng cho nó những mạch tính toán (thật ra là 1 loạt những cổng logic đại diện cho các phép logic, phép dịch bit, phép nhớ...) để cho các mạch tính toán đó có thể “đối xử” với các kiểu dữ liệu đó vốn đã bị mã hoá sang 0,1 nhưng khi kết quả được mã hoá ngược lại ra kiểu cho bạn đọc thì nó vẫn là kết quả đúng (có 1 loại mạch giải mã chuyên dụng cho việc dịch này...).
Và bạn nên nhớ kiểu dữ liệu càng phức tạp thì đòi hỏi việc biểu diễn nó trong máy tính càng phức tạp, cũng như các mạch tính toán và mạch giải mã của nó cũng sẽ rất phức tạp==>chậm, vì vậy sẽ ảnh hưởng tới tốc độ tính toán chung, cũng như bộ nhớ... Vd: kiểu nguyên đơn giản hơn kiểu chấm động (số thực)===> tính toán và làm việc trên số nguyên sẽ nhanh hơn chấm động.
Ngay cả giữa các phép toán của cùng 1 kiểu dữ liệu cũng có sự ảnh hưởng lớn. Ví dụ: như mạch nhân thì phức tạp và có nhiều qui trình hơn mạch cộng ===> phép nhân sẽ được thực hiện chậm hơn phép cộng.
Thôi, ta chấm dứt nói về kiến trúc máy tính ở đây nha, nhưng bạn cần nhớ đặc điểm về sự “nhanh-chậm” ở trên, sau này sẽ có thể cần nhắc lại đấy... (Chứ nhắc nhiều về kiến trúc snow ko khoái lắm, nhớ lúc trước cả lớp chín mươi mấy người thi mà có chưa tới hai chục người đậu, may mà snow cũng đậu nhưng cũng chỉ có 5 điểm là hết muốn nhớ tới kiến trúc, còn thêm cái “tên kia” ỷ 7 điểm nghênh nghênh đi qua đi lại trước mắt là muốn “đạp” dzô bàn chân hắn 1 phát rùi...).
b. Cơ bản về các kiểu dữ liệu và cấu trúc dữ liệu trong ngôn ngữ lập trình:
Trong các loại ngôn ngữ lập trình, như snow đã nói trong bài trước chúng ta đã được cung cấp 1 số kiểu dữ liệu cơ bản và các kiểu dữ liệu để cho chúng ta tự định nghĩa.
Ngay từ đầu bạn nên hiểu 1 điều, việc nắm vững các kiểu dữ liệu sẽ có tính chất “sống còn” với bạn trong lập trình. Đơn giản là vì bạn lập trình thì mục đích cuối cùng cũng chỉ nhằm đưa “thực tế” vào trong máy tính và nhờ máy tính trả lại kết quả cho mình. Vấn đề là “thực tế” thì muôn hình vạn trạng, kiểu dữ liệu cơ bản thì cũng chỉ có vài cái, vậy thì làm sao biểu diễn “thực tế” vào máy tính tốt được, vậy thì điều này đòi hỏi rất nhiều ở tài “chế biến” của bạn. (cho tới giờ snow vẫn còn phải học hỏi rất nhiều, và thường xuyên bị ngạc nhiên trước nhiều kiểu dữ liệu quá hay trong các thuật toán mình được học...).
Và bạn nên hiểu giải thuật nào thì cũng chỉ làm việc trên dữ liệu, như vậy thì tùy theo dữ liệu bạn chọn có “hay ho” hay không thì giải thuật của bạn mới có thể “hay ho” được... tức tốc độ, hiệu quả sử dụng tài nguyên máy tính...vv... của giải thuật chịu ảnh hưởng rất nhiều của kiểu dữ liệu mà nó làm việc.
b.1 Các kiểu dữ liệu cơ bản:
Thường thì tùy theo loại ngôn ngữ mà bạn sử dụng thì số kiểu dữ liệu cơ bản cung cấp sẵn sẽ nhiều hay ít. Nhưng chủ yếu vẫn chỉ là những kiểu dữ liệu về số, kí tự và luận lí(logic). Ngoài ra người ta còn phân loại theo kiểu có cấu trúc hay không có cấu trúc:
b.1.1.Các kiểu dữ liệu số bao gồm:
+số nguyên
+số thực
...
Trong các kiểu số này thì mỗi kiểu lại có nhiều kiểu khác nhau chủ yếu các “kiểu con” này chỉ khác nhau về việc có dấu hay không hoặc kích thước của chúng.
VD: trong C ta có các kiểu biến sau đều đề cập tới kiểu nguyên
int; (2 byte, có dấu)
unsign int; (2 byte, không dấu)
long(4 byte, có dấu)
unsign long(4 byte, không dấu)
b.1.2.Các kiểu kí tự:
kí tự đơn:
char (1 byte),
chuỗi kí tự:
string (gồm 1 mảng liên tiếp các kiểu char, thường thì một chuỗi kí tự sẽ được kết thúc bằng 1 kí tự đặc biệt nào đó cho máy tính nhận biết)
Ngoài ra với việc phát triển của unicode hiện nay, theo snow biết còn có kiểu char 2 byte.
b.1.3.Kiểu logic:
Thường chỉ có 1 byte, và thường thì chỉ có 2 loại giá trị TRUE (1), FALSE (0). Nhưng cũng có 1 số loại ngôn ngữ không có sẵn kiểu dữ liệu Logic chuyên biệt, nhưng bạn vẫn có thể thay thế nó bằng kiểu nguyên hay kiểu char (C/C++ là 1 ví dụ).
b.1.4.Ngoài ra ta còn nói tới kiểu có cấu trúc:
kiểu chuỗi kí tự (string) đã nói ở trên cũng có thể coi là 1 kiểu có cấu trúc đơn giản.
Ngoài ra ta còn có:
+kiểu mảng: là 1 tập hợp các ô nhớ chứa cùng 1 kiểu dữ liệu nằm liên tiếp nhau trên bộ nhớ và được truy cập tới từng thành phần nhờ vào tính toán từ vị trí của ô nhớ đầu tiên
trong kiểu mảng này còn chia ra loại mảng 1 chiều và 2 chiều... bạn có thể hiểu mảng 1 chiều là 1 dãy các biến thuộc 1 kiểu dữ liệu, còn mảng 2 chiều thì giống như 1 mô hình bảng.
VD:
mảng 1 chiều có dạng như sau:
a[0] a[1] a[2] a[3] a[4]
mảng 2 chiều:
a[0][0] a[0][1] a[0][2]
a[1][0] a[1][1] a[1][2]
a[2][0] a[2][1] a[2][2]
+kiểu dữ liệu tự định nghĩa có cấu trúc:
Đây là 1 trong những kiểu dữ liệu quan trọng giúp bạn rất nhiều trong việc đưa “thực tế” vào máy tính. Thực chất mà nói kiểu dữ liệu tự định nghĩa chỉ là 1 tập hợp bao gồm 1 vài thành phần được chọn từ các kiểu dữ liệu đã có sẵn theo 1 cấu trúc do bạn chọn. Mặc dù đơn giản như vậy nhưng nó cũng đã giúp bạn rất nhiều.
VD: yêu cầu của bạn là viết 1 chương trình quản lí các nhân viên của 1 công ty. Như vậy cái bạn cần ở đây là 1 kiểu dữ liệu có thể lưu được các thông tin cá nhân của 1 nhân viên thuộc rất nhiều kiểu khác nhau như: Tên (string), địa chỉ (string), số điện thoại (mảng số)...
Ta sẽ biểu diễn kiểu này trong C như sau:
struct NhanVien
{
char Ten[255];
char DiaChi[255];
int DienThoai[7];
};
(các con số nằm giữa 2 dấu [ ] là cho biết mảng của bạn có bao nhiêu phần tử và trong C thì kiểu string được coi là 1 mảng 1 chiều của kiểu char...)
Ở đây vì chỉ là khái quát nên snow sẽ không đi vào nói sâu, nhưng trong thực tế khi lập trình bạn phải cân nhắc việc nên sử dụng kiểu dữ liệu nào cho hợp lí và hiệu quả về mặt tài nguyên cũng như tính toán. Giống như snow đã nói ở phần số 1 tuỳ theo kiểu bạn chọn là đơn giản hay phức tạp đối với máy mà tốc độ thực hiện các phép tính trên kiểu đó sẽ nhanh hay chậm...).
Và bạn nên nhớ, khi bạn chọn 1 kiểu dữ liệu nào đó thì không chỉ đơn giản là bạn chọn cách lưu trữ giá trị mà là bạn đã chọn luôn tập các phép toán cho phép làm việc trên kiểu dữ liệu đó...
b.2 Các kiểu dữ liệu “đặc biệt”:
Ngoài ra khi phát triển lên các thế hệ ngôn ngữ lập trình cấp cao hơn, ta còn có những kiểu dữ liệu rất đặc biệt.
+Chẳng hạn như các kiểu dữ liệu được xây dựng theo kiểu phân lớp trong hướng đối tượng (OOP). Khi đó các kiểu dữ liệu không chỉ chứa trong nó dữ liệu đơn thuần mà còn chứa cả các hành vi, thậm chí có những kiểu lớp không hề chứa thành phần dữ liệu nào mà chỉ chứa các hàm hành vi...
+ Ở thế hệ ngôn ngữ thứ tư thì đối với mỗi loại ngôn ngữ ngoài các kiểu cơ bản còn có sẵn các kiểu đặc trưng cho công việc dành riêng cho loại ngôn ngữ đó.
VD: SQL có kiểu dữ liệu bảng thật ra chính là các quan hệ trong mô hình cơ sở dữ liệu quan hệ...
Trong bài này snow sẽ trình bày những khái niệm cơ bản về giải thuật, sự liên quan giữa CTDL và giải thuật...
1.Giải thuật là gì?
1 cách cơ bản, có thể coi giải thuật là 1 tập các thủ tục, hàm, cấu trúc điều khiển theo 1 trình tự thực hiện nào đó nhằm thực hiện bài toán được đặt ra cho chương trình.
Người ta thường chia ra 2 loại giải thuật cơ bản:
+Giải thuật xác định: là các loại giải thuật được áp dụng cho những vấn đề mà lời giải có thể biểu diễn được dưới dạng toán học 1 cách rõ ràng. Trong loại giải thuật này các bước để thực hiện, số lần lặp... đã được xác định trước và rất dễ dàng để tính toán chi phí phải bỏ ra cho nó. Và thường thì loại giải thuật này ít khi có chứa cấu trúc điều khiển rẽ nhánh.
Vd: Vẽ 100 điểm ngẫu nhiên trên màn hình.
+Giải thuật không xác định: loại giải thuật này áp dụng cho những vấn đề mà lời giải chưa có sẵn mà được lựa chọn qua 1 số lần chọn lựa những khả năng có thể nào đó ở những bước nào đó.
Vd: Cho 1 hình chữ nhật cụ thể. Vẽ các điểm có giá trị tọa độ x,y được phát sinh ngẫu nhiên cho tới khi điểm ngẫu nhiên nằm ngoài hình chữ nhật thì dừng.
+Chắc bạn cũng thấy thì trong thực tế, các vấn đề thường nằm dưới dạng bài toán không xác định là chính.
+Ngoài ra còn 1 loại giải thuật heuristic: nói 1 cách dễ hiểu thì đây là 1 loại giải thuật mang tính “may mắn” rất nhiều. Loại thuật toán này dựa trên 1 thứ “cảm tính” (được trừu tượng hoá thành 1 hàm đánh giá heuristic) nào đó của con người trong việc giải quyết vấn đề. Bạn cảm thấy giải quyết bài toán theo hướng nào là tốt hơn thì đi theo hướng đó. Và nếu “cảm tính” của bạn sai thì bài toán có thể trở thành dài hoặc đi vào lối cụt. Nhưng nếu “cảm tính” của bạn đúng thì bài toán có thể được giải quyết rất nhanh.
Vd: Cho 1 tập các trạm điện thoại và khoảng các giữa các trạm đã được xác định. Hãy tìm 1 cách nối dây để các trạm được nối với nhau và tốn ít dây nhất. Thì có 1 loại heuristic theo nguyên lí “tham lam” là: chọn ra trong các trạm chưa nối, dây trạm có khoảng cách ngắn nhất tới trạm đang xét. (Thật ra thuật toán này có thể thực hiện được 1 cách tối ưu bằng cách “vét cạn” tất cả các đường dây có thể tạo ra rồi chọn đường ngắn nhất, nhưng trong trường hợp số trạm là quá nhiều thì giải thuật này sẽ không hiệu quả do tốn quá nhiều thời gian, chi phí tính toán, chi phí lưu giữ kết quả...)
2. Mối liên hệ giữa giải thuật và cấu trúc dữ liệu:
Như câu “slogan” của Niklaus Wirth mà snow đã nhắc tới, 2 thứ để cấu thành chương trình là Cấu trúc đữ liệu + Giải thuật. Và giải thuật thì hoạt động dựa trên cấu trúc dữ liệu. Như vậy sẽ có 1 sự ảnh hưởng qua lại giữa CTDL mà bạn chọn lựa và thuật toán.
Nếu ngay từ đầu bạn chọn 1 CTDL “ngon lành”, thích hợp thì việc viết giải thuật sẽ rất đơn giản và tốc độ của giải thuật cũng nhanh hơn. Còn nếu bạn chọn lựa 1 CTDL không tốt thì giải thuật của bạn sẽ có thể rất rườm rà và rắc rối, ảnh hưởng tới tốc độ.
+Cho nên yêu cầu của 1 CTDL trong giải thuật là phải đơn giản, tiết kiệm tài nguyên hệ thống nhưng đầy đủ và biểu diễn được bài toán. Đồng thời những toán tử, những hàm xử lí trên dữ liệu đó phải đảm bảo đơn giản và được thực hiện nhanh chóng. Để làm được điều này đòi hỏi ở người lập trình viên những bước phân tích lúc ban đầu rất quan trọng. Bạn phải hiểu rõ những yêu cầu của đề bài, phải thấy rõ bản chất, cũng như phải biết cách thu gọn, đơn giản hoá bài toán. Cũng như bạn phải biết rõ những thao tác nào sẽ thường xuyên được thực hiện trên CTDL về sau, đây là 1 yêu cầu rất quan trọng để bạn có thể cân nhắc CTDL cho hợp lí. (Điểm này thì thút thật là snow còn phải học hỏi dài dài...)
Ví dụ: 1 ví dụ đơn giản là bài toán 8 con hậu. Cho 1 bàn cờ vua 8x8. Hãy liệt kê ra tất cả các cách đặt 8 con hậu trên bàn cờ sao cho trên mỗi hàng hoặc mỗi cột của bàn cờ chỉ có duy nhất 1 con hậu mà thôi.
Phân tích đề bài thì bạn thấy vì bài toán yêu cầu liệt kê tất cả nên chắc chắn nó sẽ được giải bằng phương pháp “vét cạn”. Vấn đề còn lại là bạn cần lưu lại kết quả của những lần “vét cạn” như thế nào.
Ở đây đơn giản nhất ta sẽ nghĩ ngay tới 1 mô hình mô phỏng rất tốt bàn cờ đó là 1 mảng 2 chiều 8x8. Các ô trống ko đặt quân cờ sẽ được đặt giá trị là False (0). Các ô có đặt quân cờ sẽ được đặt giá trị là True (1).
Nhưng vấn đề là, như vậy mỗi một trường hợp tìm được bạn lại phải lưu nó bằng 1 mảng 2 chiều 8x8 là rất tốn bộ nhớ, thứ 2 là việc duyệt trên 1 mảng 2 chiều sẽ khiến cho thuật giải của bạn trong mỗi lần duyệt kiểm tra sẽ phải tốn chi phí (n*n) làm ảnh hưởng tới tốc độ của bài toán.
Vậy bạn sẽ phải tìm ra 1 CTDL tốt hơn là mảng 2 chiều đề biểu diễn bài toán này. Nhìn đi nhìn lại tự nhiên bạn thấy “người anh em” của mảng 2 chiều là mảng 1 chiều sao mà “dễ sương” quá à... Vậy là bạn sẽ bắt đầu nghĩ xa hơn 1 chút với mảng 1 chiều và bạn sẽ tìm được 1 cách biểu diển tiết kiệm hơn nhiều.
Đó là bạn chỉ cần 1 mảng 1 chiều 8 phần tử. Mỗi phần tử của mảng được coi là biểu diễn toạ độ của lần lượt 8 con cờ trên bàn cờ theo qui ước sau: chỉ số của phần tử a[i] sẽ biểu diễn cho toạ độ hàng. Giá trị lưu trong mổi một phần tử sẽ biểu diễn cho toạ độ cột của các con hậu.
a[3]=5 <=== con hậu trên dòng thứ 3 được đặt trên cột thứ 5.
Như vậy việc lưu giữ kết quả sẽ được tiết kiệm tài nguyên bộ nhớ hơn và việc duyệt kiểm tra cũng nhanh hơn do chỉ duyệt trên 1 mảng 1 chiều 8 phần tử mà thôi.
+Ngoài ra như snow đã nói ở bài trên các kiểu dữ liệu càng phức tạp thì các toán tử làm việc trên nó sẽ phức tạp và chậm hơn.
Vd: khi làm việc với các con số bạn phải hạn chế việc sử dụng kiểu số thực (float) nếu không cần thiết thì bạn nên thay nó bằng kiểu nguyên (integer) nếu có thể...
Vd: 1 ví dụ khác cho việc chọn kiểu dữ liệu. Chẳng hạn bạn cần xây dựng 1 chương trình quản lí các nhân viên cho 1 công ty nào đó. Các nhân viên có thông tin Tên, Số điện thoại, địa chỉ.
Nếu bạn chỉ dừng ở đây mà không biết cách tự phát triển tiếp, bạn sẽ ngay lập tức tạo ra 1 cấu trúc như sau (trong C):
Code:
struct NhanVien
{
char Ten[255];
char DiaChi[255];
int DT[7]; /* thật ra là có hơi “hoang” như nad đã nói vì int tới 2 byte trong 1 mỗi một số trong số điện thoại chỉ có từ 0 -> 9 tức chưa vượt quá 1 byte. Vậy ta có thể chọn kiểu là char (trong C char còn có thể coi là 1 kiểu số nguyên 1 byte) */
};
Nhưng sau đó khi bước vào xây dựng các hàm, các chương trình làm việc trực tiếp với CTDL này bạn sẽ thấy ngay ra 1 vấn đề khó khăn. Bạn sẽ thấy thao tác thường xuyên thực hiện trên CTDL NhanVien nhất là tìm kiếm. Nhưng khi tìm kiếm 1 nhân viên bạn sẽ dựa trên khoá là gì?
Nếu theo như struct mà bạn tạo ở trên thì khoá đó sẽ là Ten. Nhưng bạn cần hiểu 1 điều là Ten vốn có kiểu là chuỗi kí tự string (trong C string được coi là mảng 1 chiều của kiểu kí tự char). Mọi thao tác trên chuỗi kí tự luôn đòi hỏi 1 sự phức tạp và tốn kém. Bao gồm việc so sánh các kí tự, độ dài chuỗi, kết thúc chuỗi, các trường hơp upper case và lower case (kí tự viết hoa hoặc thường, thường thì bạn phải chuyển tất cả kí tự trong 2 chuỗi về cùng là upper case hoặc lowercase trước khi xét)... nói chung sẽ ảnh hưởng rất nhiều đến tốc độ và tên càng dài thì càng chậm (do tên không có kích thước cố định trước...).
Cũng có vài cải tiến nho nhỏ trong các hàm có thể giúp cho việc tìm kiếm nhanh hơn. Chẳng hạn như đầu tiên bạn so sánh chiều dài 2 chuỗi tên, nếu thấy ko dài bằng nhau thì bỏ qua không cần so sánh... Nhưng bản thân hàm kiểm tra độ dài chuỗi cũng đã mất 1 chi phí O(n) do phải duyệt đếm từ đầu đến cuối chuỗi kí tự để tìm kí tự đặc biệt đánh dấu cho việc kết thúc chuỗi (hoặc lấy địa chỉ kí tự đầu, trừ địa chỉ kí tự cuối rồi chia cho kích thước kiểu kí tự). Theo snow biết ngay cả những ngôn ngữ “sừng sỏ” trong việc xử lí chuỗi hiện nay cũng còn phải “sợ” các chuỗi kí tự mặc dù vẫn chạy tốt nhưng vẫn chậm và ảnh hưởng tới tốc độ chung của chương trình (như SQL trong cơ sở dữ liệu, mặc dù có các hàm xử lí chuỗi rất tốt, nhưng 1 lập trình viên tốt trên SQL luôn tránh né chuyện so sánh các chuỗi có độ dài ko xác định nếu có thể...).
Tóm lại là bạn thấy việc dùng Ten làm khoá so sánh là điều bất khả thi và chậm. Như vậy bạn phải nghĩ tới chuyện cải tiến lại CTDL của mình 1 tí và bạn nghĩ là bạn phải “thêm thắt” gì đó vào struct ban đầu để cho nó “hay ho” hơn.
Nếu để ý thì chắc bạn thấy rằng các nhân viên trong 1 công ty ngoài Tên thì thường có thêm 1 thông tin nữa là Mã Số Nhân Viên. Vậy ta có thể có 2 kiểu struct Nhân Viên sau đây (snow sẽ phân tích từng kiểu 1):
Code:
struct NhanVien1
{
char Ten[255];
char MSNV[10];
char DiaChi[255];
int DienThoai[7];
};
hoặc
struct NhanVien2:
{
char Ten[255];
int MSNV;
char DiaChi[255];
int DienThoai[7];
};
Chắc bạn dễ dàng nhận thấy sự khác nhau giữa 2 struct trên là 1 cái có MSNV là kiểu chuỗi, 1 cái là kiểu số nguyên. Bây giờ snow nói cụ thể từng kiểu:
Thấy struct NhanVien1 có MSNV kiểu là string, chắc bạn rủa thầm: “Vớ vẩn quá nha!!! Vậy có khác gì tránh vỏ dưa gặp vỏ dừa đâu, tránh cái Ten kiểu string bằng 1 cái MSNV kiểu string thì có gì khác nhau đâu?”.
Thật ra là có khác nhau đó! Thứ nhất đây là MSNV do bạn tạo ra nên nó phải tuân theo 1 số qui tắc nhập mà bạn buộc cho nó và user buộc phải tuân thủ trong quá trình nhập cũng như tìm kiếm. Các qui tắc đó bao gồm độ dài (mã số gồm bao nhiêu kí tự), tất cả phải là upper case hoặc cùng là lower case, các con số nằm ở vị trí nào, kí tự nằm ở vị trí nào...(khác hẳn với tên vốn không có qui định độ dài, kí tự...)
Ví dụ:
HVA02321
HVA03435
thì các vị trí số và kí tự vốn đã được qui định sẵn như trên.
Với việc đã có qui tắc nhập vào này thì việc kiểm tra, tìm kiếm của bạn sẽ trở nên dễ dàng hơn và không cần 1 số thủ tục như kiểm tra độ dài chuỗi, chuyển đổi về upper case hay lower case trước khi xét... (Kiểu làm này thì bạn có thể thấy rất nhiều trong cơ sở dữ liệu. Ko phải ngẫu nhiên mà trong các Table thường có cột MãSố dùng làm Primary Key hoặc Foreign Key thay cho Tên và các câu truy vấn SQL)
Nhưng thật ra làm như vậy vẫn còn “dính dáng” tới chuỗi kí tự nên snow không khoái lắm. Snow thích kiểu struct NhanVien2 hơn. Bạn cho MSNV là 1 con số nguyên, vậy thì việc so sánh tìm kiếm sẽ trở nên nhanh gọn hơn nhiều. Mỗi lần nhập 1 nhân viên mới thì chương trình sẽ tự tìm 1 con số thích hợp rùi gán cho nhân viên đó. Vấn đề chỉ là bạn phải dự đoán được số nhân viên có thể tăng tới bao nhiêu để chọn ra 1 kiểu dữ liệu đủ lớn cho MSNV.
+Ngoài ra bạn còn phải cân nhắc tới các toán tử làm việc trên dữ liệu (điều này snow đã từng đề cập trước đó). Các toán tử cơ bản do các ngôn ngữ lập trình cung cấp cho bạn vốn có những chi phí thực hiện khác nhau (điều này mang tính chất hệ thống). Nếu chương trình của bạn đòi hỏi có nhiều xử lí và tính toán thì khi sử dụng các toán tử bạn phải cân nhắc sao cho toán tử phải có chi phí “nhẹ” nhàng để tốc độ tính toán nhanh nhất có thể.
Vd:
Code:
x=y*2+1;
bạn nên hiểu là trong kiến trúc máy tính có các mạch shift, nhớ giải mã, đảo bit .... là các mạch cơ bản (snow đã đề cập trước đây rùi). Các mạch khác như mạch cộng và mạch nhân chủ yếu được cấu thành từ tổ hợp các mạch cơ bản này, Tức là mạch nhân phức tạp và tốn nhiều chi phí hơn mạch shift (dịch bit).
Như vậy với ví dụ trên, nếu muốn cho nó nhanh hơn, trong C snow sẽ viết nó lại như sau:
Code:
x=y<<1+1;
y<<1 tức là dịch giá trị chứa trong biến y sang trái 1 bit, điều này tương đương với nhân y cho 2 (bạn xem mô hình số nhị phân là thấy ngay). Khi đó đoạn lệnh tính toán trên sẽ được thực hiện nhanh hơn.
Lượt bài của hot snow
Nguồn:forum.gamevn.com