Wie erstellt man einen robusten Fibonacci-Algorithmus?

Question

Ich habe den folgenden Algorithmus

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; 
} 

ich rohe Geschwindigkeit viel ist es egal, aber ich das Verfahren angesichts der schlechten Eingangs robust sein wollen. Meine Einschränkung ist, dass die Eingabe zwischen 1 und 46 liegen muss und wir eine Ausnahme auslösen müssen, wenn unser Aufrufer einen Fehler hat. Und wir kümmern uns nicht um rohe Geschwindigkeit. Wir wollen eine korrekte, robuste und lesbare Lösung haben.

Was kann ich tun?

Answer 1

Update: löst jetzt eine Ausnahme aus, die der aktualisierten Frage entspricht.

Ignorieren Sie die Tatsache, dass es konstante Zeit daher maxing die rohe Geschwindigkeit Sache ist, die Sie nicht kümmern. Jeder Wert für n, der nicht akzeptabel ist, gibt -1 zurück; Sie sind maximal 47, das ist auskommentiert.

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 

} 

hat keinen Sinn, Phantasie sind Sie nur 46 gültige Zahlen bekommen:

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 Rekursion zu zeigen, geschieht oft. Und im Notfall schreiben Sie es einfach um:

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); 
}