Bài 8 - Mảng (Array) (3)

Sau hai bài hướng dẫn về mảng một chiều và mảng nhiều chiều . Các bạn đã có những cái nhìn tổng quan hơn về Mảng. Hôm nay mình sẽ giới thiệu cho các bạn giải thuật cơ bản về sử dụng mảng .

Đó là sắp xếp và tìm kiếm đối với mảng . Bởi vì sau này các bạn có thể dùng một list (danh sách) các đối tượng , thực hiện tìm kiếm hay sắp xếp theo thứ tự . ... Sau loạt bài này các bạn sẽ có cách tuy duy rất căn bản đối với các giải thuật cơ bản về danh sách các đối tượng.

I. Tìm kiếm
Có rất nhiều phương pháp cũng như thuật toán tìm kiếm . Nhưng ở đây mình sẽ giới thiệu cho các bạn 2 phương pháp căn bản.
1. Tìm kiếm tuyến tính(Linear Search Approach).
Tìm kiếm tuyến tính hay tìm kiếm tuần tự là bắt đầu bằng việc so sánh x với a₁; khi x=a₁, nghiệm là vị trí a₁, tức là 1; khi x¹a₁, so sánh x với a₂. Nếu x=a₂, nghiệm là vị trí của a₂, tức là 2. Khi x¹a₂, so sánh x với a₃. Tiếp tục quá trình này bằng cách tuần tự so sánh x với mỗi số hạng của bảng liệt kê cho tới khi tìm được số hạng bằng x, khi đó nghiệm là vị trí của số hạng đó. Nếu toàn bảng liệt kê đã được kiểm tra mà không xác định được vị trí của x, thì nghiệm là 0 .

Kết quả:

int[] list = {1, 4, 4, 2, 5, -3, 6, 2};
int i = linearSearch(list, 4);  // returns 1
int j = linearSearch(list, -4); // returns -1
int k = linearSearch(list, -3); // returns 5

2. Tìm kiếm nhị phân(Binary Search Approach)

Thuật toán này có thể được dùng khi bảng liệt kê có các số hạng được sắp theo thứ tự tăng dần. Chẳng hạn, nếu các số hạng là các số thì chúng được sắp từ số nhỏ nhất đến số lớn nhất hoặc nếu chúng là các từ hay xâu ký tự thì chúng được sắp theo thứ tự từ điển. Thuật toán thứ hai này gọi là thuật toán tìm kiếm nhị phân. Nó được tiến hành bằng cách so sánh phần tử cần xác định vị trí với số hạng ở giữa bảng liệt kê. Sau đó bảng này được tách làm hai bảng kê con nhỏ hơn có kích thước như nhau, hoặc một trong hai bảng con ít hơn bảng con kia một số hạng. Sự tìm kiếm tiếp tục bằng cách hạn chế tìm kiếm ở một bảng kê con thích hợp dựa trên việc so sánh phần tử cần xác định vị trí với số hạng giữa bảng kê. Ta sẽ  thấy rằng thuật toán tìm kiếm nhị phân hiệu quả hơn nhiều so với thuật toán tìm kiếm tuyến tính.Các bạn để ý vào hình vẽ dưới sẽ hiểu tường minh hơn

Giải thuật :

public class BinarySearch {
 /** Use binary search to find the key in the list */
 public static int binarySearch(int[] list, int key) {
  int low = 0;
  int high = list.length - 1;

  while (high >= low) {
   int mid = (low + high) / 2;
   if (key < list[mid])
    high = mid - 1;
   else if (key == list[mid])
    return mid;
   else
    low = mid + 1;
  }
  return -low - 1;
 }

 public static void main(String[] args) {
  int array[] = { 1, 2, 3, 5, 7, 4, 6 };
  Scanner in = new Scanner(System.in);
  System.out.println("nhap key:");
  int key = in.nextInt();  
  System.out.println("Key vi tri " + (binarySearch(array, key) + 1));
 }
}

II. Sắp sếp (sort)

Mình sẽ giới thiệu cho các bạn những thuật toán sắp xếp cơ bản . Để sau này các bạn có thể trả lời phỏng vấn một cách nguy hiểm hơn . Có thể các bạn biết nhưng thuật toán này . Tuy nhiên khi hỏi tới các bạn lại không biết tên nó , hoặc không diễn đạt được nổi nó.

1.Selection Sort

Định nghĩa giải thuật :

Lần lượt chọn phần tửnhỏnhất trong dãy chỉsố k1, k2,. . ., kn với i = 0, 1, . .,n; ki< k i+1< . . ., kn và đổi chỗ cho phần tử thứ ki. Như vậy, sau j =n-1 lần chọn, chúng ta sẽ só dãy khoá được sắp xếp theo thứ tự tăng dần. Đối với dãy số trên, 

chúng ta sẽ thực hiện như sau: 

* Lần chọn thứ 0: Tìm trong khoảng từ 0 đến n-1bằng cách thực hiện n- 1 lần so 

sánh để xác định phần tử min0 và đổi chỗ cho phần tử ở vị trí 0.

* Lần chọn thứ 1: Tìm trong khoảng từ 1 đến n-1 bằng cách thực hiện n- 2 lần so sánh để xác định phần tử min1 và đổi chỗ cho phần tử ở vị trí 1. 

.....................................................................................................................................

