Trong bài này tôi sẽ cung cấp một số bài tập để bạn rèn luyện thêm về các thuật toán về mảng một chiều.

1. Viết một chương trình để khởi tạo một mảng một chiều chứa 10 phần tử là các số nguyên, sau đó tính tổng giá trị tất cả các phần tử trong mảng và in ra.
2. Viết một chương trình để khởi tạo một mảng một chiều chứa 10 phần tử là các số nguyên, sau đó đảo ngược thứ tự các phần tử trong mảng mà không dùng mảng thứ 2. In mảng đó ra màn hình.
3. Viết một chương trình để khởi tạo một mảng một chiều chứa 10 phần tử là các số nguyên, sau đó nhập vào một giá trị x và đếm xem x xuất hiện trong mảng bao nhiêu lần?

Bài tiếp: Các thuật toán cơ bản về mảng hai chiều

Bài trước: Sắp xếp các phần tử trong mảng

Mảng hai chiều, thường thể hiện là một bảng số, trong toán học được gọi là ma trận. Ngoài ra, mảng hai chiều cũng được xem là mảng một chiều mà mỗi phần tử là một mảng một chiều.

Ví dụ: Đây là một bảng dữ liệu 2 chiều có 2 dòng và 2 cột

Khai báo: a[2][2] = {{4,5},{7,9}}

Một mảng có 4 hàng, 3 cột

Khai báo: a[4][3] = {{1,2,7},{3,1,8},{6,4,2},{8,5,6}}

Truy xuất đến một phần tử:

a[0][0]: là phần tử đầu tiên

a[2][3] là phần tử giao nhau giữa dòng thứ 3 và cột thứ 4

Các bài toán duyệt mảng hai chiều bạn sẽ thấy rõ trong các trò chơi đánh cờ, bảng tính Excel v.v.v.

Các bài toán phổ biến trên mảng hai chiều như sau:

•  Tìm một phần tử trong mảng
•  Tìm phần tử lớn nhất, nhỏ nhất
•  Tính tổng tất cả các phần tử trong mảng
•  Đổ dữ liệu sang mảng một chiều và ngược lại

Đây là các bài toán thường gặp, với hi vọng sẽ giúp bạn tự tin hơn khi làm việc với mảng một chiều.

Yêu cầu

Viết chương trình khởi tạo một mảng hai chiều có n hàng, m cột với các phần tử là số nguyên, sau đó nhập vào một phần tử x nào đó và kiểm tra xem phần tử x đã có trong mảng hay chưa?

Phân tích và tìm cách giải

• Đầu vào: mảng các phần tử a[2,3] ={{3,7,9},{2,4,1}}, giá trị x
• Đầu ra: In ra thông báo x có trong mảng hay chưa?
• Phân tích:
  • Cần duyệt qua các phần tử của mảng, rồi so sánh x và các giá trị trong mảng.
  • Nếu xuất hiện thì thông báo tìm thấy và dừng

Các bước thực hiện:

Khởi tạo mảng a[], khởi tại biến cờ found = false (chưa tìm thấy)
Nhập vào giá trị x
Cho lặp biến i từ 0 đến n-1, với n là số hàng
   Lặp biên j từ 0 đến m-1, với m số cột
      Nếu x=a[i][j]
        Dựng cờ đã tìm thấy found=true
        Dừng vòng lặp / Việc dừng vòng lặp không cần thiết sẽ giúp tăng hiệu năng của thuật toán.
Căn cứ vào kết quả biến found để thông báo kết quả có tìm thấy hay không

Cách biểu diễn thuật toán

Trong trường hợp này, tôi sử dụng ngôn ngữ giả.

Declare int a[2,3] ={{3,7,9},{2,4,1}},x, i,j, n,m

boolean found=false

Input x

n= a.lengh

m=a[0].lengh

Loop i=0 to n-1

   Loop j=0 to m-1

      If(x=a[i][j])

         found = true

         Break //Thoát khỏi vòng lặp

If (found)

   Print ‘X có trong mảng’

Else

   Print ‘X không có trong mảng’

