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.