05.05.2019 12:54
idkravitz 39 14900 Источник
Навеяно комментарием под постом Фибоначчи на собеседовании. Пользователь pavellyzhin упомянул следующую задачу на собеседовании (комментарий):
Больше года назад откликнулся на вакансию «php-программист», прислали ТЗ и там было задание с Фибоначчи: выбрать все четные числа Фибоначчи в диапазоне от 1 до 10000. Решил с помощью цикла(for). Еще там нужно было SQL-запрос составить на выборку ближайших дней рождений пользователей, что-то сверстать, точно не помню и какую-то функцию написать. Все сделал, отправил. Прислали ответ: «по итогам тестового задания Вы не приняты». Что конкретно им не понравилось так и не написали. Вот сейчас сижу и думаю, наверное все-таки из-за Фибоначчи пролетел… :)
В данном посте я собираюсь показать как можно было решить эту задачу эффектно, а может даже и эффективно, но это не точно. Заодно продемонстрирую парочку из тысяч доказанных про числа Фибоначчи фактов.


Теоретизируем



Лучшее с чего можно начать — просмотреть глазами первые N чисел Фибоначчи и попытаться обнаружить закономерность в расположении чётных чисел.

$1,1,{\bf 2},3,5,{\bf 8},13,21,{\bf 34},55,89,{\bf 144},\ldots$


В последовательности отмечены чётные числа, как можно заметить каждое 3-е число Фибоначчи — чётное и, наверное, все чётные числа стоят на позициях кратных 3. Это и будет наша догадка, теперь нам нужно её подтвердить и выработать алгоритм вычисления.

Лучшее доказательство — простое, поэтому спасибо пользователю AllexIn за простую идею, которую я первоначально упустил. Каждое последующее число Фибоначчи представляет собой сумму двух предыдущих, если два предыдущих числа — нечётные, то следующее будет чётным, если в двух предыдущих числах одно нечётное, а другое чётное, то следующее будет нечётным. В принципе одной этой идеи уже достаточно, чтобы «интуитивно нащупать» доказываемый факт. Доказательство по индукции очевидное, но не могу удержаться, чтобы не привести его

Мы доказываем, что «каждое третье число Фибоначчи — чётное, а два предшествующих каждому такому числу — нечётные».
  • База индукции. Первые два числа Фиббоначи $1,1$ — нечётные, третье число $2$ — чётное
  • Гипотеза. Пусть вплоть до некоторого кратного по номеру 3 числа Фибоначчи выполнено, что каждое третье — чётное, а два предшествующих ему — нечётные.
  • Шаг индукции. Следующее за последним чётным из гипотезы числом является нечётным, т.к. оно получается из суммы нечётного с чётным, следующее за уже этим числом также нечётное, т.к. оно получается из суммы чётного с нечётным, а уже следующее за ним — чётное, т.к. только что полученные два предыдущих для него — нечётные, по построению его номер кратен 3, оно чётное, а два предшествующих ему — нечётные.


Вот так можно доказать нашу догадку даже не прибегая к математическим выкладкам. Можно формализовать эту идею, заодно получив формулу для вычисления каждого третьего числа Фибоначчи $F_{n+3}$ из $F_n$ и $F_{n+1}$. Используя рекурентное соотношение $F_{n+2} = F_{n+1} + F_{n}$ получим:

$ F_{n+3} = F_{n+2} + F_{n+1} = 2 F_{n+1} + F_n $


Таким образом, если $F_n$ — чётное, то $F_{n+3}$ также чётное в силу этой формулы. Учитывая, что $F_3=2$, то каждое третье число Фибоначчи действительно чётное, что подтверждает часть нашей догадки. Тут необходимо убедиться, что мы не пропускаем других чётных чисел, т.е. что они все имеют номера кратные 3. Спасибо пользователю janatem за его простую идею, ведь из приведенной формулы для $F_{n+3}$ также следует, что если $F_n$ — нечётное, то $F_{n+3}$ также нечётное, таким образом получаем, что числа с номерами $3k-2,3k-1, k\in\mathbb{N}$ — нечётные (по индукции, начинаем с $F_1=F_2=1$ — нечётных), а $3k,k\in\mathbb{N}$ — чётные, что покрывает все числа Фибоначчи, а значит мы действительно покрываем всё чётные числа.