Kết quả Dry Run của mảng này như sau

Các thuật toán tính tổng tương tự như bài toán tính tổng n số tự nhiên. Bài toán tìm giá trị lớn nhất, nhỏ nhất tương tự mảng một chiều. Các bạn hãy tự thực hiện.

Bài tiếp: Thuật toán đổ dữ liệu về mảng một chiều và ngược lại

Bài trước: Bài tập về mảng một chiều

Nếu bạn đã quen với các bài toán về sắp xếp hoặc các bài toán khác trên mảng một chiều, bạn có thể đổ mảng hai chiều vào mảng một chiều, sau đó thực hiện các bài toán đặc trưng, sau đó đổ lại kết quả vào mảng 2 chiều.

Yêu cầu

Viết chương trình khởi tạo một mảng hai chiều có n hàng, m cột với các phần tử là số nguyên, sau đó đổ dữ liệu này sang mảng một chiều, sắp xếp và đổ lại vào mảng 2 chiều.

Phân tích và tìm cách giải

• Đầu vào: mảng các phần tử a[2][3] ={{3,7,9},{2,4,1}}, giá trị x
• Đầu ra: In ra mảng đã sắp xếp
• Phân tích:
  • Khai báo một mảng một chiều có chiều dài bằng tổng tất cả các phần tử của mảng hai chiều. k=n*m.
  • Đổ dữ liệu từ mảng hai chiều sang mảng một chiều
  • Sắp xếp trên mảng một chiều
  • Đổ dữ liệu từ mảng một chiều sang mảng hai chiều

Các bước thực hiện

Khởi tạo mảng a[2][3], khai báo bảng b[6]

//Đổ dữ liệu từ mảng 2 chiều sang mảng 1 chiều
Cho lặp biến i từ 0 đến n-1, với n là số hàng
Lặp biên j từ 0 đến m-1, với m số cột
   b[i*m + j] = a[i][j]
Gọi lệnh sắp xếp trên bảng b đã thực hiện trong bài mảng một chiều

//Đổ dữ liệu từ mảng 1 chiều về lại mảng 2 chiều
Cho lặp biến i từ 0 đến n-1, với n là số hàng
   Lặp biên j từ 0 đến m-1, với m số cột
   a[i][j] = b[i*m + j]

Cách biểu diễn thuật toán

Trong trường hợp này, tôi sử dụng ngôn ngữ giả.

Declare int a[2,3] ={{3,7,9},{2,4,1}},b[6], i,j, n,m,k

n= a.lengh

m=a[0].lengh

// Đổ dữ liệu từ mảng hai chiều sang mảng một chiều

Loop i=0 to n-1

   Loop j=0 to m-1

      b[i*m +j] = a[i][j]

// Gọi lệnh sắp xếp mảng b

bubble_sort(b);

// Đổ dữ liệu từ mảng một chiều b sang mảng 2 chiều a

Loop i=0 to n-1

   Loop j=0 to m-1

      a[i][j]= b[i*m +j]

Ngoài ra,  bạn cũng có thể tự Dry Run để kiểm tra kết quả.

Bài tiếp: Các thuật toán cơ bản về chuỗi

Bài trước: Các thuật toán cơ bản về mảng hai chiều

Chuỗi về cơ bản nó là một mảng một chiều mà các phần tử là các ký tự. Tuy nhiên, chuỗi có một số bài toán đặc thù mà bạn hay gặp như:

• Tìm một ký tự trong chuỗi
• Đếm số ký tự trong chuỗi
• Tìm một chuỗi con trong một chuỗi
• Đảo ngược chuỗi
• Tách chuỗi

Đây là các bài toán thường gặp, với hy vọng sẽ giúp bạn tự tin hơn khi làm việc với chuỗi.

Bài 1: Viết chương trình khởi tạo một chuỗi, sau đó nhập vào một ký tự c rồi đếm số lần ký tự c xuất hiện trong chuỗi.

Phân tích và tìm cách giải

