Chương trình C++ tìm giai thừa của một số bằng quy hoạch động

Giai thừa của một số nguyên dương n bằng tích của các số từ 1 đến n (1×2×3×...×n). Giai thừa không tồn tại với số âm. Dưới đây là chương trình C++ tính giai thừa của một số nhập vào bằng phương pháp quy hoạch động.

Thuật toán

Bắt đầu fact(int n):
  Đọc số n
  Khởi tạo i = 1, result[1000] = {0}
  result[0] = 1
  Với i = 1 đến n:
    result[i] = i * result[i-1]
  In result
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

int result[1000] = {0};

int fact(int n) {
  if (n >= 0) {
    result[0] = 1;
    for (int i = 1; i <= n; ++i) {
      result[i] = i * result[i - 1];
    }
    return result[n];
  }
}

int main() {
  int n;
  while (true) {
    cout << "Nhập số nguyên để tính giai thừa (nhập 0 để thoát): ";
    cin >> n;
    if (n == 0) break;
    cout << fact(n) << endl;
  }
  return 0;
}

Kết quả đầu ra

Nhập số nguyên để tính giai thừa (nhập 0 để thoát): 2
2
Nhập số nguyên để tính giai thừa (nhập 0 để thoát): 6
720
Nhập số nguyên để tính giai thừa (nhập 0 để thoát): 7
5040
Nhập số nguyên để tính giai thừa (nhập 0 để thoát): 10
3628800
Nhập số nguyên để tính giai thừa (nhập 0 để thoát): 0