Комментарии 32
Довольно милая статья, способная сделать интересную дискуссию в комментариях.
Мариновалась с 2013 года
Интересно, как считали? Формулой Кардано? Но там и комплексные решения могут быть. Не так всё просто. Да и много ли кто помнит формулу Кардано по памяти...
Никогда не поверю, что участники всесоюзной олимпиады по математике решали эту «задачу» численно, а не выводом ответа по формуле - а в этом случае даже в 88м году речи о минутах быть не могло…
P.S. Какие комплексные корни? У многочлена третьей степени всегда есть действительный корень, если он единственный, то экстремум один, если есть ещё, то два или три
Никогда не поверю, что участники всесоюзной олимпиады по математике решали эту «задачу» численно
А в чём проблема считать численно? Если отбросить константную часть с определением границ интервалов и вычислением коэффициентов, то искать корень кубического многочлена даже с дихотомией уйдёт не больше нескольких десятков итераций.
Давайте заменим эту задачу на задачу "найти корни квадратного уравнения". Если вам так задачу поставить, будет ли вашим первым решением численное?
Если заменить задачу, то и решение будет другим.
Уверен, что средний участник всесоюзной олимпиады на память написать формулы Кардано и корректно запрограммировать их не смог бы. Там кроме очевидной проблемы - помнить алгоритм и формулы - достаточно относительно небольших, но хлопотных граблей: нужно привести уравнение к каноническому заменой (а потом обратно), возникают квадратные корни из отрицательных чисел (которые потом уходят, но в коде придётся их хранить аккуратно отдельно), нужно кубический корень считать через степень с учетом знака (что-то типа SGN(X)*(ABS(X)^(1/3))).
Причем тут же еще такой момент: 1988 год, компьютеров еще почти нигде и никаких нет. Если хоть какие-то есть, в школе то это уже очень продвинутая школа. И скорее всего это были другие компьютеры, тогда был жуткий зоопарк в школах: ДВК, УКНЦ, БК, Корветы, Агаты и прочее. Ямахи с MSX были крутыми и редкими, BASIC между всеми этими компьютерами отличался, да и писать на нём менее удобно, чем в современных IDE.
А численные алгоритмы достаточно простые. Если совсем лень думать, то и дихотомия сойдёт. Чуть сложнее методом секущих (хорд) - но там надо убедиться, что корень не кратный. Еще чуть сложнее (надо еще выражение производной написать) метод Ньютона. Но в любом случае все эти методы пишутся достаточно просто.
Вы очень плохо представляете себе участников всеросса (всесоюзной). Там часть по приколу помнит 300 знаков числа Пи, а вы про формулу Кардано… Да они ее выведут за пять минут, если не помнят, потому что 💯 помнят, как она выводится
Ну да, ну да, я очень плохо их себе представляю. :) На самом деле, конечно, представляю: пусть сам я даже на зональные не прошёл, да и число пи помнил только до 80-го знака (сейчас уже до 40 знаков еле вспомню), но участников всероссийских и некоторых национальных олимпиад знаю достаточно.
Ну я не знаю, как ваш год рождения, а мой (89й) формулу Кардано вывести на бумажке за пять минут мог. А вот запрогать быстро и без ошибок например метод Ньютона могло меньшее количество, чем вывести формулу Кардано.
Проблема не вывести формулу. Проблема написать код. Это лишь кажется, что явную формулу проще написать, чем численный метод. Дихотомию, вон, мой сын шестикклассник на "олимпиадном C++" или на Python напишет, я в 9 классе и выше точно мог метод секущих написать (знаю, потому что писал), в выпускном классе Ньютона мог. А вот написать явную формулу (в BASIC-коде) для корня при отрицательном дискриминанте уже совсем не так просто.
(Дата рождения в профиле есть)
Возможно, из-за того, что я не знаю Бейсика, а всю жизнь прогаю на си, но фраза «написать явную формулу для корня при отрицательном дискриминанте уже совсем не так просто» вызывает у меня странные чувства) В Бейсике нет конструкции if?
Комплексных чисел точно нет.
А в каком месте с обсуждаемый задаче они нужны? И вообще, зачем они нужны на уровне языка?
Как минимум результат получается комплексный - просто выдать можно и так, но если нужно работать дальше, лучше иметь тип на уровне языка с оптимизациями в компиляторе типа такой.
Задача - найти экстремумы многочлена четвёртой степени. Просветите, что такое комплексный экстремум и что такое знак ‘<‘ (или ‘>’) для комплексных чисел?
Каких то людей-компьютеров изобразили ) Я вот больше помню, как после тура на всесоюзной вечером сначала подушками в номере гостиницы кидались, а когда соседи начали жаловаться - по полотенцам вылезли через окно на улицу и гуляли по ночному Смоленску. Я тогда формулу Кардано точно не знал (и сейчас не выведу), Пи помнил только восемь знаков как на Б3-34. Другие могли знать больше, всё таки кого то и здесь вижу.
Хм, не знаю, как решали тогда, но я бы попробовал считать так.
Считаем коэффициенты первой и второй производной. Но, да, формулы Кардано я на память не готов воспроизводить, поэтому пойдём другим путём.
Нули второй производной дадут нам точки перегиба исходного многочлена и потенциальные экстремумы производной. Отдельно обрабатываем случай 1 корня второй производной и отсутствия корней второй производной (расписывать в комментарии лень). Один из нулей первой производной будет между точками перегиба (пусть это x1 и x2).
Из исходного многочлена нетрудно найти такие x0 и x3, что все экстремумы будут лежать в этих границах (как только x^4 становится больше остальной части многочлена). Искать можно как в лоб по формулам, так и просто удвоением шага.
Теперь, считая, что мы уже разобрали особые случаи, у нас нули первой производной между точками x0, x1, x2, x3. Всего 3 интервала. Можно считать в лоб дихотомией - даже сейчас не более 64 итераций на каждый (около 10 FP операций каждая). Т.е. "на круг" можно уложиться условно в тысячи FP операций. Даже на процессоре частотой около 1 миллиона восьмибитных операций в секунду (а в Ямахах был именно такой - Z80, у него частота была около 3 МГц и минимум 4 такта на инструкцию), даже с интерпретируемым BASIC есть все шансы спокойно уложиться в минуту.
Если дихотомия лишком долго, то можно по-быстрому метод Ньютона или метод секущих запилить - они сходятся быстрее. За два часа любое из этих решений вроде посильно набрать. Даже на MSX (я как-то больше на Корветах и Спектруме писал, но в целом специфику представляю).
Заглянул на Википедию: Первая Всесоюзная олимпиада проходила с 13 по 20 апреля 1988 года в Свердловске.
Всё же это называлось олимпиадой по информатике, у меня и пруфы есть:
Привет всем, кто себя нашел :)
Но на фото Харьков и 1990 год.
Но олимпиада по информатике, а не по программированию.
Я запутался. Вы пишите "олимпиада в Свердловске, вот пруф, что это называлось иначе". Но на фото - Харьков. Как олимпиада в Харькове что-то доказывает по поводу олимпиады в Свердловске? Я определённо что-то не понимаю.
Мой первый абзац - это ответ автору статьи на утверждение, что олимпиада в Свердловске была в 1989 году. В википедии написано другое.
Второй абзац - утверждение, что в СССР олимпиад по программированию не было. Пруф немного притянут за уши, чтобы похвастаться - что поделать, в Харькове я был, а в Свердловске - нет. :)
Да, их называли по информатике, потому что такой предмет есть в школе. Но там всегда решали задачи как на олимпиадах по программированию
По математике был только на последней всесоюзной, Смоленск 1991. До этого в том же году на областной в качестве развлечения после самого тура пустили в класс с такими же Ямахами, но просто поиграть - помню и тогда офигел от звука/графики после школьных БК 0010Ш...
Не знаю как на счет "Первая Всесоюзная олимпиада". 1989 году закончил школу в Киргизии г. Фрунзе. Так вот с 1986 года участвовал в олимпиадах по информатике. Те же Ямахи, Агаты, ДВК.
Первая в СССР олимпиада по программированию