• Đầu vào: s=”IVIETTECH”, giá trị c
• Đầu ra: In ra thông báo số lần c xuất hiện trong chuỗi
• Phân tích:
  • Nhập vào ký tự c
  • Khởi tạo biến đến count=0
  • Duyệt qua chuỗi s và tăng count lên 1 mỗi khi gặp chuỗi c

Cách biểu diễn thuật toán

Trong trường hợp này, tôi sử dụng ngôn ngữ giả.

Declare   String s=”IVIETTECH”

char c

int count=0

Input c

Loop i=0 to s.lengh -1

   If(c=s[i] Or upper(c)=s[i])

      Count=count +1

If coun>0

   Print c + ‘xuat hien ’ + count + ‘ lan trong chuoi ’ + s

Else

   Print c + ‘ khong co trong chuoi trong chuoi’ + s

 Yêu cầu mở rộng bài toán trên

Bạn thay đổi chương trình trên để có thể đếm số ký tự  trong chuỗi và in ra số lần xuất hiện của các ký tự trong chuỗi đó.

Ví dụ: s={IVIETTECH}

Kết quả in ra:

I – 2

V-1

E-2

T-2

C-1

H-1

Hướng dẫn

• Viết một hàm nhận ký tự cần đếm và vị trí của ký tự đó. Ví dụ countChar(String s, char c, int i)
• Trong đó:
  1. Lặp từ 0 -> đến i-1 nếu ký tự đó đã xuất hiện thì thoát khỏi hàm (đã đếm rồi).
  2. Lặp từ i đến cuối chuỗi, đến số lần xuất hiện của ký tự đó
  3. In ký tự đó ra theo dạng c-count
• Trong hàm main cho lặp từ đầu đến cuối chuỗi và gọi hàm countChar ở trên để đếm và in ra.

Bài tiếp: Thuật toán tìm chuỗi con

Bài trước: Thuật toán đổ dữ liệu về mảng một chiều và ngược lại

Tìm một chuỗi con trong một chuỗi có sẵn là bài toán thường gặp. Hầu hết các ngôn ngữ lập trình đều cung cấp hàm này. Tuy nhiên, nếu bạn nhận được yêu cầu viết chương trình để thực hiện điều này thì bạn sẽ làm thế nào. Bài dưới đây sẽ nói về điều đó.

Yêu cầu

Viết chương trình khởi tạo một chuỗi, sau đó nhập một chuỗi mới và kiểm tra xem chuỗi mới có xuất hiện trong chuỗi đã có trước đó hay không?

Phân tích và tìm cách giải

• Đầu vào: s=”thanh pho da nang”, Chuỗi mới s1={nang}
• Đầu ra: In ra thông báo chuỗi s1 có xuất hiện trong chuỗi s hay không?
• Phân tích:

– Bạn cần lấy chữ đầu tiên của chuỗi s1 để so sánh với các ký tự của s.

– Nếu không có ký tự nào khớp bạn sẽ thông báo ngay s1 xuất hiện trong s.

– Nếu có ký tự khớp bạn so sánh hết các ký tự của chuổi s1 và các ký tự của chuỗi s tương ứng từ vị trí khớp.

    + Nếu khớp hoàn toàn bạn thông báo đã tìm thấy

    + Nếu không khớp hoàn toàn bạn quay lại vòng lặp chính để thực hiện cho đến vị trí k=s.length-s1.length

Cách biểu diễn thuật toán

Trong trường hợp này, tôi sử dụng ngôn ngữ giả.

Declare   String s="thanh pho da nang", s1

Boolean found=false

Int i,j

Input s1

If s1.lenght >s.length

   Print "Chuoi can tim phai ngan hon chuoi chua no"

   Exit

Else {

   Loop i from 0 to s.length – s1.lenght

     If(s[i]=s1[0]) then {

        found=true

        Loop j from 1 to s1.length-1 {

           if s[i+j]<>s[j] then

              found=false

              break //Thoát khỏi vòng lặp j
         }

        if found then break //thoát khỏi vòng lặp I vì đã tìm thấy
      }

   If found

      Print s1 + ‘ chua trong chuoi ’ + s

   Else

      Print s1 + ‘ khong co trong chuoi ’ + s
}