Есть ещё способ, как можно было бы показать, что других чётных чисел нет. Предположим, что существует число $F_m$ — чётное и $0\not\equiv m\mod 3$, тогда $m = 3k - 1$ или $m=3k + 1$, где $k$ — какое-то натуральное.

Обратимся к матричному представлению чисел Фибоначчи из оригинального поста

$ \begin{pmatrix}0&1\\1&1\end{pmatrix}^n=\begin{pmatrix}F_{n-1}&F_n\\F_n&F_{n+1}\end{pmatrix} $


Вычисляя определитель обеих частей, получим

$ (-1)^n=F_{n+1}F_{n-1}-F_n^2 $


Отсюда следует, что делители чисел $F_{n+1}, F_n$ и $F_{n-1}, F_n$ совпадают с делителями $(-1)^n$, т.е. соседние числа Фибоначчи взаимнопросты. Это же означает, что взаимнопросты и числа $F_{3k}, F_{3k-1}$ и $F_{3k}, F_{3k+1}$, т.е. $F_{3k}$ и $F_m$. Но по предположению $F_m$ — чётное, а $F_{3k}$ — чётное по доказанному ранее. Таким образом других чётных чисел, кроме $F_{3k}$, где $k\in \mathbb{N}$ в последовательности Фибоначчи не существует. А также мы установили интересный факт, что соседние числа Фибоначчи взаимнопросты.

Напоследок покажем как минимум ещё один способ доказать нашу догадку — воспользоваться теоремой Люка.

Теорема Люка. Целое число делит $F_m$, и $F_n$, тогда и только тогда, когда оно является делителем $F_d$, где $d = \gcd(m,n)$, в частности

$ \gcd(F_m, F_n)=F_{\gcd(m,n)} $


Тут $\gcd$ — наибольший общий делитель. Если положить $m=3$, то $\gcd(2, F_n)=F_{\gcd(3,n)}$. Если $F_n$ — чётное, то левая часть равна 2, тогда чтобы правая часть тоже равнялась 2 необходимо, чтобы $n$ делилось на 3 и в то же время верно и обратное. Таким образом получаем именно то, что мы и хотели доказать.

Итак, каждое третье число Фибоначчи — чётное, а каждое чётное имеет номер кратный трём. Мы тщательно доказали это и никто не смеет в этом теперь усомниться.

Алгоритм


А теперь осталось придумать алгоритм. Можно конечно поступить, как изначально сделал pavellyzhin, но вместо того чтобы проверять $0\equiv F_n\mod 2$, мы можем проверить $0\equiv n\mod 3$, вот это поворот! Правда это никак не влияет на число итераций алгоритма, ведь мы просто изменили фильтр последовательности. Лучше сразу генерировать подпоследовательность чисел Фибоначчи с нужным нам свойством (чётность), поэтому другой очевидный способ это воспользоваться формулой Бине

$ F_n=\left\lfloor\frac{\varphi^n}{\sqrt{5}}\right\rceil, \qquad n\in\{3,6,\ldots,3k\ldots\} $


Тут имеются свои сложности с эффективностью вычислений, подробней об этом сказано в оригинальном посте. Поэтому предлагаю лучший, на мой взгляд, способ — итеративное вычисление $F_{n+3}$, это можно сделать, как мы ранее показали, по формуле $F_{n+3} = 2F_{n+1} + F_n$. Чтобы построить итеративный переход в алгоритме, нам понадобится вычислять $F_{n+4}$, тут всё так же просто

$F_{n+4}=F_{n+3}+F_{n+2} = 2F_{n+1}+F_n + F_{n+1}+F_n = 3F_{n+1}+2F_n$


Кстати, вообще говоря несложно доказать, что

$ F_{n+m}=F_mF_{n+1} + F_{m-1}F_n $


