Как создать надежный алгоритм фибоначчи?

У меня есть следующий алгоритмКак создать надежный алгоритм фибоначчи?

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, и мы должны выбросить исключение, когда у нашего вызывающего есть ошибка. И мы не заботимся о сырой скорости. Мы хотим иметь правильное, надежное и читаемое решение.

Что я могу сделать?

источник

2016-04-19 Anonymous

Вам просто нужно защититься от 'n <= 0'. В этом случае вы можете выбросить исключение, или если вы выберете возвращаемое значение -1. В настоящее время он просто вернет 1 для этих значений. – juharr

Начните с заявления (1), что представляет собой хороший ввод, и (2) каковы последствия плохого ввода. –

@ EricLippert 1) Хороший ввод - любое положительное число 2) последствия плохого ввода - возврат -1 –

Обновление: теперь исключает исключение, соответствующее обновленному вопросу.

Игнорирование того факта, что это постоянное время, поэтому максимальная скорость, которую вы не заботитесь. Любое значение для 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 ------------------------------

Фибо часто делается, чтобы показать рекурсию. И в крайнем случае вы просто переписываете его:

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

источник

2016-04-19 17:57:05 Tatarize

Я думаю, что это код TDD выглядит так ... – fjardon

fib (int n) { if ((n> 46) || (n <0)) throw new System.ArgumentException ("FAIL!", "Index" , ex); if (n == 0) return 1; return n * fib (n-1); } – Tatarize

Ваш рекурсивный пример неверен (это факторная функция, а не фибоначчи). – Zong

Как создать надежный алгоритм фибоначчи?

ответ

Смежные вопросы