Этот пост затрагивает три моих любимых темы — математику, передачу знаний через опыт (учебные юнит-тесты) и важность исследований.
Большинству разработчиков известно о последовательности Фибоначчи , в основном через собеседования.
Чтобы кратко подытожить ряд определен:
F ( n ) = F ( n-1 ) + F ( n-2 ), n> 2
F (1) = F (2) = 1
Есть определение варианта:
F ( n ) = F ( n-1 ) + F ( n-2 ), n> 1
F (1) = 1
F (0) = 0
Существует четыре хорошо известных решения вопроса доски «напишите код для вычисления F (n)».
Рекурсия — вам нужно упомянуть об этом, чтобы показать, что вы довольны рекурсией, но вы также должны упомянуть, что это действительно плохая идея, поскольку она требует O (2 n ) стекового времени и пространства, поскольку вы удваиваете работу для каждого n .
Рекурсия с запоминанием — это может быть хорошим подходом, если вы укажете, что это хорошее обобщение. По сути, это рекурсия, но вы поддерживаете кеш (памятку), поэтому вам нужно сделать рекурсивный вызов только один раз — последующие рекурсивные вызовы просто ищут кэшированное значение. Это гибкий метод, поскольку он может использоваться для любой чисто рекурсивной функции. (То есть рекурсивная функция, которая зависит исключительно от своих входных данных и не имеет побочных эффектов.) Первые вызовы требуют O (n) времени, стека и пространства кучи. Я не помню, имеет ли значение, если сначала вы делаете рекурсивный вызов с меньшим или большим значением.
Если у вас есть постоянный кэш, последующие вызовы требуют O (1) времени и места в стеке и O (n) пространства кучи.
Итерация — если вы не можете кэшировать значения (или просто хотите эффективно инициализировать кеш), вы можете использовать итеративный подход. Это требует времени O (n), но только O (1) стека и пространства кучи.
Прямое приближение — наконец, есть известное приближение, использующее φ , или вариант, использующий sqrt (5) . Это O (1) для времени, пространства стека и пространства кучи. Это хороший подход, если вы 1) используете таблицу поиска для наименьших значений и 2) убедитесь, что n не слишком велико.
Последний пункт часто упускается из виду. Аппроксимация работает только до тех пор, пока вы не превысите точность вашего числа с плавающей запятой. F ( 100 000 ) должно быть хорошо. F ( 1 000 000 000 000 ) не может быть. Итерационный подход не практичен с такими большими числами.
Исследование
Знаете ли вы, что есть два других решения с производительностью O (LG (N)) (в Википедии) во времени и пространстве? (Я не уверен, что это O (lg (n)), поскольку это не алгоритм «разделяй и властвуй» — два рекурсивных вызова не разделяют начальную работу между ними, но с запоминанием это определенно меньше, чем O (n) . Я подозреваю, но не могу быстро доказать, что это O (LG 2 (N)) .)
В Википедии мы знаем:
F ( 2n-1 ) = F 2 ( n ) + F 2 ( n-1 )
F ( 2n ) = F ( n ) (F ( n ) + 2F ( n-1 ))
Это просто переписать это как рекурсивный метод для F ( n ).
Есть еще одно свойство, которое рассматривает три случая — F ( 3n-2 ), F ( 3n-1 ) и F ( 3n ). Смотрите код для деталей.
Эти сайты предоставляют множество дополнительных свойств последовательностей Фибоначчи и связанных с ними Лукаса . Мало кто из разработчиков когда-либо должен знать эти свойства, но в тех редких случаях час исследований может сэкономить дни работы.
Реализация
Теперь мы можем использовать наши исследования для реализации подходящих методов для последовательностей Фибоначчи и Лукаса.
Расчет Фибоначчи
(Этот код не показывает оптимизацию с использованием прямого приближения для некэшированных значений при достаточно малых n .)
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
/** * Get specified Fibonacci number. * @param n * @return */ @Override public BigInteger get(int n) { if (n < 0) { throw new IllegalArgumentException("index must be non-negative"); } BigInteger value = null; synchronized (cache) { value = cache.get(n); if (value == null) { int m = n / 3; switch (n % 3) { case 0: value = TWO.multiply(get(m).pow(3)) .add(THREE.multiply(get(m + 1)).multiply(get(m)) .multiply(get(m - 1))); break; case 1: value = get(m + 1).pow(3) .add(THREE.multiply(get(m + 1) .multiply(get(m).pow(2)))) .subtract(get(m).pow(3)); break; case 2: value = get(m + 1).pow(3) .add(THREE.multiply(get(m + 1).pow(2) .multiply(get(m)))) .add(get(m).pow(3)); break; } cache.put(n, value); } } return value; } |
Итератор Фибоначчи
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
/** * ListIterator class. * @author bgiles */ private static final class FibonacciIterator extends ListIterator { private BigInteger x = BigInteger.ZERO; private BigInteger y = BigInteger.ONE; public FibonacciIterator() { } public FibonacciIterator(int startIndex, FibonacciNumber fibonacci) { this.idx = startIndex; this.x = fibonacci.get(idx); this.y = fibonacci.get(idx + 1); } protected BigInteger getNext() { BigInteger t = x; x = y; y = t.add(x); return t; } protected BigInteger getPrevious() { BigInteger t = y; y = x; x = t.subtract(x); return x; } } |
Расчет Лукаса
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
/** * Get specified Lucas number. * @param n * @return */ public BigInteger get(int n) { if (n < 0) { throw new IllegalArgumentException("index must be non-negative"); } BigInteger value = null; synchronized (cache) { value = cache.get(n); if (value == null) { value = Sequences.FIBONACCI.get(n + 1) .add(Sequences.FIBONACCI.get(n - 1)); cache.put(n, value); } } return value; } |
Лукас итератор
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
/** * ListIterator class. * @author bgiles */ private static final class LucasIterator extends ListIterator { private BigInteger x = TWO; private BigInteger y = BigInteger.ONE; public LucasIterator() { } public LucasIterator(int startIndex, LucasNumber lucas) { idx = startIndex; this.x = lucas.get(idx); this.y = lucas.get(idx + 1); } protected BigInteger getNext() { BigInteger t = x; x = y; y = t.add(x); return t; } protected BigInteger getPrevious() { BigInteger t = y; y = x; x = t.subtract(x); return x; } } |
образование
Как лучше всего рассказать другим разработчикам о существовании этих неожиданных отношений? Код, конечно!
Как лучше всего рассказать другим разработчикам о существовании кода, демонстрирующего эти отношения? Юнит тесты, конечно!
Легко написать модульные тесты, которые одновременно проверяют нашу реализацию и сообщают другим разработчикам о приемах, которые они могут использовать для улучшения своего кода. Ключ должен предоставить ссылку на дополнительную информацию.
Последовательность Фибоначчи
|
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
|
public class FibonacciNumberTest extends AbstractRecurrenceSequenceTest { private static final BigInteger MINUS_ONE = BigInteger.valueOf(-1); /** * Constructor */ public FibonacciNumberTest() throws NoSuchMethodException { super(FibonacciNumber.class); } /** * Get number of tests to run. */ @Override public int getMaxTests() { return 300; } /** * Verify the definition is properly implemented. * * @return */ @Test @Override public void verifyDefinition() { for (int n = 2; n < getMaxTests(); n++) { BigInteger u = seq.get(n); BigInteger v = seq.get(n - 1); BigInteger w = seq.get(n - 2); Assert.assertEquals(u, v.add(w)); } } /** * Verify initial terms. */ @Test @Override public void verifyInitialTerms() { verifyInitialTerms(Arrays.asList(ZERO, ONE, ONE, TWO, THREE, FIVE, EIGHT)); } /** * Verify that every third term is even and the other two terms are odd. * This is a subset of the general divisibility property. * * @return */ @Test public void verifyEvenDivisibility() { for (int n = 0; n < getMaxTests(); n += 3) { Assert.assertEquals(ZERO, seq.get(n).mod(TWO)); Assert.assertEquals(ONE, seq.get(n + 1).mod(TWO)); Assert.assertEquals(ONE, seq.get(n + 2).mod(TWO)); } } /** * Verify general divisibility property. * * @return */ @Test public void verifyDivisibility() { for (int d = 3; d < getMaxTests(); d++) { BigInteger divisor = seq.get(d); for (int n = 0; n < getMaxTests(); n += d) { Assert.assertEquals(ZERO, seq.get(n).mod(divisor)); for (int i = 1; (i < d) && ((n + i) < getMaxTests()); i++) { Assert.assertFalse(ZERO.equals(seq.get(n + i).mod(divisor))); } } } } /** * Verify the property that gcd(F(m), F(n)) = F(gcd(m,n)). This is a * stronger statement than the divisibility property. */ @Test public void verifyGcd() { for (int m = 3; m < getMaxTests(); m++) { for (int n = m + 1; n < getMaxTests(); n++) { BigInteger gcd1 = seq.get(m).gcd(seq.get(n)); int gcd2 = BigInteger.valueOf(m).gcd(BigInteger.valueOf(n)) .intValue(); Assert.assertEquals(gcd1, seq.get(gcd2)); } } } /** * Verify second identity (per Wikipedia): sum(F(i)) = F(n+2)-1 */ @Test public void verifySecondIdentity() { BigInteger sum = ZERO; for (int n = 0; n < getMaxTests(); n++) { sum = sum.add(seq.get(n)); Assert.assertEquals(sum, seq.get(n + 2).subtract(ONE)); } } /** * Verify third identity (per Wikipedia): sum(F(2i)) = F(2n+1)-1 and * sum(F(2i+1)) = F(2n) */ @Test public void verifyThirdIdentity() { BigInteger sum = ZERO; for (int n = 0; n < getMaxTests(); n += 2) { sum = sum.add(seq.get(n)); Assert.assertEquals(sum, seq.get(n + 1).subtract(ONE)); } sum = ZERO; for (int n = 1; n < getMaxTests(); n += 2) { sum = sum.add(seq.get(n)); Assert.assertEquals(sum, seq.get(n + 1)); } } /** * Verify fourth identity (per Wikipedia): sum(iF(i)) = nF(n+2) - F(n+3) + 2 */ @Test public void verifyFourthIdentity() { BigInteger sum = ZERO; for (int n = 0; n < getMaxTests(); n++) { sum = sum.add(BigInteger.valueOf(n).multiply(seq.get(n))); BigInteger x = BigInteger.valueOf(n).multiply(seq.get(n + 2)) .subtract(seq.get(n + 3)).add(TWO); Assert.assertEquals(sum, x); } } /** * Verify fifth identity (per Wikipedia): sum(F(i)^2) = F(n)F(n+1) */ public void verifyFifthIdentity() { BigInteger sum = ZERO; for (int n = 0; n < getMaxTests(); n += 2) { BigInteger u = seq.get(n); BigInteger v = seq.get(n + 1); sum = sum.add(u.pow(2)); Assert.assertEquals(sum, u.multiply(v)); } } /** * Verify Cassini's Identity - F(n-1)F(n+1) - F(n)^2 = -1^n */ @Test public void verifyCassiniIdentity() { for (int n = 2; n < getMaxTests(); n += 2) { BigInteger u = seq.get(n - 1); BigInteger v = seq.get(n); BigInteger w = seq.get(n + 1); BigInteger x = w.multiply(u).subtract(v.pow(2)); Assert.assertEquals(ONE, x); } for (int n = 1; n < getMaxTests(); n += 2) { BigInteger u = seq.get(n - 1); BigInteger v = seq.get(n); BigInteger w = seq.get(n + 1); BigInteger x = w.multiply(u).subtract(v.pow(2)); Assert.assertEquals(MINUS_ONE, x); } } /** * Verify doubling: F(2n-1) = F(n)^2 + F(n-1)^2 and F(2n) = * F(n)(F(n-1)+F(n+1)) = F(n)(2*F(n-1)+F(n). */ @Test public void verifyDoubling() { for (int n = 1; n < getMaxTests(); n++) { BigInteger u = seq.get(n - 1); BigInteger v = seq.get(n); BigInteger w = seq.get(n + 1); BigInteger x = v.multiply(v).add(u.pow(2)); Assert.assertEquals(seq.get((2 * n) - 1), x); x = v.multiply(u.add(w)); Assert.assertEquals(seq.get(2 * n), x); x = v.multiply(v.add(TWO.multiply(u))); Assert.assertEquals(seq.get(2 * n), x); } } /** * Verify tripling. */ @Test public void verifyTripling() { for (int n = 1; n < getMaxTests(); n++) { BigInteger u = seq.get(n - 1); BigInteger v = seq.get(n); BigInteger w = seq.get(n + 1); BigInteger x = TWO.multiply(v.pow(3)) .add(THREE.multiply(v).multiply(u).multiply(w)); Assert.assertEquals(seq.get(3 * n), x); x = w.pow(3).add(THREE.multiply(w).multiply(v.pow(2))) .subtract(v.pow(3)); Assert.assertEquals(seq.get((3 * n) + 1), x); x = w.pow(3).add(THREE.multiply(w.pow(2)).multiply(v)).add(v.pow(3)); Assert.assertEquals(seq.get((3 * n) + 2), x); } }} |
Lucas Sequence
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
public class LucasNumberTest extends AbstractRecurrenceSequenceTest { private static final FibonacciNumber fibonacci = new FibonacciNumber(); /** * Constructor */ public LucasNumberTest() throws NoSuchMethodException { super(LucasNumber.class); } /** * Get number of tests to run. */ @Override public int getMaxTests() { return 300; } /** * Verify the definition is properly implemented. * * @return */ @Test @Override public void verifyDefinition() { for (int n = 2; n < getMaxTests(); n++) { BigInteger u = seq.get(n); BigInteger v = seq.get(n - 1); BigInteger w = seq.get(n - 2); Assert.assertEquals(u, v.add(w)); } } /** * Verify initial terms. */ @Test @Override public void verifyInitialTerms() { verifyInitialTerms(Arrays.asList(TWO, ONE, THREE, FOUR, SEVEN, ELEVEN, BigInteger.valueOf(18), BigInteger.valueOf(29))); } /** * Verify Lucas properties. */ @Test public void verifyLucas() { // L(n) = F(n-1) + F(n+1) for (int n = 2; n < getMaxTests(); n++) { Assert.assertEquals(seq.get(n), fibonacci.get(n - 1).add(fibonacci.get(n + 1))); } } /** * F(2n) = L(n)F(n) */ @Test public void verifyLucas2() { for (int n = 2; n < getMaxTests(); n++) { Assert.assertEquals(fibonacci.get(2 * n), seq.get(n).multiply(fibonacci.get(n))); } } /** * F(n) = (L(n-1)+ L(n+1))/5 */ @Test public void verifyLucas3() { for (int n = 2; n < getMaxTests(); n++) { Assert.assertEquals(FIVE.multiply(fibonacci.get(n)), seq.get(n - 1).add(seq.get(n + 1))); } } /** * L(n)^2 = 5 F(n)^2 + 4(-1)^n */ @Test public void verifyLucas4() { for (int n = 2; n < getMaxTests(); n += 2) { Assert.assertEquals(seq.get(n).pow(2), FIVE.multiply(fibonacci.get(n).pow(2)).add(FOUR)); } for (int n = 1; n < getMaxTests(); n += 2) { Assert.assertEquals(seq.get(n).pow(2), FIVE.multiply(fibonacci.get(n).pow(2)).subtract(FOUR)); } }} |
Вывод
Очевидно, что разработчикам редко нужно вычислять числа Фибоначчи, если они не работают над проблемами Project Euler или на собеседовании. Этот код не будет иметь прямой полезности.
В то же время это мощная демонстрация ценности инвестирования одного или двух часов в исследования, даже если вы уверены, что уже знаете все, что вам нужно знать. Вам, вероятно, не нужна реализация BigInteger, но некоторые люди могут посчитать, что подход O (lg (n)) предпочтительнее, чем оценка с использованием степеней φ, или могут использовать отношения, обсуждаемые на страницах MathWorld и Wikipedia.
Исходный код
Хорошая новость в том, что я опубликовал исходный код для этого … и плохая новость в том, что это часть постоянного рисования, когда я занимаюсь проблемами Project Euler . (Здесь нет решений — это просто исследование идей, вдохновленных проблемами. Так что код немного грубоват и не должен использоваться, чтобы решить, следует ли мне приводить меня на собеседование (если вы не впечатлены): http : //github.com/beargiles/projecteuler .
| Ссылка: | Последовательности Фибоначчи и Лукаса от нашего партнера по JCG Bear Giles в блоге Invariant Properties . |