Sàng nguyên tố - Prime Number Sieve

Sàng nguyên tố là thuật toán do Eratosthenes đưa ra để tìm các số nguyên tố. Nó có đặc điểm khác với thuật toán khác là kiểm tra các số nguyên tố theo kiểu sàng lọc, xét tất cả những số cần kiểm, những số nào không phải là số nguyên tố thì bỏ đi. Thuật toán thích hợp cho bài toán tìm tất cả các số nguyên tố trong khoảng [a, b] mà đặc biệt hiệu quả khi khoảng cách giữa a, b là rất lớn.
Để tìm các số không phải số nguyên tố chỉ cần dựa vào các số nguyên tố ban đầu, VD số 2 là số nguyên tố thì các số chia hết cho 2 chắc chắn không phải là số nguyên tố, số 3 là số nguyên tố thì tất cả các số là bội của 3 đều bị loại bỏ, cứ như vậy những số được giữ lại là các số nguyên tố.

Cấu trúc dữ liệu STACK – QUEUE

I. STACK – Ngăn xếp
1. Khái niệm:
Một ngăn xếp là một cấu trúc dữ liệu dạng thùng chứa (container) của các phần tử (thường gọi là các nút (node)) và có hai phép toán cơ bản: push and pop. Push bổ sung một phần tử vào đỉnh (top) của ngăn xếp, nghĩa là sau các phần tử đã có trong ngăn xếp. Pop giải phóng và trả về phần tử đang đứng ở đỉnh của ngăn xếp. Trong stack, các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi stack.
VD thực tế : có thể coi stack như 1 băng đạn , mỗi viên đạn là 1 phần tử. chỉ có thể lắp đạn vào đầu băng đạn (push ) và mỗi lần bắn sẽ bắn viên đạn trên cùng băng đạn ( pop). Hay còn gọi là LIFO (Last In First Out) vào trước ra trước.

2. Khai báo:
#include<stack> // thư viện
Ví dụ khai báo stack kiểu int
stack<int> s; (nếu kiểu kí tự thì khia báo stack<char>s)
s.size() : trả về kích thước hiện tại của stack (số phần tử trong stack).
s.empty() : true (1) stack nếu rỗng, và (0) ngược lại.
s.push(x) : đẩy phần tử x vào đỉnh stack.
s.pop() : loại bỏ phẩn tử ở đỉnh của stack.
s.top() : truy cập tới phần tử ở đỉnh stack.
Tất cả hàm trên đều có Độ phức tạp O(1); 

3. Ứng dụng
-Đảo ngược xâu: nhập từng kí tự xâu cho vào stack, sau đó lấy từng kí tự ra ta sẽ được 1 xâu đảo ngược.
- Chuyển hệ cơ số 10 sang cơ số 2: thực hiện liên tiếp phép chia dư n cho 2 rồi , n=n/2 và push kq phép chia dư vào stack, sau khi chia xong ta lấy các phần tử trong stack ra.
- Tính biểu thức đại số, chuyển biểu thức đại số dạng trung sang hậu tố. - Khử đệ quy (trong duyệt đồ thị DFS) 

A. Kiểu dữ liệu trong C

1. Các ký tự điều khiển

• \n : Nhảy xuống dòng kế tiếp canh về cột đầu tiên.
• \t : Canh cột tab ngang.
• \r : Nhảy về đầu hàng, không xuống hàng.
• \a : Tiếng kêu bip.
• \\ : In ra dấu \
• \” : In ra dấu “
• \’ : In ra dấu ‘
• %%: In ra dấu %

Đây chỉ là một số ký tự điểu khiển quen thuộc, hay dùng, ngoài ra còn một só ký tự điều khiển khác các bạn có thể xem thêm trong các tài liệu.
Dể hiểu rõ về các ký tự điều khiển các bạn hãy chạy thử chương trình sau và tự rút ra nhận xét cho riêng mình.

2. Từ khóa

Là các từ mà ngôn ngữ C đã xây dựng sẵn, chúng ta không nên định nghĩa lại chúng.

3. Kiểu và biến

a. Kiểu dữ liệu
Kiểu dữ liệu giống như là các thùng chứa, vật dụng để đựng đồ dùng của chúng ta. VD ca uống nước để đựng nước, cái rổ để đựng rau,…
Mỗi loại dữ liệu có kích thước khác nhau và tương ứng với miền giá trị và loại giá trị mà nó có thể thực hiện. VD kiểu int chiếm 2 byte bộ nhớ và để chứa các số nguyên,…