Bài tiếp: Thuật toán tách chuỗi

Bài trước: Các thuật toán cơ bản về chuỗi

Tách chuỗi cũng là bài toán thường gặp và trong hầu hết các ngôn ngữ lập trình đều hỗ trợ sẵn yêu cầu này. Tuy nhiên, trong bài này tôi vẫn muốn trình bày lại để bạn có trải nghiệm thêm.

Yêu cầu

Viết chương trình khởi tạo một chuỗi, sau đó nhập vào một ký tự ngăn cách, sau đó dựa vào ký tự đó để tách chuỗi đó ra thành các chuỗi con và in các chuỗi con ra.

Ví dụ: Nguyen Van An, ký tự phân cách là dấu ‘ ’

Kết quả:

Nguyen

Van

An

Phân tích và tìm cách giải

• Đầu vào: s={Nguyen Van An}, Ký tư phân cách ‘ ’
• Đầu ra: In ra các dòng:

Nguyen

Van

An

Phân tích

– Cần duyệt qua tất cả các ký tự của chuỗi S

  Kiểm tra nếu ký tự bằng ký tự ngăn cách

    + In chuỗi con ra

    + Xóa chuỗi con để nạp lại từ đầu

  Nếu không

    +Thêm ký tự vào chuỗi con

Cách biểu diễn thuật toán

Trong trường hợp này, tôi sử dụng ngôn ngữ giả.

Declare   String s={Nguyen Van An}, sc=’’

Char c=’ ’

Int i

Loop i from 0 to s.length -1

   If s[i]=c

      Print sc

      sc=’’

   Else

      sc=sc+s[i]

Đến đây thì chuỗi đã được tách.

Bài tiếp: Các thuật toán về danh sách đối tượng

Bài trước: Thuật toán tìm chuỗi con

Thuật toán về danh sách đối tượng sẽ cung cấp và hướng dẫn bạn một cách cơ bản các thao tác khi làm việc với danh sách các đối tượng từ đó bạn sẽ tự tin hơn khi làm việc với loại bài toán này.

Lập trình hướng đối tượng đã trở nên phổ biến và là lựa chọn trong hầu hết các ngôn ngữ lập trình. Do vậy các thuật toán liên quan đến đối tượng cũng là vấn đề bạn thường xuyên gặp. Thực tế thì nó cũng hoàn toàn giống như thuật toán trên các phần tử có kiểu dữ liệu nguyên thủy. Tuy nhiên, nếu lần đầu gặp bạn cũng gặp nhiều bỡ ngỡ.

Bài viết Các thuật toán về danh sách đối tượng sẽ giúp bạn làm quen, các bài toán phổ biến như:

•  Tính toán
•  Tìm kiếm
•  Sắp xếp

Đây là các bài toán thường gặp, với hy vọng sẽ giúp bạn tự tin hơn khi làm việc với danh sách các đối tượng. Tuy nhiên, phần này bạn nên tìm hiểu trong môn học Lập trình hướng đối tượng thì sẽ được giải thích kỹ hơn.

Bài 1: Viết chương trình khởi tạo một danh sách các học sinh với mỗi học sinh bao gồm các thông tin như sau: Mã học sinh, Tên học sinh, Lớp, Điểm môn Toán, Điểm môn Văn. Sau đó tìm ra học sinh có điểm Trung bình cao nhất (Điểm trung bình = (Điểm môn Toán + Điểm môn Văn)/2).

Phân tích và tìm cách giải

•  Khai báo một lớp Student{studentCode, studentName, batch, mathScore, LiteratureScore}
•  Nhập vào danh sách sinh viên
•  Xem phần tử đầu tiên (max) là phân tử có điểm trung bình cao nhất
•  Cho lặp biến i từ 0 đến n-1 với n là kích thước của mảng:
     + Nếu a[i].getAvg() >max.getAv thì max=a[i]
•  In max ra ta sẽ được giá trị lớn nhất

Cách biểu diễn thuật toán

Trong trường hợp này, tôi sử dụng ngôn ngữ giả.

//Khai bao lop Student

