Вам нужно подняться по лестнице. За один раз можно подняться на одну или две ступеньки. Сколько существует способов добраться до N-й ступеньки?

Начало здесь простое. Вы стоите на лестничном марше и хотите подняться на первую ступеньку — № 1. Для этого надо сделать всего одно действие — подняться на одну ступеньку вверх. Теперь давайте рассмотрим вторую ступеньку, то есть N = 2. Чтобы подняться на неё, имеются два варианта. Вы можете сделать два шага — по одной ступеньке за раз или сразу подняться на вторую ступеньку.

Это практически вся информация, которая нужна вам для решения этой задачи. Чтобы понять, почему, представьте, что вашей целью является ступенька № 3. Впервые в этой ситуации вы не можете попасть на неё одним движением. здесь потребуется комбинация шагов. Существует только два способа попадания на ступеньку № 3: либо в виде короткого одиночного шага (со ступеньки № 2), либо двойного шага (со ступеньки № 1). Мы уже знаем, что для подъема на ступеньку № 1 имеется лишь один вариант. Мы также знаем, что есть всего два способа подняться на ступеньку № 2. Сложите эти варианты (1 + 2 = 3), и вы получите число способов, позволяющих подняться на ступеньку № 3.

Та же самая логика применяется для подъема на каждую следующую ступеньку. Существует два способа, чтобы подняться на ступеньку № 4 — со ступеньки № 2 или со ступеньки № 3. Добавьте число способов подъема на ступеньку № 2 (2) к числу способов, позволяющих оказаться на ступеньке № 3 (3). Это даёт 5 вариантов — число способов, позволяющих оказаться на ступеньке № 4.

Легко продолжить эту серию и дальше. С увеличением числа ступенек число способов подниматься по ним нарастает, как снежный ком, что можно представить в следующем виде:

Любому человеку с математической подготовкой нижняя серия покажется до боли знакомой. Так оно и есть. Это последовательность Фибоначчи. (Чуть подробнее о ней ниже.) Интервьюер хочет получить ответ для общего случая из N ступенек.

Это просто число Фибоначчи под номером N. Леонардо Фибоначчи, также известный как Леонардо Пизанский, был самым влиятельным итальянским математиком в Средние века. Именно Фибоначчи понял невероятное превосходство арабскo-индийской позиционной системы исчисления по сравнению с римским обозначением цифр, которое все ещё использовалось в средневековой Европе. При помощи арабско-индийской системы умножение и деление можно было свести к алгоритму (еще одно арабское слово). При применении римских чисел эти операции на практике выполнять было сложно. Торговцам приходилось приглашать экспертов и дорого им платить за вычисления, которые те осуществляли при помощи абаков. В 1202 году Фибоначчи написал Liber abaci — руководство по использованию абака, в котором он расхваливал арабские числа своим читателям, которые были, скорее всего, настроены к ним скептически. В этой книге также описывается и та серия чисел, которую мы теперь называем по его фамилии. Однако её изобрел не Фибоначчи. Эта последовательность была известна еще индийским ученым, жившим в VI веке.

Напишите 1, а затем добавьте еще 1 рядом. Сложите их и получите сумму (2), которая затем добавляется к формируемой последовательности:

1 1 2

Для получения каждого нового члена лишь складывайте последние два числа в ряду/ Серия примет следующий вид.

1 1 2 3 5 8 13 21 34 55 89 144…

Поклонники теории заговоров отыскивают серии Фибоначчи в самых неожиданных местах. Хотите перевести расстояние из миль в километры? Воспользуйтесь соседними числами Фибоначчи (55 миль в час = 89 километров в час). В следующий раз, когда у вас окажется свободное время, посчитайте небольшие дольки, из которых состоит кожура ананаса, и вы обнаружите, что они образуют два накладывающихся друг на друга набора спиралей, идущих в противоположных направлениях. В одной из них восемь долей, в другой тринадцать. Оба этих числа относятся к серии Фибоначчи. Аналогичные закономерности можно увидеть в сосновых шишках, подсолнухах и артишоках. Случайность? Вряд ли, если учесть тот факт, что последовательность Фибoначчи проявила себя и в Коде Да Винчи (в виде комбинации для вскрытия сейфа), и в этом вопросе на собеседовании, который задают в компании, стремящейся к информационному доминированию во всем мире (Google, если вы не поняли).