Day 6 - Mảng và Tìm kiếm sắp xếp trong mảng - Phần 2 : Mảng kí tự và thuật toán sắp xếp, tìm kiếm.

V. Mảng ký tự

Mảng ký tự mang kiểu dữ liệu char. 

    char str[10] = { 'c', 'h', 'a', 'o', '!' };

Trong mảng str trên thì mỗi ký tự nằm ở một thành phần.  Kể cả khoảng trắng '    ' cũng được tính là 1 ký tự. Nếu dữ liệu không sử dụng đủ các index trong mảng thì các thành phần đó mang giá trị rỗng '\0'. 

 Đảo ngược vị trí các ký tự trong mảng.

Đếm số từ trong 1 câu.

Đếm số chữ số trong dãy kí tự.

VI. Tìm kiếm và sắp xếp

Tìm kiếm trong mảng là thuật toán so sánh giá trị nhập vào với từng giá trị trong mảng. Nếu trùng với giá trị trong mảng, hành động sẽ được thực hiện.

Tìm kiếm các ký tự - và thay bằng ký tự _ 

Sắp xếp trong mảng là thuật toán so sánh các giá trị trong mảng và đổi vị trí cho nhau tùy thuộc yêu cầu bài toán.

  Thuật toán INSERT sử dụng bộ nhớ đệm để sắp xếp các số theo thứ tự giảm dần

Còn rất nhiều thuật toán khác như Merge, Quick, Bubble, ... để sắp xếp mảng một cách tối ưu nhất.

VII. Kết

Mảng là một khái niệm khá hữu ích, nó và vòng lặp là những công cụ hữu hiệu giúp cắt ngắn thời gian thực hiện các tác vụ so sánh, tính toán .

Day 6 - Mảng và Tìm kiếm sắp xếp dữ liệu trong mảng - Phần 1: Mảng

ARRAY - Mảng

 I. Mảng là gì ?

Mảng là tập hợp của các dữ liệu có chung kiểu như int hay char. Mình sẽ nói về mảng 1 chiều ở bài này thôi, mảng đa chiều tính sau. Mảng với n thành phần luôn bắt đầu bằng thành phần 0 và kết thúc ở thành phần n-1. 0 và n-1 được gọi là giới hạn - bounds của mảng.

                        int  num[10] = { 2, 25,37343, 232, 1265, 45543}

 Chèn thêm giá trị V vào bất kì vị trí nào trong mảng.

Với 1 mảng ví dụ như trên, mảng có 10 thành phần. "2" sẽ nằm ở thành phần 0, mảng đã xác định trước 6 thành phần. 4 thành phần còn lại còn trống, có thể được thêm sau này. Cần lưu ý rằng nếu index - số thứ tự thành phần vượt quá giới hạn, sẽ có những lỗi xảy ra tùy theo các compiler khác nhau. 

 1 mảng 2 chiều với i, j để xác định vị trí thành phần. nguồn bcdonline.net

II. Xác định 1 mảng

Để xác định 1 mảng, chúng ta cần xác định những tính chất sau của mảng: 
- storage class: Lớp lưu trữ. Có 4 lớp trong C là automatic, register, static và external.
 +external dùng để định nghĩa mảng ngoài hàm và automatic để định nghĩa mảng nằm trong hàm.
 +Mặc định lớp automatic sẽ được sử dụng cho mảng ( và biến ).
 +static sẽ khiến cho mảng tồn tại đến khi chương trình kết thúc, còn các lớp khác sẽ biến mất sau khi không được sử dụng nữa.
 +register thì đặt biến ngay trong CPU, nhằm mục đích truy cập tốc độ siêu nhanh ( gấp nhiều lần bộ nhớ ). register chỉ sử dụng được với biến.

- Data type : Kiểu dữ liệu. Mảng chỉ có thể lưu được 1 kiểu dữ liệu duy nhất cho tất cả các thành phần của nó. int char double float là 4 kiểu dữ liệu được sử dụng trong mảng, không dùng void

- array name: Cái này tương tự như đặt tên biến, chả khác gì.
- array size: Độ lớn của mảng, đây là cái khác biệt nhất so với cả xác định 1 biến. Đây là tổng số thành phần mà mảng có thể lưu trữ được.  
  

 III. Sử dụng mảng

 Sau khi đã xác định mảng, chúng ta có thể gọi ra các thành phần trong mảng như sau:

