0

tl;dr：我应该如何处理像20! * 20!Objective-C 中的数字？

我正在通过Project Euler学习 Objective-C 。这很有趣，但我一直遇到的一个问题是处理任意大的数字。我对这些东西还是很陌生，所以我不知道为什么像 Python 这样的东西比 Obj-C 更容易处理大量数字。

举个例子Problem 15：

Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 x 20 grid?

这很容易。使用组合学：

（20+20）！/ 20!(20!)
-> 815915283247897734345611269596115894272000000000 / 5919012181389927685417441689600000000
-> 137846528820

在 Python 中：

import math  
print math.factorial(40) / (math.factorial(20) * math.factorial(20))

但是在 Objective-C 中呢？我还没有找到一种方法来迫使如此大量的人通过。使用 2 x 2 示例可以正常工作。我可以得到9C4 = 126，因为它应该是。但是我应该如何处理像这样的数字20!？

我已经尝试使用NSDecimalNumber，它似乎支持每个数字更多的数字，假设您可以将其转换为Mantissa x Exponent并且不介意精度损失，但这并没有证明太有用，因为我无法计算了解如何让 Obj-C 从 a 创建尾数%llu，我确实介意精度损失。

到目前为止，我的代码正确地生成了阶乘，因为它似乎unsigned long long处理了如此大的值，但在 上阻塞x * y，因此getCombinatoricOf:20 and:20返回1。

#import "Problem15.h"

@implementation Problem15

- (unsigned long long)factorial:(NSNumber *)number {
    unsigned long long temp = 1;
    for (int i = [number intValue]; i > 0; i--) {
        temp *= i;
    }
    return temp;
}

- (unsigned long long)getCombinatorcOf:(NSNumber *)x and:(NSNumber *)y {
    NSNumber *n = @([x intValue] + [y intValue]);
    NSNumber *n_factorial = @([self factorial:n]);
    NSNumber *x_factorial = @([self factorial:x]);
    NSNumber *y_factorial = @([self factorial:y]);
    return ([n_factorial unsignedLongLongValue] / ([x_factorial unsignedLongLongValue] * [y_factorial unsignedLongLongValue]));
}

- (NSString *)answer {
    NSNumber *x = @5;
    NSNumber *y = @4;
    unsigned long long answer = [self getCombinatoricOf:x and:y];
    return [NSString stringWithFormat:@"\n\nProblem 15: \nHow many routes are there through a 20 x 20 grid? \n%llu", answer];
}

@end
4

1 回答 1

1

它不是 Objective-C，但您可以将GMP用作普通的 C 库。

还有 GMP 的 Objective-C 包装器，例如GMPInt。

于 2012-11-06T09:13:13.760 回答