Tổng hợp các Giải thuật - Thuật toán cơ bản giải bằng Java - Phần 1

1. Kiểm tra số nguyên tố

Code java:

/**

 * @author JavaDevExpress

 *

 */

public class KiemTraSoNguyenTo {

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int n = 9;
  if (isPrimeNumber(n) == true) {
   System.out.println("La so nguyen to.");
  } else {
   System.out.println("Khong phai so nguyen to.");
  }
 }

 /*+ Định nghĩa: Là số nguyên lớn hơn 1, chỉ có 2 ước là 1 và chính nó.
  Các số nguyên tố từ 1-100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
  41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
 + Thuật toán: Để kiểm tra 1 số nguyên n có phải số nguyên tố hay không, ta làm theo các bước.
 - Nếu n<2 thì không phải số nguyên tố.
 - Kiểm tra trong đoạn từ 2..sqrt(n) xem có ước của n không, nếu có tồn tại thì n không phải số nguyên tố
 - Ngược lại, n là số nguyên tố.*/

 public static boolean isPrimeNumber(int n) {
  if (n < 2) {
   return false;
  } else {
   int temp = (int) Math.sqrt(n);
   for (int i = 2; i <= temp; i++) {
    if (n % i == 0) {
     return false;
    }
   }
  }
  return true;
 }
}

2. Phương pháp sàng Eratosthene

Code java:

package javadevexpress.blogspot.com;

/**
 * @author JavaDevExpress
 *
 */
public class PhuongPhapSang_Eratosthene {

 public static void main(String[] args) {
 
  int n = 48;
  boolean[] isPrime = SeiveOfEratosthene(n);
  System.out.println("Day cac so nguyen to nho hon: " + n);
  for (int i = 2; i < isPrime.length; i++) {
   if(isPrime[i] == true){
    System.out.println(i);
   }
  }
 }

 /*+ Mục đích: Để lập bảng các số nguyên tố nhỏ hơn hoặc bằng 1 số n cho trước.
 + Thuật toán: Sử dụng 1 bảng bool isPrimeNumber[0..n+1] để lưu kết quả
 - Khởi tạo: tất cả các số từ 1->n là nguyên tố.
 - Xóa số 1 ra khỏi bảng.
 - Lặp: Tìm 1 số nguyên tố đầu tiên trong bảng sau đó xóa tất cả các bội của nó trong bảng.
 - Quá trình lặp kết thúc khi gặp số nguyên tố >= sqrt(n).
 - Tất cả các số chưa bị xóa trong bảng là số nguyên tố.*/

 public static boolean[] SeiveOfEratosthene(int n)
 {
  //tao mang boolean
  boolean[] isPrime=new boolean[n+1];
   
  //khởi tạo: các số từ 1->n được coi là nguyên tố.
     for (int i = 0; i <= n; i++)
     {
         isPrime[i] = true;
     }
   
     //so 1 khong phai so nguyen to
     isPrime[1] = false;
     int k = 1;
   
     //lap cho den khi k <= (int)Math.sqrt(n) sai thi khong lap nua (tham khao vong lap while)
     //hay noi cach khac khi nao k <= can bac 2 cua n thi thuc hien vong lap
     while (k <= (int)Math.sqrt(n))
     {
         k++;
         //tìm số nguyên tố đầu tiên
         while (!isPrime[k]) k++;
       
         //xóa các bội của k khỏi danh sách các số nguyên tố
         int j = 2;
         while (k * j <= n)
         {
             isPrime[k * j] = false;
             j++;
         }
     }
     return isPrime;
 }
}

3. Tìm ước số chung lớn nhất

Code java:

package javadevexpress.blogspot.com;

/**
 * @author JavaDevExpress
 *
 */
public class TimUCLN_GreatestCommonDivisor {

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int a = 12;
  int b = 15;
  System.out.println(deQuy_GCD(a, b));
  System.out.println(khuDeQuy_GCD(a, b));
 }

 /*+ Định nghĩa: Ước số chung lớn nhất (Greatest Common Divisor) của 2 số a và b,
 được định nghĩa như sau: gcd(a,b)=d <=> d là số lớn nhất trong tất cả các ước chung của a và b.
 Uoc so cua 12: U12(1;2;3;4;6;12)
 Uoc so cua 30: U30(1;2;5;6;10;15;30)
 GCD(12;30) = 6
 + Thuật toán: Giải thuật Euclid, định nghĩa đệ qui như sau:
 - gcd(a,0)=a
 - gcd(a,b)=gcd(b,a mod b)*/

 public static int deQuy_GCD(int a, int b)
 {
  //neu b = 0, uoc chung lon nhat chinh la a
     if (b == 0){
     
      return a;
     } else {
     
      //chia lay phan du
      int temp = a % b ;
      return deQuy_GCD(b, temp);
     }
 }

 public static int khuDeQuy_GCD(int a, int b)
 {
     while (b != 0)
     {
      //chia lay phan du
         int temp = a % b;
         a = b; b = temp;
     }
     return a;
 }

}

4. Tìm bội số chung nhỏ nhất

Code java:

package javadevexpress.blogspot.com;

/**
 * @author JavaDevExpress
 *
 */
public class TimBCNN_LeastCommonMultiple {

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int a = 15;
  int b = 6;
  System.out.println(LCM(a, b));
 }

 /*+ Định nghĩa: Bội số chung nhỏ nhất
 (Least Common Multiple) của 2 số a và b được định nghĩa LCM(a,b) = m
 <=> m là số nhỏ nhất trong tất cả các bội chung của a và b.
 B(4) = {0;4;8;12;16;20;24;28;32;...}
 B(6) = {0;6;12;18;24;30;36;...}
 => BCNN cua 4 va 6: BC(4;6) = 12 hay LCM(4,6) = 12
 + Thuật toán: Ta có công thức:
 LCM(a,b) = |a*b|/gcd(a,b)*/

 public static int LCM(int a, int b)
 {
  //tri tuyet doi a*b
  int abs = Math.abs(a * b);
            //su dung ham tim UCLN
     return abs / TimUCLN_GreatestCommonDivisor.khuDeQuy_GCD(a, b);
 }
}

5. Tính giai thừa

Code java:

package javadevexpress.blogspot.com;

/**
 * @author JavaDevExpress
 *
 */
public class GiaiThua_Factorial {

 public static void main(String[] args){
 
  int a = 14;
 
  System.out.println(deQuy_Factorial(a));
  System.out.println(khuDeQuy_Factorial(a));
 }

 /*Giai thừa của 1 số nguyên dương n là tích tất cả các số nguyên dương nhỏ hơn hoặc bằng n*/

 public static long deQuy_Factorial(int n)
 {
     if (n == 0) {
     
      return 1;
     } else {
     
      return deQuy_Factorial(n - 1) * n;
     }
 }

 public static long khuDeQuy_Factorial(int n)
 {
     long result = 1;
     for (int i = 1; i <= n; i++)
     {
         result *= i;
     }
     return result;
 }
}

Tham khảo code C++, C# tại http://diendan.congdongcviet.com/showthread.php?t=54134
Src sưu tầm: http://congdongcviet.com