* Lần chọn thứ i: Tìm trong khoảng từ i đến n-1 bằng cách thực hiện n- i lần so sánh để xác định phần tử mini và đổi chỗ cho phần tử ở vị trí i. 

* Lần chọn thứ n-2: Tìm trong khoảng từ n-2 đến n-1 bằng cách thực hiện 1 lần so 

sánh để xác định phần tử min n-2 và đổi chỗ cho phần tử ở vị trí n-2. 

Cụ thể sẽ được mô tả dưới hình sau :

Giải thuật :

public static void selectionSort(double[] list) {
 double currentMax;
 currentMax = list[0];
 int currentMaxIndex = 0;
 for (int i = list.length - 1; i >= 1; i--)
 // Find the maximum in the list[0..i]
 {
  for (int j = 1; j <= i; j++) {
   if (currentMax < list[j]) {
    currentMax = list[j];
    currentMaxIndex = j;
   }
  }
  // Swap list[i] with list[currentMaxIndex] if necessary;
  if (currentMaxIndex != i) {
   list[currentMaxIndex] = list[i];
   list[i] = currentMax;
  }
 }
}

2. Insertion Sort

Insert Sort được thực hiện dựa trên kinh nghiệm của những người chơi bài. Khi có i-1 lá bài đã được sắp xếp đang ở trên tay, nay ta thêm lá bài thứ i thì lá bài đó được so sánh với lá bài i-1, i-2, . . để tìm được vị trí thích hợp và chèn vào quân bài thứ i.

Nguyên tắc thực hiện như sau :

* Lấy phần tử đầu tiên i0, đương nhiên tập một phần tử là tập đã được sắp xếp. 

* Lấy tiếp phần tử thứ i1 chọn vị trí thích hợp của phần tử thứ i1 trong tập hai phần tử và thực hiện đổi chỗ.

* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

* Lấy tiếp phần tử thứ ik chọn vị trí thích hợp của phần tử thứ ik trong tập hai ik-1 phần tử và thực hiện đổi chỗ, dãy sẽ được sắp xếp hoàn toàn sau n-1 lần chèn phần tử vào vị trí thích hợp. 

Cụ thể như hình vẽ sau :

Giải thuật :

public static void insertionSort(double[] list) {
 for (int i = 1; i < list.length; i++) {
  /**
   * insert list[i] into a sorted sublist list[0..i-1] so that
   * list[0..i] is sorted.
   */
  double currentElement = list[i];
  int k;
  for (k = i - 1; k >= 0 && list[k] > currentElement; k--) {
   list[k + 1] = list[k];
  }
  // Insert the current element into list[k+1]
  list[k + 1] = currentElement;
 }
}

3 . Sắp xếp nổi bọt (Bubble Sort)

Bubble Sort được thực hiện bằng cách đổi chỗ liên tiếp hai phần tử kế cận khi chúng ngược thứ tự. Quá trình thực hiện được duyệt từ đáy lên đỉnh. Như vậy, sau lần duyệt thứ nhất,phần tử lớn nhất sẽ được xếp đúng ở vị trí thứ n-1, ở lần duyệt thứ k thì k phần tử lớn nhất đã được xếp đúng vị trí n-1, n-2, . ., n-k+1. Sau lần duyệt thứ n-1, toàn bộ n phần tử sẽ được sắp xếp. Với phương pháp này, các phần tử có giá trị nhỏ được nổi dần lên như nước sủi bọt nhờ đó nó có tên gọi “phương pháp sủi bọt”.

Giải thuật :

public void bubbleSort(int [] array){
 for(int i = 0; i< array.length; i++){
            for (int j = array.length - 1; j > 0; j--) {
               if(array[j] < array[j-1]){
                   int temp = array[j];
                   array[j] = array[j-1];
                   array[j-1] = temp;
               }
           }    
       }
}

4. Quick Sort

Quick Sort là chọn ngẫu nhiên một phần tử nào đó của dãy làm khoá chốt. Tính từ khoá chốt, các phần tử nhỏ hơn khoá phải được xếp vào trước chốt (đầu dãy), mọi phần tử sau chốt được xếp vào sau chốt (cuối dãy). Để làm được việc đó, các phần tử trong dãy sẽ được so sánh với khoá chốt và tráo đổi vị trí cho nhau, hoặc cho khoá chốt nếu phần tử đó lớn hơn chốt mà lại nằm trước chốt hoặc nhỏ hơn chốt nhưng lại nằm sau chốt. Khi việc đổi chỗ lần đầu tiên đã thực hiện xong thì dãy hình thành hai đoạn: một đoạn bao gồm các phần tử nhỏ hơn chốt, một đoạn gồm các phần tử lớn hơn chốt, còn chốt chính là vị trí của phần tử trong dãy được sắp xếp.

Áp dụng cho mỗi đoạn trước chốt và sau chốt cho tới khi các đoạn còn lại hai phần tử thì việc ghi nhớ không còn cần thiết nữa. Dãy sẽ được sắp xếp khi tất cả các đoạn được xử lý xong. Ví dụ với dãy:

42  23 74 11 65 58 94 36 99 87

Ta chọn chốt đầu tiên là 42. Để phát hiện ra hai khoá cần đổi chỗ cho nhau, ta dùng hai biến i, j với giá trị ban đầu i=2, j=10. Nếu ki< 42 thì tiếp tục tăng i và lặp lại cho tới khi 