Class Student{

   Int studentCode // Mã sinh viên

   String studentName // Tên sinh viên

   String batch // Tên lớp

   Double mathScore    //Điểm môn toán

   Double literatureScore   //Điểm môn văn

//Viết các getter và setter ở đây

// Viết hàm tính điểm Trung bình

Double getAvg(){

   Return  (mathScore + literatureScore)/2

}

}

Declare List<Student> studentList

Input(List<student> studentList){

   Boolean choice=true

   Loop choice

      new student

      Input student.setStudentCode

      Input student.setStudentName

      Input student.setBatch

      Input student.setMathScore

      Input student.setLiteratureScore

      studentList.add(student)  //Thêm student vào danh sách

      Input choice // Thay đổi giá trị choice

}

FindMax(List<Student> studentList){

   Student max = studentList.get(0)

   Loop i=1 to studentList.length-1

      If studentList.get(i).getAvg()>max.getAvg()

         max=studentList.get(i)

   Print max

}

Bài tiếp: Thuật toán sắp xếp danh sách đối tượng

Bài trước: Thuật toán tách chuỗi

Sắp xếp danh sách đối tượng là bài toán thường gặp, nếu các ngôn ngữ mạnh về lập trình hướng đối tượng và đã có sẵn hàm sắp xếp thì bạn chỉ cần khai báo Interface cho lớp thì có thể dùng được. Nếu bạn không thích dùng Interface thì có thể tham khảo bài này.

Bài 1: Viết chương trình khởi tạo một danh sách các học sinh với mỗi học sinh bao gồm các thông tin như sau: Mã học sinh, Tên học sinh, Lớp, Điểm môn Toán, Điểm môn Văn. Sau đó sắp xếp học sinh theo thứ tự giảm dần theo kết quả học tập. Kết quả học tập được hiểu theo điểm trung bình của các môn (Điểm trung bình = (Điểm môn Toán + Điểm môn Văn)/2).

Phân tích và tìm cách giải

•  Khai báo một lớp Student{studentCode, studentName, batch, mathScore, LiteratureScore}
•  Nhập vào danh sách sinh viên
•  Sử dụng thuật toán nổi bọt để sắp xếp danh sách theo điểm trung bình

Cách biểu diễn thuật toán sắp xếp danh sách đối tượng

Trong trường hợp này, tôi sử dụng ngôn ngữ giả.

//Khai bao lop Student

Class Student{

   Int studentCode // Mã sinh viên

   String studentName // Tên sinh viên

   String batch // Tên lớp

   Double mathScore    //Điểm môn toán

   Double literatureScore   //Điểm môn văn

   //Viết các getter và setter ở đây

   // Viết hàm tính điểm Trung bình

   Double getAvg(){

   Return  (mathScore + literatureScore)/2

   }

}

Declare List<Student> studentList

Input(List<student> studentList){

   Boolean choice=true

   Loop choice

   new student

   Input student.setStudentCode

   Input student.setStudentName

   Input student.setBatch

   Input student.setMathScore

   Input student.setLiteratureScore

   studentList.add(student)  //Thêm student vào danh sách

   Input choice // Thay đổi giá trị choice

}

// Sắp xếp danh sách học sinh

SortStudentList(List<Student> studentList){

   Student temp;

   Loop i=0 to studentList.length-2

      Loop j=i+1 to studentList.length-1

         If(studentList.get(i).getAvg()< studentList.get(j).getAvg())then

            temp= studentList.get(i)

            studentList.set(i, studentList.get(j))

            studentList.set(j, temp)

   PrintStudentList(studentList)

}

// In danh sách học sinh trong list

PrintStudentList(List<Student> studentList){

   Loop each student in list

Print student

}

Như đã nói ngay từ đầu phần này giúp bạn làm quen với cách biểu diễn thuật toán, còn chi tiết về các thuật toán của phần hướng đối tượng bạn cần nghiên cứu kỹ trong môn học Lập trình hướng đối tượng.

Bài tiếp: Các thuật toán đệ quy

Bài trước: Các thuật toán về danh sách đối tượng