Comments 39
наверное, все чётные числа стоят на позициях кратных 3
Эмпирически? Догадка?
ЛОЛ. Нечетные числа всегда в сумме своей дают четное. А нечетное с четным — нечетное.
Или я не понял и эта статья — стёб на тему «доказываем простое сложно»?
Even[0]=2;
Even[1]=8;
for(int i=2;i<N; i++) {
Even[i]=Even[i-1]*4 + Even[i-2];
}Так тоже можно
t = 1: F(n) = F(n-1) + F(n-2) — сама последовательность Фибоначчи
t = 2: F(2*n) = 3*F(2*(n-1)) — F(2*(n-2))
t = 3: F(3*n) = 4*F(3*(n-1)) + F(3*(n-2))
t = 4: F(4*n) = 7*F(4*(n-1)) — F(4*(n-2))
t = 5: F(5*n) = 11*F(5*(n-1)) + F(5*(n-2))
Обобщая, имеем
F(t*n) = a(t)*F(t*(n-1)) + (-1)^(t+1)*F(t*(n-2))
Нетрудно видеть, что последовательность a(t) также является последовательностью a-la Фибоначчи, с базой 1, 3: 1,3,4,7,11,18…
Для t>=3 справедливо a(t) = 2*F(t) + F(t-3) (полагая F(0) = 0).
Доказать, думаю, по индукции вполне возможно, просто вывод долгий получится.
Остался вопрос, на сколько вообще актуально знание математики для программиста PHP? Почему-то мне кажется, что такое знание математики требуется в единичных случаях. Больше необходимы умения связать несвязуемое, там 1С прицепить к сайту, плагин для магазина какой добавить...
Вполне допускаю это, но смотрю на большинство сайтов, которыми сам пользуюсь, и вот не понимаю я, где там может жить даже такая довольно примитивная математика из статьи.
Соответственно, и когда требуется программист для впихивания невпихуемого, а на собеседовании от него требуют каких-то извращений с высшей математикой и квантовой физикой, то мне это начинает напоминать требование высшего образования и докторской степени от уборщицы.
Так-то уборщица тоже использует химию, при мытье полов и физику, когда отдирает прилипшую жвачку, а математику при подсчёте своей зарплаты.
И да, я не хочу ни сколько принизить профессию программиста, да и уборщицы тоже. Мне просто кажется, что зачастую подобные требования выдвинутые работодателями не совсем адекватны.
Boomburum, не работает отображение формул на мобилке, fix pls :(
У меня в ios/chrome формулы отображаются.
>Решил с помощью цикла(for)
>while
Мы вам перезвоним.
[/sarcasm]
2 * 4 + 0 (перед единицей, очевидно, идет ноль) = 8
8 * 4 + 2 = 34
34 * 4 + 8 = 144
144 * 4 + 34 = 610
610 * 4 + 144 = 2584
и тд, думаю, задумка ясна.
существуют ли ещё чётные числа Фибоначчи чей номер не кратен 3?
После чего идет несколько абзацев выкладок, чтобы это доказать. При том, что выше уже выписано равенство из которого это тривиальным образом следует:
F_{n+3} = 2F_{n+1} + F_n
Если F_n — нечетное, то F_{n+3} — тоже нечетное. Остается лишь проверить четность двух первых чисел ряда.
Вот сейчас сижу и думаю, наверное все-таки из-за Фибоначчи пролетел
Я так и не понял, почему. Если задача действительно стояла так, как описано в письме (выбрать все четные числа Фибоначчи в диапазоне от 1 до 10000), то решение пишется за две минуты:
def fib():
a, b = 1, 1
yield a
while True:
yield b
a, b = b, a + b
def even_fib(n=10000):
for i in fib():
if i > n:
return
if i % 2 == 0:
yield iИ именно такое решени, написанное за две минуты, является верным и самым подходящим, потому что корректно решает задачу минимальными ресурсами. И даже выполняется за смешное время:
In [3]: %time list(even_fib())
Wall time: 15.7 µs
Out[3]: [2, 8, 34, 144, 610, 2584]Даже для больши́х значений:
In [5]: %time list(even_fib(10**30))
Wall time: 54.8 µs
Out[5]: [2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040, 3524578, 14930352, 63245986, 267914296, 1134903170, 4807526976, 20365011074, 86267571272, 365435296162, 1548008755920, 6557470319842, 27777890035288, 117669030460994, 498454011879264, 2111485077978050, 8944394323791464, 37889062373143906, 160500643816367088, 679891637638612258, 2880067194370816120, 12200160415121876738, 51680708854858323072, 218922995834555169026, 927372692193078999176, 3928413764606871165730, 16641027750620563662096, 70492524767089125814114, 298611126818977066918552, 1264937032042997393488322, 5358359254990966640871840, 22698374052006863956975682, 96151855463018422468774568, 407305795904080553832073954, 1725375039079340637797070384, 7308805952221443105020355490, 30960598847965113057878492344, 131151201344081895336534324866, 555565404224292694404015791808]Без дополнительных условий, любые исследования и попытки оптимизировать — бесполезная трата рабочего времени.
Что конечно не уменьшет интересность статьи, если отойти от просто решения тестового задания.
Дело в том, что в PHP числа только до 64 бит точности. А дальше они становятся double, у которых не проверить четность из-за маленького диапазона.
А в Питоне числа безразмерные
In [16]: print(10**100 + 1)
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001В PHP же нестрогая типизация, там скорее всего получится что-то такое:
php > print(10**30 + 1);
"десять в тридцатой один"
Самое смешное было как то такое же тз. Фибоначи, запрос с др, и третье найти количество белых пикселей на изображении,
К третьему заданию придрались, и я ещё написал два разных способа и доказал через картинку созданную самим php что количество пикселов считает верно. Фибоначи нашёл какой то пример в мане про генераторы, запрос сам составил. Оказывается это стандартный набор). Я отказался, так как удалёнка. Типо я прошёл
Чётные числа Фибоначчи