gặp phần tử thứ  ki>42. Duyệt các phần tử thứ kj với 42 nếu kj> 42 thì j giảm đi một, cho 

tới khi gặp phần tử thứ kj<42 thì phần tử thứ ki và kj được đổi chỗ cho nhau. Quá trình sẽ

được lặp lại với ki và kj  cho tới khi i=j chính là vị trí dành cho khoá 42. Cuối cùng chúng ta 

đổi chỗ 42 cho khoá cho kj.

Các bạn có thể tham khảo hình ảnh tại đây để có thể hiểu rõ hơn về nguyên lý của thuật toán quick sort

Giải thuật :

// Tìm chốt
 public int findPivot(int i, int j, int[] array) {
         if (array.length == 1) {
             return -1;
         }
         int k = i + 1;
         int pivot = array[i];

         while ((k <= j) && (array[k] == pivot)) {
             k++;
         }
         if (k > j) {
             return -1;
         }
         if (array[k] > pivot) {
             return k;
         } else {
             return i;
         }
     }

 // Tìm partition
 public int pointPartition(int i, int j, int pivotKey, int[] array) {
       int partition = -1;
         int L = i;
         int R = j;
         while (L <= R) {
             while (array[L] < pivotKey)
                 L++;
             while (array[R] >= pivotKey)
                 R--;
             if (L < R) {
                 int temp = array[L]; 
                 array[L] = array[R];
                 array[R] = temp;
             }
         }
         partition = L;
         return partition;  
     }

    // Sắp xếp
     public void quickSort(int i, int j, int[] array) {
         int pivot = findPivot(i, j, array);
         if (pivot == -1)
             return;
         int partition = pointPartition(i, j, array[pivot], array);
         quickSort(i, partition - 1, array);
         quickSort(partition, j, array);
    }

OK như vậy là cũng ổn rồi . Bây giờ là bài tập vận dụng của các bạn . Hãy chăm chỉ lên nào các chiến binh.

Bài 1 :Viết chương trình nhập vào vào mảng A có n phần tử, các phần tử là những số nguyên lớn hơn 0 và nhỏ hơn 100 được nhập vào từ bàn phím. Thực hiện các chức năng sau

a)      Tìm phần tử lớn nhất và lớn thứ 2 trong mảng cùng chỉ số của các số đó.

b)      Sắp xếp mảng theo thứ tự giảm dần (Sử dụng một trong các thuật toán sắp xếp ở trên).

c)Nhập một số nguyên x và chèn x vào mảng A sao cho vẫn đảm bảo tính sắp xếp giảm dần

Note : Trong source code mình làm theo hướng khác để các bạn hiểu thêm về cách làm.

Bài 2 : Nhập số n và dãy các số thực  a₀ , a₁ ,..., a_n-1. Không đổi chỗ các phần tử và không dùng thêm mảng số thực nào khác (có thể dùng mảng số nguyên nếu cần) hãy cho hiện trên màn hình dãy trên theo thứ tự tăng dần

Bài 3 : Viết chương trình thử nghiệm các thuật toán trên một dãy n số nguyên ngẫu nhiên (10<n<100)

a)      Sắp xếp chọn

b)      Sắp xếp chèn

c)      Sắp xếp nổi bọt

d)     Sắp xếp nhanh

e)      Sắp xếp trộn (bổ sung)

f)       Sắp xếp vun đống (Heap Sort) (bố sung)

Source code : here

Pass extract : https://coderandtutorial.blogspot.com

Bài 8 - Mảng( Array) (2)

Sau loạt bài trước mình đã hướng dẫn các bạn về mảng 2 chiều . Hôm nay mình sẽ hướng dẫn các bạn tiếp về cách sử dụng mảng 2 chiều và mảng nhiều chiều .
Mảng 2 chiều là mảng của mảng 1 chiều . Nghe có vẻ lủng củng , nhưng thực chất nó chính là như vậy.
I. Cú pháp

dataType[][] arrayRefVar;

hoặc :

dataType arrayRefVar[][];

ví dụ :

int[][] matrix;

or

int matrix[][];

Cách tạo một mảng mới nó như thế nào : matrix = new int[5][5];

Mảng vừa tạo có 25 phần tử.
Gán giá trị cho mảng 2 chiều cũng phức tạp hơn mảng 1 chiều . Cụ thể 

Đôi khi các bạn thường hay nhầm lẫn hay lúng túng mỗi khi nhập mảng . Thì thứ tự nó sẽ được thực hiện cụ thể như sau :
Ví dụ tôi nhập một mảng 2 chiều có 3 hàng và 4 cột :

Cứ nhập theo tuần tự Hàng hết xong tới cột
Ngoài ra chúng ta có thể khai báo mảng khuyết như sau :

Thực chất mảng khuyết trên nó là dạng này:

int[][] triangleArray = new int[5][];
triangleArray[0] = new int[5];
triangleArray[1] = new int[4];
triangleArray[2] = new int[3];
triangleArray[3] = new int[2];
triangleArray[4] = new int[1];

II. Một số cách sử dụng mảng 2 chiều
* khởi tạo mảng 2 chiều với n giá trị

for(int row = 0; row < matrix.length; row++) {
  for (int column = 0; column < matrix[row].length; column++) {
    matrix[row][column] = (int)(Math.random() * 100);
  }
}

