У Стругацких, скорее, наоборот. Не фантастический антураж в конце неуместно вторгается в детективную интригу, а детективная подводка в начале перетягивает на себя глубинный НФ-посыл.
Я не понимаю, что имеется ввиду под суммой всех разрядов, т.к. каждая цифра совпадает с номером ее разряда. И как Шпунтик понимает, что пропущенный разряд - 5? Объясните поподробнее, пожалуйста, например, как договариваются Винтик и Шпунтик.
Это в приведенном примере цифра совпадает с номером ее разряда, а в общем случае -- как получится. Имеется в виду попросту сумма цифр во всех разрядах.
Шпунтик просто вычисляет эту сумму и берет последнюю цифру (или, что то же самое, остаток от деления на 10). И эта цифра магическим образом оказывается равной номеру пропущенного Незнайкой (и заполненного Винтиком) разряда.
А вот чтобы эта магия сработала, Винтик и Шпунтик и должны договориться, что Винтик будет вписывать не какую попало цифру, а именно такую, чтобы получившийся остаток был равен этому номеру. Это сделать несложно, поскольку сумму остальных цифр (кроме своей) он знает, знает и остаток от деления этой суммы на 10, может рассчитать, насколько этот остаток отличается от нужного ему (то есть от номера пропущенного разряда), а значит, может выбрать такую цифру, чтобы эту разницу компенсировать (одной цифры всегда хватит).
Это один способ, самый очевидный. Но вообще-то, не обязательно действовать именно по такому алгоритму. В общем случае, В&Ш могут заранее подготовить специальную таблицу, в которой для каждого из возможных заданий Незнайки будет записано, какую цифру Винтик должен вписать. Задание состоит из 9 цифр и номера пропущенного разряда (например, 012346789 и 5), но можно представлять его и как результат вставки спецсимвола на место пропущенного разряда (например. 01234_6789) -- это одно и то же. Результат Винтика тоже можно представлять как одну вписываемую цифру (например, 5), а можно как готовый результат ее подстановки (например, 0123456789). Шпунтик потом получит это число (результат подстановки), найдет его в той же таблице с другой стороны и посмотрит, какое должно было быть задание Незнайки, чтобы получилось такое число.
Только вот, чтобы магия срабатывала, обязательно должно быть, чтобы не только у Винтика был единственный вариант ответа для каждого задания, но и чтобы наоборот, каждый ответ Винтика мог быть получен из только из одного задания (иначе говоря, чтобы не было такого, что разные задания дают один и тот же ответ).
Это и называется взаимно-однозначным отображением. На картинке на месте X будет задание Незнайки, а на месте Y -- результат Винтика.
Важно, что и цифр в используемой системе счисления 10, и разрядов в рассматриваемом числе столько же. Когда задача кажется слишком сложной, иногда помогает рассмотреть сначала более простую ("редуцированную", как выразился автор поста) задачу. В нашем случае, мы можем вместо 10 взять 2, 3, 4 и так далее -- главное, чтобы и система счисления (то есть, попросту размер набора используемых цифр), и количество разрядов в числе равнялись одному и тому же значению.
…подсчет перманента ничем не лучше простого перебора вариантов.
По сути – это он и есть :)). Но отсюда возникает вопрос: а не значит ли это, что более эффективный алгоритм подсчёта попросту невозможен? (Ответа я не знаю, если что)
Почему? Количество шаблонов равно количеству чисел, деленному на размер алфавита из цифр (потому что n цифр заменяем одним джокером), и умноженному на количество разрядов в числе (потому что делаем это для каждого разряда).
Имеем регулярный двудольный граф степени 10, задающий отображение двух множеств. Одно множество -- все последовательности десятичных цифр длиной 10 (далее чисел); другое множество -- все "шаблоны" (последовательности цифр, в которых ровно одна из цифр заменена на символ-джокер; далее шаблоны). Размер каждой из долей 10^10, при этом каждое число связано с 10 разными шаблонами, а каждый шаблон -- с 10 разными числами.
Незнайка выбирает шаблон, после чего Винтик выбирает одно из чисел, связанных с этим шаблоном, после чего Шпунтик должен выбрать из шаблонов, связанных с этим числом, тот же шаблон, что был выбран Незнайкой изначально.
Для того чтобы последнее было возможно, необходимо и достаточно выбрать в упомянутом графе регулярный подграф степени 1 (или, иными словами, совершенное паросочетание). Иначе говоря, из каждых 10 ребер, инцидентных одному и тому же числу, оставить ровно одно, но при этом так, чтобы и из каждых 10 ребер, инцидентных одному и тому же шаблону, осталось тоже ровно одно.
Число совершенных паросочетаний в двудольном графе равно перманенту его матрицы смежности. (Перманент -- это как детерминант, но все слагаемые со знаком "+").
В теории, этого достаточно. На практике, вычисление перманента -- вычислительно сложная задача и при n=10^10 ловить нечего.
У Винтика на выходе одна цифра, и у Шпунтика на выходе одна цифра. […] Число возможных взаимно-однозначных комбинаций этих двух цифр сверху ограничено 10!
Откуда взялось требование взаимной однозначности этих цифр? Почему Шпунтик не может для одной и той же цифры Винтика вернуть разные цифры в зависимости от контекста?
Позвольте, заданный вопрос существенно полагается на формат коммуникации между Винтиком и Шпунтиком -- а именно на возможность однозначно восстановить прообраз продемонстрированной Шпунтику комбинации. Не любое отображение годится, а лишь то, которое обладает таким свойством.
И разумеется, номер пропущенного разряда кодируется не просто одной цифрой, которую пишет Винтик, а этой цифрой, взятой в контексте, заданным Незнайкой.
Винтик и Шпунтик имеют на входе таблицу из всех возможных комбинаций 10 цифр – 9 написанных Незнайкой плюс номер пропущенного разряда.
Не совсем так. Это Винтик имеет такую таблицу. А Шпунтик имеет другую таблицу: синтаксически это всё те же комбинации 10 цифр, но семантически это 9 цифр, написанных Незнайкой, плюс одна, написанная Винтиком, -- а номер пропущенного разряда как раз ему неизвестен.
Винтик отображает первую таблицу во вторую, а Шпунтик -- вторую в первую. Поэтому и требуется взаимная однозначность.
Ошибка в том, что подменяют понятия. В [верном] утверждении "квадрат есть частный случай прямоугольника" речь идет об иммутабельных объектах, а в примерах нарушения LSP — уже об имеющих состояние.
А компания запрашивает выплаченную стипендию назад только для тех, кто прошел стажировку, но отказался работать, или все-таки для всех непрошедших тоже?
Да, по аналогии. Если работает так: пришёл в парикмахерскую, заплатил денег, полчаса посидел – вышел с причёской, значит, должно работать и так: пришёл на курсы, заплатил денег, полтора месяца походил – и ты специалист.
Причём маркетологи курсов сами создают такое впечатление, когда пишут: специалисты в этой области зарабатывают <подставьте сумму>. Ведь подразумевается: заплатил 100 тысяч один раз – и получай каждый месяц по 300. Выгодная инвестиция! То, что платить придётся не за коробочное решение, а за сырьё для самостоятельной обработки, обычно скромно умалчивается.
Ну, антипаттерн по определению – часто встречающийся в реальной жизни подход, здесь никакого противоречия нет. Само по себе это наблюдение не отвечает на вопрос, насколько адекватна предлагаемая альтернатива.
Пользовательская история: Как пользователь, я хочу использовать поле поиска для ввода названия города, отеля или улицы, чтобы я мог найти подходящие варианты отелей.
Критерии приемки базового интерфейса поиска
Поле поиска размещено в верхней панели.
Поиск начинается, когда пользователь щелкает "Поиск".
Поле содержит подсказку серым текстом: "Куда вы направляетесь?"
Подсказка исчезает, как только пользователь начинает вводить текст.
Насколько я понимаю, такая детализация пользовательских историй – это антипаттерн. На этапе их составления определяется, ЧТО делать (какие потребности пользователя закрывать). Решения о том, КАК делать (какие средства использовать), принимаются на этапе "Вся команда обсуждает истории и КП".
У Стругацких, скорее, наоборот. Не фантастический антураж в конце неуместно вторгается в детективную интригу, а детективная подводка в начале перетягивает на себя глубинный НФ-посыл.
А мне понравилось (с) :)). Введенского напоминает. Хочу продолжения :)
Это в приведенном примере цифра совпадает с номером ее разряда, а в общем случае -- как получится. Имеется в виду попросту сумма цифр во всех разрядах.
Шпунтик просто вычисляет эту сумму и берет последнюю цифру (или, что то же самое, остаток от деления на 10). И эта цифра
магическим образомоказывается равной номеру пропущенного Незнайкой (и заполненного Винтиком) разряда.А вот чтобы эта магия сработала, Винтик и Шпунтик и должны договориться, что Винтик будет вписывать не какую попало цифру, а именно такую, чтобы получившийся остаток был равен этому номеру. Это сделать несложно, поскольку сумму остальных цифр (кроме своей) он знает, знает и остаток от деления этой суммы на 10, может рассчитать, насколько этот остаток отличается от нужного ему (то есть от номера пропущенного разряда), а значит, может выбрать такую цифру, чтобы эту разницу компенсировать (одной цифры всегда хватит).
Это один способ, самый очевидный. Но вообще-то, не обязательно действовать именно по такому алгоритму. В общем случае, В&Ш могут заранее подготовить специальную таблицу, в которой для каждого из возможных заданий Незнайки будет записано, какую цифру Винтик должен вписать. Задание состоит из 9 цифр и номера пропущенного разряда (например, 012346789 и 5), но можно представлять его и как результат вставки спецсимвола на место пропущенного разряда (например. 01234_6789) -- это одно и то же. Результат Винтика тоже можно представлять как одну вписываемую цифру (например, 5), а можно как готовый результат ее подстановки (например, 0123456789). Шпунтик потом получит это число (результат подстановки), найдет его в той же таблице с другой стороны и посмотрит, какое должно было быть задание Незнайки, чтобы получилось такое число.
Только вот, чтобы магия срабатывала, обязательно должно быть, чтобы не только у Винтика был единственный вариант ответа для каждого задания, но и чтобы наоборот, каждый ответ Винтика мог быть получен из только из одного задания (иначе говоря, чтобы не было такого, что разные задания дают один и тот же ответ).
Это и называется взаимно-однозначным отображением. На картинке на месте X будет задание Незнайки, а на месте Y -- результат Винтика.
Важно, что и цифр в используемой системе счисления 10, и разрядов в рассматриваемом числе столько же. Когда задача кажется слишком сложной, иногда помогает рассмотреть сначала более простую ("редуцированную", как выразился автор поста) задачу. В нашем случае, мы можем вместо 10 взять 2, 3, 4 и так далее -- главное, чтобы и система счисления (то есть, попросту размер набора используемых цифр), и количество разрядов в числе равнялись одному и тому же значению.
*натягивается на
По сути – это он и есть :)). Но отсюда возникает вопрос: а не значит ли это, что более эффективный алгоритм подсчёта попросту невозможен? (Ответа я не знаю, если что)
Почему? Количество шаблонов равно количеству чисел, деленному на размер алфавита из цифр (потому что n цифр заменяем одним джокером), и умноженному на количество разрядов в числе (потому что делаем это для каждого разряда).
Да. Скачал Python-скриптик где-то на SO. Могу прислать файл
В общем, так.
Имеем регулярный двудольный граф степени 10, задающий отображение двух множеств. Одно множество -- все последовательности десятичных цифр длиной 10 (далее чисел); другое множество -- все "шаблоны" (последовательности цифр, в которых ровно одна из цифр заменена на символ-джокер; далее шаблоны). Размер каждой из долей 10^10, при этом каждое число связано с 10 разными шаблонами, а каждый шаблон -- с 10 разными числами.
Незнайка выбирает шаблон, после чего Винтик выбирает одно из чисел, связанных с этим шаблоном, после чего Шпунтик должен выбрать из шаблонов, связанных с этим числом, тот же шаблон, что был выбран Незнайкой изначально.
Для того чтобы последнее было возможно, необходимо и достаточно выбрать в упомянутом графе регулярный подграф степени 1 (или, иными словами, совершенное паросочетание). Иначе говоря, из каждых 10 ребер, инцидентных одному и тому же числу, оставить ровно одно, но при этом так, чтобы и из каждых 10 ребер, инцидентных одному и тому же шаблону, осталось тоже ровно одно.
Число совершенных паросочетаний в двудольном графе равно перманенту его матрицы смежности. (Перманент -- это как детерминант, но все слагаемые со знаком "+").
В теории, этого достаточно. На практике, вычисление перманента -- вычислительно сложная задача и при n=10^10 ловить нечего.
(Для тернарного случая мои расчеты дали 10752)
Откуда взялось требование взаимной однозначности этих цифр? Почему Шпунтик не может для одной и той же цифры Винтика вернуть разные цифры в зависимости от контекста?
"Иногда усердие превозмогает и рассудок" (с)
Позвольте, заданный вопрос существенно полагается на формат коммуникации между Винтиком и Шпунтиком -- а именно на возможность однозначно восстановить прообраз продемонстрированной Шпунтику комбинации. Не любое отображение годится, а лишь то, которое обладает таким свойством.
И разумеется, номер пропущенного разряда кодируется не просто одной цифрой, которую пишет Винтик, а этой цифрой, взятой в контексте, заданным Незнайкой.
Не совсем так. Это Винтик имеет такую таблицу. А Шпунтик имеет другую таблицу: синтаксически это всё те же комбинации 10 цифр, но семантически это 9 цифр, написанных Незнайкой, плюс одна, написанная Винтиком, -- а номер пропущенного разряда как раз ему неизвестен.
Винтик отображает первую таблицу во вторую, а Шпунтик -- вторую в первую. Поэтому и требуется взаимная однозначность.
Ошибка в том, что подменяют понятия. В [верном] утверждении "квадрат есть частный случай прямоугольника" речь идет об иммутабельных объектах, а в примерах нарушения LSP — уже об имеющих состояние.
The glocky kuzdra shteckly budled the bocker and is kurdyaking the bockerling.
Спасибо за подробный и чёткий ответ!
А компания запрашивает выплаченную стипендию назад только для тех, кто прошел стажировку, но отказался работать, или все-таки для всех непрошедших тоже?
Да, по аналогии. Если работает так: пришёл в парикмахерскую, заплатил денег, полчаса посидел – вышел с причёской, значит, должно работать и так: пришёл на курсы, заплатил денег, полтора месяца походил – и ты специалист.
Причём маркетологи курсов сами создают такое впечатление, когда пишут: специалисты в этой области зарабатывают <подставьте сумму>. Ведь подразумевается: заплатил 100 тысяч один раз – и получай каждый месяц по 300. Выгодная инвестиция! То, что платить придётся не за коробочное решение, а за сырьё для самостоятельной обработки, обычно скромно умалчивается.
Ну, антипаттерн по определению – часто встречающийся в реальной жизни подход, здесь никакого противоречия нет. Само по себе это наблюдение не отвечает на вопрос, насколько адекватна предлагаемая альтернатива.
Насколько я понимаю, такая детализация пользовательских историй – это антипаттерн. На этапе их составления определяется, ЧТО делать (какие потребности пользователя закрывать). Решения о том, КАК делать (какие средства использовать), принимаются на этапе "Вся команда обсуждает истории и КП".