Тогда формально алгоритм записывается следующим образом (текущее чётное число Фибоначчи $F_n$, следующее за ним число Фибоначчи $F_{n+1}$, $M$ — верхняя граница для чисел, заданная в условии задачи):

  1. $F_n\leftarrow F_3 = 2,\quad F_{n+1}\leftarrow F_4=3$
  2. Если $F_n > M$, то закончить, иначе добавить в результат $F_n$
  3. $(F_n, F_{n+1})\leftarrow (2F_{n+1} + F_n, 3F_{n+1}+2F_n)$, перейти на шаг 2.

Алгоритм достаточно тривиален — мы просто перепрыгиваем на каждое третье число Фибоначчи и выводим его (если оно не больше $M$). Сложность алгоритма всё так же линейна, но число повторений шага 2 в точности равняется числу чётных чисел Фибоначчи в диапазоне $1\ldots M$, для сравнения простой алгоритм с фильтрацией требует в 3 раза больше итераций (на каждое найденное будет приходиться 2 отброшенных).

Алгоритм существует на бумаге, на чём там было собеседование, PHP? Чтож расчехляем напоследок PHP значит

function evenfibs($ubound) {
  $result = [];
  [$evenf, $nextf] = [2, 3];
  while($evenf <= $ubound) {
    array_push($result, $evenf);
    [$nextf, $evenf] = [
      3 * $nextf + 2 * $evenf,
      2 * $nextf + $evenf];
   }
  return $result;
}


Примечание: Этот способ всегда можно улучшить, как, например, показал пользователь hunroll. Идея в том, что для вычислений нам не нужно ничего лишнего, кроме уже частично полученного результата, т.е. мы можем вычислять чётные числа используя только предыдущие чётные числа Фибоначчи.

$ F_{n+3} = 2F_{n+1}+F_{n} = 3F_n + 2F_{n-1} = 3F_n + F_{n-1} + F_{n-1} =\\ 3F_n + (F_{n-1} + F_{n-2}) + F_{n-3} = 4F_n + F_{n-3} $



function evenfibs($ubound) {
  if($ubound < 2) return [];
  $evens = [2];
  $next = 8;
  for($i = 1; $next <= $ubound; $i++) {
    $evens[$i] = $next;
    $next = $evens[$i]*4 + $evens[$i-1];
  }
  return $evens;
}


Обобщение


Мы упомянули тут теорему Люка, которая гласит, что $\gcd(F_m, F_n)=F_{\gcd(m,n)}$. Как следствие из неё мы можем получить, что число Фибоначчи $F_n$ кратно числу $F_m$, тогда и только тогда, когда его номер $n$ кратен номеру $m$. Т.е. каждое 4-е число Фибоначчи делится на 3, каждое 5-е на 5, каждое 6-е на 8 и т.д.

Тогда несложным образом получаем алгоритм вычисления подпоследовательности Фибоначчи, в которой элементы кратны какому-то заданному числу $F_m$. Используя тот факт, что

$ F_{n+m}=F_mF_{n+1} + F_{m-1}F_n\\ F_{n+m+1}=F_{m+1}F_{n+1}+F_mF_n $


Предыдущий алгоритм превращается в

  1. $F_n\leftarrow F_m,\quad F_{n+1}\leftarrow F_{m+1}$
  2. Если $F_n > M$, то закончить, иначе добавить в результат $F_n$
  3. $(F_n, F_{n+1})\leftarrow (F_mF_{n+1} + F_{m-1}F_n, F_{m+1}F_{n+1}+F_mF_n)$, перейти на шаг 2.

Где $F_{m-1},F_m,F_{m+1}$ можно задать как константы.

Обобщение примечания. Как справедливо заметил пользователь ignorance, в обобщенном случае также можно построить алгоритм, который использует только числа из частичного результата.

$ F_{n+1} = F_n + F_{n-1}\\ F_{n+2} = 3F_{n} - F_{n-2}\\ F_{n+3} = 4F_{n} + F_{n-3}\\ F_{n+4} = 7F_{n} - F_{n-4}\\ F_{n+5} = 11F_{n} + F_{n-5}\\ \cdots\\ F_{n+t} = (F_t + 2F_{t-1})F_n + (-1)^{t-1}F_{n-t} $



Докажем, это методом математической индукции, при t = 1 и t = 2 выполнение очевидно. Пусть выполненно вплоть до некоторого t, тогда

