Спасибо, интересно! Я бы никогда не узнал, что формулу Кардано придумал совсем не Кардано, если бы тут не прочитал. Что заставляет задуматься, сколько есть еще известных вещей, изобретение которых приписывают совсем не тем людям? Возможно оффтопик, но тема интересная, и хочу поделиться своими эмоциями из курса тфкп:
формула Эйлера для функции Римана обнаруживает связь между тфкп и простыми числами. Кстати, эта формула элементарно доказывается, доказательство доступно не математикам.
Вы упомянули основную теорему алгебры, самое тут крутое, что она доказывает, что комплексные числа являются алгебраическим замыканием действительных чисел. Известно, что любое поле имеет алгебраическое замыкание, и это доказывается с помощью аксиомы выбора! Это показывает связь тфкп с алгеброй и теорией множеств.
Голоморфные функции очень тесно связаны с гармоническими функциями (это почти одно и то же в каком-то смысле), что показывает тесную связь между тфкп и дифурами! Про это вообще редко говорят, но лично мне это кажется какой-то мистикой, что абстрактное алгебраическое расширение действительных чисел корнем квадратного уравнения можно наделить метрикой, кривизной и прочими векторными расслоениями (что, конечно же, показывает тесную связь между тфкп и геометрией/топологией)
Матановские техники, разработанные для тфкп (типа теоремы Коши) неожиданно позволяют решать разные задачи, напрямую никак не связанные с комплексными числами (например, посчитать сумму обратных квадратов натуральных чисел через вычеты). В каком-то смысле, это показывает связь тфкп с реальной жизнью (если для вас, как и для меня, решение интересных задачек является важной частью жизни!)
Кажется, вашу идею можно спасти, если добавить третью эвристику - для двух кругов, касающихся большого круга, добавить два круга сверху их симметрично, примерно так:
xx
O O
Это работает для n = 12 и 15 (единственные n до 20, на которых не работают ваши эвристики), но сломается на больших n (кажется, для n=29), там вообще начинается жесть, когда шары образуют несимметричную сеть "распорок". Но для таких n уже перебор будет слишком медленно работать.
я не физик и могу ошибаться, но насколько я понимаю, теорема как раз и доказывает, что удерживать плазму с помощью сферического поля в принципе невозможно. Сфера не является менее практичной, она физически невозможна. Так что если какой-то стартап и пытается это сделать, это не отличается от изобретения вечного двигателя. С другой стороны, я и не утверждаю, что изобретатели токомака явно пользовалсь этой теоремой - согласен, что они исходили из практических соображений.
Ага, правда, иногда случайности не случайны. Известна история, когда два студента Принстона обнаружили, что комбинация их фамилий звучит по-английски очень неприлично, и решили, что должны обязательно написать совместную статью. Теперь в математике есть машина Кокса-Цукера (Cox-Zucker Machine)
Это, конечно, баловство, но я уместил решение в восемь строчек на питоне! Тут смысла не очень много, это просто формальное преобразование ранее полученных формул с целью уменьшения количества кода.
def cnt(N, b):
f1, f2 = [1]*N, [1]*N
for k in range(1, N//(b-1) + 2):
for n in reversed(range(N)):
f1[n] += sum(f1[n - min(b-1, n, n+1-(k-1)*(b-1)) : n])
for t in range(1, min(2*b-1, n+1, n+2-(k-1)*(b-1))):
f2[n] += (b - abs(b-1-t))*f2[n-t]
return [f2[i] * 4 - f1[i] * 4 + 1 for i in range(N)]
Спасибо, интересная задача! Я немного подумал над ней, но в комментариях хабра мало места, чтобы подробно написать. Примерно так получилось (рассуждения, в принципе, повторяют ваши, но только в более привычных обозначениях): Во-первых, возьмем основание системы счисления произвольное b вместо 10, мне так формулы легче воспринимаются. Для положительных x обозначим сумму цифр Теперь сначала рассмотрим одномерный случай: посчитаем количество таких x, что для всех , будем называть такие числа достижимыми (из нуля). Для этого введем две функции: - количество достижимых чисел в отрезке и , равная единице, если сумма цифр последнего числа в отрезке не превосходит n, иначе нулю. То есть, она говорит, можем ли мы продолжать смотреть следующие отрезки, или надо остановиться. Тогда f и q можно выразить такими формулами:
Теперь точно так же рассмотрим двумерный случай. Удивительно, что условие на то, надо ли нам рассматривать следующий квадрат или нет, сводится к той же самой функции q (не зависящей от размерности!). Я строго не смог доказать это, но там должны быть примерно ваши рассуждения. Для двумерной f формула почти такая же:
Или можно ее сократить до одной суммы, если взять diag(t) равной количеству пар x, y в квадрате bxb, в сумме не превосходящих t:
Теперь, имея одномерную и двумерную функции, можно получить ответ по принципу inclusion-exclusion. Что касается кода, то проверить правильность результата можно обычным поиском (в глубину или ширину, неважно): код на питоне
Вычислить сразу все решения до заданного n можно по этой рекуррентной формуле: код на питоне, вроде бы результаты совпадают с вашими c b=10, N=900.
Сложность алгоритма O(n^2 * b), так как надо итерировать f до значений k=O(n).
В математике вероятность определяется как нормированная мера на сигма-алгебре множеств, в этом контексте событие определяется как измеримое множество. Поэтому явное перечисление множеств (событий) и задание меры на них является фундемантальным и математически корректным способом ввести вероятность.
Спасибо, интересно. Я всегда считал, что естественное обобщение - произведение n-1 вектора в n-менром пространстве как вектор длиной площадь n-1-мерного параллелограмма и перпендикулярный им, и его можно посчитать как определитель матрицы, в которой строки - координаты векторов и базис. Но, согласно википедии, существует много вариантов обобщений, в зависимости от того, какие свойства векторного произведения мы хотим сохранить.
А точно есть такие правила? В Википедии (особенно в Computer Science) много ссылок на форумы и даже личные страницы, когда, например, нет или мало научных статей на эту тему - часто встречается, когда люди делают исследования и не считают нужным их публиковать в авторитетных источниках. Например, в этой статье первые четыре ссылки ведут на форумы и личные страницы (хотя, насколько я знаю, основные результаты по этой теме опубликованы)
Это стандартная задача на поиск в глубину, таких много на литкоде. Самый простой (и медленный) вариант на питоне:
from sys import setrecursionlimit
from textwrap import wrap
setrecursionlimit(100000)
words = open('words.txt').read().split()
def no_repeats(word): return len(set(word)) == len(word)
words = [word for word in words if len(word) == 5 and no_repeats(word)]
def dfs(result, index):
if len(result) >= 25:
print(wrap(result, 5))
return
if index >= len(words):
return
if no_repeats(result+words[index]):
dfs(result+words[index], index+1)
dfs(result, index+1)
dfs("", 0)
Спасибо, интересная статья! Насчет сортировки циклических сдвигов - а вы не пробовали стандартный prefix doubling algorithm - он, насколько я помню, довольно просто пишется, и работает за O(N*log N), сильно быстрее наивного, хотя и медленнее линейных. Но и классический алгоритм Укконена по построению суффиксного дерева на питоне занимает всего 50 строк, хотя самому его написать (и, главное, отладить), наверное, сложно.
не уверен насчет оптимизатора js, но после оптимизатора с++ не будет ни того, ни другого: деление превратится в умножение на reciprocal (throughput = 1 инструкция/такт), а if - в conditional move (2 инструкции/такт). Мне кажется, ни то, ни то не будет узким местом, скорее уж обращение к памяти
я пытался строить все варианты с половиной кубиков (18 для n=8, 22 или 23 для n=9). В вашем случае границы, как на рис.4, сложность в том, что на любой позиции над средней линией можно поставить квадратик размера 1 (допустим, он бы еще не был использован), и тоже получится правильная граница. То есть, "жадное" заполнение сверху вниз и слева направо не работает, надо перебирать больше вариантов, по крайней мере, близко к границе. Или я чего-то не учитываю?
Спасибо, интересно! Я бы никогда не узнал, что формулу Кардано придумал совсем не Кардано, если бы тут не прочитал. Что заставляет задуматься, сколько есть еще известных вещей, изобретение которых приписывают совсем не тем людям?
Возможно оффтопик, но тема интересная, и хочу поделиться своими эмоциями из курса тфкп:
формула Эйлера для функции Римана обнаруживает связь между тфкп и простыми числами. Кстати, эта формула элементарно доказывается, доказательство доступно не математикам.
Вы упомянули основную теорему алгебры, самое тут крутое, что она доказывает, что комплексные числа являются алгебраическим замыканием действительных чисел. Известно, что любое поле имеет алгебраическое замыкание, и это доказывается с помощью аксиомы выбора! Это показывает связь тфкп с алгеброй и теорией множеств.
Голоморфные функции очень тесно связаны с гармоническими функциями (это почти одно и то же в каком-то смысле), что показывает тесную связь между тфкп и дифурами! Про это вообще редко говорят, но лично мне это кажется какой-то мистикой, что абстрактное алгебраическое расширение действительных чисел корнем квадратного уравнения можно наделить метрикой, кривизной и прочими векторными расслоениями (что, конечно же, показывает тесную связь между тфкп и геометрией/топологией)
Матановские техники, разработанные для тфкп (типа теоремы Коши) неожиданно позволяют решать разные задачи, напрямую никак не связанные с комплексными числами (например, посчитать сумму обратных квадратов натуральных чисел через вычеты). В каком-то смысле, это показывает связь тфкп с реальной жизнью (если для вас, как и для меня, решение интересных задачек является важной частью жизни!)
Здесь: https://habr.com/ru/articles/945486/comments/#comment_28829868
Кажется, вашу идею можно спасти, если добавить третью эвристику - для двух кругов, касающихся большого круга, добавить два круга сверху их симметрично, примерно так:
Это работает для n = 12 и 15 (единственные n до 20, на которых не работают ваши эвристики), но сломается на больших n (кажется, для n=29), там вообще начинается жесть, когда шары образуют несимметричную сеть "распорок". Но для таких n уже перебор будет слишком медленно работать.
кажется, это не всегда работает. Например, для n=15 оптимальная упаковка не найдется
я не физик и могу ошибаться, но насколько я понимаю, теорема как раз и доказывает, что удерживать плазму с помощью сферического поля в принципе невозможно. Сфера не является менее практичной, она физически невозможна.
Так что если какой-то стартап и пытается это сделать, это не отличается от изобретения вечного двигателя.
С другой стороны, я и не утверждаю, что изобретатели токомака явно пользовалсь этой теоремой - согласен, что они исходили из практических соображений.
о, отличная задача, по таким можно отдельный обзор писать. Навскидку еще приходит в голову задача о разборчивой невесте
Ага, правда, иногда случайности не случайны. Известна история, когда два студента Принстона обнаружили, что комбинация их фамилий звучит по-английски очень неприлично, и решили, что должны обязательно написать совместную статью. Теперь в математике есть машина Кокса-Цукера (Cox-Zucker Machine)
Это, конечно, баловство, но я уместил решение в восемь строчек на питоне! Тут смысла не очень много, это просто формальное преобразование ранее полученных формул с целью уменьшения количества кода.
Спасибо, интересно было вспомнить (хотя у мы только симплекс-метод проходили, когда-то вручную его программировал, без всяких библиотек).
это вот этот курс? оставлю ссылку, может, кто-то захочет посмотреть (а вдруг?!!)
Спасибо, интересная задача!
для всех 
, будем называть такие числа достижимыми (из нуля).
- количество достижимых чисел в отрезке ![[0, b^k]](https://habrastorage.org/getpro/habr/formulas/0/00/004/004304a805b694745c153506aacadd11.svg)
и 
, равная единице, если сумма цифр последнего числа в отрезке ![[0, b^k]](https://habrastorage.org/getpro/habr/formulas/0/00/004/004304a805b694745c153506aacadd11.svg)
не превосходит n, иначе нулю. То есть, она говорит, можем ли мы продолжать смотреть следующие отрезки, или надо остановиться.
Я немного подумал над ней, но в комментариях хабра мало места, чтобы подробно написать. Примерно так получилось (рассуждения, в принципе, повторяют ваши, но только в более привычных обозначениях):
Во-первых, возьмем основание системы счисления произвольное b вместо 10, мне так формулы легче воспринимаются. Для положительных x обозначим сумму цифр
Теперь сначала рассмотрим одномерный случай: посчитаем количество таких x, что
Для этого введем две функции:
Тогда f и q можно выразить такими формулами:
Теперь точно так же рассмотрим двумерный случай. Удивительно, что условие на то, надо ли нам рассматривать следующий квадрат или нет, сводится к той же самой функции q (не зависящей от размерности!). Я строго не смог доказать это, но там должны быть примерно ваши рассуждения. Для двумерной f формула почти такая же:
Или можно ее сократить до одной суммы, если взять diag(t) равной количеству пар x, y в квадрате bxb, в сумме не превосходящих t:
Теперь, имея одномерную и двумерную функции, можно получить ответ по принципу inclusion-exclusion.
Что касается кода, то проверить правильность результата можно обычным поиском (в глубину или ширину, неважно): код на питоне
Вычислить сразу все решения до заданного n можно по этой рекуррентной формуле: код на питоне, вроде бы результаты совпадают с вашими c b=10, N=900.
Сложность алгоритма O(n^2 * b), так как надо итерировать f до значений k=O(n).
упс, хотел написать длинный комментарий, но случайно опубликовал его. Напишу его заново и опубликую
В математике вероятность определяется как нормированная мера на сигма-алгебре множеств, в этом контексте событие определяется как измеримое множество.
Поэтому явное перечисление множеств (событий) и задание меры на них является фундемантальным и математически корректным способом ввести вероятность.
Спасибо, интересно. Я всегда считал, что естественное обобщение - произведение n-1 вектора в n-менром пространстве как вектор длиной площадь n-1-мерного параллелограмма и перпендикулярный им, и его можно посчитать как определитель матрицы, в которой строки - координаты векторов и базис.
Но, согласно википедии, существует много вариантов обобщений, в зависимости от того, какие свойства векторного произведения мы хотим сохранить.
А точно есть такие правила? В Википедии (особенно в Computer Science) много ссылок на форумы и даже личные страницы, когда, например, нет или мало научных статей на эту тему - часто встречается, когда люди делают исследования и не считают нужным их публиковать в авторитетных источниках.
Например, в этой статье первые четыре ссылки ведут на форумы и личные страницы (хотя, насколько я знаю, основные результаты по этой теме опубликованы)
Это стандартная задача на поиск в глубину, таких много на литкоде. Самый простой (и медленный) вариант на питоне:
Спасибо, интересная статья!
Насчет сортировки циклических сдвигов - а вы не пробовали стандартный prefix doubling algorithm - он, насколько я помню, довольно просто пишется, и работает за O(N*log N), сильно быстрее наивного, хотя и медленнее линейных. Но и классический алгоритм Укконена по построению суффиксного дерева на питоне занимает всего 50 строк, хотя самому его написать (и, главное, отладить), наверное, сложно.
как это не меняется? (5, 1) -> (6, 4)
не уверен насчет оптимизатора js, но после оптимизатора с++ не будет ни того, ни другого: деление превратится в умножение на reciprocal (throughput = 1 инструкция/такт), а if - в conditional move (2 инструкции/такт). Мне кажется, ни то, ни то не будет узким местом, скорее уж обращение к памяти
я пытался строить все варианты с половиной кубиков (18 для n=8, 22 или 23 для n=9).
В вашем случае границы, как на рис.4, сложность в том, что на любой позиции над средней линией можно поставить квадратик размера 1 (допустим, он бы еще не был использован), и тоже получится правильная граница. То есть, "жадное" заполнение сверху вниз и слева направо не работает, надо перебирать больше вариантов, по крайней мере, близко к границе. Или я чего-то не учитываю?
А сколько у вас времени работало для n=8?