Tìm số Hermite thứ N trong C++

Giới thiệu

Cho số nguyên N. Tìm số Hermite thứ N. Số Hermite Hₙ định nghĩa bằng công thức truy hồi: Hₙ = -2(n-1)Hₙ₋₂, với H₀=1, H₁=0.

Dãy Hermite: 1, 0, -2, 0, 12, 0, -120, 0, 1680, 0…

Ví dụ minh họa

Đầu vào 1

N = 7

Đầu ra 1

0

Đầu vào 2

N = 6

Đầu ra 2

-120

Phương pháp 1: Đệ quy

N lẻ ⇒ Hₙ = 0. N chẵn ⇒ áp dụng công thức truy hồi.

Chương trình minh họa

#include <iostream>
using namespace std;

int calcNHermiteNumber(int N) {
    if (N == 0) return 1;
    if (N % 2 == 1) return 0;
    return -2 * (N - 1) * calcNHermiteNumber(N - 2);
}

int main() {
    int N = 10;
    cout << "The " << N << "th hermite Number is " << calcNHermiteNumber(N);
    return 0;
}

Đầu ra

The 10th hermite Number is -30240

Phương pháp 2: Công thức đóng - O(N)

N lẻ ⇒ 0. N chẵn: Hₙ = (-1)^(N/2) × 2^(N/2) × (N-1)!! Trong đó (N-1)!! = (N-1)×(N-3)×...×3×1 (tử số kép).

Chương trình minh họa

#include <iostream>
#include <cmath>
using namespace std;

int calcSemiFact(int n) {
    int factVal = 1;
    for (int i = 1; i <= n; i += 2)
        factVal *= i;
    return factVal;
}

int calcNHermiteNumber(int n) {
    if (n % 2 == 1) return 0;
    int HermiteNumber = pow(2, n/2) * calcSemiFact(n-1);
    if ((n/2) % 2 == 1) HermiteNumber *= -1;
    return HermiteNumber;
}

int main() {
    int N = 10;
    cout << "The " << N << "th hermite Number is " << calcNHermiteNumber(N);
    return 0;
}

Đầu ra

The 10th hermite Number is -30240