$ F_{n+t+1}=F_{n+t} + F_{n+t-1}=\\ (F_t + 2F_{t-1})F_n + (-1)^{t-1}F_{n-t} + \\ (F_{t-1} + 2F_{t-2})F_n + (-1)^{t-2}F_{n-t+1} = \\ (F_t + F_{t-1} + 2(F_{t-1}+F_{t-2}))F_n + (-1)^{t-1}(F_{n-t}-F_{n-t+1})=\\ (F_{t+1}+2F_t)F_n + (-1)^{t-1}(F_{n-t}-F_{n-t}-F_{n-t-1})=\\ (F_{t+1}+2F_t)F_n + (-1)^tF_{n-t-1} $



Что-то вроде итога


Задачка конечно полностью синтетическая, количество итераций очень мало (для $M=10000$ ответ содержит всего 6 чисел, т.е. выполнено было 6 итераций, а первоначальному алгоритму «в лоб» потребовалось бы 18), но таким образом юзернейм, который открыл для себя тут в этом что-то новое сможет теперь показать чуть более глубокое математическое знание в числах Фибоначчи на собеседовании.

Edit: Спасибо пользователям janatem и AllexIn за простые доказательства, я включил их в «Теоретизируем», а также hunroll за алгоритм использующий в вычислениях только уже полученные чётные числа и пользователю ignorance за его обобщение.

Комментарии (39)


  1. AllexIn
    05.05.2019 16:34
    #20114142
    +3

    наверное, все чётные числа стоят на позициях кратных 3

    Эмпирически? Догадка?
    ЛОЛ. Нечетные числа всегда в сумме своей дают четное. А нечетное с четным — нечетное.
    Или я не понял и эта статья — стёб на тему «доказываем простое сложно»?


    1. idkravitz Автор
      06.05.2019 09:19
      #20116408
      +1

      Нет — это я балбес) спасибо, добавил в статью


    1. alex-ivanovich
      06.05.2019 09:42
      #20116486

      Это ж очевидно. На этом доказательную часть можно было бы и закончить :)


  1. hunroll
    05.05.2019 16:39
    #20114162

    Even[0]=2;
