本文共 1325 字，大约阅读时间需要 4 分钟。

Objective-C实现卡特兰数递归算法

卡特兰数是一组正整数，用于解决类似括号匹配、路径问题等组合数学问题。通过Objective-C编程，我们可以轻松实现卡特兰数的计算。以下是使用递归算法计算卡特兰数的实现示例。

代码片段：

#import 
   
    
unsigned long catalanNumber(unsigned long n) {
    if (n == 0) {
        return 1;
    }
    return catalanNumber(n - 1) * (2 * n) / (n + 1);
}
   

程序运行步骤

使用说明

卡特兰数的递归公式为：

C(n) = C(n-1) * (2n) / (n+1)

其中，C(0) = 1

程序实现了上述公式，能够计算从C(0)到C(n)的所有卡特兰数值。

编译和测试

int main(int argc, const char *argv) {
    unsigned long n = 5; // 输入要计算的卡特兰数的索引
    unsigned long catalan = catalanNumber(n);
    printf("卡特兰数C(%lu) = %lu\n", n, catalan);
    return 0;
}

运行程序，会看到从C(0)到C(5)的卡特兰数值。

扩展功能

为了提高性能，可以考虑使用记忆化缓存技术。可以通过添加一个全局变量来存储已经计算过的卡特兰数值。

static NSMutableDictionary *catalanCache = nil;
unsigned long catalanNumber(unsigned long n) {
    if (catalanCache == nil) {
        catalanCache = [NSMutableDictionary new];
        catalanCache[@"C(0)"] = 1;
    }
    if (catalanCache objectForKey:@"C(n)") {
        return [catalanCache objectForKey:@"C(n)"];
    }
    if (n == 0) {
        [catalanCache setObject:1 forKey:@"C(0)"];
        return 1;
    }
    unsigned long result = catalanNumber(n - 1) * (2 * n) / (n + 1);
    [catalanCache setObject:result forKey:@"C(n)"];
    return result;
}

这样可以避免重复计算，提高程序运行效率。