Комментарии 61
Задачка из славного учебника SICP.
Это на какую должность такая задача? О_о. Я понял, что ничего не знаю.
Нужно только заметить, что предложенное выражение самоподобно
автору осталось раскрыть — что такое «самоподобное выражение»…
Объясните мне как это
вдруг стало отрицательным? — чтобы значение дроби получилось 3,7
1/(1-0,72)=3,7
вдруг стало отрицательным? — чтобы значение дроби получилось 3,7
1/(1-0,72)=3,7
А потом фронтендик говнокодить :)
Значение первой дроби из собеседования автор так и не назвал…
НЛО прилетело и опубликовало эту надпись здесь
В чём практический смысл такой задачи на собеседовании? Если соискатель знает как решать — он решит, если не знает — вряд ли догадается. Олимпиадников набираете? Или на работе они будут математикой заниматься?
Статья не о том, какие вопросы надо задавать на собеседовании. Хотя смею полагать, что прочитавший теперь сможет подобные задачи решить. А это уже хорошо.
Тогда при чём тут слово «собеседование» в заголовке статьи? (Да-да, понимаю, это потому что такая задача попалась на собеседовании). Видите ли в чём дело, я против таких задач на собеседовании. Именно потому что на собеседовании не вижу в них особого смысла. А к самой статье никаких претензий, разумеется, нет.
Да не так чтобы очень. Вспомнить хотя бы известную задачу на собеседовании дизайнера: «Нарисуйте круг в фотошопе не пользуясь мышью».
Я теперь тоже могу эту конкретную задачу решить.
Но это не делает меня дизайнером.
Я теперь тоже могу эту конкретную задачу решить.
Но это не делает меня дизайнером.
Смысл как раз есть, эта задача имеет единственное решение — одно это уже намного лучше абстрактных про люки или шарики. Поскольку интервьюируемый скорее всего не математик, его слегка напугает эта страшная формула (предусловие теста по выведению из зоны комфорта выполнено). С другой стороны, смысл её понятен даже школьнику. Решение так же не требует специальных знаний, нужно только заметить закономерность. В общем, идеальный тест для навыков необходимых программисту.
Приятно читать такие комментарии.
НЛО прилетело и опубликовало эту надпись здесь
эта задача имеет единственное решение
Вообще-то нет. Еще как минимум -1,618… =(-sqrt(5)-1)/2, и я подозреваю есть ещё много периодических последовательностей
Х[i+1] = 1/(X[i] + 1)
X[0] = X[N]
Я про исходную задачу говорил, а не квадратное уравнение. Т.е. решение в данном случае это подмножество решений квадратного уравнения. Поскольку оно является множеством оно однозначно определено.
Вообще это неформальное решение, так что отрицательное x можно отбросить из рассмотрения что бы не доказывать что знаменатель на каждом шаге не может быть 0, иначе придётся давать формальные определения сходимости и доказывать каждый шаг, т.е. строить теорию цепных дробей.
При чём тут эта последовательность, куда вы её собрались подставлять???
Вообще это неформальное решение, так что отрицательное x можно отбросить из рассмотрения что бы не доказывать что знаменатель на каждом шаге не может быть 0, иначе придётся давать формальные определения сходимости и доказывать каждый шаг, т.е. строить теорию цепных дробей.
При чём тут эта последовательность, куда вы её собрались подставлять???
С другой стороны, смысл её понятен даже школьнику.
Смысл великой теоремы Ферма тоже понят школьнику. Но на доказательством бились три века xD
Настораживает, когда программист совсем не математик. В смысле, не умеет решать квадратное уравнение
Ну не знаю, я вот последний раз с ними сталкивался много лет назад. Тогда решал с легкостью, а сейчас помню только что-то там про дискриминациюант. Возможно, за 15 минут в гугле вспомню, но как-то гуглить на собеседовании — это не очень.
Достаточно представлять откуда берется этот самый дискриминант, тогда получить для него формулу не представляет труда. Благо, вывод формулы для квадрата суммы не является чем-то сложным.
Я вот даже смутно помню как эту формулу использовать. Даже если бы я ее вывел.
Подставляете коэффициенты и получаете значения корней.
Если в процессе полезут корни из отрицательных чисел, либо включаете комплексный режим, либо говорите, что действительных корней нет.
Та если бы мне сейчас было необходимо, то я бы нагуглил детали и решил. Я знал, как решаются эти уравнения. Даже участвовал в математических олимпиадах и занимал неплохие места. Но это было уже лет 10-15 назад, и все это очень сильно забылось, потому на собеседовании я бы так и сказал:
— Я не помню, как решать квадратические уравнения, так как 10 не решал, но если для работы будет необходимо, то вспомнить это — полчаса времени.
— Я не помню, как решать квадратические уравнения, так как 10 не решал, но если для работы будет необходимо, то вспомнить это — полчаса времени.
Собеседование в НИИ ?
В ответ на такую задачку я попросил бы её же задать каждому действующему сотруднику в этой компании примерно той же должности. И всех не ответивших уволить как не прошедших «собеседование»
Задача предлагалась на предварительном этапе, до очного собеседования. Действующим тоже задавали. Увольнять не стали. К большому сожалению, уровень соискателей сильно упал. Двигаемся к тому, чтобы на собеседовании показывать кубики с цифрами.
А я попросил бы юз-кейс из практики приближенный к данной задаче. И после того как не получил бы удовлетворительный ответ сказал бы пока-пока этой компании.
Вообще у меня сложилось впечатление, что у подобных задач одна цель — показать соискателям что они дно и прогнуть по з.п.
Вообще у меня сложилось впечатление, что у подобных задач одна цель — показать соискателям что они дно и прогнуть по з.п.
Против таких, которые хотят «показать соискателям что они дно и прогнуть по з.п.» есть один довольно известный и очень действенный способ. Надо в ответ на глубокие вопросы задавать в ответ точно такие же глубокие вопросы собеседующему. Суть вот в чём. Не все кандидаты понимают смысл «СО-беседования». То есть, не только они отбирают кандидатов, но и вы отбираете интересную компанию и команду.
И когда слышите в свой адрес издевательские вопросы, то можете смело задавать точно такие же вопросы. На удивлённые взгляды отвечайте: «А что? Я хочу работать в команде профессионалов, которые знают как применять volatile и чем семафор отличается от мьютекса, а шаблон стратегии от фабрики. Что, не знаете? Жаль. Видно, нам с вами не по пути»
И когда слышите в свой адрес издевательские вопросы, то можете смело задавать точно такие же вопросы. На удивлённые взгляды отвечайте: «А что? Я хочу работать в команде профессионалов, которые знают как применять volatile и чем семафор отличается от мьютекса, а шаблон стратегии от фабрики. Что, не знаете? Жаль. Видно, нам с вами не по пути»
НЛО прилетело и опубликовало эту надпись здесь
Обычный матан. Сходящиеся и расходящиеся ряды. Единственное, что многие после универа это подзабывают, а так никакой сверх математикой тут и не пахнет. Если курил матан в свое время, то все вполне легко решаемо, даже если и подзабыл.
> Вот такое исследование получилось
Исследование про три частных случая?
Исследование про три частных случая?
Ну нет. Из статьи понятно как получить систему уравнений для поиска предельных отношений в рассмотренных рядах. А вот для решения таких систем при количестве исходных уравнений больше трех, скорее всего, уже нужно ПО для символьной математики. С карандашом и ручкой я справиться не могу. Да и смысла большого в этом не вижу.
Прикола ради такую задачку написал своим коллегам на доске. Сказал, что это задачка на собеседование. Почесали голову, доску исписали. Ну, вообщем коллективно всё свелось к «развёртыванию» дроби и выводе квадратного уравнения с нахождением корня. Кто-то подтянул матлаб и циклом определил схождение ряда. Было весело )))
Я просто к тому, что будучи вчерашними студентами любой из нас наверняка бы её и решил или хотя бы попытался. А 10-15-летние разработчики — уже не факт, что даже пробовать станут, хотя интерес и проявят. А в целом даже грустно — время идёт и уже многое напрочь забывается, когда годами пилишь какие-нибудь высокоскоростные интерфейсы (хотя надо заметить что я не «чистый» программист, а хардварный инженер-программист).
Я просто к тому, что будучи вчерашними студентами любой из нас наверняка бы её и решил или хотя бы попытался. А 10-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. Если решаете математическую задачу, отвлекитесь от программистского подхода «сейчас машина всё нам посчитает».
Во первых, существование предела нужно доказывать. Если кто-то думает, что можно обойтись, пусть поинтересуется парадоксом Перрона.
Во вторых, даже постановка «найдите отношение соседних членов» может оказать некорректной. Поясню.
Возьмём соотношение 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. Если решаете математическую задачу, отвлекитесь от программистского подхода «сейчас машина всё нам посчитает».
Прекрасный комментарий. Я занимаюсь скорее арифметикой, чем математикой. Как правило, свои размышления произвожу по дороге на работу, в электричке. Доказать наличие предела я не могу. В таких вопросах поступаю как физик, делаю предположение, потом ставлю эксперимент. Тоже самое и с этими пределами. Посмотрел в Excel и сравнил корнем полученного выражения. А за общий подход к таким задачам большое спасибо. Я его не увидел. Теперь этот пробел исправлен.
Здесь вспоминается анекдот:
Как доказать что все нечётные числа простые?Надеюсь, что никого не обидел.
Математик: 3-простое, 5-простое, 7-простое, дальше по индукции…
Физик: 3-простое, 5-простое, 7-простое, 9-ошибка эксперимента, 11-простое,…
Инженер: 3-простое, 5-простое, 7-простое, 9-простое,...
Ещё несколько соображений.
Существование предела можно доказать, если работает один из таких подходов.
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 и обоснование его сходимости.
И есть сильное подозрение, что если рекуррентное соотношение «короткое», коэффициенты и начальные значения «небольшие», то расчёт вручную нескольких сотен первых членов будет достаточным основание для сходимости. Но доказательство (если утверждение вообще верно) со всеми выкладками и обоснованиями, включая точные оценки для «короткое», «небольшие» и «несколько сотен» займёт приличный размер.
Куда удобнее просто получить явную формулу для f(n), тогда поведение частного сразу станет очевидным.
Существование предела можно доказать, если работает один из таких подходов.
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 свободный член уравнения забьёт остальные.
А вот при больших степенях могут оказаться близкие комплексные корни и здесь можно серьёзно завязнуть в оценках.
А вот при больших степенях могут оказаться близкие комплексные корни и здесь можно серьёзно завязнуть в оценках.
Куда удобнее просто получить явную формулу для f(n), тогда поведение частного сразу станет очевидным.
Куда удобнее просто получить явную формулу для f(n), тогда поведение частного сразу станет очевидным.
Вы говорите о явной формуле для n -ого члена последовательности? Для чисел Фибоначчи — это формула Бине, для следующего случая (узнал, что такие числа называются числа трибоначчи) общая формула есть в статье по ссылке. А есть ли формула для произвольного n? И есть ли свое название у того вида рядов, которые были рассмотрены в статье? Заранее благодарен.
Для знакомых с линейной алгеброй
Перейдём от уравнения (где все члены перенесены в левую часть) к системе. Обозначим через 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, и всё сводится к возведению в степерь Жордановых клеток.
Эту конструкцию вы могли видеть в решении линейных дифференциальных уравнений с постоянными коэффициентами. Практически всё дословно перенеосится на дискретный случай.
Тогда g(n) = A^n g(0). Переходим к собственному базису, A=T^{-1}BT, и всё сводится к возведению в степерь Жордановых клеток.
Эту конструкцию вы могли видеть в решении линейных дифференциальных уравнений с постоянными коэффициентами. Практически всё дословно перенеосится на дискретный случай.
Итого, общее решение можно найти таким образом. Решаем то самое «уравнение для потенциального предела». Пусть a, b, c… — его корни. Тогда общий член выглядит как Aa^n + Bb^n + Cc^n +… Если корни простые, то A, B, C — константы. Для кратных корней это будут многочлены от n степени на единицу меньше кратности. В случае комплексных корней лучше разбить их на пары сопряженных и от экспонент (a+bi)^n, (a-bi)^n перейти к r^n sin(n phi), r^n cos(n phi). Все коэффициенты находятся из начальных условий.
Теперь по поводу «формула для произвольного n». Лень разбираться, но я сильно сомневаюсь, что корни для произвольного n будут выражаться в радикалах. Можно поставить вопрос иначе — как будут распределяться корни при росте стпени. Тут ответа не знаю, увы. Можете спросить на dxdy.ru, там люди подкованные.
Я бы сказал, что парадокс Перрона не соблюдает все условия бесконечности (самого большого числа): 1² = 1, но 1+1 = 2, а это больше 1, значит 1 не самое большое число. Бесконечность + бесконечность = бесконечность.
Пожалуйста, объясните, как получилось уравнение x = 1 / (1 + x). Первоначальное обобщение должно выглядеть как x(n) = 1 / (1 + x(n-1)), по идеи.
Задача, на мой взгляд, сравнима с вопросом на интервью мальчика из Amazon-а об оптимальном поиске всех палиндромов в строке. Т.е. мальчик хочет увидеть реализацию алгоритма Манакера, написанную на доске (хотя сам узнал об этом алгоритме за день до интервью).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Об одной задаче, которую больше не предлагают на собеседовании