Аааа. Если предварительно построить эту обратную польскую запись, то да. Просто я подумал, что Вы предлагаете с деревом работать и на этапе вычисления.
Дерево, может, и удобнее, но явно проигрывает по скорости. Например, дерево придется обходить рекурсивно. А если пытаться оптимизировать вычисление, то все равно придем либо к ОПЗ, либо к чему-то среднему между AST и ОПЗ.
А вот что касается отсутствия лишних проверок на этапе вычисления это идея хорошая. Правда, на сколько мне известно, правильная реализация алгоритма предполагает все проверки на этапе построения обратной польской записи.
Очень важно отметить, что поскольку эта программа написана на Си (или, говоря точнее, на компилируемом языке программирования), то, когда дело доходит до использования чисел с плавающей запятой, возникают присущие таким языкам неточности.
О каких неточностях идет речь? Почему эти неточности присущи только си и компилируемым языкам? В каких языках таких неточностей нету?
Формулировка задачи оказалась неоднозначной. Я подумал, что таблички даны не для "озвучивания" предположения о цвете своей шляпы, а для коммуникации между мудрецами. И что ответ надо по прежнему выкрикивать. Перечитав несколько раз формулировку и предложенное автором решение я понял, что неверно интерпретировал условие.
В задаче 2 нет как такового первого, второго и т.д. Все мудрецы находятся в равных условиях. Получается, что если у мудреца нету информации о табличке, которую поднял первый (кто бы этим "первым" ни оказался), то, с учетом равных условий, у мудреца нету информации ни об одно из табличек, поднятых его коллегами. Получается, что таблички бесполезны и вовсе не нужны. А без табличек гарантированно верно назвать свой цвет никто не может.
Оказывается, два мудреца могут так хитро договориться, чтобы гарантированно один из них угадал свой цвет. Один мудрец поднимает табличку того же цвета, что и цвет колпака на другом мудреце, а тот, наоборот, поднимает табличку противоположного цвета.
Получается, что цвет таблички (здесь и далее под цветом таблички подразумеваю цвет поднятой вверх таблички) в руках мудреца B совпадает с цветом шляпы мудреца A. При этом мудрец A видит табличку мудреца B. То есть мудрец A знает цвет своей шляпы. Аналогично если поменять A и B местами.
Но затем Вы пишете
Легко видеть, что ровно один из них "угадает" свой цвет: первый, если король надел одинаковые колпаки, и второй - в противном случае.
Изначально я слишком сумбурно описал предлагаемую стратегию. Исправляюсь. Далее идет аккуратное описание стратегии.
Назовем мудреца A особым по отношению к мудрецу B, если мудрец B может гарантированно верно назвать цвет своей шляпы, основываясь лишь на цветах шляп остальных мудрецов и на названном мудрецом A цвете, действуя по стратегии, описанной в решении к первой задаче.
В задаче 1 мудрец под номером 1 является особым по отношению ко всем остальным и не существует особого мудреца по отношению к первому. То есть все мудрецы кроме особого знали какой цвет назвал особый мудрец и знали цвета шляп всех остальных мудрецов. Но особый мудрец мог и не называть никакой цвет, а просто поднять табличку с нужным цветом, если таблички всех цветов имелись в его распоряжении.
Чтобы перейти к задаче 2 надо поправить определение выше, заменив слово "названном" на что-то более подходящее. Я не смог подобрать удачное слово, которое бы одновременно означает как "названном", так и "показанном", поэтому пусть будет "названном или показанном".
Переходим к задаче 2. С учетом вышесказанного можно придумать такую стратегию: случайным образом выбирается мудрец, который будет особым по отношению ко всем остальным и на цвет именно его карточки все остальные будут обращать внимание. В таком случае все мудрецы кроме одного гарантированно ответят правильно.
Однако стратегию можно улучшить. Для этого можно заметить, что любой из мудрецов является особым по отношению ко всем остальным. То есть каждый из мудрецов может для себя выбрать какого-нибудь мудреца и назвать правильно цвет своей шляпы. Таким образом приходим к стратегии, когда ВСЕ мудрецы гарантированно верно назовут цвет своей шляпы.
Эту стратегию можно обобщить и для последующих задач.
Не очень понял задачу 2. Разве нельзя поступить по аналогии с 1 задачей только вместо слов показать табличку нужного цвета в зависимости от четности количества черных/белых шляп у остальных. Дальше все как в первой задаче только вместо "первого" (в качестве того на чью табличку обращать внимание) каждый из мудрецов для себя выберет любого. И тогда каждый сможет ответить правильно. Стало быть, и в оставшихся задачах будет такой же ответ.
Ну тут имеется в виду немного другое. В алгебре вводят понятия кольца и евклидова кольца (кольцо с определенной на нем нормой, удовлетворяющей паре свойств) и уже в рамках евклидова кольца доказывают существование и единственность разложения на простые с точностью до умножения на обратимые элементы поля (например, x^2 = (x) * (x) = (x / 2) * (2 x) = ... в кольце многочленов). Но перед этим дается определение простого элемента:
Необратимый ненулевой элемент p целостного кольца называется простым, если он не может быть представлен в виде p = ab, где a и b –– необратимые элементы
Поэтому в кольце целых чисел простыми являются числа вида ±p. Так что не обязательно простое число является натуральным. Тут просто дело в том, что в школах обычно существенно упрощают, убирая из рассмотрения отрицательные числа, так как это только запутать может.
Что Вы имеете в виду под многострочным режимом? Если речь идет о написании длинных формул в несколько строк, то можно использовать окружение multline (обратите внимание, что именно multline, а не multiline) из пакета amsmath. Вместо $$ x = y $$ нужно писать \begin{multline} x = \\ y \end{multline}. Каждый раз, когда хотите сделать перенос необходимо использовать \\.
У LaTeX есть небольшая особенность как он выбирает пробелы вокруг некоторых символов. Например, +b превращается в , а a+b превращается в (обратите внимание на пробел между + и b). Поэтому для красивого разбиения формулы на операторах типа +/- стоит писать \begin{multline} x + {} \\ {} + y \end{multline}; для = такой трюк не требуется: \begin{multline} x = \\ = y \end{multline}.
Операция деления это далеко не 2 такта. На современных компьютерах деление порядка 50 тактов, а вот суммирование, умножение — один.
Кроме того, первоначальный вариант функции wholeMod можно ускорить. if дешевле, чем % (эта операция, как известно, основана на делении), то есть лучше сделать взятие остатка и потом return res if res >=0 else res + domain
Введение к статье сразу напомнило при скрибд: чтобы отменить подписку нужно раз 10 прекликать, что ты хочешь отказаться от подписки. Сколько знакомых знаю (да и я сам), кто там делал себе бесплатный пробный период, все в итоге попадали на списание и уже потом тщательно проверяли, что подписка отменена.
Как мне кажется, хорошим является вариант с range. Только, я бы вынес всё, что Вы писали внури тела функции в отдельный класс и кроме варианта range (end) добавил бы range (begin, end) и, быть может, range (begin, end, step). Но куда более удобным вариантом будет сделать класс шаблонным. Тогда можно будет писать, например, for (auto i : range (it1, it2)).
У GCC есть специальные опции:
-fpic: Generate position-independent code (PIC) suitable for use in a shared library, if supported for the target machine.
-fPIC: If supported for the target machine, emit position-independent code, suitable for dynamic linking and avoiding any limit on the size of the global offset table.
-fpie -fPIE: These options are similar to -fpic and -fPIC, but the generated position-independent code can be only linked into executables.
Точно! Вы правы. Я что-то не подумал об усложнениях, которые появляются.
Ваша дополнительная идея очень хорошая. Ее можно слегка оптимизировать. Не уверен, что это сильно поможет. Когда Вы хотите произвести вычисления для некоторого элемента в середине поля, Вам необходимо знать предущую линию (под нее выделить память), в текущей линии предыдущий элемент, текущий и следующий (под них можно выделить 3 локальных переменных) и следующая линия (которая и так есть в исходном массиве, так как Вы еще не успели начать ее «портить»).
Тогда кешируется куски не 4 массивов, а лишь 3.
Но это, скорее оптимизация по памяти, чем по времени.
Аааа. Если предварительно построить эту обратную польскую запись, то да. Просто я подумал, что Вы предлагаете с деревом работать и на этапе вычисления.
Дерево, может, и удобнее, но явно проигрывает по скорости. Например, дерево придется обходить рекурсивно. А если пытаться оптимизировать вычисление, то все равно придем либо к ОПЗ, либо к чему-то среднему между AST и ОПЗ.
А вот что касается отсутствия лишних проверок на этапе вычисления это идея хорошая. Правда, на сколько мне известно, правильная реализация алгоритма предполагает все проверки на этапе построения обратной польской записи.
О каких неточностях идет речь? Почему эти неточности присущи только си и компилируемым языкам? В каких языках таких неточностей нету?
В конструкторе класса выражение
лучше заменить на
Формулировка задачи оказалась неоднозначной. Я подумал, что таблички даны не для "озвучивания" предположения о цвете своей шляпы, а для коммуникации между мудрецами. И что ответ надо по прежнему выкрикивать. Перечитав несколько раз формулировку и предложенное автором решение я понял, что неверно интерпретировал условие.
Знатно я, однако, опростоволосился =)
В задаче 2 нет как такового первого, второго и т.д. Все мудрецы находятся в равных условиях. Получается, что если у мудреца нету информации о табличке, которую поднял первый (кто бы этим "первым" ни оказался), то, с учетом равных условий, у мудреца нету информации ни об одно из табличек, поднятых его коллегами. Получается, что таблички бесполезны и вовсе не нужны. А без табличек гарантированно верно назвать свой цвет никто не может.
В решении к задаче 2 Вы пишете
Получается, что цвет таблички (здесь и далее под цветом таблички подразумеваю цвет поднятой вверх таблички) в руках мудреца B совпадает с цветом шляпы мудреца A. При этом мудрец A видит табличку мудреца B. То есть мудрец A знает цвет своей шляпы. Аналогично если поменять A и B местами.
Но затем Вы пишете
Поясните, пожалуйста, что Вы имели в виду?
Изначально я слишком сумбурно описал предлагаемую стратегию. Исправляюсь. Далее идет аккуратное описание стратегии.
Назовем мудреца A особым по отношению к мудрецу B, если мудрец B может гарантированно верно назвать цвет своей шляпы, основываясь лишь на цветах шляп остальных мудрецов и на названном мудрецом A цвете, действуя по стратегии, описанной в решении к первой задаче.
В задаче 1 мудрец под номером 1 является особым по отношению ко всем остальным и не существует особого мудреца по отношению к первому. То есть все мудрецы кроме особого знали какой цвет назвал особый мудрец и знали цвета шляп всех остальных мудрецов. Но особый мудрец мог и не называть никакой цвет, а просто поднять табличку с нужным цветом, если таблички всех цветов имелись в его распоряжении.
Чтобы перейти к задаче 2 надо поправить определение выше, заменив слово "названном" на что-то более подходящее. Я не смог подобрать удачное слово, которое бы одновременно означает как "названном", так и "показанном", поэтому пусть будет "названном или показанном".
Переходим к задаче 2. С учетом вышесказанного можно придумать такую стратегию: случайным образом выбирается мудрец, который будет особым по отношению ко всем остальным и на цвет именно его карточки все остальные будут обращать внимание. В таком случае все мудрецы кроме одного гарантированно ответят правильно.
Однако стратегию можно улучшить. Для этого можно заметить, что любой из мудрецов является особым по отношению ко всем остальным. То есть каждый из мудрецов может для себя выбрать какого-нибудь мудреца и назвать правильно цвет своей шляпы. Таким образом приходим к стратегии, когда ВСЕ мудрецы гарантированно верно назовут цвет своей шляпы.
Эту стратегию можно обобщить и для последующих задач.
Не очень понял задачу 2. Разве нельзя поступить по аналогии с 1 задачей только вместо слов показать табличку нужного цвета в зависимости от четности количества черных/белых шляп у остальных. Дальше все как в первой задаче только вместо "первого" (в качестве того на чью табличку обращать внимание) каждый из мудрецов для себя выберет любого. И тогда каждый сможет ответить правильно. Стало быть, и в оставшихся задачах будет такой же ответ.
Ну тут имеется в виду немного другое. В алгебре вводят понятия кольца и евклидова кольца (кольцо с определенной на нем нормой, удовлетворяющей паре свойств) и уже в рамках евклидова кольца доказывают существование и единственность разложения на простые с точностью до умножения на обратимые элементы поля (например, x^2 = (x) * (x) = (x / 2) * (2 x) = ... в кольце многочленов). Но перед этим дается определение простого элемента:
Необратимый ненулевой элемент p целостного кольца называется простым, если он не может быть представлен в виде p = ab, где a и b –– необратимые элементы
Поэтому в кольце целых чисел простыми являются числа вида ±p. Так что не обязательно простое число является натуральным. Тут просто дело в том, что в школах обычно существенно упрощают, убирая из рассмотрения отрицательные числа, так как это только запутать может.
Что Вы имеете в виду под многострочным режимом? Если речь идет о написании длинных формул в несколько строк, то можно использовать окружение multline (обратите внимание, что именно multline, а не multiline) из пакета amsmath. Вместо
$$ x = y $$нужно писать\begin{multline} x = \\ y \end{multline}. Каждый раз, когда хотите сделать перенос необходимо использовать\\.У LaTeX есть небольшая особенность как он выбирает пробелы вокруг некоторых символов. Например,
, а 
(обратите внимание на пробел между
+bпревращается вa+bпревращается в+иb). Поэтому для красивого разбиения формулы на операторах типа+/-стоит писать\begin{multline} x + {} \\ {} + y \end{multline}; для=такой трюк не требуется:\begin{multline} x = \\ = y \end{multline}.Код вида `$$ \begin{align} ... \end{align} $$` в LaTeX работать не будет. Необходимо удалить `$$`.
Откуда в этой публикации появился тег `java`? :)
Операция деления это далеко не 2 такта. На современных компьютерах деление порядка 50 тактов, а вот суммирование, умножение — один.
Кроме того, первоначальный вариант функции
wholeModможно ускорить.ifдешевле, чем%(эта операция, как известно, основана на делении), то есть лучше сделать взятие остатка и потомreturn res if res >=0 else res + domainВведение к статье сразу напомнило при скрибд: чтобы отменить подписку нужно раз 10 прекликать, что ты хочешь отказаться от подписки. Сколько знакомых знаю (да и я сам), кто там делал себе бесплатный пробный период, все в итоге попадали на списание и уже потом тщательно проверяли, что подписка отменена.
Не могу не отметить, что можно код
заменить на
:)
range. Только, я бы вынес всё, что Вы писали внури тела функции в отдельный класс и кроме вариантаrange (end)добавил быrange (begin, end)и, быть может,range (begin, end, step). Но куда более удобным вариантом будет сделать класс шаблонным. Тогда можно будет писать, например,for (auto i : range (it1, it2)).-fpic: Generate position-independent code (PIC) suitable for use in a shared library, if supported for the target machine.
-fPIC: If supported for the target machine, emit position-independent code, suitable for dynamic linking and avoiding any limit on the size of the global offset table.
-fpie -fPIE: These options are similar to -fpic and -fPIC, but the generated position-independent code can be only linked into executables.
Ваша дополнительная идея очень хорошая. Ее можно слегка оптимизировать. Не уверен, что это сильно поможет. Когда Вы хотите произвести вычисления для некоторого элемента в середине поля, Вам необходимо знать предущую линию (под нее выделить память), в текущей линии предыдущий элемент, текущий и следующий (под них можно выделить 3 локальных переменных) и следующая линия (которая и так есть в исходном массиве, так как Вы еще не успели начать ее «портить»).
Тогда кешируется куски не 4 массивов, а лишь 3.
Но это, скорее оптимизация по памяти, чем по времени.