* Cách hiển thị mảng 2 chiều

for (int row = 0; row < matrix.length; row++) {
  for (int column = 0; column < matrix[row].length; column++) {
    System.out.print(matrix[row][column] + " ");
  }

  System.out.println();
}

* Tổng các phần tử

int total = 0;
for (int row = 0; row < matrix.length; row++) {
  for (int column = 0; column < matrix[row].length; column++) {
    total += matrix[row][column];
  }
}

* Tổng các phần tử của cột

 for (int column = 0; column < matrix[0].length; column++) {

  int total = 0;
  for (int row = 0; row < matrix.length; row++)
    total += matrix[row][column];
  System.out.println("Sum for column " + column + " is " + total);
}

* Số lớn nhất của hàng

int maxRow = 0;
int indexOfMaxRow = 0;

// Get sum of the first row in maxRow
for (int column = 0; column < matrix[0].length; column++) {
  maxRow += matrix[0][column];
}

for (int row = 1; row < matrix.length; row++) {
  int totalOfThisRow = 0;
  for (int column = 0; column < matrix[row].length; column++) {
    totalOfThisRow += matrix[row][column];
    if (totalOfThisRow > maxRow) {
      maxRow = totalOfThisRow;
      indexOfMaxRow = row;
    }
  }
}

System.out.println("Row " + indexOfMaxRow 
   + " has the maximum sum" + " of " + maxRow); 

Chú ý : Đối với mảng 2 chiều thì như vậy . Tương tự với mảng 3 chiều , 4 chiều ,... n chiều cũng chỉ là dạng mảng của mảng của mảng mà thôi . Các bạn nắm chắc mảng 2 chiều thì có vạn chiều các bạn cũng hoàn toàn có thể làm được
Sau đây là các ví dụ cụ thể và hoàn chỉnh hơn về cách sử dụng mảng nhiều chiều .
III. Ví dụ vận dụng
Ví dụ  :

Viết chương trình nhập vào vào ma trận A có n dòng, m cột, các phần tử là những số nguyên lớn hơn 0 và nhỏ hơn 100 được nhập vào từ bàn phím. Thực hiện các chức năng sau:

a)Tìm phần tử lớn nhất của ma trận cùng chỉ số của số đó.

b)      Tìm và in ra các phần tử là số nguyên tố của ma trận (các phần tử không nguyên tố thì thay bằng số 0).

c)      Sắp xếp tất cả các cột của ma trận theo thứ tự tăng dần và in kết quả ra màn hình.

public class Ex1_UseArray2 {
 public static int nhap() {
  Scanner input = new Scanner(System.in);
  boolean check = false;
  int n = 0;
  while (!check) {
   System.out.print(" ");
   try {
    n = input.nextInt();
    check = true;
   } catch (Exception e) {
    System.out.println("Ban phai nhap so! hay nhap lai...");
    input.nextLine();
   }
  }
  return (n);
 }
 public static boolean checkSNT(int n) {
  if (n > 1) {
   for (int i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0)
     return false;
   }
   return true;
  } else
   return false;
 }
 public static void inMT(int[][] A, int n, int m) {
  int i, j;
  for (i = 0; i < n; i++) {
   System.out.print("\n");
   for (j = 0; j < m; j++)
    System.out.print(" " + A[i][j]);
  }
 }
 public static int findMaxMT(int[][] A, int n, int m) {
  int Max = A[0][0];
  for (int i = 0; i < n; i++) {
   for (int j = 0; j < m; j++) {
    if (Max < A[i][j])
     Max = A[i][j];
   }
  }
  return (Max);
 }
 // Tim nhung phan tu la SNT
 public static void phanTuSNT(int[][] A, int n, int m) {
  int count = 0, i, j;
  System.out.println("\nCac phan tu la SNT (nhung phan tu ko la SNT =0): ");
  for (i = 0; i < n; i++) {
   System.out.print("\n");
   for (j = 0; j < m; j++) {
    if (checkSNT(A[i][j])) {
     count++;
     System.out.print(" " + A[i][j]);
    } else
     System.out.print(" " + 0);
   }
  }
  System.out.println("\n Co " + count + " phan tu la so nguyen to");
 }
 // Sap xep cac cot theo thu tang dan
 public static void sortColum(int[][] A, int n, int m) {
  int i, j, temp;
  for (j = 0; j < m; j++) {
   for (i = 1; i < n; i++) {
    if (A[i - 1][j] > A[i][j]) {
     temp = A[i - 1][j];
     A[i - 1][j] = A[i][j];
     A[i][j] = temp;
    }
   }
  }
  inMT(A, n, m);
 }
 public static void main(String[] args) {
  System.out.print("Nhap so hang n=");
  int n = nhap();
  System.out.print("Nhap so cot m=");
  int m = nhap();
  int[][] A = new int[n][m];
  int i, j;
  for (i = 0; i < n; i++) {
   for (j = 0; j < m; j++) {
   System.out.println("Nhap phan tu thu A[" + (i + 1) + "]["
      + (j + 1) + "]= ");
    A[i][j] = nhap();
   }
  }
  System.out.println("Ma tran nhap vao: ");
  inMT(A, n, m);
  for (i = 0; i < n; i++) {
   for (j = 0; j < m; j++) {
   if (A[i][j] == findMaxMT(A, n, m))
  System.out.println("\nPhan tu o hang " + i + " cot " + j
   + " dat Max: A[" + i + "][" + j + "]= " + A[i][j]);
   }
  }

  phanTuSNT(A, n, m);
  sortColum(A, n, m);
 }
}