- num[0] , num[9-2] , num[18/3], num[i], ....

index trong mảng bắt buộc là số nguyên dương. Còn lại việc chúng ta xác định index thế nào thì thoải mái, miễn sao nó là số nguyên dương. 

 

Index trong mảng luôn luôn là số dương.

Khác với biến, chúng ta không thể trực tiếp so sánh và tương tác 2 mảng dù chúng có giống nhau đến mấy. Chúng ta chỉ có thể tương tác giữa những thành phần trong mảng: so sánh, gán giá trị, ....
  

Sử dụng phép so sánh các giá trị trong mảng để tìm ra số lớn nhất.

 Sử dụng phép so sánh các giá trị trong mảng để nhận xét tính tăng giảm của mảng.

Hợp nhất 2 mảng vào bằng cách gán từng giá trị cho mảng thứ 3.

 Thuật toán sắp xếp thứ tự giảm dần trong mảng sử dụng 1 vòng lặp. 

Phần sau sẽ viết về Mảng ký tự và các thuật toán sắp xếp tối ưu.

Vòng lặp - FOR / WHILE / DO WHILE - Phần 3: Do while và các lệnh nhảy.

IV. DO WHILE

- Vòng lặp do while có khả năng khác biệt so với 2 vòng lặp kia, đó là việc thực hiện hành động trước khi kiểm tra biểu thức đánh giá ( gọi vui là Tiền trảm hậu tấu ^^ )

Cấu trúc do while như sau:
    do { hành động } while ( biểu thức đánh giá )
 

 

Sử dụng do while để hiển thị số chia hết cho 5.

  Như trên hình ta thấy, do while bắt đầu bằng việc hành động trước, sau đó mới xuống kiểm tra biểu thức đánh giá trong while. Chính vì thế, nếu chúng ta muốn chuyển do while sang while hay for, ta cần tính toán tăng thêm 1 lần lặp trong vòng while.

  Dãy số Fibonacci thể hiện dưới vòng lặp do while.

Tương tự vòng while, vòng lặp do while cũng được tự do trong câu lệnh hơn vòng for.

Tiếp theo sẽ là những lệnh nhảy sử dụng để thoát khỏi hành động đang diễn ra.

V. Lệnh nhảy

 Đôi khi trong chương trình có những trường hợp đặc biệt mà khi gặp, ta sẽ bỏ qua, dừng vòng lặp, hay đơn giản là thoát khỏi chương trình. Có 5 lệnh nhảy : return, goto, break, continue, exit (). 

return : Được sử dụng để trả giá trị về cho hàm. Phần này mình sẽ viết sau khi học xong hàm

go to: Sử dụng để đi đến bất kì identifier nào được gọi. Ví dụ:

int i;

LOOP:
for ( i=0;i<10;i++){

      printf("%d",i); }
goto LOOP;

Trong đó LOOP là identifier, được gán vào lệnh for. Khi gọi LOOP bằng goto, chương trình sẽ quay lại việc thực hiện vòng lặp ngay lập tức.

Vì đặc tính di chuyển tự do, goto sẽ khiến logic và flowchart của chương trình trở nên phức tạp. Việc sử dụng goto cần phải suy xét kĩ trong những chương trình lớn.

continue: Sử dụng trong vòng lặp, khi hành động đến continue, vòng đó sẽ bị dừng lại và thực hiện 1 vòng lặp mới.

break: Sử dụng trong vòng lặp và switch. Khi hành động đến break, toàn bộ cấu trúc lặp hay switch đó sẽ kết thúc, chương trình chạy tiếp.

exit (): Khi gặp exit, chương trình sẽ kiểm tra đúng sai với biểu thức trong ngoặc. Nếu biểu thức trong ngoặc là ĐÚNG, chương trình sẽ kết thúc.

VI. Kết luận

Có thể nói vòng lặp là công cụ tiết kiệm thời gian hữu hiệu nhất của 1 lập trình viên. Các vòng lặp hoàn toàn giống nhau về mặt ý nghĩa, có thể chuyển kiểu vòng lặp này sang vòng lặp kia chỉ trong 1 phút. 

