如何创建健壮的fibonacci算法

本文关键字：fibonacci 算法 何创建 创建 | 更新日期: 2024-10-22 13:57:00

我有以下算法

int fib(int n)
{
    if (n == 1 || n == 2)
       return 1;
    var fibprev = 1;
    var fib = 1;
    for (var cur = 2 ; cur < n ; ++cur)
    {
       var temp = fib;
       fib += fibprev;
       fibprev = temp;
    }
    return fib;
}

我不太关心原始速度，但我确实希望该方法在面对糟糕的输入时保持稳健。我的限制是输入必须在1到46之间，并且当我们的调用者有错误时，我们必须抛出异常。我们不在乎原始速度。我们希望有正确、稳健和可读的解决方案。

我能做什么？

如何创建健壮的fibonacci算法

更新：现在抛出异常，符合更新后的问题。

忽略了它是恒定时间的事实，因此最大化了你不在乎的原始速度。任何不可接受的n值都返回-1；他们的最大值是47，所以这已经被评论掉了。

    int fib(int n) {
    switch (n) {
        case 0: return 0;
        case 1: return 1;
        case 2: return 1;
        case 3: return 2;
        case 4: return 3;
        case 5: return 5;
        case 6: return 8;
        case 7: return 13;
        case 8: return 21;
        case 9: return 34;
        case 10: return 55;
        case 11: return 89;
        case 12: return 144;
        case 13: return 233;
        case 14: return 377;
        case 15: return 610;
        case 16: return 987;
        case 17: return 1597;
        case 18: return 2584;
        case 19: return 4181;
        case 20: return 6765;
        case 21: return 10946;
        case 22: return 17711;
        case 23: return 28657;
        case 24: return 46368;
        case 25: return 75025;
        case 26: return 121393;
        case 27: return 196418;
        case 28: return 317811;
        case 29: return 514229;
        case 30: return 832040;
        case 31: return 1346269;
        case 32: return 2178309;
        case 33: return 3524578;
        case 34: return 5702887;
        case 35: return 9227465;
        case 36: return 14930352;
        case 37: return 24157817;
        case 38: return 39088169;
        case 39: return 63245986;
        case 40: return 102334155;
        case 41: return 165580141;
        case 42: return 267914296;
        case 43: return 433494437;
        case 44: return 701408733;
        case 45: return 1134903170;
        case 46: return 1836311903;
        //case 47: return 2971215073;
    }
    System.ArgumentException argEx = new System.ArgumentException("Index is out of range", "index", ex);
    throw argEx
}

幻想没有意义——你只能得到46个有效号码：

0:  0
1:  1
2:  1
3:  2
4:  3
5:  5
6:  8
7:  13
8:  21
9:  34
10: 55
11: 89
12: 144
13: 233
14: 377
15: 610
16: 987
17: 1597
18: 2584
19: 4181
20: 6765
21: 10946
22: 17711
23: 28657
24: 46368
25: 75025
26: 121393
27: 196418
28: 317811
29: 514229
30: 832040
31: 1346269
32: 2178309
33: 3524578
34: 5702887
35: 9227465
36: 14930352
37: 24157817
38: 39088169
39: 63245986
40: 102334155
41: 165580141
42: 267914296
43: 433494437
44: 701408733
45: 1134903170
46: 1836311903
^-- 32 bit signed int max ------------------------------
47: 2971215073
^-- 32 bit unsigned int max ------------------------------
48: 4807526976
49: 7778742049
50: 12586269025
51: 20365011074
52: 32951280099
53: 53316291173
54: 86267571272
55: 139583862445
56: 225851433717
57: 365435296162
58: 591286729879
59: 956722026041
60: 1548008755920
61: 2504730781961
62: 4052739537881
63: 6557470319842
64: 10610209857723
65: 17167680177565
66: 27777890035288
67: 44945570212853
68: 72723460248141
69: 117669030460994
70: 190392490709135
71: 308061521170129
72: 498454011879264
73: 806515533049393
74: 1304969544928657
75: 2111485077978050
76: 3416454622906707
77: 5527939700884757
78: 8944394323791464
^-- JavaScript Number (53 bit signed int) max ------------------------------
79: 14472334024676221
80: 23416728348467685
81: 37889062373143906
82: 61305790721611591
83: 99194853094755497
84: 160500643816367088
85: 259695496911122585
86: 420196140727489673
87: 679891637638612258
88: 1100087778366101931
89: 1779979416004714189
90: 2880067194370816120
91: 4660046610375530309
92: 7540113804746346429
^-- 64 bit signed int max ------------------------------
93: 12200160415121876738
^-- 64 bit unsigned int max ------------------------------

Fib通常用于显示递归。在紧要关头，你只需重写它：

int fib (int n) {
    if ((n > 46) || (n < 0)) throw new System.ArgumentException("FAIL!", "index", ex);
    return (n < 2)?1:fib(n-1) + fib(n-2); 
}
相关文章：