Sau đây là bài tập để các bạn luyện tập . Hãy nhỡ luyện tập thường xuyên để có được kết quả ngọt ngào nhất nhé.

Bài 1 :Viết chương trình nhập vào vào ma trận A có n dòng, m cột, các phần tử là những số
nguyên lớn hơn 0 và nhỏ hơn 100 được nhập vào từ bàn phím. Thực hiện các chức
năng sau:

a)     Tìm phần tử lớn nhất của ma trận cùng chỉ số của số đó.

b)     Tìm và in ra các phần tử là số nguyên tố của ma trận
(các phần tử không nguyên tố thì thay bằng số 0).

c )Tìm hàng trong ma trận có nhiều số nguyên tố nhất

Bài 2 :Viết chương trình nhập các hệ số của đa thức P bậc n (0<n<20). Thực hiện các chức năng sau:

a)      Tính giá trị của đa thức P theo công thức Horner:

 P(x)=((((a_nx+ a_n-1)x+ a_n-2... + a₁)x+ a₀

b)      Tính đạo hàm của đa thức P. In ra các hệ số của đa thức kết quả.

c)      Nhập thêm đa thức Q bậc m. Tính tổng hai đa thức P và Q. 

Source code : here

pass extract : https://coderandtutorial.blogspot.com

Bài 8 - Mảng (Array) (1)

Tiếp tục loạt bài hướng dẫn Java tutorial . Hôm nay mình sẽ giới thiệu cho các bạn về cách tạo mảng , sử dụng mảng và các giải thuật liên quan tới mảng.

Mảng là một tập hợp các phần tử có chung kiểu ,được biểu diễn thành một đối tượng tổ hợp . Mảng có thể là kiểu số , kiểu ký tự , kiểu đối tượng....

I . Cách khai báo mảng một chiều

Cú pháp :

dataType[] arrayRefVar; hoặc dataType arrayRefVar[];

Cách tạo một mảng một chiều mới .

dataType[] arrayRefVar = new dataType[arraySize];

Ví dụ :

double[] myList = new double[10];

Có nghĩa là khai báo một mảng có 10 phẩn tử kiểu dữ liệu của mỗi phần tử là double.

Như các bài hướng dẫn trước mình có nhắc tới bộ nhớ heap . Thì khi tạo mới một mảng thì sẽ tạo 1 ô nhớ trên bộ nhớ máy , lưu trữ đối tượng mảng , và bộ nhớ này tiếp tục lưu trữ địa chỉ của các phần tử của mảng , rồi reffer tới nó.

Chính vì tính khả chuyển và linh động thế này của mảng nên ta có thể gọi lấy giá trị của một phần tử bất kỳ của mảng .

Ví dụ mình muốn lấy phần tử thứ 9 trong mảng myList trên.

arrayRefVar[index];

double a = myList[9]

Hoặc gán 1 giá trị của phần tử này bằng phép thực hiện toán tử của các phần tử khác

myList[2] = myList[0] + myList[1];

Cách gán giá trị cho mảng:

dataType[] arrayRefVar = {value0, value1, ..., valuek};

ví dụ :

double[] myList = {1.9, 2.9, 3.4, 3.5}; hoặc

double[] myList = new double[4];
myList[0] = 1.9;
myList[1] = 2.9;
myList[2] = 3.4;
myList[3] = 3.5;

hoặc

double[] myList;
myList = {1.9, 2.9, 3.4, 3.5};

Khi muốn nhập hoặc in ra nhiều phần tử chúng ta có thể thực hiện các vòng lặp để gán giá trị . Như bài trước tôi đã hướng dẫn:

for(int i = 0; i < myList.length; i++) {
  myList[i] = Math.random() * 100;
}//nhập phần tử

/* thực hiện vào ra với mảng */

for(int i = 0; i < myList.length; i++) {
  System.out.print(myList[i] + " ");
}//in phần tử

vì vậy sử dụng mảng rất là tiện lợi ví dụ :

//Tính tổng tất cả các phần tử

double total = 0;

for (int i = 0; i < myList.length; i++) {
  total += myList[i];
}

//Tìm phần tử lớn nhất

double max = myList[0];
for (int i = 1; i < myList.length; i++) {
  if (myList[i] > max) max = myList[i];
}

// Tìm phần tử có chỉ số nhỏ nhất có giá trị lớn nhất

double max = myList[0];
int indexOfMax = 0;
for (int i = 1; i < myList.length; i++) {
  if (myList[i] > max) {
    max = myList[i];
    indexOfMax = i;
  }
}

II. Cơ chế copy Array

Khi ta thực hiện phép gán mảng có cùng số phần tử với nhau cho nhau . Nếu các bạn thực hiện gán nó như gán giá trị cho biến. Thì thực chất nó chỉ là thay đổi địa chỉ ô nhớ của mảng được gán bằng mảng bị gán . Cụ thể đó là:

Thực hiện phép gán 2 mảng : list2 = list1;

Vì vậy nên ta phải thực hiện copy từng phẩn tử trong mảng với nhau cụ thể.