Even[1]=8;
for(int i=2;i<N; i++) {
   Even[i]=Even[i-1]*4 + Even[i-2];
}

    Так тоже можно


    1. idkravitz Автор
      06.05.2019 10:14
      #20116658

      Спасибо, добавил в конец секции «Алгоритм»


      1. ignorance
        06.05.2019 11:24
        #20117020
        +1

        Более того, это обобщается. Любую t-подпоследовательность (составленную из чисел, стоящих на местах, кратных t) Фибоначчи можно выразить через ее саму. Смотрите
        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).

        Доказать, думаю, по индукции вполне возможно, просто вывод долгий получится.


        1. idkravitz Автор
          06.05.2019 11:38
          #20117108

          a(t) лучше переписать в виде a(t)=F(t)+2F(t-1), тогда оно будет определелено для всех t>=1

          Идея интересная, попробую придумать доказательство покороче)


          1. ignorance
            06.05.2019 11:54
            #20117200

            Да, действительно.
            Я попробовал в лоб вывести через равенство
            F(n+t) = F(t)*F(n+1) + F(t-1)*F(n)
            Но приехал к остаточному члену
            F(t-2)*F(n) — F(t)*F(n-2)
            Возможно, уже есть известное равенство для таких выражений?


            1. idkravitz Автор
              06.05.2019 12:24
              #20117450

              Я доказал индукцией, вставил в статью в конец секции «Обобщение», спасибо)


  1. kvazimoda24
    05.05.2019 17:13
    #20114282

    Остался вопрос, на сколько вообще актуально знание математики для программиста PHP? Почему-то мне кажется, что такое знание математики требуется в единичных случаях. Больше необходимы умения связать несвязуемое, там 1С прицепить к сайту, плагин для магазина какой добавить...


    1. yu-hritsaiy
      05.05.2019 17:28
      #20114352

      У вас слишком ограниченное видение работы программистом, на php так же пишутся большие приложения, а не только связывают не связуемое и не впихуемое


      1. kvazimoda24
        05.05.2019 17:45
        #20114398
        +2

        Вполне допускаю это, но смотрю на большинство сайтов, которыми сам пользуюсь, и вот не понимаю я, где там может жить даже такая довольно примитивная математика из статьи.
        Соответственно, и когда требуется программист для впихивания невпихуемого, а на собеседовании от него требуют каких-то извращений с высшей математикой и квантовой физикой, то мне это начинает напоминать требование высшего образования и докторской степени от уборщицы.


    1. maximw
      05.05.2019 18:40
      #20114600
      +3

      Из всего пласта математики, преподанного в универе, в веб-разработке пригодилась только пару раз дискретная математика (графы и конечные автоматы) и немного тервер. Остальная огромная часть математики полезна, но как общее развитие мышления.


    1. idkravitz Автор
      05.05.2019 18:54
      #20114648

      Бэкэнд в онлайн-игрушках (браузерки и флеш — точно) нередко пишут на PHP, если там прокрадываются элементы геймдизайна, то знание математики будет полезным.


      1. Soffort
        06.05.2019 14:56
        #20118492

        По-хорошему, геймдизайнер в таких случаях должен предоставить формулы или алгоритм. От разработчика знание подобных вещей нужно, скорее, для увеличения производительности.


    1. middle
      06.05.2019 06:05
      #20116034

      Вы используете математику каждый раз, когда задумываетесь о том, правильно ли работает программа. То есть когда пишите её, когда ищете баги, когда читаете чужой код. Потому что во всех этих случаях вам приходится рассуждать. Мысленно доказывать леммы и теоремы об этом коде, искать противоречия, находить контрпримеры. В общем, как мольеровский Мещанин — вы говорите прозой, но не догадываетесь об этом :)))


      1. kvazimoda24
        06.05.2019 09:25
        #20116438

        Является ли это той математикой, о которой идёт речь в статье, или это всё же ближе к логике и алгоритмике?
        Так-то уборщица тоже использует химию, при мытье полов и физику, когда отдирает прилипшую жвачку, а математику при подсчёте своей зарплаты.
        И да, я не хочу ни сколько принизить профессию программиста, да и уборщицы тоже. Мне просто кажется, что зачастую подобные требования выдвинутые работодателями не совсем адекватны.


        1. middle
          06.05.2019 09:44
          #20116492

          Для решения этой задачи не требуется ничего, кроме способности совершать логические умозаключения. Автор статьи пошёл в ней гораздо дальше того, что требовалось в задаче. Сомневаюсь, что авторы задачи требовали от него чего-то большего, чем подсчёта N-го числа и проверки его на чётность. Не rocket science.


  1. storm_r1der
    05.05.2019 18:55
    #20114650
    +5

    Boomburum, не работает отображение формул на мобилке, fix pls :(


    1. Boomburum
      06.05.2019 16:46
      #20119266

      А можете больше подробностей в личку прислать? На каком девайсе/ос/браузере не работает.
      У меня в ios/chrome формулы отображаются.


      1. storm_r1der
        07.05.2019 21:58
        #20125978
        +1

        Уже все заработало, не знаю, с чем связано)

        На всякий случай: Xiaomi Redmi Note 4x, Chrome 73.0.3683.90, включая отображение версии для ПК.


  1. izac
    05.05.2019 19:35
    #20114774
    +2

    [sarcasm]
    >Решил с помощью цикла(for)
    >while

    Мы вам перезвоним.
    [/sarcasm]


  1. ainoneko
    05.05.2019 19:51
    #20114812
    +3

    … А потом оказалось, что потенциальный работодатель чётными числами называет числа, стоящие на чётных местах (2-е, 4-е, 6-е, ...)?


    1. dzmitry_li
      06.05.2019 07:58
      #20116188

      Значит можно сказать — потенциальный работодатель не умеет давать чёткие ТЗ


      1. MarazmDed
        06.05.2019 10:07
        #20116620

        Значит можно сказать — потенциальный работодатель не умеет давать чёткие ТЗ

        … Добро пожаловать в реальный мир :) Не знаю, на счет работодателей, но подавляющее большинство Заказчиков не умеет давать четкие ТЗ и предпочитают играться с формой квадрата.


  1. janatem
    05.05.2019 20:25
    #20114938
    +1

    существуют ли ещё чётные числа Фибоначчи чей номер не кратен 3?

    После чего идет несколько абзацев выкладок, чтобы это доказать. При том, что выше уже выписано равенство из которого это тривиальным образом следует:
    F_{n+3} = 2F_{n+1} + F_n
    Если F_n — нечетное, то F_{n+3} — тоже нечетное. Остается лишь проверить четность двух первых чисел ряда.


    1. idkravitz Автор
      06.05.2019 09:19
      #20116412

      Упустил, спасибо, добавил в статью


  1. MSC6502
    05.05.2019 21:10
    #20115086
    -5

    Само словосочетание «программист PHP» оксюморон.


  1. pallada92
    06.05.2019 10:00
    #20116568

    Кстати, есть ещё одна прикольная задача про сумму первых n четных чисел Фибоначчи, которая решается за О(1). Сумма чисел Фибоначчи от 1 до 3n равна числу Ф. с номером 3n + 2, с другой стороны это удвоенная сумма первых n четных чисел Ф. т. к. каждое чётное равно сумме двух предыдущих, а они как раз идут группами по три. То есть ответ что-то вроде F(3n+2) / 2, который считается напрямую по формуле Бине.


  1. n0rbert
    06.05.2019 11:16
    #20116966
    -1

    Мнится мне, что работодатель, говоря про Фибоначчи, имел в виду рекурсию. А в рекурсию могут не только лишь все…


    1. Soffort
      06.05.2019 14:58
      #20118516

      Мнится мне, что программисты должны работать по ТЗ, а не догадками, кто там что имел в виду.


      1. n0rbert
        06.05.2019 19:24
        #20120098

        Вот если примут на работу, дадут ТЗ. А это был тест на наличие компетенций. И человек его не прошел. Потому что не все задачи решаются в лоб. Через цикл for.


        1. Soffort
          06.05.2019 20:22
          #20120310

          А сколько начнёт кушать памяти «компетентное» рекурсивное решение не в лоб через пару тысяч итераций?


  1. homm
    06.05.2019 16:34
    #20119198

    Вот сейчас сижу и думаю, наверное все-таки из-за Фибоначчи пролетел

    Я так и не понял, почему. Если задача действительно стояла так, как описано в письме (выбрать все четные числа Фибоначчи в диапазоне от 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]

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


    Что конечно не уменьшет интересность статьи, если отойти от просто решения тестового задания.


    1. idkravitz Автор
      06.05.2019 18:27
      #20119842

      Наверное вы не смотрели оригинальный пост или уже забыли) там всесторонне рассматривались способы вычисления N-ого числа Фибоначчи, ну и юзернейм этим комментарием как бы иронизировал, что наверное в этой самой простой задаче собака то и была зарыта. А так вы все правильно заметили в 99% случаев чем проще решение, тем лучше, а основное назначение этого поста — жвачка для мозгов.


  1. Mr_Chelovek
    06.05.2019 17:07
    #20119412

    Прелесть этого примера еще и в том, что он не будет работать на PHP, если его перевести как есть.

    Дело в том, что в PHP числа только до 64 бит точности. А дальше они становятся double, у которых не проверить четность из-за маленького диапазона.

    А в Питоне числа безразмерные

    In [16]: print(10**100 + 1)                                                                                                     
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001


    В PHP же нестрогая типизация, там скорее всего получится что-то такое:

    php > print(10**30 + 1);
"десять в тридцатой один"


    1. idkravitz Автор
      06.05.2019 18:29
      #20119870

      Там ограничение на значение чисел Фибоначчи, а не на их номер, поэтому будет работать. Если изменить задачу и поставить ограничение в 10000 на количество чисел, то да, надо будет подключать длинную арифметику.


  1. Compolomus
    07.05.2019 00:38
    #20121226

    Самое смешное было как то такое же тз. Фибоначи, запрос с др, и третье найти количество белых пикселей на изображении,
    К третьему заданию придрались, и я ещё написал два разных способа и доказал через картинку созданную самим php что количество пикселов считает верно. Фибоначи нашёл какой то пример в мане про генераторы, запрос сам составил. Оказывается это стандартный набор). Я отказался, так как удалёнка. Типо я прошёл