b. Biến – hằng
Tương ứng với mỗi kiểu dữ liệu chúng ta có các biến, hằng thuộc các kiểu đó và có miền giá trị tương ứng như trên dùng để lưu giá trị. Các bạn cần phân biệt kiểu và biến.
VD cái rổ A để đựng rau muống, cái rổ B để đựng rau cần thì tương ứng biến a lưu giá trị số 5, còn biến b lưu giá trị số 9 mặc dù chúng cùng kiểu
Biến có thể thay đổi trong quá trình thực hiện chương trình còn hằng thì không thể.
Cách khai báo biến: kiểu_dữ_liệu tên_biến;
– Tên biến hợp lệ là một chuỗi ký tự liên tục gồm: Ký tự chữ, số và dấu gạch dưới. Ký tự đầu của tên phải là chữ hoặc dấu gạch dưới. Khi đặt tên không được đặt trùng với các từkhóa.
Ví dụ1 :
Các tên đúng: delta, a_1, Num_ODD, Case
Các tên sai: 3a_1 (ký tự đầu là số); num-odd (sử dụng dấu gạch ngang); int (đặt tên trùng với từkhóa) ; del ta (có khoảng trắng); f(x) (có dấu ngoặc tròn)
Lưu ý: Trong C, tên phân biệt chữ hoa, chữ thường
Ví dụ2 : number khác Number ; case khác Case (case là từ khóa, do đó bạn đặt tên là Case vẫn đúng)
Cú pháp: kiểu danh_sach_cac_bien;

Bài 2 – Hello World

Chúng ta có thể sử dụng các công cụ khác nhau nhưng đưới đây là 3 công cụ phổ biến và tiện lợi nhất

• Dev C
• CodeBlocks
• Visual C
  …
  Ngoài ra bạn nào dùng Linux thì chúng ta có thể dùng Geany cũng là một phần mềm tương đối tốt.

Các bạn có thể sử dụng một trong các phần mềm trên để phục vụ cho việc học tập của mình nhưng mình khuyên các bạn nên dùng Dev C hoặc CodeBlocks (trong windows) và Geany trong Linux.

2. Chương trình đầu tiên Hello World

Và đây là nội dung bài đầu tiên của chúng ta. Nội dung rất đơn giản: Chương trình đầu tiên

Bạn ấn F9 hoặc cái nút thứ 3 (4 màu liền nhau) ở thanh công cụ để biên dịch và chạy chương trình. Kết quả của chúng ta:


Dòng thứ 1: bắt đầu bằng // cho biết hàng này là hàng diễn giải (chú thích). Khi dịch và chạy chương trình, dòng này không được dịch và cũng không thi hành lệnh gì cả. Mục đích của việc ghi chú này giúp chương trình rõ ràng hơn. Sau này bạn đọc lại chương trình biết chương trình làm gì.
Dòng thứ 2,3: chứa phát biểu tiền xử lý #include <stdio.h> và #include<stdlib.h>. Vì trong chương trình này ta sử dụng hàm thư viện của C là printf và system, do đó bạn cần phải có khai báo của hàm thư viện này để báo cho trình biên dịch C biết. Nếu không khai báo chương trình sẽ báo lỗi. Về chức năng của từng thư viện mình sẽ nói trong các bài sau nhá.
Dòng thứ 4: int main() là thành phần chính của mọi chương trình C (bạn có thể viết
main() hoặc void main(). Tuy nhiên, bạn nên viết theo dạng int main() để chương trình rõ ràng hơn (Về vấn đề này mình sẽ nói cụ thể sau). Mọi chương trình C đều bắt đầu thi hành từ hàm main. Cặp dấu ngoặc () cho biết đây là khối hàm (function). Hàm int main() có từ khóa int đầu tiên cho biết hàm này trả về giá trị kiểu nguyên (int).
Dòng thứ 5 và 9: cặp dấu ngoặc móc {} giới hạn thân của hàm. Thân hàm bắt đầu bằng
dấu { và kết thúc bằng dấu }.
Dòng thứ 6: printf (“Chuong trinh C dau tien cua toi !\n”); , chỉ thị cho máy in ra chuỗi ký tự nằm trong nháy kép (“”). Hàng này được gọi là một câu lệnh, kết thúc một câu lệnh trong C phải là dấu
chấm phẩy( ; ).
Dòng thứ 7: system(“pause”); chỉ thị máy dừng lại chương trình tại nơi mà nó được gọi. Trong Th này ta dùng để dừng màn hình xem kết quả
Dòng 8: return 0; Trả về giá trị kiểu nguyên là 0 theo như đúng ban đầu là khai báo int main().
Lưu ý:
1. Trong chương trình này mình không dùng thư viện conio.h vì trong chuẩn C không có thư viện này, và từ đó cũng không dùng được getch() để dừng màn hình mà mình đã thay bằng lệnh system(“pause”);
2. Khi dùng hàm return để trả về giá trị của hàm thì các bạn có thể bỏ qua lệnh này chương trình vẫn chạy nhưng về chuẩn là sai, trả về 1 cũng sai, tóm lại là trả về 0. Còn sai thế nào mình nói sau.
Bài của chúng ta coi như là hết !!!

Bài 1. Tổng quan về lập trình và ngôn ngữ lập trình C 

I.Các khái niệm cơ bản 

1.Lập trình máy tính 
-  Gọi tắt là lập trình (programming).
-  Nghệ thuật cài đặt một hoặc nhiều thuật toán trừu tượng có liên quan với nhau bằng một ngôn ngữ lập trình để tạo ra một chương trình máy tính.

2.Thuật toán 
-  Là tập hợp (dãy) hữu hạn các chỉ thị (hành động) được định nghĩa rõ ràng nhằm giải quyết một bài toán cụ thể nào đó.

a. Ví dụ 
Thuật toán giải PT bậc nhất: ax + b = 0
(a, b là các số thực).
Input : a, b thuộc R
Output : đưa ra nghiệm x.

b. Các bước giải  
-    Nếu a = 0
+ b = 0 thì phương trình có nghiệm bất kì.
+ b ≠ 0 thì phương trình vô nghiệm.
Nếu a ≠ 0
 Phương trình có nghiệm duy nhất x = -b/a

3.Các tính chất của thuật toán 
- Tính chính xác: quá trình tính toán hay các thao tác máy tính thực hiện là chính xác.
- Tính rõ ràng: các câu lệnh minh bạch được sắp xếp theo thứ tự nhất định.
- Tính khách quan: được viết bởi nhiều người trên máy tính nhưng kết quả phải như nhau.
- Tính phổ dụng: có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau.
- Tính kết thúc: hữu hạn các bước tính toán.

QUY HOẠCH ĐỘNG


I. Quy hoạch động là gì?

1. Đệ quy và quy hoạch động :

         - Như các bạn đã biết đến phương pháp đệ quy ở chương trước, phương pháp đệ quy tính toán các bài toán bằng cách giải quyết các bài toán nhỏ hơn thông qua lời gọi hàm đến chính nó. Tuy nhiên phương pháp đệ quy thường sử dụng bộ nhớ lớn và thời gian tính toán khổng lồ. Và quy hoạch động là một kỹ thuật nhằm cải thiện hai nhược điểm lớn trên của đệ quy là sử dụng bộ nhớ lớn và thời gian tính toán rất lớn.
        - Quy hoạch động là một phương pháp khó, vì mỗi bài toán tối ưu đều có một đặc thù riêng, nên cách giải quyết hoàn toàn khác nhau đòi hỏi người lập trình phải nắm vững bản chất của quy hoạch động.

2. Quy hoạch động là gì ?

       - Trạng thái là gì? Trạng thái là một trường hợp, một bài toán con của 1 bài toán lớn.
       - Quy hoạch động :  Quy hoạch động là kĩ thuật được dùng khi có một công thức hoặc một (một vài) trạng thái bắt đầu. Một bài toán được tính bởi các bài toán nhỏ hơn đã được tìm ra từ trước, và kết quả các bài toán sẽ được lưu lại để những lần tính toán tiếp theo nếu cần đến những kết quả đó thì không cần tốn thêm thời gian thực hiện lại những bài toán này nữa. Nói cách khác, quy hoạch động bắt đầu từ việc giải các bài toán nhỏ, để từ đó từng bước giải quyết bài toán lớn hơn , và cuối cùng là bài toán lớn nhất ( bài toán ban đầu).

       QHĐ có độ phức tạp đa thức nên sẽ chạy nhanh hơn quay lui và duyệt trâu.

3. Ưu nhươc điểm :

      - Ưu điểm : chương trình chạy nhanh, mang tính tối ưu hóa cao
      - Nhược điểm :  + Sự kết hợp giữa các bài toán con chưa chắc cho ta bài toán lớn.
                                + Số lượng các bài toán con cần giải quyết có thể rất lớn.

II. Hai cách tiếp cận quy hoạch động.

Bài toán ví dụ :  Tìm số Fibonacci thứ n: xây dựng hàm tính trực tiếp dãy Fibo thứ n theo định nghĩa toán học với công thức truy hồi : F[k] = F[k-1] + F[k-2] , F[0] = 1 , F[1] =1. Cho n tìm F[n]. Chúng ta sẽ tìm cách giải quyết bài toán này bằng các cách tiếp cận dưới đây.

Cách giải thông thường khi dùng đệ quy, quay lui : Độ phức tạp cho phương pháp này là O(2^n) vì mỗi lần gọi hàm tính F[k] ta phải gọi đến hai bài toán con, và phải đi sâu tính lại các bài toán con đó. Ví dụ : Fibo(4) = Fibo(3)+Fibo(2) , Fibo(3) = Fibo(2)+Fibo(1) : ở đây Fibo(3) phải thực hiện tính 2 lần và với n bài toán đều phải tính lại 2 lần sẽ khiến độ phức tạp là O(2^n), tuy nhiên quy hoạch động có lưu trữ các bài toán và có thể giải quyết điều này.

Quy hoạch động thường dùng một trong hai cách tiếp cận :  

1. Top-down (Từ trên xuống): 

Bài toán được chia thành các bài toán con, các bài toán con này được giải và lời giải được ghi nhớ để phòng trường hợp cần dùng lại chúng, và các bài toán con này tiếp tục gọi đến bài toán con của chúng đến khi đủ dữ kiện để lấy ra kết quả tính toán.

Đây là kỹ thuật đệ quy và lưu trữ được kết hợp với nhau, quy hoạch động giải quyết.


Áp dụng với bài toán ví dụ : Ta sẽ thực hiện lời gọi tính toán trực tiếp đến bài toán gốc Fibo (n) và bài toán này sẽ được chia nhỏ và sau khi tính được kết quả sẽ được lưu trữ vào mảng, và khi gặp lại bài toán đã được tính toán rồi ta sẽ không cần thực hiện đệ quy đi sâu vào để giải quyết của bài toán con đó nữa.

Phân tích độ phức tạp : So với phương pháp đệ quy –quay lui, cách tiếp cận này lưu trữ lại những bài toán đã được tính và khi cần không cần phải đi sâu vào nữa, bài toán Fibo(k) gọi đến hai bài toán nhỏ hơn nên số lượng bài toán tối đa là n +1 bài toán Fibo(0) … Fibo(n) và khi tính được đến đâu ta lưu trữ kết quả mỗi bài toán lại đến đó nên bài toán tương đương với tối đa n+1 lần lưu trữ nên độ phức tạp của thuật toán chỉ là O(n). Và đương nhiên quy hoạch động có thể chạy với n lên đến hàng triệu trong khi đệ quy quay lui chỉ chạy với n rất nhỏ (n < 25).

Từ đó cho ta thấy cách giải quyết của quy hoạch động cho ta độ phức tạp chỉ là số lượng bài toán và có thể nhân thêm với chi phí chuyển bài toán (ở những bài toán khác) ở đây là phép tính trực tiếp nên độ phức tạp là O(n*1) ~ O(n).


2. Bottom-up (Từ dưới lên):

Tất cả các bài toán con có thể cần đến đều được giải trước (từ bài toán cơ sở trở đi) , sau đó được dùng để xây dựng lời giải cho các bài toán lớn hơn.

Cách tiếp cận này tốt hơn về không gian bộ nhớ dùng cho ngăn xếp và số lời gọi hàm. Tuy nhiên, đôi khi việc xác định tất cả các bài toán con cần thiết cho việc giải quyết bài toán cho trước không được trực quan như Top-down. 

Cách tiếp cận này cho ta thấy rõ độ phức tạp của thuật toán quy hoạch động : một vòng for O(n). Ở đây ta thực hiện chuẩn bị sẵn các bài toán đã tính được : đầu tiên là F[0] và F[1] sau đó sẽ lần lượt tính các F[2] -> F[3] … và cuối cùng sẽ được F[n] là kết quả bài toán. Cách tiếp cận này code sẽ ngắn gọn hơn nhiều nhưng với nhiều bài toán phức tạp hơn thì sẽ không trực quan như Top-down do phải điều chỉnh thứ tự gọi các bài toán cho lần lượt ở vòng for để đúng với quy trình đi từ nhỏ đến lớn. Tuy nhiên các tiếp cận này luôn tốt hơn khi cài đặt chính xác do đây là giải thuật khử đệ quy cho bài toán Top-down.

3.  Phương pháp giải bài toán quy hoạch động : 

Để giải quyết bài toán quy hoạch động ta chỉ cần xác định được hai vấn đề :

• Thứ nhất là : Bài toán cơ sở. 
• Thứ hai là   : Công thức truy hồi. 

Và để có được công thức truy hồi, ta phải xác định được bài toán với đủ dữ kiện để có thể xây dựng được công thức truy hồi đi đến bài toán lớn nhất.

Do mỗi bài toán quy hoạch động đều có đặc thù riêng nên để hiểu rõ cách xác định bài toán và xây dựng bài toán cơ sở và công thức truy hồi, các bạn sẽ được xem ví dụ cụ thể cho một số bài toán quy hoạch động ở bài viết "Một số bài toàn, ví dụ về quy hoạch động" tại Nhanduccc's Blog.