Comments 61
Нужно только заметить, что предложенное выражение самоподобно
автору осталось раскрыть — что такое «самоподобное выражение»…
вдруг стало отрицательным? — чтобы значение дроби получилось 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, иначе придётся давать формальные определения сходимости и доказывать каждый шаг, т.е. строить теорию цепных дробей.
При чём тут эта последовательность, куда вы её собрались подставлять???
С другой стороны, смысл её понятен даже школьнику.
Смысл великой теоремы Ферма тоже понят школьнику. Но на доказательством бились три века xD
Достаточно представлять откуда берется этот самый дискриминант, тогда получить для него формулу не представляет труда. Благо, вывод формулы для квадрата суммы не является чем-то сложным.
Подставляете коэффициенты и получаете значения корней.
Если в процессе полезут корни из отрицательных чисел, либо включаете комплексный режим, либо говорите, что действительных корней нет.
— Я не помню, как решать квадратические уравнения, так как 10 не решал, но если для работы будет необходимо, то вспомнить это — полчаса времени.
Собеседование в НИИ ?
Задача предлагалась на предварительном этапе, до очного собеседования. Действующим тоже задавали. Увольнять не стали. К большому сожалению, уровень соискателей сильно упал. Двигаемся к тому, чтобы на собеседовании показывать кубики с цифрами.
Вообще у меня сложилось впечатление, что у подобных задач одна цель — показать соискателям что они дно и прогнуть по з.п.
И когда слышите в свой адрес издевательские вопросы, то можете смело задавать точно такие же вопросы. На удивлённые взгляды отвечайте: «А что? Я хочу работать в команде профессионалов, которые знают как применять volatile и чем семафор отличается от мьютекса, а шаблон стратегии от фабрики. Что, не знаете? Жаль. Видно, нам с вами не по пути»
Исследование про три частных случая?
Ну нет. Из статьи понятно как получить систему уравнений для поиска предельных отношений в рассмотренных рядах. А вот для решения таких систем при количестве исходных уравнений больше трех, скорее всего, уже нужно ПО для символьной математики. С карандашом и ручкой я справиться не могу. Да и смысла большого в этом не вижу.
Я просто к тому, что будучи вчерашними студентами любой из нас наверняка бы её и решил или хотя бы попытался. А 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. Если решаете математическую задачу, отвлекитесь от программистского подхода «сейчас машина всё нам посчитает».
Прекрасный комментарий. Я занимаюсь скорее арифметикой, чем математикой. Как правило, свои размышления произвожу по дороге на работу, в электричке. Доказать наличие предела я не могу. В таких вопросах поступаю как физик, делаю предположение, потом ставлю эксперимент. Тоже самое и с этими пределами. Посмотрел в 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), тогда поведение частного сразу станет очевидным.
Куда удобнее просто получить явную формулу для f(n), тогда поведение частного сразу станет очевидным.
Вы говорите о явной формуле для n -ого члена последовательности? Для чисел Фибоначчи — это формула Бине, для следующего случая (узнал, что такие числа называются числа трибоначчи) общая формула есть в статье по ссылке. А есть ли формула для произвольного n? И есть ли свое название у того вида рядов, которые были рассмотрены в статье? Заранее благодарен.
Тогда 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, там люди подкованные.
Равенство выполняется при предельном переходе. Устремляем n в бесконечность и говорим, что если предел существует, то он будет удовлетворять этому соотношению.
Об одной задаче, которую больше не предлагают на собеседовании