ภาพรวมปัญหา
หา Hermite Number Hₙ ซึ่งนิยามโดย:
H₀ = 1, H₁ = 0 Hₙ = -2(n-1)Hₙ₋₂ สำหรับ n ≥ 2
ลำดับ: 1, 0, -2, 0, 12, 0, -120, 0, 1680, 0, -30240, ...
ตัวอย่าง
อินพุต
N = 7
เอาต์พุต
0
อินพุต
N = 6
เอาต์พุต
-120
วิธีแก้ปัญหา
วิธีที่ 1: Recursion
int calcNHermiteNumber(int N) {
if (N == 0) return 1;
if (N % 2 == 1) return 0;
return -2 * (N - 1) * calcNHermiteNumber(N - 2);
}
วิธีที่ 2: สูตรปิด (Closed Form) - O(N) ⭐
ถ้า N คี่ → Hₙ = 0
ถ้า N คู่ → Hₙ = (-1)^(N/2) × 2^(N/2) × (N-1)!!
โดย (N-1)!! = (N-1)×(N-3)×...×3×1 (Double Factorial / Semi-factorial)
โค้ดตัวอย่าง (สูตรปิด)
#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 hermite = pow(2, n / 2) * calcSemiFact(n - 1);
if ((n / 2) % 2 == 1) hermite *= -1;
return hermite;
}
int main() {
int N = 10;
cout << "The " << N << "th hermite Number is " << calcNHermiteNumber(N);
return 0;
}
เอาต์พุต
The 10th hermite Number is -30240
สรุป
Hermite Numbers เป็น 0 สำหรับ index คี่ สำหรับ index คู่ใช้สูตร Double Factorial
