Chương trình Java cho giai thừa

Hôm nay chúng ta sẽ nói về giai thừa và những cách phổ biến nhất để tìm giai thừa. Đây là một trong những chức năng cơ bản nhất mà một lập trình viên cần phải biết và có thể làm việc với. Vâng, chúng ta hãy bắt đầu. Giai thừa của số n, ký hiệu là n!, là giá trị của tích (phép nhân) của tất cả các số tự nhiên từ 1 đến n. Đây là giao diện của nó (hãy làm mới kiến ​​thức toán học của bạn): Và có thêm một quy tắc nhỏ cho 0: Nếu chúng ta muốn tính sự khác biệt giữa 6! và 4!: Hãy xem điều này sẽ như thế nào khi được triển khai trong lập trình. Chúng ta sẽ khám phá một vài cách để thực hiện phép tính giai thừa trong Java.

Giải pháp thông thường trong chương trình giai thừa

Đây là một chương trình giai thừa đơn giản sử dụng vòng lặp:

class FactorialExample{  
 public static void main(String args[]){  
  int i,fact=1;  
  int number=7;// our number to do the necessary calculations in class Factorial    
  for(i=1;i<=number;i++){    
      fact=fact*i;    
  }    
  System.out.println("Factorial of "+number+" is: "+fact);    
 }  
}

Đầu ra của chúng tôi trên bảng điều khiển sẽ là: Và một ví dụ nữa để sắp xếp mọi thứ:

public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i; // finding factorial of number using loops
  }
  return result;
}

Không có gì khó khăn ở đây: chúng tôi sử dụng số đã truyền làm kích thước của vòng lặp, trong đó chúng tôi nhân với tất cả các số trước đó cho đến khi chúng tôi nhận được f. Và trong chính:

System.out.println(getFactorial(6) - getFactorial(4));

Kiểm tra mã, chúng tôi thấy rằng chúng tôi nhận được kết quả mong muốn: 696.

giải pháp đệ quy

Đệ quy xảy ra khi một phương thức gọi chính nó. Phương pháp như vậy được gọi là phương pháp đệ quy. Theo quy định, nó bao gồm hai phần:

1. Điều kiện kết thúc — khi điều kiện kết thúc được thỏa mãn, phương thức sẽ ngừng gọi chính nó và bắt đầu chuyển các giá trị lên. Rốt cuộc, nếu không có điều kiện kết thúc, thì chúng ta sẽ có một vòng lặp vô hạn, với phương thức tự gọi nó lặp đi lặp lại cho đến khi chúng ta nhận được StackOverflowError .
2. Bất kể logic nào mà tình huống yêu cầu cộng với một cuộc gọi đệ quy, nhưng với một giá trị đầu vào khác.

Tìm giai thừa trong Java là một ví dụ hoàn hảo về thời điểm sử dụng đệ quy:

public static int getFactorial(int f) { // finding factorial of number using recursive solution
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}

Điều kiện kết thúc đệ quy của chúng ta sẽ là khi chúng ta đạt đến 1. Nếu tham số không phải là 1, thì chúng ta nhân giá trị hiện tại với kết quả của lệnh gọi đệ quy tiếp theo đến phương thức (mà chúng ta chuyển giá trị hiện tại trừ đi 1).

Giải pháp với Stream

Bất kỳ ai chưa quen với chức năng Luồng của Java, hoặc bất kỳ ai muốn làm mới bộ nhớ của mình, sẽ có lợi khi đọc về đây .

public static int getFactorial(int f) { // finding factorial of number using Stream 
  if (f <= 1) {
     return 1;
  }
  else {
     return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
  }
}

Ở đây, chúng tôi sử dụng lớp IntStream đặc biệt , lớp này cung cấp cho chúng tôi các khả năng bổ sung khi làm việc với một luồng các giá trị int. Để tạo một luồng như vậy, chúng ta sử dụng phương thức rangeClosed tĩnh của nó, phương thức này tạo ra các giá trị từ 2 đến f, bao gồm, với gia số là 1. Tiếp theo, chúng ta sử dụng phương thức rút gọn để kết hợp tất cả các giá trị. Cụ thể hơn, chúng tôi chỉ ra cách chúng tôi muốn kết hợp các giá trị. Cuối cùng, chúng tôi nhận được giá trị kết quả bằng cách sử dụng phương thức getAsInt của thiết bị đầu cuối .

Sử dụng BigInteger

Trong Java, lớp BigInteger thường được sử dụng để xử lý các số, đặc biệt là số LỚN. Thật vậy, nếu chúng ta sử dụng int thì giai thừa tối đa mà chúng ta có thể xử lý mà không làm mất dữ liệu là 31. Đối với kiểu dữ liệu dài , giai thừa tối đa là 39. Nhưng nếu chúng ta cần giai thừa là 100 thì sao? Hãy điều chỉnh các giải pháp trước đó cho BigInteger.

giải pháp thông thường

public static BigInteger getFactorial(int f) { // finding factorial of number using BigInteger
  BigInteger result = BigInteger.ONE;
  for (int i = 1; i <= f; i++)
     result = result.multiply(BigInteger.valueOf(i));
  return result;
}

Thuật toán về cơ bản là giống nhau, nhưng ở đây chúng tôi sử dụng các khả năng của BigInteger: BigInteger.ONE là giá trị bắt đầu bằng 1 và phép nhân () được sử dụng để nhân giá trị giai thừa trước đó với số hiện tại.

giải pháp đệ quy

public static BigInteger getFactorial(int f) {
  if (f <= 1) {
     return BigInteger.valueOf(1);
  }
  else {
     return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
  }
}

Logic chung của giải pháp không thay đổi, ngoại trừ một số phương pháp được thêm vào để làm việc với BigInteger.

Giải pháp với Stream

public static BigInteger getFactorial(int f) {
  if (f < 2) {
     return BigInteger.valueOf(1);
  }
  else {
     return IntStream.rangeClosed(2, f).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
  }
}

Mọi thứ về cơ bản là giống nhau, nhưng với BigInteger. Lớp Stream cung cấp cho chúng ta phương thức mapToObj mà chúng ta sử dụng để chuyển đổi các giá trị int thành BigInteger để sau đó nhân chúng với chính chúng bằng cách sử dụng phương thức multi (và get() đã được thêm vào để lấy một đối tượng từ trình bao bọc Tùy chọn ). Nếu chúng ta chạy bất kỳ phương thức nào trong ba phương thức này với đối số là 100, thì chúng ta sẽ tránh được lỗi tràn ngăn xếp và nhận được kết quả chính xác: