Giai thừa trong lập trình Java

Hôm nay chúng ta sẽ nói về 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 biết, đồng thời có thể làm việc với nó. Vậy hãy bắt đầu. Giai thừa của n là giá trị tích (phép nhân) của tất cả các số tự nhiên từ 1 đến n, ký hiệu là n! Nó trông như thế nào:

1! =  1
2! =  1 * 2 = 2
3! =  1 * 2 * 3 = 6
4! =  1 * 2 * 3 * 4 = 24
5! =  1 * 2 * 3 * 4 * 5  = 120

Và một quy tắc nhỏ nữa, cho 0:

!0  = 1

Ví dụ: nếu chúng ta muốn nhận được chênh lệch giai thừa 6! và 4!:

6!-4! = 1⋅2⋅3⋅4⋅5⋅6 - 1⋅2⋅3⋅4 = 720 - 24 = 696

Chúng ta hãy xem điều này trông như thế nào trong Java và hiểu một số cách để tính giai thừa.

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

public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i;
  }
  return result;
}

Không có gì phức tạp: chúng tôi sử dụng số nhận được làm kích thước của chu kỳ, trong đó chúng tôi nhân với tất cả các số trước đó cho đến khi đạt f. Và trong chính:

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

Chúng tôi kiểm tra và nhận được kết quả mong muốn: 696.

Giải pháp đệ quy

Đệ quy đang thực hiện một số logic bằng cách gọi một phương thức trên chính nó. Phương pháp này được gọi là đệ quy. Thông thường nó bao gồm hai phần:

1. điều kiện thoát của phương thức, khi đạt đến điều kiệ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. Nếu không, chúng ta sẽ nhận được một vòng lặp vô hạn khi gọi chính một phương thức và kết quả là StackOverflowError .

2. một số xử lý (logic) cần thiết trong một tình huống nhất định + gọi chính nó, nhưng với một giá trị đến khác.

Ví dụ lý tưởng của chúng ta cho đệ quy ngày nay là tìm giai thừa:

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}

Chúng tôi đặt điều kiện để thoát đệ quy khi nó đạt đến 1. Nếu đối số không phải là 1 thì chúng tôi nhân giá trị hiện tại với kết quả của lệnh gọi tiếp theo đến phương thức này (trong đó chúng tôi gửi giá trị hiện tại -1).

Giải pháp với luồng

Đối với những người không biết chức năng truyền phát hoặc những người muốn làm mới bộ nhớ của mình, việc đọc phần này sẽ rất hữu ích .

public static int getFactorial(int f) {
  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 một lớp đặc biệt IntStream, lớp này cung cấp các khả năng bổ sung khi làm việc với luồng từ các giá trị int. Để tạo một luồng như vậy, chúng tôi sử dụng phương thức tĩnh rangeClosed của nó, phương thức này tạo các giá trị từ 2 đến f bao gồm bước 1. Tiếp theo, chúng tôi kết hợp tất cả các giá trị bằng phương thức rút gọn, cụ thể là chúng tôi chỉ ra trong đó cách chúng tôi muốn kết hợp chúng. Cuối cùng, chúng ta nhận được giá trị kết quả bằng phương thức terminal getAsInt.

Sử dụng BigInteger

Trong Java, lớp BigInteger thường được sử dụng để xử lý các số, đặc biệt là các số BIG . Rốt cuộc, nếu chúng ta sử dụng int, thì giai thừa tối đa mà chúng ta có thể lấy mà không làm mất dữ liệu là 31, trong thời gian dài - 39. Nhưng nếu chúng ta cần giai thừa 100 thì sao? Hãy xem xét các giải pháp trước đó nhưng sử dụng BigInteger.

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

public static BigInteger getFactorial(int f) {
  BigInteger result = BigInteger.ONE;
  for (int i = 1; i <= f; i++)
     result = result.multiply(BigInteger.valueOf(i));
  return result;
}

Thuật toán đếm 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 - để đặt giá trị bắt đầu thành 1. nhân - nhân giữa giá trị giai thừa trước đó và 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 làm việc với BigInteger được thêm vào.

Giải pháp với luồng

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();
  }
}

Về cơ bản mọi thứ đều giống nhau, nhưng với BigInteger. Trong luồng hiện tại, chúng tôi có phương thức mapToObj, với phương thức này chúng tôi chuyển đổi các giá trị int thành BigInteger để sau đó nhân chúng lại với nhau bằng cách sử dụng phương thức multiple (à, chúng tôi đã thêm get để 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ố 100 thì chúng ta sẽ không bị tràn và sẽ nhận được:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000