На простых задачах это неинтересно. Попробуйте сравнить на более сложных, особенно где есть нетривиальное состояние. Например:
quick sort: его, конечно, можно написать без рекурсии, но код будет, мягко говоря, нечитабельным
задача с литкода про восстановление дерева по его inorder и preorder. Решается элементарно за 5 минут с помощью рекурсии, в 5 строк кода на питоне. У нее есть нерекурсивное решение, в чем-то изящное, но оно сильно нетривиальное, и там надо додуматься до хитрого инварианта того, что пихать в стек.
Хочу поправить себя, я тут неправду написал, конечно, вставка O*log(n)) амортизированная. Тут еще кажется, что сортировка массива добавляет еще один лог-фактор, но в Питоне, как и в Яве, сортировка является вариантом TimSort, который работает за линейное время, если сортируемый массив состоит из небольщого количества уже отсортированных кусков (так как внутри он использует merge sort). Поэтому полезный трюк на питоне или Яве (но не на C++ или C#) - если надо сделать merge sort, можно просто слить массивы в один массив, и использовать стандартный сорт!
вот, если кому интересно, реализация на питоне (поиск и вставки, без удаления), получилось 9 строчек. Вставка O(1) амортизированная, поиск O(log^2(n)). На практике, перед вставкой надо тоже делать поиск, чтобы избежать дубликатов, но для этого можно добавить простой хешсет, чтобы вставка осталась O(1).
Интересно, оказывается, эта структура имеет название. Я думал, это "народный" трюк, чтобы делать "дешевый аналог" деревьев, если в вашем языке программирования нет их из коробки, и нет возможности использовать дополнительные библиотеки. Я похожий трюк даже один раз использовал для какой-то задачи с литкода, потому что не знал, есть ли в питоне sorted set) Основное ее преимущество перед деревьями - простота реализации. Если не гнаться за излишней оптимизацией, реализация [на питоне] занимает буквально десяток строчек! Она, кажется, позволяет делать большую часть того, что могут и обычные деревья, за счет дополнительного log-фактора. Этот лог фактор можно убить с помощью эзотерической техники fractional cascading (но непонятно, нафига, так как это уже сложнее, чем "вращать деревья"). Этот подход, если я правильно понимаю, является частным случаем log-structure merge tree, на котором основаны поисковые движки типа lucene, и многие nosql базы данных (cassandra, rocksdb)
Хорошая задача, она демонстрирует основной результат теории, которую называют красивым словом "heavy hitters theory" (не знаю, как правильно перевести на русский - может, "важные чуваки"?) Лет 10 назад она активно развивалась, и было много научных работ на эту тему (последнее время я за ней не слежу, может, до сих пор там что-то новое придумывают) Там два основных результата - это теорема Бойера-Мура о поиске значений, встречающихся в потоке больше половины раз , о которой @Alexandroppolus упоминает, и ее обобщение на n/k раз теорема Мисра-Грис. Также там активно исследовались вероятностные методы, так что идея автора (если я правильно понимаю) - очень хорошая на практике, потому что вероятность ложного результата обычно падает экспоненциально по количеству попыток. То есть, если взять ваш алгоритм и повторить раз 50, то вероятность его ошибки будет сильно меньше вероятности того, что прилетит заряженная частица с солнца и поменяет бит в памяти компьютера. Конечно, есть еще вероятность злонамеренной атаки на генератор случайных чисел, но эта проблема тоже имеет теоретическое решение :) Ну и важная часть исследований доказывает разные ограничения. Я знаю реальный случай, когда начальник попросил программиста найти моду (самое повторяющееся значение в потоке) с использованием констатной памяти. Программист ему гордо показал теорему, которая говорит, что это невозможно!
если номера изначально не отсортированы, и их много, то наверно самый быстрый теоретический подход - это для каждого номера выполнять predecessor query за O(1) по началам диапазонов. Например, сохранять a_i в Van Emde Boas tree. Я когда-то слышал, что якобы в роутерах похожий подход используют для матчинга ip по диапазонам, но в википедии про это нет, так что это, наверно, anecdotal evidence. Но, судя по тому, что эта структура в реальности почти не используется, там наверняка слишком большие константы, и бинпоиск выгоднее на задачах ожидаемого размера.
Ну, может, и изврат)) мне просто интересны эти задачи с точки зрения ментальной нагрузки. Иногда это называют cyclomatic complexity, но я определяю как матожидание количества исправлений от первой версии до полностью рабочей. Я иногда могу потратить пару часов на задачу LeetCode easy, пытаясь ее написать так, чтобы минимизировать количество потенциальных ошибок. С этой точки зрения heap для меня проще бинпоиска, у которого много пограничных случаев, которые надо в голове держать. Это, кстати, и в работе помогает - развивает интуицию, как надо писать код, чтобы потом его мучительно не отлаживать ))
да, если его оформлять как отдельный переиспользуемый класс, то получается много кода. Но на интервью, вроде бы, обычно нормально относятся к сокращению кода. Я сейчас попробовал написать по памяти хип сорт, примерно так получилось:
def sieve_down(arr, i, n):
while True:
lt,rt,best = i*2+1, i*2+2, i
if lt < n and arr[lt] > arr[best]: best = lt
if rt < n and arr[rt] > arr[best]: best = rt
if best == i: break
arr[i], arr[best], i = arr[best], arr[i], best
def heapsort(arr):
for i in reversed(range(len(arr))):
sieve_down(arr, i, len(arr))
for i in reversed(range(len(arr))):
arr[0], arr[i] = arr[i], arr[0]
sieve_down(arr, 0, i)
Спасибо за подробный рассказ! Я, конечно, поражаюсь (ну и немного завидую) вашему упорству! Вы пишете про динамическое программирование: "Прорыв произошёл не сразу и не за одну тему" - А это было сколько по времени? В смысле, месяц, год, неделя?
Ну и конечно, главный вопрос: почему не питон? :)
И чтоб два раза не вставать, хочу "защитить" мой любимый Heap - я не согласен, что его долго писать, он довольно простой, если в голове держать, какие элементы куда просеиваются. А если делать heapsort - там даже просеивания вверх не нужно, только просеивание вниз, и весь код умещается строчек в 15 на питоне! Для меня бинпоиск сложнее, чем heap, потому что там надо в голове держать, что вернуть, если элемент не найден, или есть несколько одинаковых элементов.
Не соглашусь, скорее это как хотеть играть на пианино, но вместо того, чтобы сразу учить концерт Рахманинова и писать свою симфонию, два года играть гаммы и "к Элизе". Для профессиональных писанистов это скорее норма. И если уж продолжать аналогию, то цель была - попасть в оркестр пианистом, а теперь поменялась на "научиться играть на пианино" - я бы не назвал это провалом))
Я, кажется, решил задачу для n=10 (получается, задача 3025 года!) Мой результат - 290,794,520 решений, или 36,349,315 решений без учета симметрии. Программа работала 3 недели на 8-ядерном AMD EPYC, и проверила чуть больше 500 триллионов позиций (шагов DFS). Конечно, надо будет перепроверять результат, тем более что там много хитрых оптимизаций, и вероятность ошибки не исключена. Для сравнения, программа считает результат для n=8 за 2 секунды (16 секунд однопоточно), а для n=9 - за 15 минут (2 часа однопоточно). Надо, наверно, будет потом опубликовать код и подробно описать оптимизации, они сами по себе довольно интересные.
Я часто вижу такую точку зрения, что эти задачки на литкоде и собеседованиях - это такая лотерея, что человек их заучивает, и потом либо ему повезло, и он похожую задачу решал, либо не повезло. Мне кажется, эти задачи скорее простые примеры из базового курса по Computer Science - то есть, если вы этот курс прошли, и прорешали эти задачи, то вероятность встретить задачу уровня easy/medium, к которой вообще непонятно, как подступиться, мала. Даже если в вузе такого курса не было, их на ютубе много, от MIT или МФТИ, например. Другое дело, что многим быстрее рискнуть и бессистемно запомнить принцип решения пары сотен задач, чем проходить годовой курс и разбираться в теории, но я не знаю, насколько это проблема собеседований.
По поводу сделать research - далеко не всегда его можно делать, если вы не знаете основы computer science (А если знаете - то решение задачек на собеседовании не будет проблемой). В гугле часто возникают задачи, для которых надо придумать новый, прежде несуществующий, алгоритм, а не просто применить новый, они публикуют научные статьи каждый год.
ну это почти определение предела в хаусдорфовом топологическом пространстве (если окрестность заменить на замкнутое множество). Для евклидовых пространств - одно из нескольких десятков эквивалентных, далеко не самое мощное. Собственно, такое количество эквивалентных определений и удобно, что для доказательства можно выбрать наиболее подходящее. Я очень сомневаюсь, что оно может упростить ряд доказательств, потому что для него даже метрики не нужно, только наличие свойства отделимости (я тут, конечно, говорю о строгих доказательствах)
ну это же просто неверно в общем случае. Возьмите последовательность 0, sinx, 0, sin2x, 0, sin3x, ... в пространстве непрерывных функций на отрезке от 0 до 2π (с практически любой метрикой, например, L2). У нее единственная точка сгущения - 0, но предела нет. вместо sin(nx) можно взять базис в любом бесконечномерном пространстве с метрикой.
Для полноты картины хочу оставить ссылку на статью 2003 года, которая обобщает задачу на произвольные фигуры, и вводит понятие partridge number как минимальное n, для которого задача имеет решение (то есть, partridge number квадрата равен 8) Так, partridge number равностороннего треугольника равен 9; а есть ли невыпуклые фигуры, для которых задача имеет решение - вроде как до сих пор неизвестно (возможно, потому что никто ей всерьез не занимался)
C# всегда был одним из моих основных языков программирования, и, пожалуй, самым любимым, еще до его официального релиза в 2002 году, когда к нам на мат-мех СПБГУ приходили ребята из Микрософт показать новый крутой язык. Я хорошо помню, как они на наших глазах открыли Visual Studio, написали "Console.", вызвали контекстную подсказку, и ноутбук завис намертво! Его перезагрузили, и со второго раза все получилось!
Потом я много лет на нем работал (вместе с Java и C++), но где-то после шестой версии он начал терять популярность и уступать яве и Go (хотя вы можете возразить, что Ява всегда была популярнее?). И такое впечатление, на самом высоком уровне в Микрософт было принято решение экстенсивного развития языка. Я помню, я читал тикет про nullable types (известное изменение в семантике языка, делающее все классы по умоллчанию non-nullable), еще до его официального принятия. Там один человек спросил: "Теперь выражение default(T) больше не имеет тип T - вам не кажется, что это не консистентно?" На что представилель Микрософта прямо ответил: "на данном этапе развития языка создание сообщества вокруг него для нас важнее его внутренней непротиворечивости."
Тем не менее, я признаю, что это было, наверно, правильное решение. Сейчас c# мультипарадигменный, я на нем писал и суровый энтерпрайз с абстрактными фабриками, и супербыстрые числодробилки с System.Runtime.Intrinsics и вычислениями на видеокарте с ILGPU.net, и ad-hoc скрипты как в питоне. Если кто увлекается программистскими задачками, и решает Advent of Code каждый год, знает, что подавляющее большинство их делают на питоне. Я решал их на c# два последних года, и даже пару раз попал на глобальный leaderboard (что лично для меня огромное достижение, так как приходится соревноваться и с competitive programmers, соревнующихся с детства, так и с LLMs, решающих простые задачи за секунды)! Я описал свой опыт использования c# вместо питона на реддите в этой статье.
Лично мое мнение - современный C# очень недооценен: он по удобству тулинга сопоставим с Ява, по скорости разработки - с Питоном, по скорости компиляции - с Go, по скорости работы - с C++. То ли Микрософт не вполне справились с продвижением языка, то ли это не было для них приоритетом...
Ну, вроде бы автор блога признает ваше авторство, в блоге есть ссылка на последовательность OEIS (или он это добавил после вашего комментария?). А автор видео, скорее всего, больше фокусировался на развлекательной составляющей, чем на научной.
Спасибо, интересно! Я бы никогда не узнал, что формулу Кардано придумал совсем не Кардано, если бы тут не прочитал. Что заставляет задуматься, сколько есть еще известных вещей, изобретение которых приписывают совсем не тем людям? Возможно оффтопик, но тема интересная, и хочу поделиться своими эмоциями из курса тфкп:
формула Эйлера для функции Римана обнаруживает связь между тфкп и простыми числами. Кстати, эта формула элементарно доказывается, доказательство доступно не математикам.
Вы упомянули основную теорему алгебры, самое тут крутое, что она доказывает, что комплексные числа являются алгебраическим замыканием действительных чисел. Известно, что любое поле имеет алгебраическое замыкание, и это доказывается с помощью аксиомы выбора! Это показывает связь тфкп с алгеброй и теорией множеств.
Голоморфные функции очень тесно связаны с гармоническими функциями (это почти одно и то же в каком-то смысле), что показывает тесную связь между тфкп и дифурами! Про это вообще редко говорят, но лично мне это кажется какой-то мистикой, что абстрактное алгебраическое расширение действительных чисел корнем квадратного уравнения можно наделить метрикой, кривизной и прочими векторными расслоениями (что, конечно же, показывает тесную связь между тфкп и геометрией/топологией)
Матановские техники, разработанные для тфкп (типа теоремы Коши) неожиданно позволяют решать разные задачи, напрямую никак не связанные с комплексными числами (например, посчитать сумму обратных квадратов натуральных чисел через вычеты). В каком-то смысле, это показывает связь тфкп с реальной жизнью (если для вас, как и для меня, решение интересных задачек является важной частью жизни!)
Кажется, вашу идею можно спасти, если добавить третью эвристику - для двух кругов, касающихся большого круга, добавить два круга сверху их симметрично, примерно так:
xx
O O
Это работает для n = 12 и 15 (единственные n до 20, на которых не работают ваши эвристики), но сломается на больших n (кажется, для n=29), там вообще начинается жесть, когда шары образуют несимметричную сеть "распорок". Но для таких n уже перебор будет слишком медленно работать.
На простых задачах это неинтересно. Попробуйте сравнить на более сложных, особенно где есть нетривиальное состояние. Например:
quick sort: его, конечно, можно написать без рекурсии, но код будет, мягко говоря, нечитабельным
задача с литкода про восстановление дерева по его inorder и preorder. Решается элементарно за 5 минут с помощью рекурсии, в 5 строк кода на питоне. У нее есть нерекурсивное решение, в чем-то изящное, но оно сильно нетривиальное, и там надо додуматься до хитрого инварианта того, что пихать в стек.
Хочу поправить себя, я тут неправду написал, конечно, вставка O*log(n)) амортизированная.
Тут еще кажется, что сортировка массива добавляет еще один лог-фактор, но в Питоне, как и в Яве, сортировка является вариантом TimSort, который работает за линейное время, если сортируемый массив состоит из небольщого количества уже отсортированных кусков (так как внутри он использует merge sort).
Поэтому полезный трюк на питоне или Яве (но не на C++ или C#) - если надо сделать merge sort, можно просто слить массивы в один массив, и использовать стандартный сорт!
вот, если кому интересно, реализация на питоне (поиск и вставки, без удаления), получилось 9 строчек.
Вставка O(1) амортизированная, поиск O(log^2(n)). На практике, перед вставкой надо тоже делать поиск, чтобы избежать дубликатов, но для этого можно добавить простой хешсет, чтобы вставка осталась O(1).
Интересно, оказывается, эта структура имеет название. Я думал, это "народный" трюк, чтобы делать "дешевый аналог" деревьев, если в вашем языке программирования нет их из коробки, и нет возможности использовать дополнительные библиотеки. Я похожий трюк даже один раз использовал для какой-то задачи с литкода, потому что не знал, есть ли в питоне sorted set)
Основное ее преимущество перед деревьями - простота реализации. Если не гнаться за излишней оптимизацией, реализация [на питоне] занимает буквально десяток строчек!
Она, кажется, позволяет делать большую часть того, что могут и обычные деревья, за счет дополнительного log-фактора. Этот лог фактор можно убить с помощью эзотерической техники fractional cascading (но непонятно, нафига, так как это уже сложнее, чем "вращать деревья").
Этот подход, если я правильно понимаю, является частным случаем log-structure merge tree, на котором основаны поисковые движки типа lucene, и многие nosql базы данных (cassandra, rocksdb)
Хорошая задача, она демонстрирует основной результат теории, которую называют красивым словом "heavy hitters theory" (не знаю, как правильно перевести на русский - может, "важные чуваки"?)
Лет 10 назад она активно развивалась, и было много научных работ на эту тему (последнее время я за ней не слежу, может, до сих пор там что-то новое придумывают)
Там два основных результата - это теорема Бойера-Мура о поиске значений, встречающихся в потоке больше половины раз , о которой @Alexandroppolus упоминает, и ее обобщение на n/k раз теорема Мисра-Грис.
Также там активно исследовались вероятностные методы, так что идея автора (если я правильно понимаю) - очень хорошая на практике, потому что вероятность ложного результата обычно падает экспоненциально по количеству попыток. То есть, если взять ваш алгоритм и повторить раз 50, то вероятность его ошибки будет сильно меньше вероятности того, что прилетит заряженная частица с солнца и поменяет бит в памяти компьютера. Конечно, есть еще вероятность злонамеренной атаки на генератор случайных чисел, но эта проблема тоже имеет теоретическое решение :)
Ну и важная часть исследований доказывает разные ограничения. Я знаю реальный случай, когда начальник попросил программиста найти моду (самое повторяющееся значение в потоке) с использованием констатной памяти. Программист ему гордо показал теорему, которая говорит, что это невозможно!
если номера изначально не отсортированы, и их много, то наверно самый быстрый теоретический подход - это для каждого номера выполнять predecessor query за O(1) по началам диапазонов. Например, сохранять a_i в Van Emde Boas tree.
Я когда-то слышал, что якобы в роутерах похожий подход используют для матчинга ip по диапазонам, но в википедии про это нет, так что это, наверно, anecdotal evidence.
Но, судя по тому, что эта структура в реальности почти не используется, там наверняка слишком большие константы, и бинпоиск выгоднее на задачах ожидаемого размера.
Ну, может, и изврат)) мне просто интересны эти задачи с точки зрения ментальной нагрузки. Иногда это называют cyclomatic complexity, но я определяю как матожидание количества исправлений от первой версии до полностью рабочей.
Я иногда могу потратить пару часов на задачу LeetCode easy, пытаясь ее написать так, чтобы минимизировать количество потенциальных ошибок. С этой точки зрения heap для меня проще бинпоиска, у которого много пограничных случаев, которые надо в голове держать.
Это, кстати, и в работе помогает - развивает интуицию, как надо писать код, чтобы потом его мучительно не отлаживать ))
да, если его оформлять как отдельный переиспользуемый класс, то получается много кода. Но на интервью, вроде бы, обычно нормально относятся к сокращению кода. Я сейчас попробовал написать по памяти хип сорт, примерно так получилось:
Спасибо за подробный рассказ! Я, конечно, поражаюсь (ну и немного завидую) вашему упорству!
Вы пишете про динамическое программирование: "Прорыв произошёл не сразу и не за одну тему" - А это было сколько по времени? В смысле, месяц, год, неделя?
Ну и конечно, главный вопрос: почему не питон? :)
И чтоб два раза не вставать, хочу "защитить" мой любимый Heap - я не согласен, что его долго писать, он довольно простой, если в голове держать, какие элементы куда просеиваются. А если делать heapsort - там даже просеивания вверх не нужно, только просеивание вниз, и весь код умещается строчек в 15 на питоне! Для меня бинпоиск сложнее, чем heap, потому что там надо в голове держать, что вернуть, если элемент не найден, или есть несколько одинаковых элементов.
Не соглашусь, скорее это как хотеть играть на пианино, но вместо того, чтобы сразу учить концерт Рахманинова и писать свою симфонию, два года играть гаммы и "к Элизе". Для профессиональных писанистов это скорее норма.
И если уж продолжать аналогию, то цель была - попасть в оркестр пианистом, а теперь поменялась на "научиться играть на пианино" - я бы не назвал это провалом))
Я, кажется, решил задачу для n=10 (получается, задача 3025 года!) Мой результат - 290,794,520 решений, или 36,349,315 решений без учета симметрии.
Программа работала 3 недели на 8-ядерном AMD EPYC, и проверила чуть больше 500 триллионов позиций (шагов DFS). Конечно, надо будет перепроверять результат, тем более что там много хитрых оптимизаций, и вероятность ошибки не исключена. Для сравнения, программа считает результат для n=8 за 2 секунды (16 секунд однопоточно), а для n=9 - за 15 минут (2 часа однопоточно).
Надо, наверно, будет потом опубликовать код и подробно описать оптимизации, они сами по себе довольно интересные.
Я часто вижу такую точку зрения, что эти задачки на литкоде и собеседованиях - это такая лотерея, что человек их заучивает, и потом либо ему повезло, и он похожую задачу решал, либо не повезло.
Мне кажется, эти задачи скорее простые примеры из базового курса по Computer Science - то есть, если вы этот курс прошли, и прорешали эти задачи, то вероятность встретить задачу уровня easy/medium, к которой вообще непонятно, как подступиться, мала. Даже если в вузе такого курса не было, их на ютубе много, от MIT или МФТИ, например.
Другое дело, что многим быстрее рискнуть и бессистемно запомнить принцип решения пары сотен задач, чем проходить годовой курс и разбираться в теории, но я не знаю, насколько это проблема собеседований.
По поводу сделать research - далеко не всегда его можно делать, если вы не знаете основы computer science (А если знаете - то решение задачек на собеседовании не будет проблемой). В гугле часто возникают задачи, для которых надо придумать новый, прежде несуществующий, алгоритм, а не просто применить новый, они публикуют научные статьи каждый год.
ну это почти определение предела в хаусдорфовом топологическом пространстве (если окрестность заменить на замкнутое множество). Для евклидовых пространств - одно из нескольких десятков эквивалентных, далеко не самое мощное. Собственно, такое количество эквивалентных определений и удобно, что для доказательства можно выбрать наиболее подходящее.
Я очень сомневаюсь, что оно может упростить ряд доказательств, потому что для него даже метрики не нужно, только наличие свойства отделимости (я тут, конечно, говорю о строгих доказательствах)
ну это же просто неверно в общем случае. Возьмите последовательность 0, sinx, 0, sin2x, 0, sin3x, ... в пространстве непрерывных функций на отрезке от 0 до 2π (с практически любой метрикой, например, L2). У нее единственная точка сгущения - 0, но предела нет.
вместо sin(nx) можно взять базис в любом бесконечномерном пространстве с метрикой.
Для полноты картины хочу оставить ссылку на статью 2003 года, которая обобщает задачу на произвольные фигуры, и вводит понятие partridge number как минимальное n, для которого задача имеет решение (то есть, partridge number квадрата равен 8)
Так, partridge number равностороннего треугольника равен 9; а есть ли невыпуклые фигуры, для которых задача имеет решение - вроде как до сих пор неизвестно (возможно, потому что никто ей всерьез не занимался)
C# всегда был одним из моих основных языков программирования, и, пожалуй, самым любимым, еще до его официального релиза в 2002 году, когда к нам на мат-мех СПБГУ приходили ребята из Микрософт показать новый крутой язык. Я хорошо помню, как они на наших глазах открыли Visual Studio, написали "Console.", вызвали контекстную подсказку, и ноутбук завис намертво! Его перезагрузили, и со второго раза все получилось!
Потом я много лет на нем работал (вместе с Java и C++), но где-то после шестой версии он начал терять популярность и уступать яве и Go (хотя вы можете возразить, что Ява всегда была популярнее?). И такое впечатление, на самом высоком уровне в Микрософт было принято решение экстенсивного развития языка. Я помню, я читал тикет про nullable types (известное изменение в семантике языка, делающее все классы по умоллчанию non-nullable), еще до его официального принятия. Там один человек спросил: "Теперь выражение default(T) больше не имеет тип T - вам не кажется, что это не консистентно?" На что представилель Микрософта прямо ответил: "на данном этапе развития языка создание сообщества вокруг него для нас важнее его внутренней непротиворечивости."
Тем не менее, я признаю, что это было, наверно, правильное решение. Сейчас c# мультипарадигменный, я на нем писал и суровый энтерпрайз с абстрактными фабриками, и супербыстрые числодробилки с System.Runtime.Intrinsics и вычислениями на видеокарте с ILGPU.net, и ad-hoc скрипты как в питоне. Если кто увлекается программистскими задачками, и решает Advent of Code каждый год, знает, что подавляющее большинство их делают на питоне. Я решал их на c# два последних года, и даже пару раз попал на глобальный leaderboard (что лично для меня огромное достижение, так как приходится соревноваться и с competitive programmers, соревнующихся с детства, так и с LLMs, решающих простые задачи за секунды)! Я описал свой опыт использования c# вместо питона на реддите в этой статье.
Лично мое мнение - современный C# очень недооценен: он по удобству тулинга сопоставим с Ява, по скорости разработки - с Питоном, по скорости компиляции - с Go, по скорости работы - с C++. То ли Микрософт не вполне справились с продвижением языка, то ли это не было для них приоритетом...
Ну, вроде бы автор блога признает ваше авторство, в блоге есть ссылка на последовательность OEIS (или он это добавил после вашего комментария?). А автор видео, скорее всего, больше фокусировался на развлекательной составляющей, чем на научной.
Спасибо, интересно! Я бы никогда не узнал, что формулу Кардано придумал совсем не Кардано, если бы тут не прочитал. Что заставляет задуматься, сколько есть еще известных вещей, изобретение которых приписывают совсем не тем людям?
Возможно оффтопик, но тема интересная, и хочу поделиться своими эмоциями из курса тфкп:
формула Эйлера для функции Римана обнаруживает связь между тфкп и простыми числами. Кстати, эта формула элементарно доказывается, доказательство доступно не математикам.
Вы упомянули основную теорему алгебры, самое тут крутое, что она доказывает, что комплексные числа являются алгебраическим замыканием действительных чисел. Известно, что любое поле имеет алгебраическое замыкание, и это доказывается с помощью аксиомы выбора! Это показывает связь тфкп с алгеброй и теорией множеств.
Голоморфные функции очень тесно связаны с гармоническими функциями (это почти одно и то же в каком-то смысле), что показывает тесную связь между тфкп и дифурами! Про это вообще редко говорят, но лично мне это кажется какой-то мистикой, что абстрактное алгебраическое расширение действительных чисел корнем квадратного уравнения можно наделить метрикой, кривизной и прочими векторными расслоениями (что, конечно же, показывает тесную связь между тфкп и геометрией/топологией)
Матановские техники, разработанные для тфкп (типа теоремы Коши) неожиданно позволяют решать разные задачи, напрямую никак не связанные с комплексными числами (например, посчитать сумму обратных квадратов натуральных чисел через вычеты). В каком-то смысле, это показывает связь тфкп с реальной жизнью (если для вас, как и для меня, решение интересных задачек является важной частью жизни!)
Здесь: https://habr.com/ru/articles/945486/comments/#comment_28829868
Кажется, вашу идею можно спасти, если добавить третью эвристику - для двух кругов, касающихся большого круга, добавить два круга сверху их симметрично, примерно так:
Это работает для n = 12 и 15 (единственные n до 20, на которых не работают ваши эвристики), но сломается на больших n (кажется, для n=29), там вообще начинается жесть, когда шары образуют несимметричную сеть "распорок". Но для таких n уже перебор будет слишком медленно работать.