Tuy nhiên, việc phân loại vòng lặp giúp chúng ta lựa chọn sáng suốt hơn khi gặp các tình huống khác nhau: biết trước số vòng lặp thì dùng for, không biết thì dùng while, thực hiện trước khi kiểm tra thì dùng do while. Và để điều khiển chương trình dễ dàng hơn, những lệnh nhảy sẽ được thêm vào tùy ý để ngắt vòng lặp. 

Vòng lặp - FOR / WHILE / DO WHILE - Phần 2: Vòng lặp WHILE

III. Vòng lặp WHILE

- Vòng lặp while có cấu trúc đơn giản như sau:

        while (biểu thức đánh giá) { hành động }

Thật đơn giản. Đây có thể coi là cấu trúc lặp gốc. Hoạt động của nó chỉ đơn giản là kiểm tra tính ĐÚNG của biểu thức, sau đó thực hiện hành động, rồi tiếp tục kiểm tra biểu thức cho đến khi giá trị biểu thức là SAI thì kết thúc.

 Cấu trúc while sẽ kiểm tra biểu thức trong ngoặc đơn, sau đó thực hiện hành động trong ngoặc kép.

Như bài tập trên, chuyển thể từ cấu trúc for sang cấu trúc while rất đơn giản : Để biểu thức khởi đầu viết trước lệnh while, biểu thức cập nhật sẽ viết bên trong lệnh while. 

Ví dụ:

                       Vòng lặp FOR                         ||                               Vòng lặp WHILE

for ( i=0;i<10;i++){                                        ||             i=0; while (i<10) {

      printf("%d",i); }                                       ||                   printf("%d",i); i++; }

Nếu như trong vòng for, biểu thức cập nhật luôn luôn là hành động cuối cùng thì trong vòng while, ta có thể để nó ở bất cứ đâu ta muốn bên trong ngoặc kép.

Vì đặc tính tự do này, vòng lặp while thường được sử dụng trong các trường hợp ta không biết trước số lần lặp khi viết code.

  Đưa vào 1 số và tính giai thừa. Ta thực hiện vòng lặp phép nhân với số k tăng dần từng đơn vị.

Phần cuối sẽ nói về vòng lặp do while và lệnh nhảy.

Vòng lặp - FOR / WHILE / DO WHILE - Phần 1: Khái niệm vòng lặp. Vòng lặp FOR

LOOP - Vòng lặp

Sự ra đời của vòng lặp là tất yếu khi không ai muốn tự tay thực hiện hàng trăm hay hàng ngàn câu lệnh có cấu trúc giống hệt nhau. Với tốc độ xử lý vượt trội con người, máy tính sẽ làm thay chúng ta điều đó.

I. Vòng lặp là gì ?

Vòng lặp là cấu trúc thực hiện lệnh lặp đi lặp lại cho đến khi nó thỏa mãn yêu cầu đưa ra ( hoặc sẽ lặp vô tận ).  Vòng lặp trong lập trình C có thể viết ở dưới 3 dạng khác nhau, đó là:

- FOR (;;){}

- WHILE (){}

-DO {} WHILE ()

Về mặt ý nghĩa, 3 vòng lặp này giống hệt nhau, hoàn toàn có thể viết sang kiểu lặp còn lại, mặc dù vòng do while có hơi khác 1 chút. 

Việc chia ra 3 kiểu vòng lặp khác nhau nhằm mục đích thuận tiện và dễ hiểu hơn trong từng trường hợp. Sau đây mình sẽ phân tích chi tiết các loại vòng lặp.

 1 dạng vòng lặp. nguồn
www.w3resource.com

II. Vòng lặp FOR

 - Vòng lặp for có dạng như sau:

         for (biểu thức khởi đầu ; biểu thức đánh giá ; biểu thức cập nhật  ) { hành động }

- Trong vòng lặp for, bất cứ vị trí nào cũng có thể để trống. Một vòng lặp for đầy đủ thường dùng để viết lệnh lặp biết trước được số lần lặp là bao nhiêu, mỗi lần lặp thay đổi như thế nào. Vì thế vòng lặp for thường được sử dụng trong tính toán số học.

1 bài tập với vòng for cơ bản. Hiện tên theo số tuổi đưa vào

