今日は、n が非常に大きい場合のフィボナッチ n 項の計算にかなりの時間を費やしました。私は Objective-C を使用することにしましたが、時間がかかったことを考えると、後から考えると最善の決定ではなかったかもしれません。私は調査し、他のプログラミング言語を使用している他の人にも有効と思われる Binet の式を使用することにしました。
double phi = (sqrt(5) + 1) / 2.0;
long long j = (long long) round(pow(phi, number) / sqrt(5));
C の fibonacci(number) 関数の要点です。これを NSDecimalNumber を使用して Objective-C に変換しようとしました。私の方法は次のようになります。
NSDecimalNumber* squareRootOfFive = [NSDecimalNumber decimalNumberWithString: [[NSNumber numberWithDouble:sqrt(5)] stringValue]];
NSDecimalNumber* phi = [[squareRootOfFive decimalNumberByAdding:[NSDecimalNumber one]] decimalNumberByDividingBy:[NSDecimalNumber decimalNumberWithString:@"2"]];
return [[[phi decimalNumberByRaisingToPower: number] decimalNumberByDividingBy:squareRootOfFive] decimalNumberByRoundingAccordingToBehavior: [NSDecimalNumberHandler decimalNumberHandlerWithRoundingMode: NSRoundPlain scale:2 raiseOnExactness:NO raiseOnOverflow:YES raiseOnUnderflow:NO raiseOnDivideByZero:NO ]];
素晴らしく読みやすいです。このコードは、X が 700 より大きく 800 より小さい最初の X フィボナッチ数に対して機能します。最終的に次のエラー/出力が得られます。
2013-02-01 17:27:19.977 Euler25[14907:303] フィボナッチ数 792 は 166 桁です
2013-02-01 17:27:19.989 Euler25[14907:303] *** キャッチされない例外 'NSDecimalNumberOverflowException' が原因でアプリを終了します。理由: 'NSDecimalNumber オーバーフロー例外'
*** 最初のスロー コール スタック:
0 CoreFoundation 0x00007fff8c3b10a6 __exceptionPreprocess + 198
1 libobjc.A.dylib 0x00007fff880443f0 objc_exception_throw + 43
2 CoreFoundation 0x00007fff8c3b0e7c +[NSException raise:format:] + 204
3 Foundation 0x00007fff8c88bc3d -[NSDecimalNumberHandler exceptionDuringOperation:error:leftOperand:rightOperand:] + 193
4 Foundation 0x00007fff8c88ad46 _checkErrorAndRound + 60
5 Foundation 0x00007fff8c88b1e2 -[NSDecimalNumber decimalNumberByRaisingToPower:withBehavior:] + 156
6 Euler25 0x0000000100001bb2 +[Euler25 fibonacci:] + 402
7 Euler25 0x0000000100001978 main + 184
8 libdyld.dylib 0x00007fff8a5147e1 start + 0
9 ??? 0x0000000000000001 0x0 + 1
きれいにフォーマットできません。私はこのコードを使用して Project euler [問題 25]( [1]: http://projecteuler.net/ [2]: https://projecteuler.net/problem=25 ) を解決しました。 Objective-C では、NSDecimalNumber を使用していない場合、この問題をさらに進める方法がわかりません。おそらく、使用すべき数学のトリックがありますか?
前もって感謝します。