卡特兰数计算遇整数溢出无报错，如何实现错误提示？

你的问题核心是带符号整数溢出属于C++未定义行为，系统不会自动抛出错误，导致结果被静默篡改。要解决这个问题，需要从「扩大存储类型」和「添加溢出检测」两方面入手：

1. 改用更大的整数类型 #

int的上限只有2147483647，卡特兰数增长极快，n=20就会超出范围。先把存储类型换成unsigned long long，它的上限是18446744073709551615，能支持计算到n=33的卡特兰数（C₃₃=8646064801558534470）。

2. 在递归中加入溢出检测 #

即使换了大类型，超过上限后还是会溢出，所以需要在计算过程中手动检测，一旦溢出就抛出异常，让main函数捕获并提示错误。

修改后的完整代码 #

#include <iostream>
#include <stdexcept>
#include <climits> // 用于ULLONG_MAX

using namespace std;

unsigned long long catalan(int n) {
    if (n < 0) {
        throw invalid_argument("n cannot be negative");
    }
    if (n <= 1) {
        return 1;
    }
    unsigned long long total = 0;
    for (int i = 0; i < n; ++i) {
        unsigned long long left = catalan(i);
        unsigned long long right = catalan(n - i - 1);
        
        // 检测乘法溢出：如果left > ULLONG_MAX / right，说明乘积会超过上限
        if (left > ULLONG_MAX / right) {
            throw overflow_error("Catalan number exceeds maximum value of unsigned long long");
        }
        unsigned long long product = left * right;
        
        // 检测加法溢出：如果total > ULLONG_MAX - product，说明累加后会溢出
        if (total > ULLONG_MAX - product) {
            throw overflow_error("Catalan number exceeds maximum value of unsigned long long");
        }
        total += product;
    }
    return total;
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        cout << "Usage: " << argv[0] << " <n>" << endl;
        return 1;
    }
    
    unsigned long long res;
    try {
        int n = stoi(argv[1]);
        res = catalan(n);
        cout << res << endl;
    } catch (const out_of_range& e) {
        cout << "Input number out of range for int type." << endl;
        return 0;
    } catch (const invalid_argument& e) {
        cout << e.what() << endl;
        return 0;
    } catch (const overflow_error& e) {
        cout << e.what() << endl;
        return 0;
    }
    
    return 0;
}

关键修改点说明 #

• 递归函数返回值和total变量改用unsigned long long，提升存储上限。
• 乘法前检查：left > ULLONG_MAX / right，避免乘积溢出。
• 加法前检查：total > ULLONG_MAX - product，避免累加溢出。
• 新增对负数输入的异常抛出，完善输入合法性检查。
• main函数中新增对invalid_argument和overflow_error的捕获，分别处理非法输入和溢出情况。

3. 更大数值的处理（可选） #

如果需要计算n>33的卡特兰数，unsigned long long也不够用，这时需要使用大整数库（比如GMP、Boost.Multiprecision）来支持任意精度的整数运算。

内容的提问来源于stack exchange，提问作者Awakoto