int[] sourceArray = {2, 3, 1, 5, 10};
int[] targetArray = new int[sourceArray.length];
for (int i = 0; i < sourceArray.length; i++) {
  targetArray[i] = sourceArray[i];
}

III. Sử dụng array trong method.

public class Test {
  public static void main(String[] args) {
    int x = 1; // x represents an int value
    int[] y = new int[10]; // y represents an array of int values
    m(x, y); // Invoke m with arguments x and y
    System.out.println("x is " + x);
    System.out.println("y[0] is " + y[0]);
  }
  public static void m(int number, int[] numbers) {  
    number = 1001; // Assign a new value to number
    numbers[0] = 5555; // Assign a new value to numbers[0]
  }
}

Chúng ta thấy rằng method m được gọi thì x vẫn là 1, và y[0] = 5555. Bởi vì y tham chiếu tới cùng một mảng. Sau đó số y mới reffer tới giá trị của nó.

* Tương tự với trả về variable thì trả về mảng trong method cũng tương tự .

/** Count the occurrences of each letter */
   public static int[] countLetters(char[] chars) {
     // Declare and create an array of 26 int
     int[] counts = new int[26];
     // For each lowercase letter in the array, count it
     for (int i = 0; i < chars.length; i++) 
       counts[chars[i] - 'a']++;

     return counts;
   }

   /** Create an array of characters */
   public static char[] createArray() {
     // Declare an array of characters and create it
     char[] chars = new char[100];
     // Create lowercase letters randomly and assign
     // them to the array
     for (int i = 0; i < chars.length; i++) 
       chars[i] = RandomCharacter.getRandomLowerCaseLetter();
     // Return the array
     return chars;
} 

IV . Ví dụ cụ thể khi sử dụng array.

Ví dụ 1 :

Viết chương trình liệt kê tất cả các xâu nhị phân độ dài n.

public class Ex1_XauNhiPhan {
 public static int nhap() {
  Scanner input = new Scanner(System.in);
  boolean check = false;
  int n = 0;
  while (!check) {
   System.out.print(" ");
   try {
    n = input.nextInt();
    check = true;
   } catch (Exception e) {
    System.out.println("Ban phai nhap so! hay nhap lai...");
    input.nextLine();
   }
  }
  return (n);
 }
 public static void main(String[] args) {
  System.out.println("Nhap n");
  int n = nhap();
  int[] array = new int[n];
  int tich;
  do {
   tich = 1;
   // In ra mang va tinh tich cac phan tu trong mang
   System.out.println("");
   for (int j = 0; j < n; j++) {
    System.out.print(" " + array[j]);
    tich *= array[j];
   }
   int i = n - 1;
   do {
    if (array[i] == 0) {
     array[i] = 1;
     for (int j = n - 1; j > i; j--) {
      array[j] = 0;
     }
     break;
    } else
     i--;
   } while (i >= 0);
  } while (tich != 1);
 }
}

Ví dụ 2 :

Viết chương trình liệt kê tất cả các hoán vị của 1, 2, .., n

public class Ex2_LietKeHoanVi {
 public static int nhap() {
  Scanner input = new Scanner(System.in);
  boolean check = false;
  int n = 0;
  while (!check) {
   System.out.print(" ");
   try {
    n = input.nextInt();
    check = true;
   } catch (Exception e) {
    System.out.println("Ban phai nhap so! hay nhap lai...");
    input.nextLine();
   }
  }
  return (n);
 }
 public static void main(String[] args) {
  System.out.print("Nhap n");
  int n = nhap();
  int[] array = new int[n + 2];
  int i, j, k = n - 1, temp, check = 1;
  for (i = 0; i < n; i++) {
   array[i] = i + 1;
  }
  System.out.println("Cac hoan vi ke la: ");
  try {
  i = n - 2;
  while (check > 0) {
  // In ra hoan vi
  System.out.println("   ");
  for (j = 0; j < n; j++) {
   System.out.print(" " + array[j]);
  }
  for (i = n - 2; i >= 0; i--) {
  check = 1;
  if (array[i] < array[i + 1]) {
   if (i == n - 2) {
   temp = array[i];
   array[i] = array[n - 1];
   array[n - 1] = temp;
   break;
  } else {
 // Tim so a[k] nho nhat ma >a[i] trong cac so ben
 // phai a[i]
 k = i + 1;
 for (j = i + 1; j < n; j++) {
  if (array[i + 1] > array[j]
  && array[j] > array[i])
  k = j;
  }
 // Doi cho a[k] va a[i]
  temp = array[i];
  array[i] = array[k];
  array[k] = temp;
 // Sap xep lai tu a[i+1] toi a[n]
 for (j = i + 1; j < n; j++) {
  for (int m = i + 1; m < n; m++) {
  if (array[j] < array[m]) {
  temp = array[j];
  array[j] = array[m];
  array[m] = temp;
  }
 }
 }
 break;
 }
 } else {
  check = 0;
  // break;
 }
 }
 // if(i==0)check=0;
 }
} catch (Exception e) {
}
}
}

OK. Tạm thời mình tạm dừng tại đây .

Sau đây là bài tập để các bạn luyện tập thêm . Hãy tự giác luyện tập nhé.