- Vòng lặp for đầy đủ sẽ lần lượt đặt giá trị khởi đầu, sau đó kiểm tra biểu thức, nếu biểu thức đánh giá đưa ra là ĐÚNG ( True ) thì hành động sẽ được thực hiện ( tương tự với cấu trúc điều kiện IF ), sau đó sẽ thực hiện hoạt động ở phần biểu thức cập nhật và quay trở lại với bước kiểm tra biểu thức. Khi biểu thức đưa ra giá trị SAI ( False ), vòng lặp sẽ kết thúc, chuyển sang lệnh tiếp theo.

Lệnh for rất tốt khi sử dụng để tính toán

Lưu ý: Nếu chúng ta có nhiều hơn 1 câu lệnh trong biểu thức, chúng ta hoàn toàn có thể sử dụng dấu "," để viết các lệnh con bên trong dấu ngoặc đơn.

Sử dụng nhiều lệnh trong biểu thức đánh giá, để trống biểu thức khởi đầu.

Bài viết sau sẽ viết về cấu trúc while, cấu trúc đơn giản hơn của for.

Ngày 3 - Câu lệnh rẽ nhánh - Lệnh If và mở rộng của If - Lệnh Switch

IF ... Else - Câu lệnh điều kiện

Làm thế nào để máy tính đưa ra những quyết định khác nhau tùy theo điều kiện hay dữ liệu chúng ta nhập vào ?

1. Lệnh điều kiện là gì ?

Là câu lệnh dùng để đặt điều kiện cho máy tính thực hiện hành động nào đó. Máy tính sẽ kiểm tra tính đúng sai của biểu thức trước khi thực hiện hành động kế tiếp. Có 2 câu lệnh căn bản trong C để kiểm tra điều kiện và thực hiện lệnh là : if và switch

2. Lệnh IF

Câu lệnh căn bản nhất dùng để kiểm tra điều kiện cho hành động của chương trình. Lệnh if có dạng như sau:

if ( biểu thức ) { hành động}

 

Trên đây là flowchart kiểm tra số a 

có chia hết cho b hay không

. Hình thoi thể hiện phép kiểm tra. 

Đường Y sẽ tương đương với hành động 

của lệnh if sau khi kiểm tra biểu thức. 

Trong câu lệnh if, biểu thức được kiểm tra trước khi hành động được thực hiện. Biểu thức trong câu lệnh này được kiểm tra tính Đúng hoặc Sai. Nếu biểu thức đúng, hành động sẽ được thực hiện. Nếu biểu thức sai, sẽ không có gì xảy ra và chương trình sẽ tiếp tục chạy sang phần tiếp theo.

 Comment: 1 lệnh if hoàn toàn có thể kiểm tra nhiều biểu thức con liên tục để thực hiện hành động tiếp theo. Ví dụ như :

if ( a == 3 || a == 2 ){

    printf (" %d la so nguyen to",a); }

Trong câu lệnh trên, mình sử dụng 2 dấu gạch sổ để kiểm tra biểu thức con a = 3 HOẶC biểu thức con a = 2. Nếu muốn kiểm tra cả 2 biểu thức cùng đúng ( biểu thức 1 đúng VÀ biểu thức 2 đúng ) thì ta sử dụng "&&".

Lưu ý: Nếu biểu thức được đưa vào lệnh if không thể so sánh được ví dụ:

if (2){hành động}

 thì mặc định hành động của lệnh if sẽ được thực hiện.

3. Mở rộng các trường hợp cho lệnh IF

3.1 IF ... ELSE

Đây là câu lệnh để chúng ta đặt hành động cho chương trình ngay cả khi biểu thức bị sai. Với câu lệnh này, chương trình sẽ luôn thực hiện một trong 2 hành động được đặt ra theo 2 đường Đúng và Sai, bao quát được tất cả các trường hợp xảy ra.

if ( biểu thức ){ hành động 1}

else { hành động 2 }               

Đường N thể hiện hành động của lệnh else khi điều kiện kiểm tra không thỏa mãn. Khi đó sẽ có 1 kết quả khác được in ra màn hình.

3.2 IF ... ELSE IF ... 

