Для решения данной задачи не требуется знания природы таких дробей и области, в которой эти дроби применяются. Нужно только заметить, что предложенное выражение самоподобно и может быть представлено в виде: А это, в свою очередь, приводит к обычному квадратному уравнению:
Теперь скажем, что данные дроби имеют особое название, это цепные дроби, и они используются, как одна из форм записи вещественных чисел. В рассмотренном примере бесконечная цепная дробь имеет самое простое представление. В ее записи используются только единицы, и длина её периода тоже равна единице. Любопытно, что выражаемое ею число очень широко представлено, и не только в математическом мире, и даже имеет собственное название — обратная величина для «золотого сечения». Получим несколько приближений для данного числа, используя его представление через цепную дробь. На первом шаге отбросим второе слагаемое в знаменателе. Получим , теперь запишем следующее приближения, используя полученный результат, как второе слагаемое в сумме под знаком дроби Повторим эту операцию ещё раз В результате мы получим следующий ряд:
Обратимся теперь к такому понятию, как последовательность Фибоначчи. Так называются члены числового ряда, составленного по следующему правилу. Первый и второй член ряда равны единице, а каждый последующий равен сумме двух предыдущих. Составим ряд образованный отношениями двух соседних членов последовательности Фибоначчи Не правда ли, знакомая запись? Действительно, предел отношения двух чисел Фибоначчи выражается обратной величиной «золотого сечения». Получим этот результат.
Из определения следует, что Введем следующее обозначение Тогда предыдующее равенство запишется как В пределе Введем обозначение . Тогда мы получим уравнение, которое уже приводили в начале статьи.
Теперь рассмотрим последовательность, у которой три первых члена равны единицы, а каждый последующий равен сумме трех предыдущих. Найдем предел, к которому стремится отношение двух соседних членов последовательности. По определению Разделим левую и правую часть на . Тогда в используемых ранее обозначениях мы можем записать: Теперь разделим левую и правую часть на . Получим следующее cоотношение: Обозначим
В новых обозначениях система уравнений будет выглядеть так: Данная система приводится к следующему уравнению: Оно имеет одно вещественное решение Если рассмотреть ряд для последовательности, у которой каждый член равен сумме уже четырех предыдущих, то мы придем к системе из трех уравнений: А эта система приводится к следующему нелинейному уравнению:
Это уравнение имеет два вещественных корня. Решением нашей задачи будет:
Вот такие наблюдения произошли, благодаря одной задаче на собеседовании.
Комментарии (60)
golf2109
30.06.2017 02:38+6Нужно только заметить, что предложенное выражение самоподобно
автору осталось раскрыть — что такое «самоподобное выражение»…
staticlab
30.06.2017 07:50Запись
предполагает, что все соседние подходящие дроби (а следовательно, все они между собой) равны, что очевидно неверно.
Я уже не говорю о том, что золотое сечение представляется вовсе не уравнением
x^2 + x - 1 = 0, а, внезапно,x^2 - x - 1 = 0.
scientes
30.06.2017 09:33Разумеется, отношения чисел с одинаковой разницей индексов не равны. Равенство возникает при предельном переходе.
Замечание по золотому сечению учел, значение.дроби — это обратная к золотому сечению величина.
GlukKazan
30.06.2017 08:41+5В чём практический смысл такой задачи на собеседовании? Если соискатель знает как решать — он решит, если не знает — вряд ли догадается. Олимпиадников набираете? Или на работе они будут математикой заниматься?
scientes
30.06.2017 09:39-1Статья не о том, какие вопросы надо задавать на собеседовании. Хотя смею полагать, что прочитавший теперь сможет подобные задачи решить. А это уже хорошо.
GlukKazan
30.06.2017 12:13+4Тогда при чём тут слово «собеседование» в заголовке статьи? (Да-да, понимаю, это потому что такая задача попалась на собеседовании). Видите ли в чём дело, я против таких задач на собеседовании. Именно потому что на собеседовании не вижу в них особого смысла. А к самой статье никаких претензий, разумеется, нет.
Adel-S
02.07.2017 16:34+2Да не так чтобы очень. Вспомнить хотя бы известную задачу на собеседовании дизайнера: «Нарисуйте круг в фотошопе не пользуясь мышью».
Я теперь тоже могу эту конкретную задачу решить.
Но это не делает меня дизайнером.
beavis88
30.06.2017 10:12-1Смысл как раз есть, эта задача имеет единственное решение — одно это уже намного лучше абстрактных про люки или шарики. Поскольку интервьюируемый скорее всего не математик, его слегка напугает эта страшная формула (предусловие теста по выведению из зоны комфорта выполнено). С другой стороны, смысл её понятен даже школьнику. Решение так же не требует специальных знаний, нужно только заметить закономерность. В общем, идеальный тест для навыков необходимых программисту.
VMichael
30.06.2017 10:48+8Мы в свое время пробовали давать тесты про люки и шарики. Потом давать математические задачки.
За более чем 10 лет собеседований, у меня сложилось мнение, что все эти тесты никак не коррелируют с дальнейшей работой сотрудника. Есть люди, которых хлебом не корми дай задачки порешать, но работают увы, плохо. И наоборот.
В подавляющем большинстве случаев, если человек пришелся «по душе» во время беседы «ни о чем», то и далее работать с ним комфортно, не зависимо от результата решения головоломок.
Пришел к тому, в итоге, что на собеседовании эффективнее обсуждать темы максимально близкие к тем, которыми будет заниматься сотрудник и тестовое задание на знание продукта (в нашем случае Transact SQL), с которым будет работать сотрудник, а не математические задачки и ребусы с шарадами.
Если в работе нужна реально математика, тогда имеет смысл спрашивать математическую базу, но таких мест относительно мало, хотя задачки любят спрашивать многие.
А уже как работает человек в реальной работе, все равно открывается только во время испытательного срока на реальных задачах.scientes
30.06.2017 10:56-1У нас есть все и математика и тесты, максимально приближенные к предметной области, и учет психологических качеств соискателя. Но нам нужно, чтобы человек знал, хотя бы, арифметику. От приведенного примера отказались, задавать некому. Хорошо ещё, что он послужил поводом для этой статьи.
VMichael
30.06.2017 11:03+7Я и не возражаю, если нужна математика в работе, математику нужно спрашивать.
Я про то, что есть много работ, где математика не используется, но ее все равно спрашивают.
Как пример:
Работал я в банке неск. лет. Там тоже любили спрашивать математические задачки и рассказывать о мега перспективах. И текучка была просто бешенная. Когда мне поручили участвовать в собеседованиях, я говорил кандидатам: работа мега скучная. Ковырять отчетность. Математика выше арифметики не нужна. Продукт устоявшийся, прорывов не намечается. Перестали меня брать на собеседования, ты говорят, нам всех кандидатов распугаешь. Но себе в группу я все же собеседовал и у меня текучка стала близка к 0, просто люди понимали, что их ждет и уже решали, нужно ли им это. Я считаю, что это выгоднее, чем обучать человека системе, а он через 2-3 месяца сваливает.
От приведенного примера отказались, задавать некому.
Молодцы, в Кайдзен это называется «провести корректирующие мероприятия» :)
leshabirukov
30.06.2017 15:13+3эта задача имеет единственное решение
Вообще-то нет. Еще как минимум -1,618… =(-sqrt(5)-1)/2, и я подозреваю есть ещё много периодических последовательностей
Х[i+1] = 1/(X[i] + 1)
X[0] = X[N]
beavis88
04.07.2017 11:33Я про исходную задачу говорил, а не квадратное уравнение. Т.е. решение в данном случае это подмножество решений квадратного уравнения. Поскольку оно является множеством оно однозначно определено.
Вообще это неформальное решение, так что отрицательное x можно отбросить из рассмотрения что бы не доказывать что знаменатель на каждом шаге не может быть 0, иначе придётся давать формальные определения сходимости и доказывать каждый шаг, т.е. строить теорию цепных дробей.
При чём тут эта последовательность, куда вы её собрались подставлять???
grossws
30.06.2017 16:03+6С другой стороны, смысл её понятен даже школьнику.
Смысл великой теоремы Ферма тоже понят школьнику. Но на доказательством бились три века xD
hurtavy
02.07.2017 13:12Настораживает, когда программист совсем не математик. В смысле, не умеет решать квадратное уравнение
TheShock
02.07.2017 22:25Ну не знаю, я вот последний раз с ними сталкивался много лет назад. Тогда решал с легкостью, а сейчас помню только что-то там про дискримин
ациюант. Возможно, за 15 минут в гугле вспомню, но как-то гуглить на собеседовании — это не очень.grossws
02.07.2017 23:31Достаточно представлять откуда берется этот самый дискриминант, тогда получить для него формулу не представляет труда. Благо, вывод формулы для квадрата суммы не является чем-то сложным.
TheShock
02.07.2017 23:51Я вот даже смутно помню как эту формулу использовать. Даже если бы я ее вывел.
MikailBag
03.07.2017 21:18Подставляете коэффициенты и получаете значения корней.
Если в процессе полезут корни из отрицательных чисел, либо включаете комплексный режим, либо говорите, что действительных корней нет.TheShock
03.07.2017 21:32Та если бы мне сейчас было необходимо, то я бы нагуглил детали и решил. Я знал, как решаются эти уравнения. Даже участвовал в математических олимпиадах и занимал неплохие места. Но это было уже лет 10-15 назад, и все это очень сильно забылось, потому на собеседовании я бы так и сказал:
— Я не помню, как решать квадратические уравнения, так как 10 не решал, но если для работы будет необходимо, то вспомнить это — полчаса времени.
samodum
30.06.2017 09:42+14В ответ на такую задачку я попросил бы её же задать каждому действующему сотруднику в этой компании примерно той же должности. И всех не ответивших уволить как не прошедших «собеседование»
scientes
30.06.2017 09:48-1Задача предлагалась на предварительном этапе, до очного собеседования. Действующим тоже задавали. Увольнять не стали. К большому сожалению, уровень соискателей сильно упал. Двигаемся к тому, чтобы на собеседовании показывать кубики с цифрами.
Odrin
30.06.2017 11:31+7уровень соискателей сильно упал
Кого приглашаете на собеседование, те и приходят.
TerraV
02.07.2017 20:10+1А я попросил бы юз-кейс из практики приближенный к данной задаче. И после того как не получил бы удовлетворительный ответ сказал бы пока-пока этой компании.
Вообще у меня сложилось впечатление, что у подобных задач одна цель — показать соискателям что они дно и прогнуть по з.п.samodum
05.07.2017 00:58+1Против таких, которые хотят «показать соискателям что они дно и прогнуть по з.п.» есть один довольно известный и очень действенный способ. Надо в ответ на глубокие вопросы задавать в ответ точно такие же глубокие вопросы собеседующему. Суть вот в чём. Не все кандидаты понимают смысл «СО-беседования». То есть, не только они отбирают кандидатов, но и вы отбираете интересную компанию и команду.
И когда слышите в свой адрес издевательские вопросы, то можете смело задавать точно такие же вопросы. На удивлённые взгляды отвечайте: «А что? Я хочу работать в команде профессионалов, которые знают как применять volatile и чем семафор отличается от мьютекса, а шаблон стратегии от фабрики. Что, не знаете? Жаль. Видно, нам с вами не по пути»samodum
06.07.2017 11:44И в лице собеседующих коллег эти «умники» будут поставлены в неловкое положение
VMichael
30.06.2017 09:45+1Должность — программист математик?
scientes
30.06.2017 10:01Программист с хорошей математической подготовкой. Впрочем этот тест он, скорее на то, как функционирует мозг соискателя, а не на практические знания. Впрочем, способных к озарению крайне мало, и это нисколько не умоляет деловые и профессиональные качества остальных.
HomunCulus
30.06.2017 10:18Обычный матан. Сходящиеся и расходящиеся ряды. Единственное, что многие после универа это подзабывают, а так никакой сверх математикой тут и не пахнет. Если курил матан в свое время, то все вполне легко решаемо, даже если и подзабыл.
Eldhenn
30.06.2017 10:19> Вот такое исследование получилось
Исследование про три частных случая?scientes
30.06.2017 10:32Ну нет. Из статьи понятно как получить систему уравнений для поиска предельных отношений в рассмотренных рядах. А вот для решения таких систем при количестве исходных уравнений больше трех, скорее всего, уже нужно ПО для символьной математики. С карандашом и ручкой я справиться не могу. Да и смысла большого в этом не вижу.
Eldhenn
30.06.2017 10:46Вот если бы вы исследовали эти системы/уравнения, нашли подходы к их решению, ну и вообще что-то общее про «расширенные Фиббоначи» — было бы хорошее исследование. А пока что это выглядит как преамбула к исследованию.
scientes
30.06.2017 10:59Соглашусь с Вашим мнением, это не исследование, а наблюдение. Исправил текст.
AlexanderS
30.06.2017 11:48Прикола ради такую задачку написал своим коллегам на доске. Сказал, что это задачка на собеседование. Почесали голову, доску исписали. Ну, вообщем коллективно всё свелось к «развёртыванию» дроби и выводе квадратного уравнения с нахождением корня. Кто-то подтянул матлаб и циклом определил схождение ряда. Было весело )))
Я просто к тому, что будучи вчерашними студентами любой из нас наверняка бы её и решил или хотя бы попытался. А 10-15-летние разработчики — уже не факт, что даже пробовать станут, хотя интерес и проявят. А в целом даже грустно — время идёт и уже многое напрочь забывается, когда годами пилишь какие-нибудь высокоскоростные интерфейсы (хотя надо заметить что я не «чистый» программист, а хардварный инженер-программист).staticlab
30.06.2017 12:32С обращением непрерывной дроби в простую через подходящие дроби можно ознакомиться здесь (§2).
Вообще кажется, что такую задачу решит:
- тот, кто знает, как решать (помнит рекуррентные правила Эйлера, к которому здесь имеет отношение и ряд Фибоначчи) или что эта задача имеет отношение к золотому сечению;
- тот, кто сам сможет повторить все математические выкладки (да, а на работе будет заниматься максимум арифметикой).
scientes
30.06.2017 13:00А вот любопытно, если попросить на собеседовании написать программу для расчета данной дроби с требуемой точностью, это вызовет затруднение? Это сложная задача для программистов ?
grossws
30.06.2017 16:08Можно и что-нибудь попроще. Например, приближенное вычисление sin/cos/sqrt с заданной точностью. А тем кто сильно понтовался просто немного увеличить требуемую точность (оставив неточными пару младших бит, например).
Parseval
01.07.2017 11:02+15Автору спасибо за интерес к математике. Надеюсь, он не исчезнет после небольшого холодного душа.
Во первых, существование предела нужно доказывать. Если кто-то думает, что можно обойтись, пусть поинтересуется парадоксом Перрона.
Во вторых, даже постановка «найдите отношение соседних членов» может оказать некорректной. Поясню.
Возьмём соотношение f(n+1) = 2f(n) — 2f(n-1), f(1) = 1, f(2) = 1.
Не поленитесь посчитать пару десятков следующих членов. Сюрприз — будут нули, причём их бесконечно много.
Можете взять другие начальные условия. Например, f(1) = 1, f(2) = 3. Сюрприз номер два — отношение будет принимать значения 3, 4/3, 1/2, -2 и дальше по кругу. Предела опять нет.
А у последовательности f(n+1) = 2f(n) — 3f(n-1) отношение будет прыгать без никакого намёка на предел.
Логичный вопрос — а что же тогда делать? Ответ — то, что вы можете обосновать. Допустим (допустим, а не постулирем!), у отношения f(n+1)/f(n) существует существует предел x. Тогда у f(n+2)/f(n) = (f(n+2)/f(n+1))/(f(n+1)/f(n)) тоже есть предел и он равен x^2. Аналогично для f(n+3)/f(n) стремится к x^3.
Для примера возьмём последнее уравнение. Поделив обе части на f(i), получим, что предел должен быть корнем уравнения x^4 — x^3 — x^2 — x — 1 = 0. Или предела нет, ещё ничего не доказано. Это и есть граница того, что можно доказать совсем на пальцах.
Между прочим, коэффициенты будут теми же самыми, что и в рекуррентном соотношении, и это неспроста. Собственно, найдя решения уравнения можно получить явную формулу для общего члена последовательности. Знакомые с линейной алгеброй могут попробовать разобраться самостоятельно.
Мораль 1. Баги бывают не только в наших программах, но и в рассуждениях.
Мораль 2. Если решаете математическую задачу, отвлекитесь от программистского подхода «сейчас машина всё нам посчитает».scientes
01.07.2017 11:10Прекрасный комментарий. Я занимаюсь скорее арифметикой, чем математикой. Как правило, свои размышления произвожу по дороге на работу, в электричке. Доказать наличие предела я не могу. В таких вопросах поступаю как физик, делаю предположение, потом ставлю эксперимент. Тоже самое и с этими пределами. Посмотрел в Excel и сравнил корнем полученного выражения. А за общий подход к таким задачам большое спасибо. Я его не увидел. Теперь этот пробел исправлен.
GlukKazan
02.07.2017 15:31+4Здесь вспоминается анекдот:
Как доказать что все нечётные числа простые?
Надеюсь, что никого не обидел.
Математик: 3-простое, 5-простое, 7-простое, дальше по индукции…
Физик: 3-простое, 5-простое, 7-простое, 9-ошибка эксперимента, 11-простое,…
Инженер: 3-простое, 5-простое, 7-простое, 9-простое,...
Parseval
03.07.2017 14:51Ещё несколько соображений.
Существование предела можно доказать, если работает один из таких подходов.
1. Последовательность x(n) будет, например, монотонно возрастать и при этом все x(n) не превышают x (единственно возможный кандидат в пределы).
2. Монотонности может и не быть, x(n) «прыгает» вокруг x, но всё же можно сравнить |x(n+1) — x| с |x(n) — x| и окажется, например, что их частное не превышает какого-нибудь у<1 или наличие другой оценки гарантирующей сходимость (тут придётся вспоминать матанализ). Для примера можете посмотреть на итеративный процесс для вычисления корня t(n+1) = (t(n) + a/t(n))/2 и обоснование его сходимости.
И есть сильное подозрение, что если рекуррентное соотношение «короткое», коэффициенты и начальные значения «небольшие», то расчёт вручную нескольких сотен первых членов будет достаточным основание для сходимости. Но доказательство (если утверждение вообще верно) со всеми выкладками и обоснованиями, включая точные оценки для «короткое», «небольшие» и «несколько сотен» займёт приличный размер.Для тех, кто знает, как выглядит общее решениеОтсутствие предела и при этом малое изменение x(n) говорит о том, что доминирующим членом в f(n) будет a^n sin(bn +c) при очень малом b. Само a не может быть большим (по предположениям на коэффициенты), поэтому при слишком малом b свободный член уравнения забьёт остальные.
А вот при больших степенях могут оказаться близкие комплексные корни и здесь можно серьёзно завязнуть в оценках.scientes
03.07.2017 15:36Куда удобнее просто получить явную формулу для f(n), тогда поведение частного сразу станет очевидным.
Вы говорите о явной формуле для n -ого члена последовательности? Для чисел Фибоначчи — это формула Бине, для следующего случая (узнал, что такие числа называются числа трибоначчи) общая формула есть в статье по ссылке. А есть ли формула для произвольного n? И есть ли свое название у того вида рядов, которые были рассмотрены в статье? Заранее благодарен.
Parseval
03.07.2017 17:04Для знакомых с линейной алгебройПерейдём от уравнения (где все члены перенесены в левую часть) к системе. Обозначим через g(n) вектор-столбец из последовательных членов (f(n), f(n-1), ..., f(n-k))^T, где k = количество членов в рекуррентном соотношении минус два. Например, для соотношения Фибоначчи это (f(n), f(n-1))^T. В результате получим, что g(n+1) = A g(n), где в матрице A первая строка — это коэффициенты уравнения, а последующие — (0… 1… 0) — единица в i cтроке стоит на i-1 месте, остальные нули.
Тогда g(n) = A^n g(0). Переходим к собственному базису, A=T^{-1}BT, и всё сводится к возведению в степерь Жордановых клеток.
Эту конструкцию вы могли видеть в решении линейных дифференциальных уравнений с постоянными коэффициентами. Практически всё дословно перенеосится на дискретный случай.
romy4
02.07.2017 11:41Я бы сказал, что парадокс Перрона не соблюдает все условия бесконечности (самого большого числа): 1? = 1, но 1+1 = 2, а это больше 1, значит 1 не самое большое число. Бесконечность + бесконечность = бесконечность.
NElias
02.07.2017 20:02Пожалуйста, объясните, как получилось уравнение x = 1 / (1 + x). Первоначальное обобщение должно выглядеть как x(n) = 1 / (1 + x(n-1)), по идеи.
scientes
03.07.2017 10:08Равенство выполняется при предельном переходе. Устремляем n в бесконечность и говорим, что если предел существует, то он будет удовлетворять этому соотношению.
NElias
03.07.2017 13:14-1Сложно. Не припомню чтоб подобное решали на мат. анализе. Похоже это теорема какая-то и ещё нужно предел найти.
sens_boston
02.07.2017 20:05Задача, на мой взгляд, сравнима с вопросом на интервью мальчика из Amazon-а об оптимальном поиске всех палиндромов в строке. Т.е. мальчик хочет увидеть реализацию алгоритма Манакера, написанную на доске (хотя сам узнал об этом алгоритме за день до интервью).
atosdo
Задачка из славного учебника SICP.