Bài 1: Tính giá trị của đa thức  P(x)=a_nxⁿ+ a_n-1x^n-1+ ... + a₁x+ a₀ theo cách tính của Horner: P(x)=((((a_nx+ a_n-1)x+ a_n-2... + a₁)x+ a₀

Bài 2 :Viết chương trình nhập một số nguyên dương n và thực hiện các chức năng sau:

a)Tính tổng các chữ số của n.

b)Phân tích n thành các thừa số nguyên tố. 

Bài 3 :Nhập số liệu cho  dãy số thực  a₀ , a₁ ,..., a_n-1. Hãy liệt kê các phần tử  xuất hiện trong dãy đúng 2 lần

Source code : here

pass extract : https://coderandtutorial.blogspot.com

Bài 7 - Method (Phương thức)

Method hay là hàm . Để quy định một nhóm lệnh được thực hiện riêng lẻ , và được gọi bởi hàm main hoặc một hàm nào khác .
Như các bài trước tôi đã nói tới bộ nhớ stack . Để lưu trữ luồng xử lý . Thì hàm gọi tới hàm hay lệnh gọi tới hàm cũng là một luồng xử lý theo kiểu stack vậy.
1. Cách khai báo phương thức (method)

modifier returnValueType methodName(list of parameters) {
  // Method body;
}

Trong đó:
modifier: khả năng truy nhập
returnValueType : kiểu trả về (void , String , boolean , int , float , Object ...)
methodName : tên phương thức
list of parameters : danh sách các tham số dùng cho method ( có thể có 1 or n tham số hoặc có thể không có).
Ví dụ:

2. Cách gọi tới method
* method return ra giá trị :

int larger = max(3, 4);

* print giá trị của method:

System.out.println(max(3, 4));

* method gọi tới một method khác

public class TestMax {
 /** Main method */
   public static void main(String[] args) {
     int i = 5;
     int j = 2;
     int k = max(i, j);
     System.out.println("The maximum between " + i +
        " and " + j + " is " + k);
   }

    /** Return the max between two numbers */
   public static int max(int num1, int num2) {
     int result;
     if (num1 > num2)
        result = num1;
     else
       result = num2;
    return result; 
   }
 }

Trong chương trình trên các tham số i, j tương ứng:

3. Kết luận

Qua cách sử dụng phương thức (method) ta có thể chia nhỏ chương trình thành từng khối lệnh , thực hiện từng chức năng riêng  biệt để khiến cho chúng ta quản lý code đơn giản và dễ dàng hơn.

Sau đây là một số câu hỏi lý thuyết và bài tập vận dụng cho các bạn:

A. Lý thuyết (question)

Bài 1 : Kiểu trả về của hàm main ?(What is the return type of a main method?).

Bài 2 : Phát hiện và sửa chữa sai xót của chương trình sau :

public class Test {
  public static method1(int n, m) {
    n += m;
    xMethod(3.4);
  }
  public static int xMethod(int n) {
     if (n > 0) return 1;
     else if (n == 0) return 0;
     else if (n < 0) return -1;
    }
}

B. Bài tập vận dụng (exercise)

Bài 1 : viết method tinh tổng sau .(Write a method to compute the following series)

Test với kết quả sau :(Write a test program that displays the following table)