Khi chúng ta cần nhiều hơn là 2 hành động đi liền với nhiều biểu thức khác nhau, chúng ta sẽ sử dụng thêm else if để tăng số lượng hành động chương trình có thể thực hiện.

if ( biểu thức 1 ) { hành động 1 }       

else if ( biểu thức 2 ) { hành động 2 }

...

else if ( biểu thức n ) { hành động n }

    

Khi chúng ta cần in 1 trong nhiều kết quả khác nhau, cần dùng đến else if.

Chương trình sẽ kiểm tra lần lượt từng biểu thức từ trên xuống dưới. Nếu bất cứ biểu thức nào đúng, hành động tương ứng sẽ được thực hiện và dừng việc kiểm tra các biểu thức còn lại. Nếu không, sẽ không có hành động nào được thực hiện trừ khi viết thêm lệnh else.

3.3 Nested IF - Cấu trúc IF nằm trong IF / ELSE

Cấu trúc này hiểu đơn giản là : 1 lệnh if khác được đặt trong hành động của if / else nằm đằng trước nó. Cấu trúc này dùng để kiểm tra nhiều biểu thức không liên tục trước khi đưa ra hành động.

if ( biểu thức 1){                  

if ( biểu thức 2){ ...} 

...}                        

Cấu trúc tương tự else if

So với cấu trúc else if kiểm tra nhiều biểu thức liên tục, cấu trúc này có lợi cho máy tính khi có biểu thức con trùng nhau, vì chương trình không phải kiểm tra lại biểu thức đã được kiểm tra từ trước, qua đó tăng hiệu suất xử lý theo thời gian.

Comment: Cái này rất dễ nhầm do có nhiều bậc kiểm tra không liên tục, nên sử dụng cùng với Flowchart để không bị rối và nhầm lẫn khi code. ( thường là lỗi ngoặc nhọn )

4. Lệnh Switch

Với lệnh if, ta kiểm tra giá trị đúng / sai của biểu thức. Còn với lệnh switch, ta so sánh bằng nhau kết quả của biểu thức. Giá trị được so sánh với kết quả của biểu thức chỉ có thể là hằng số nguyên  hoặc là hằng ký tự.

switch ( biểu thức ){
    case hằng 1:
        hành động 1; break;
    case hằng 2:
        hành động 2; break;
....
    case hằng n:
        hành động n; break;
    default:
        hành động;
}

          switch dùng với nhiều trường hợp 
so sánh với giá trị nguyên/ ký tự

Nhìn cấu trúc trên, ta có thể thấy chương trình sẽ so sánh lần lượt từ 1 đến n. Nếu bất cứ giá trị nào bằng với kết quả của biểu thức, hành động tương ứng sẽ diễn ra, sau đó thoát khỏi lệnh switch thông qua lệnh break. Nếu không có lệnh break, quá trình so sánh và ( có thể ) thực hiện hành động tương ứng sẽ diễn ra cho đến khi kiểm tra hết các hằng giá trị hằng đã đưa ra.

default có thể hiểu tương ứng với else khi không còn giá trị để so sánh, chương trình sẽ thực hiện hành động tương ứng với default. Thường default được đặt cuối cùng nên không cần thêm lệnh break để thoát khỏi switch.

Comment: Chúng ta có thể đặt nhiều trường hợp ( case ) có chung một hành động bằng cách viết như sau:
Ví dụ:
case hằng 1:
case hằng 2:
case hằng 3:
    printf("hi"); break;

Khi đó, nếu kết quả của biểu thức trùng với 1 trong 3 hằng giá trị trên, câu lệnh printf() sẽ được thực hiện.

5. Kết luận

Tùy vào nhu cầu sử dụng, ta có thể lựa chọn cấu trúc lệnh khác nhau cho phù hợp với hoàn cảnh. if hay if else dùng cho số lượng biểu thức con và trường hợp ít, nhiều hơn chút là if else-if. Còn Nested if thì dùng cho số lượng biểu thức cần kiểm tra lớn hơn, dễ bị trùng lặp. switch dùng cho việc so sánh với hằng số hay hằng ký tự, biến thể của if để đơn giản hóa việc code.

 Sử dụng lệnh rẽ nhánh để viết thuật toán kiểm tra 1 số nguyên dương bất kỳ là số nguyên tố hay không.