Pull to refresh

Об одной задаче, которую больше не предлагают на собеседовании

Reading time 2 min
Views 33K
В одной компании кандидатам на вакансию программиста какое-то время предлагалась следующая задача. Найти значение дроби:

$\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+...}}}} $


Для решения данной задачи не требуется знания природы таких дробей и области, в которой эти дроби применяются. Нужно только заметить, что предложенное выражение самоподобно и может быть представлено в виде:

$x=\frac{1}{1+x}$

А это, в свою очередь, приводит к обычному квадратному уравнению:

$x^2+x-1=0\\ x=\frac{sqrt(5)-1}{2}\\ x=0,618033988...$



Теперь скажем, что данные дроби имеют особое название, это цепные дроби, и они используются, как одна из форм записи вещественных чисел. В рассмотренном примере бесконечная цепная дробь имеет самое простое представление. В ее записи используются только единицы, и длина её периода тоже равна единице. Любопытно, что выражаемое ею число очень широко представлено, и не только в математическом мире, и даже имеет собственное название — обратная величина для «золотого сечения». Получим несколько приближений для данного числа, используя его представление через цепную дробь. На первом шаге отбросим второе слагаемое в знаменателе. Получим $\frac{1}{1}$, теперь запишем следующее приближения, используя полученный результат, как второе слагаемое в сумме под знаком дроби $\frac{1}{1+\frac{1}{1}}=\frac{1}{2}$ Повторим эту операцию ещё раз $\frac{1}{1+\frac{1}{2}}=\frac{2}{3}$ В результате мы получим следующий ряд:

$\frac{1}{1},\frac{1}{2},\frac{2}{3},\frac{3}{5},\frac{5}{8},\frac{8}{13}...$


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

$1,1,2,3,5,8,13,21...$

Составим ряд образованный отношениями двух соседних членов последовательности Фибоначчи

$\frac{1}{1},\frac{1}{2},\frac{2}{3},\frac{3}{5},\frac{5}{8},\frac{8}{13}...$

Не правда ли, знакомая запись? Действительно, предел отношения двух чисел Фибоначчи выражается обратной величиной «золотого сечения». Получим этот результат.
Из определения следует, что

$F_{i+1}=F_i+F_{i-1}$

$\frac{F_{i+1}}{F_i}=1+\frac{F_{i-1}}{F_i}$

Введем следующее обозначение

$s_{i-j}=\frac{F_i}{F_j}$

Тогда предыдующее равенство запишется как

$s_1=1+s_{-1}$

В пределе

$s_1=\frac{1}{s_{-1}}$

Введем обозначение $x=s_{-1}$. Тогда мы получим уравнение, которое уже приводили в начале статьи.

$x=\frac{1}{1+x}$


Теперь рассмотрим последовательность, у которой три первых члена равны единицы, а каждый последующий равен сумме трех предыдущих.

$1,1,1,3,5,9,17,31,57,105,...$

Найдем предел, к которому стремится отношение двух соседних членов последовательности. По определению

$F_{i+3}=F_i+F_{i+1}+F_{i+2}$

Разделим левую и правую часть на $F_{i+1}$. Тогда в используемых ранее обозначениях мы можем записать:

$s_2=s_{-1}+s_1+1$

Теперь разделим левую и правую часть на $F_{i+2}$. Получим следующее cоотношение:

$s_1=s_{-2}+s_{-1}+1$

Обозначим

$s_1=x\\ s_2=y$

В новых обозначениях система уравнений будет выглядеть так:

$y=\frac{1}{x}+x+1\\x=\frac{1}{x}+\frac{1}{y}+1$

Данная система приводится к следующему уравнению:

$y^3-3y^2-y-1=0$

Оно имеет одно вещественное решение

$y=3,382976...$

Если рассмотреть ряд для последовательности, у которой каждый член равен сумме уже четырех предыдущих,

$1,1,1,1,4,7,13,25,49,94,181,349,...$

то мы придем к системе из трех уравнений:

$z=x+y+\frac{1}{x}+1\\ y=x+\frac{1}{x}+\frac{1}{y}+1\\ x=\frac{1}{z}+\frac{1}{y}+\frac{1}{x}+1 $

А эта система приводится к следующему нелинейному уравнению:

$y^4-3y^3-3y^2+y+1=0$


Это уравнение имеет два вещественных корня. Решением нашей задачи будет:

$y=3,715495... $


Вот такие наблюдения произошли, благодаря одной задаче на собеседовании.
Tags:
Hubs:
+1
Comments 61
Comments Comments 61

Articles