Bài 2 : Tính giá trị của đa thức  P(x)=a_nxⁿ+ a_n-1x^n-1+ ... + a₁x+ a₀ theo cách tính của Horner: P(x)=((((a_nx+ a_n-1)x+ a_n-2... + a₁)x+ a₀

Bài 12-doc

Source code tham khảo : here

pass extract :https://coderandtutorial.blogspot.com

Bài 6 : Cấu trúc lặp (Loop structures)

Tiếp tục loạt bài hướng dẫn Java tutorial.

Trong bài hướng dẫn ngày hôm nay tôi sẽ hướng dẫn các bạn một cấu trúc điều khiển khác trong Java .Đó là cấu trúc lặp (loop) . Đây là một cấu trúc rất quan trọng , giúp chúng ta có thể thực hiện một đoạn mã thực hiện tuần tự , lặp đi lặp lại theo một cấu trúc nào đó.

Trong Java cung cấp các cách thức để lặp một đoạn mã như sau.

I. Sử dụng vòng lặp while.

Cú pháp

while (loop-continuation-condition) {
  // Loop body
  Statement(s);
}

Trong đó loop-continuation-condition là điều kiện lặp . Nếu không đúng điều kiện này thì chương trình sẽ không chạy vào phần "loop body". 

Ví dụ :

int count = 0;
while (count < 100) {
  System.out.println("Welcome to Java!");
  count++;
}

flow chart 

Trong ví dụ trên thì dòng Welcome to Java! thực hiện in ra 100 lần.

Thực hiện một ví dụ nho nhỏ với while

Viết chương trình chuyển đổi một số tự nhiên ở hệ cơ số 10 thành số ở hệ cơ số b bất kì (1< b≤ 36)

import java.util.Scanner;
public class DoiCoSo_DemoWhile {
 public static void doiCoSo(int n, int base) {
  if (n >= base)
   doiCoSo(n / base, base);
  if (n % base > 9)
   System.out.printf("%c", n % base + 55);
  else
   System.out.print((n % base));
 }
 public static int nhap() {
  Scanner input = new Scanner(System.in);
  boolean check = false;
  int n = 0;
  while (!check) {
   System.out.print(" ");
   try {
    n = input.nextInt();
    check = true;
   } catch (Exception e) {
    System.out.println("Ban phai nhap so! hay nhap lai...");
    input.nextLine();
   }
  }
  return (n);
 }
 public static void main(String[] args) {
  System.out.println("Nhap n");
  int n = nhap();
  System.out.println("Nhap vao co so can chuyen sang b");
  int b = nhap();
  System.out.println("So " + n + " chuyen sang co so " + b + " thanh: ");
  doiCoSo(n, b);
 }
}

II. Sử dụng lặp do...while

Cú pháp

do {
  // Loop body;
  Statement(s);
} while (loop-continuation-condition);

Trong đó loop-continuation-condition là điều kiện lặp . Nếu không đúng điều kiện này thì chương trình sẽ thoát khỏi loop body .

Ở đây while khác với do...while đó là điều kiện lặp ở trước hay ở sau . 

Flow chart

Ví dụ sử dụng do ... while

Nhập vào số vào và ấn ok . Nếu chọn 0 thì sẽ hiển thị tổng các chữ số trước đó và thoát 

import javax.swing.JOptionPane;
public class DemoDoWhile {
 public static void main(String[] args) {
  int data;
  int sum = 0;
  do {
   String dataString = JOptionPane
     .showInputDialog(
       null,
       "Enter an int value:\n(the program exits if the input is 0)",
       "TestDo", JOptionPane.QUESTION_MESSAGE);
   data = Integer.parseInt(dataString);
   sum += data;
  } while (data != 0);

  JOptionPane.showMessageDialog(null, "The sum is " + sum, "TestDo",
    JOptionPane.INFORMATION_MESSAGE);
 }
}

III. Vòng lặp for

Vòng lặp for thực chất cũng là một dạng biến tấu từ vòng lặp while

i = initialValue; // Initialize loop control variable
while (i < endValue) {
  // Loop body
  ...
  i++; // Adjust loop control variable
}

Vòng lặp for có cú pháp như sau :

for (initial-action; loop-continuation-condition;
     action-after-each-iteration) {
  // Loop body;
  Statement(s);
}

Ví dụ :

for(int i = 0 ; i < 10 ; i ++){

    System.out.println("" + i );

}

Hoặc 

for(int i = 0 ; ;i++){

System.out.println("" + i );
} // lặp vô hạn
Hoặc
for(; ;){
    System.out.println(" xin ch");
}
Ví dụ :
flow chart



Ví dụ : Một số được gọi là sốthuận nghịch độc nếu ta đọc từ trái sang phải hay từ phải sang trái số đó ta vẫn nhận được một số giống nhau. Hãy liệt kê tất cả các số thuận nghịch độc có sáu chữ số (Ví dụ số: 558855)
public class SoThuanNghich_For {
 public static boolean testSoThuanNghich(int n) {
  StringBuilder xau = new StringBuilder();
  String str = "" + n;
  xau.append(str);
  String check = "" + xau.reverse();
  if (str.equals(check))
   return true;
  else
   return false;
 }
 public static void main(String[] args) {
  int n, count = 0;
  for (n = 100000; n <= 999999; n++) {
   if (testSoThuanNghich(n)) {
    System.out.println(n);
    count++;
   }
  }
  System.out.println("Co " + count + " so thuan nghich co 6 chu so");
 }
}
Lưu ý :Ngoài cách viết for thông thường ta còn các cách viết vòng lặp for như sau:
- fore:
for ([Kiểu dữ liệu] [đối tượng] : [độ dài mảng đối tượng]) {
          //Body loop  
}
tương đương với :
for(int i = 0 ; i <= mang.lenght ; i ++){};
- form:
for (Map.Entry<Object, Object> en : m.entrySet()) {
            Object object = en.getKey();
            Object object1 = en.getValue();         
}
-forc:
for (Iterator it = col.iterator(); it.hasNext();) {
            Object object = it.next();          
}
- fori :
for (int i = 0; i < args.length; i++) {
            String string = args[i];
}
Vân vân...
Những cách sử dụng vòng for này tôi sẽ nói cụ thể hơn trong nhưng loạt bài hướng dẫn sau
IV . Một số lưu ý khi sử dụng cấu trúc lặp
- Không dùng vòng lặp while(true) hay for true ...
- Một số lỗi khi viết cấu trúc lặp thường gặp




Sau đây là bài tập để các bạn luyện tập :
Bài 1 : Viết chương trình phân tích một số nguyên thành các thừa số nguyên tố .Vídụ: Số 28 được phân tích thành 2 x 2 x 7
Bài 2 : Hãy viết chương trình tính tổng các chữ số của một số nguyên bất kỳ. Ví dụ: Số  8545604 có tổng các chữ số là: 8+5+4+5+6+0+4=32
Bài 3 :Viết chương trình nhập một số nguyên dương n và thực hiện các chức năng sau:

a)      Liệt kê các ước số của n. Có bao nhiêu ước số.

b)      Liệt kê các ước số là nguyên tố của n.
Hi vọng các bạn tự giác hoàn thành các bài tập trên do chính sức lao động mình bỏ ra. Như vậy thì trình độ code của các bạn sẽ dần dân nâng được tới tầm cao mới.
Source code : here
pass : https://coderandtutorial.blogspot.com

Bài 6 : Cấu trúc lặp (Loop structures)