Алгоритм основан на теореме о разделяющей оси. Для 3D случая это разделяющая плоскость.
Определение будет такое: если между двумя фигурами существует плоскость (для 2D прямая), относительно которой фигуры лежат по разные стороны, то такие фигуры не пересекаются.
В теореме о разделяющей оси идёт речь про выпуклые фигуры. В статье это всплывает мельком в середине.
Мне кажется решение задачи 6 это пример того, как не нужно решать такие задачи. Видно же, что функции под интегралами и пределы интегрирования выбраны не случайно, а именно:
А значит, сумма интегралов равна сумме площадей криволинейных трапеций, которую можно представить как разность площадей двух прямоугольников:
биты, байты, размерность переменных, переполнение, sizeof, символьные последовательности, ука.затели — это из разряда must know
Вы могли бы пояснить, почему это must know? Во многих современных языках биты, байты, указатели – это всё под капотом и позволяет сосредотачиваться на главном – на самом программировании. Условно говоря, чтобы быть хорошим водителем автомобиля с автоматом (не пилотом болида, прошу заметить), мне не важно, как устроен двигатель, кроме самых общих представлений. Мне важнее знать ПДД.
Ах, да. Должен ли начинающий программист изучать ассемблер?
Но ведь у Математики роскошный хелп, лучший из всех, что я видел. С кратким введением, с разбором всех опций, с разделами Applications, Possible issues и Neat Examples. Преподов можно понять.
Так мы и действуем по индукции. Только для индукции нужно пять монет и одна монета из кармана, одна монета у нас виртуальная — мы её будем всё время откладывать, а монету из кармана делаем из заведомо настоящих монет (12 13), например.
Попробуйте сначала по алгоритму 1 (с одной настоящей монетой в кармане) найти за одно взвешивание фальшивую среди двух, потом за два взвешивания — среди пяти, потом проследите как работает индукция для 13 и далее, и вы увидите, что наш алгоритм абсолютно детерменирован. Вы же математик всё-таки, у вас получится.
1. Смотрите, допустим мы произвели взвешивание 4х4, и оказалось, что 1 2 3 4 < 5 6 7 8
Следующее взвешивание, которую нужно сделать (и которое следует из моего решения), это (1 5) (2 6) ? (3 7) (12 13)
Если происходит равенство, то все монеты, участвующие во взвешивании настоящие, следовательно фальшивой является толстая монета (4 8), которая не участвовала во взвешивании. Последним взвешиванием мы узнаём легче толстая фальшивая монета или тяжелее. (4 8) ? (12 13)
Если монета (4 8) легче, то фальшивая монета 4, если тяжелее — 8.
Если вы внимательно прочитаете ещё раз моё решение, то вам не составит труда разобрать все остальные случаи.
2.
Во-вторых, вы не совсем верно используете «информационный подход»
>>Здесь должен быть аргумент «нет, ты!» =)
Мы не сможем склеить все случаи, просто не сможем. Если какое-либо из взвешиваний закончится перевесом, то когда мы найдём фальшивую монету мы обязательно будем знать, тяжелее она или легче: для этого достаточно вспомнить на какой стороне весов она лежала (здесь можно придумать задачу про квантовые монеты, где эту несправедливость жизни можно обойти, но наши монеты классические, увы). Таким образом, в одном и ровно в одном случае мы не узнаем ничего про вес фальшивой монеты: когда все взвешивания закончатся равенством. Но это позволяет скостить нам только один вариант. Так что это точная нижняя оценка (и она достижима при наличии настоящей монетки в кармане).
Кстати, оценка Дайсона для количества монет меньше на одну монету, чем лучшая оценка. В частности, за 3 взвешивания можно определить фальшивую не среди 12 монет максимум, а среди 13 монет.
По ссылке оценка ½(3n – 3), то есть для двух взвешиваний это 6. Если я не так понял, поясните, пожалуйста, как за 2 взвешивания определить фальшивую монету из 12.
Ваша оценка для первого случая верна, а для второго — нет.
Давайте воспользуемся информационным подходом: в первом случае (когда известно, тяжелее монета или легче) у нас есть A случаев, а каждое взвешивание может дать три исхода (больше, меньше и равно) и в лучшем случае должно уменьшать количество случаев в 3 раза, поэтому, действительно
Если нам неизвестно, тяжелее фальшивая монета или легче, у нас 2A случаев, и оценка должна быть порядка
Что меньше, чем ваша оценка «сверху».
Прежде чем приводить алгоритм, можно ещё улучшить оценку: представим себе, что мы провели все взвешивания, и весы всё время оказывались в равновесии. Даже если в этом случае мы сможем определить фальшивую монету, мы не сможем сказать, тяжелее она или легче (а в задаче это в общем-то и не спрашивается). Таким образом, два случая «сливаются» в один и мы можем, вообще говоря, определить фальшивую за взвешиваний. Однако, это можно сделать только в одном случае: если у нас в кармане есть заведомо настоящая монета.
Утверждение 1:если у нас в кармане есть заведомо настоящая монета, то мы можем определить за n взвешиваний фальшивую среди монет.
Доказательство проведём по индукции. База для n=1. За одно взвешивание мы можем определить фальшивую среди монет. Мы достаём монету из кармана и кладём на одну из чаш весов, а на вторую чашу кладём одну из двух монет среди которых нам нужно определить фальшивку. Если весы в равновесии, то фальшивая монета не участвовала во взвешивании, если не в равновесии — фальшивая та, что на чаше весов.
Допустим, утверждение 1 справедливо для n. Докажем, что за n+1 взвешивание мы сможем определить фальшивую среди монет. Заметим, что если мы добавим к тестовым монетам нашу монету из кармана, то их количество поделится на три:
Тогда разделим наши монеты на три равные кучки, две кучки положим на чаши весов, одну отложим в сторону. Также убедимся, что монета из кармана попала на правую чашу (а не осталась в стороне). Проведём взвешивание. Если оказалось, что весы в равновесии, то фальшивая монета среди отложенных, и за n взвешиваний мы умеем её находить. Если оказалось, что весы не в равновесии, то мы делаем следующий трюк: склеиваем монеты попарно с правой и левой чаш весов. У нас должно получиться «толстых» монет. Среди этих «толстых» монет за n взвешиваний мы умеем определять фальшивую (теперь у нас нет монетки из кармана: она склеена, но мы можем изготовить новую «толстую» монету, склеив две настоящие монеты из кучки, отложенной на первом взвешивании). Единственно, за чем нужно следить, чтобы теперь «толстая» монета, «внутри» которой есть монета из кармана, всегда попадала в откладываемую стопку в последующих взвешиваниях.
Когда мы определили, какая из «толстых» монет фальшивая, мы также определили легче она или тяжелее настоящей. Теперь можно вспомнить результат первого взвешивания: если в первом взвешивании перевесила правая чаша, а фальшивая монета легче, то из двух монет, входящих в «толстую» монету, фальшивая та, которая пришла с левой чаши весов (напомню, в каждой «толстой» монете одна монета с правой чаши, а другая — с левой). Лишь в одном случае мы не можем определить, легче фальшивая или тяжелее: когда во всех взвешиваниях весы были в равновесии. Но в этом случае мы знаем, что «внутри» всё время откладываемой «толстой» монеты, которая оказалось фальшивой, одна из монет — это монета из кармана, поэтому фальшивая вторая монета. Таким образом, мы доказали базу индукции и шаг индукции.
Утверждение 2:если у нас нет дополнительных монет, то за n взвешиваний мы можем определить фальшивую среди монет (на одну меньше, чем в утверждении 1).
Сначала надо пояснить, почему мы не можем достичь максимальной оценки как в утверждении 1. Если у нас нет дополнительной монеты, то мы не можем разделить монет на три кучки. Если мы на чаши весов положим по монет, то в случае если весы окажутся не в равновесии, нам не хватит n−1 взвешиваний, чтобы различить случаев (а именно столько монет сейчас на чашах весов, и каждая может быть фальшивая). А если мы отложим монет, то оставшееся нечётное количество монет мы не сможем уравновесить.
Если же количество монет на одну меньше, то на две чаши весов положим по монет, а в сторону отложим монет. Если весы в равновесии, то за оставшиеся взвешивания мы сможем (согласно утверждению 1) определить фальшивую в отложенных монетах (роль монеты из кармана может играть любая монета с уравновешенных весов). Если весы не в равновесии, то мы также склеиваем монетки как в доказательстве утверждения 1 и добавляем виртуальную монету, которая во всех последующих взвешиваниях будет откладываться.
Проблема не в клавиатуре. В той же ссылке написано:
Буквы с готовыми акцентами прекрасны: кто-то рисовал их, ставил акценты в нужные места; убеждался, что всё попадает куда следует.
Комбинирующиеся акценты ужасны: они висят слишком высоко, чтобы случайно не прилипнуть к какой-нибудь букве, но при этом всё равно прилипают и к заглавным, и к буквам со значительными выносными элементами; в случае с широкими буквами они всё время оказываются правее середины.
От себя добавлю, что проблема индексации — это проблема программистов, а не пользователей. Другой вопрос, какой процент ваших пользователей копируют знаки с ударением на ваш сайт, и на что вы готовы ради них.
В уникоде нет готовых символов вроде: «русская е с ударением», но зато есть «латинская e с акутом». Чтобы ставить ударéния в русском тéксте, нужно не стесняясь брать символы из других алфавитов с заранее приделанными акцентами, если такие есть.
Некоторые видят в этом отступление от знаменитой семантики и настаивают на том, чтобы всё же использовать русскую букву с комбинирующимся акутом. Я считаю, что это глупый формализм, не достойный внимания.
Да, каюсь, я вас обманул с последним фокусом. Простите меня. Обобщённой суммы натуральных чисел, по-видимому, не существует. Для этого нужно использовать нелинейные регуляризации типа Дирихле.
В оправдание поясню, почему ответ в моём фокусе совпадает, например, с регуляризацией через экспоненциальный ряд. (Эта регуляризация уже не обладает стабильностью, но, по крайней мере, линейна, т.е. мы можем складывать ряды). Теперь нам действительно важно какое число будет первым: S(1,2,3...) ≠ S(0,1,2...). Но если мы разрядим ряд таким образом: a_n = 0, 1, 0, 2, 0, 3..., то его сумма не изменится:
Таким образом, для данного типа регуляризации допустимо складывание рядов и подобное разрежение без сдвига, поэтому ответ получается «верным». Но я согласен, что зря влепил последний пример в обобщённые суммы.
Что касается суммирования по Борелю, то оно, очевидно, обладает свойствами линейности. Для доказательства стабильности рассмотрим произвольный ряд a_k, добавим к нему в начало произвольный элемент a_0 и возьмём интеграл Бореля по частям:
Так что похоже, что регуляризация по Борелю всё-таки стабильна.
Вы вставили во второй и четвёртый ряд бесконечное число нулей. Не надо так =)
Два условия из определения обобщённой суммы разрешают нам
1) добавить/убрать/переставить конечное количество слагаемых
2) сложить несколько рядов почленно (с возможным домножением на множители)
Когда мы «всунули» в ряд бесконечное число нулей, мы его разрядили и его сумма изменилась, S1 не равно S2. Понятие бесконечности качественно отличается от любого сколь угодно большого числа. Иногда бесконечные суммы можно рассматривать как предел частичных конечных сумм, а иногда все частичные суммы положительные, а сумма ряда отрицательная.
Позволю не согласиться, что выбор чита — это всегда строгая процедура. Потребности физики часто были на шаг впереди строгости математики. Сначала Ньютон с Лейбницем придумали интегрально-дифференциальное исчисление, спустя век появилось строгое обоснование от Римана, а потом Лебега. Сначала Дирак вовсю использовал дельта-функции, потом математики создали теорию обобщённых функций. Таких примеров масса. Зачастую математическая интуиция полезнее строгости, хотя чем дальше в лес, тем больше контр-интуитивных для простого человека ситуаций встречается.
Есть такая штука, называется обобщённое суммирование.
Изначально у нас есть 3 аксиомы сложения конечного числа слагаемых: ассоциативность, коммутативность и дистрибутивность (линейность). С первыми двумя появляются проблемы, если мы хотим разрешить менять местами бесконечное число слагаемых (перестановкой членов можно заставить условно сходящийся ряд сходиться к любому числу) или расставлять бесконечное число скобок ( 1+(−1+1)+...=1, в то время как (1−1)+(1−1)+...=0). Поэтому мы говорим, что от бесконечной суммы мы хотим две вещи:
1. Чтобы она была похожа на сумму .
2. И чтобы она была линейна .
После этого для большинства расходящихся рядов можно сумму посчитать. Причём сумма не будет зависеть от метода суммирования (по Борелю, по Чезаро, по Эйлеру или ещё как), если метод по сути удовлетворяет двум вышеназванным свойствам.
Можно даже вместо регуляризации делать такие фокусы:
В теореме о разделяющей оси идёт речь про выпуклые фигуры. В статье это всплывает мельком в середине.
А значит, сумма интегралов равна сумме площадей криволинейных трапеций, которую можно представить как разность площадей двух прямоугольников:
Ах, да. Должен ли начинающий программист изучать ассемблер?
Попробуйте сначала по алгоритму 1 (с одной настоящей монетой в кармане) найти за одно взвешивание фальшивую среди двух, потом за два взвешивания — среди пяти, потом проследите как работает индукция для 13 и далее, и вы увидите, что наш алгоритм абсолютно детерменирован. Вы же математик всё-таки, у вас получится.
1 2 3 4 < 5 6 7 8Следующее взвешивание, которую нужно сделать (и которое следует из моего решения), это
(1 5) (2 6) ? (3 7) (12 13)Если происходит равенство, то все монеты, участвующие во взвешивании настоящие, следовательно фальшивой является толстая монета (4 8), которая не участвовала во взвешивании. Последним взвешиванием мы узнаём легче толстая фальшивая монета или тяжелее.
(4 8) ? (12 13)Если монета
(4 8)легче, то фальшивая монета4, если тяжелее —8.Если вы внимательно прочитаете ещё раз моё решение, то вам не составит труда разобрать все остальные случаи.
2.
>>Здесь должен быть аргумент «нет, ты!» =)
Мы не сможем склеить все случаи, просто не сможем. Если какое-либо из взвешиваний закончится перевесом, то когда мы найдём фальшивую монету мы обязательно будем знать, тяжелее она или легче: для этого достаточно вспомнить на какой стороне весов она лежала (здесь можно придумать задачу про квантовые монеты, где эту несправедливость жизни можно обойти, но наши монеты классические, увы). Таким образом, в одном и ровно в одном случае мы не узнаем ничего про вес фальшивой монеты: когда все взвешивания закончатся равенством. Но это позволяет скостить нам только один вариант. Так что
Давайте воспользуемся информационным подходом: в первом случае (когда известно, тяжелее монета или легче) у нас есть A случаев, а каждое взвешивание может дать три исхода (больше, меньше и равно) и в лучшем случае должно уменьшать количество случаев в 3 раза, поэтому, действительно
Если нам неизвестно, тяжелее фальшивая монета или легче, у нас 2A случаев, и оценка должна быть порядка
Что меньше, чем ваша оценка «сверху».
Прежде чем приводить алгоритм, можно ещё улучшить оценку: представим себе, что мы провели все взвешивания, и весы всё время оказывались в равновесии. Даже если в этом случае мы сможем определить фальшивую монету, мы не сможем сказать, тяжелее она или легче (а в задаче это в общем-то и не спрашивается). Таким образом, два случая «сливаются» в один и мы можем, вообще говоря, определить фальшивую за
Утверждение 1: если у нас в кармане есть заведомо настоящая монета, то мы можем определить за n взвешиваний фальшивую среди
Доказательство проведём по индукции. База для n=1. За одно взвешивание мы можем определить фальшивую среди
Допустим, утверждение 1 справедливо для n. Докажем, что за n+1 взвешивание мы сможем определить фальшивую среди
Тогда разделим наши монеты на три равные кучки, две кучки положим на чаши весов, одну отложим в сторону. Также убедимся, что монета из кармана попала на правую чашу (а не осталась в стороне). Проведём взвешивание. Если оказалось, что весы в равновесии, то фальшивая монета среди отложенных, и за n взвешиваний мы умеем её находить. Если оказалось, что весы не в равновесии, то мы делаем следующий трюк: склеиваем монеты попарно с правой и левой чаш весов. У нас должно получиться
Когда мы определили, какая из «толстых» монет фальшивая, мы также определили легче она или тяжелее настоящей. Теперь можно вспомнить результат первого взвешивания: если в первом взвешивании перевесила правая чаша, а фальшивая монета легче, то из двух монет, входящих в «толстую» монету, фальшивая та, которая пришла с левой чаши весов (напомню, в каждой «толстой» монете одна монета с правой чаши, а другая — с левой). Лишь в одном случае мы не можем определить, легче фальшивая или тяжелее: когда во всех взвешиваниях весы были в равновесии. Но в этом случае мы знаем, что «внутри» всё время откладываемой «толстой» монеты, которая оказалось фальшивой, одна из монет — это монета из кармана, поэтому фальшивая вторая монета. Таким образом, мы доказали базу индукции и шаг индукции.
Утверждение 2: если у нас нет дополнительных монет, то за n взвешиваний мы можем определить фальшивую среди
Сначала надо пояснить, почему мы не можем достичь максимальной оценки как в утверждении 1. Если у нас нет дополнительной монеты, то мы не можем разделить
Если же количество монет на одну меньше, то на две чаши весов положим по
Простите за простыню.
От себя добавлю, что проблема индексации — это проблема программистов, а не пользователей. Другой вопрос, какой процент ваших пользователей копируют знаки с ударением на ваш сайт, и на что вы готовы ради них.
У другого уважаемого человека на сайте ударения расставлены таким же путём.
В оправдание поясню, почему ответ в моём фокусе совпадает, например, с регуляризацией через экспоненциальный ряд. (Эта регуляризация уже не обладает стабильностью, но, по крайней мере, линейна, т.е. мы можем складывать ряды). Теперь нам действительно важно какое число будет первым: S(1,2,3...) ≠ S(0,1,2...). Но если мы разрядим ряд таким образом: a_n = 0, 1, 0, 2, 0, 3..., то его сумма не изменится:
Таким образом, для данного типа регуляризации допустимо складывание рядов и подобное разрежение без сдвига, поэтому ответ получается «верным». Но я согласен, что зря влепил последний пример в обобщённые суммы.
Что касается суммирования по Борелю, то оно, очевидно, обладает свойствами линейности. Для доказательства стабильности рассмотрим произвольный ряд a_k, добавим к нему в начало произвольный элемент a_0 и возьмём интеграл Бореля по частям:
Так что похоже, что регуляризация по Борелю всё-таки стабильна.
Два условия из определения обобщённой суммы разрешают нам
1) добавить/убрать/переставить конечное количество слагаемых
2) сложить несколько рядов почленно (с возможным домножением на множители)
Когда мы «всунули» в ряд бесконечное число нулей, мы его разрядили и его сумма изменилась, S1 не равно S2. Понятие бесконечности качественно отличается от любого сколь угодно большого числа. Иногда бесконечные суммы можно рассматривать как предел частичных конечных сумм, а иногда все частичные суммы положительные, а сумма ряда отрицательная.
Изначально у нас есть 3 аксиомы сложения конечного числа слагаемых: ассоциативность, коммутативность и дистрибутивность (линейность). С первыми двумя появляются проблемы, если мы хотим разрешить менять местами бесконечное число слагаемых (перестановкой членов можно заставить условно сходящийся ряд сходиться к любому числу) или расставлять бесконечное число скобок ( 1+(−1+1)+...=1, в то время как (1−1)+(1−1)+...=0). Поэтому мы говорим, что от бесконечной суммы мы хотим две вещи:
1. Чтобы она была похожа на сумму
2. И чтобы она была линейна
После этого для большинства расходящихся рядов можно сумму посчитать. Причём сумма не будет зависеть от метода суммирования (по Борелю, по Чезаро, по Эйлеру или ещё как), если метод по сути удовлетворяет двум вышеназванным свойствам.
Можно даже вместо регуляризации делать такие фокусы: