ВОПРОС
Буратине дали три яблока. два он съел. сколько яблок после этого у Буратины?
ОТВЕТ
может одно?
Нифига.
Никто же не знает сколько у него уже было яблок до этого.
Элементарные операции, логика и анализ
Начнем с того, что во-первых, не определено, что есть «Буратино», Во-вторых не определено, что есть «яблоко», более того, с понятием «дали» тоже проблемы. Про понятие «съел» я вообще боюсь говорить. Давайте не будем «миксовать» элементарные операции с логикой и анализом.
Не оговорено, например, что между операциями «дали», «съел» и «подсчет остатка» ничего с яблоками не происходит. А ведь запросто может прийти кто-то и дать еще яблок, например, после того, как он съел два. Или отобрать их. В таком случае мы не можем сказать, какой будет остаток даже в случае, если мы знаем начальное значение.
Не оговорено так же, могут ли появиться клоны буратин. А ведь запросто может появиться несколько одинаковых, не различимых между собой буратин. Будут ли яблоки у них общие или у каждого свои? Если буратины не различимы, то яблоки могут быть только общие, поскольку даже для того, что бы дать яблоки «любому случайному» буратино, нужно этого случайного буратину каким-то образом выбрать из общей массы буратин.
Замечание насчет неопределенности операций «дали» и «съел» — это очень важное замечание. Одно дело, если это атомарные операции. Совсем другое дело, если Буратино ест яблоки в несколько этапов. Например, так:
1) вытащил все яблоки из кармана. Тут есть два варианта. а) После выполнения этой операции в кармане не остается ни одного яблока и б) если в кармане хранится записка с цифрой, которая обозначает количество яблок, то эта записка не меняется — количество остается неизменным.
2) выбрал из них два
3) положил остаток в карман. Как правило, после операции «положил» старое значение заменяется на новое.
Аналогично можно было бы определить операцию «дали».
Не верно думать, что обычно операция поедания яблок буратинами — это атомарная операция. Это только некоторые определенные, довольно редко встречающиеся, специально для этого предназначенные типы буратин не разбивают процесс поедания яблок на этапы. Да и то, это только внешне кажется, что у этих специальных буратин процесс поедания яблок не разбит на этапе, внутри же эти буратины, скорее всего, действуют по описанному ниже алгоритму синхронизации.
Не верно также думать, что «положить» — это означает «прибавить», а не «присвоить». Операция сложения ничего сама по себе не меняет — нам же требуется запомнить, что яблоки были добавлены и теперь их количество изменилось. Если яблоки просто добавить и при этом не запомнить результат, то добавлять не имеет смысла — количество яблок от этого не поменяется.
Карман сам по себе не выполняет никаких вычислений, точно так же, как и операция сложения не может быть использована для хранения данных.
Ошибки синхронизации разных буратин
Если допустить наличие неразличимых между собой клонов, то может сложиться ситуация, когда Буратино не сможет съесть яблоки, даже если они есть в достаточном количестве.
Например, у Буратино в кармане 10 яблок. Он хочет съесть два яблока. Он вытаскивает все яблоки из кармана. В кармане остается ноль яблок (по первому варианту операции «вытащил»). В этот момент появляется клон и тоже хочет съесть два яблока. Поскольку в кармане нет яблок, тот этот клон остается без яблок, хотя если он догадается подождать, когда первый Буратино положит остаток в карман, то он сможет съесть свои два яблока.
В этом примере буратино должен уметь ждать, когда клон положит остаток в карман. Если не ждать, то Буратино останется голодным, даже если яблоки есть в достаточном количестве. Не так-то просто отличить, что в кармане ноль яблок из-за того, что эти яблоки находятся на руках у одного из клонов или из-за того, что яблок просто нет.
Яблоки могут появиться из ниоткуда, если после операции «вытащил из кармана» количество яблок в кармане не меняется.
Например, если у нас только один Буратино, у него в кармане десять яблок, он выбирает их (согласно нашей операции в кармане остается десять), отсчитывает свои два яблока и остаток — восемь яблок — кладет обратно в карман, заменяя цифру 10 цифрой восемь. Как только появляется клон — картина резко меняется. Первый выбрал 10 яблок, и пока первый отсчитывал свои два, второй тоже выбрал 10 яблок. Первый положил в карман остаток — 8 яблок. И второй тоже положил в карман остаток — 8 яблок. В итоге в кармане осталось 8 яблок, хотя сначала было десять, два буратино съели по два яблока и при этом никакие яблоки извне не поступали.
Если допустить, что Буратино может есть яблоки «в долг», то может возникнуть ситуация, когда яблоки берутся из ниоткуда и исчезают вникуда.
Например, у Буратино в кармане 10 яблок. Он хочет съесть два яблока. По нашему алгоритму он вытаскивает эти десять яблок из кармана и в кармане (по первому варианту операции «вытащил») остается ноль яблок. Тут приходит клон и тоже хочет съесть два яблока. Он видит, что в кармане ноль яблок и ест два яблока в долг. Первый Буратино отсчитал свои два яблока и положил оставшиеся восемь в карман. После этого второй Буратино отсчитал свои два яблока из вытащенных нуля яблок и получившийся остаток — минус два яблока — кладет в карман. В итоге в кармане минус два яблока, хотя только два буратины съели по два яблока, изначально было десять и никакие яблоки больше никуда не передавались -- яблоки исчезли в неизвестном направлении.
Допустим, в этом примере было не 10, а 1048576 яблок и Буратино хотел съесть 9876 яблок. Посчитать, сколько будет 1048576-9876 несколько сложнее, чем 0-9876, поэтому первый Буратино замешкался, подсчитывая остаток, и пока первый подсчитывал свой остаток, второй быстро посчитал и положил -9876 яблок в карман. После этого первый досчитал остаток и положил 1038700 в карман. В итоге количество яблок в кармане уменьшилось только на 9876, хотя в сумме двумя буратинами было съедено 9876*2=19752 яблока -- 9876 яблок взялось из ниоткуда.
В кармане может быть дырка — это когда яблоки пожираются червями вне зависимости от согласия на то буратин. Как проводить учет яблок в таком случае — не совсем ясно.
Клоны буратин — это пользователи, обращающиеся к страницам сайта. Вы никогда не знаете, обращается ли в данный момент к этому сайту кто-нибудь ещё.
Сплошь и рядом ходят толпы одинаковых неразличимых между собой буратин. Обращаются к моему сайту и едят яблоки из одного и того же файла. И при этом так и норовят есть яблоки одновременно сразу по нескольку. Задача вполне обычная. Я вообще даже затруднюсь объяснить буратинам, что они должны яблоки есть по очереди — ведь для этого каждый следующий буратино должен знать, а ест ли кто-нибудь яблоки сейчас.
Для такого случая есть аутоинкремент. Оно тебе всех буратин посчитает в лучшем виде.
Ну и что мне это дает? Это с точки зрения буратин они одинаковые. А с точки зрения яблок, поедаемых буратинами — все буратины разные: яблоки знают, что они находятся у этого, а не у другого буратины. Очередь, в которой стоят буратины, сама по себе вносит вполне конкретные различия: этот буратино пришел первым, тот — вторым. В своих примерах именно на эти различия я и опирался. Но от того, что мы знаем, кто каким пришел, задача определения того, ждать ли буратине, когда предыдущий доест яблоки и положит остаток в корман или уходить голодным, потому что в кормане нет яблок — не становится проще.
Алгоритм синхронизации — критические секции
Как сообщить второму буратине, что перед ним в очереди есть другие буратины и он должен ждать? Для этого нужно завести отдельный карман, и положить туда специальное негниющее и несъедобное яблоко. Это яблоко будет признаком того, что какой-то другой буратино сейчас кушает яблоки. Чтобы избежать приведённой выше путаницы, буратино должен кушать яблоки примерно по такому алгоритму:
1. Проверить, на месте ли спецяблоко. Если его нет, то считаем, что какой-то другой буратино в данный момент кушает яблоки, и поэтому текущий буратино буратино должен ждать, когда яблоко появится.
2. Как только спецяблоко появилось, буратино берёт его себе и идёт вместе с ним кушать обычные яблоки.
3. Когда буратино съел свои яблоки, он должен положить спецяблоко на место.
Но в этом примере может случиться так, что буратино умрёт, когда будет кушать свои яблоки. В таком случае он не вернёт спецяблоко на место, и тогда все следующие буратины будут вынуждены вечно стоять в очереди, ожидая появления спецяблока. Для того, чтобы справиться с этой ситуацией, нужно договориться, что буратины могут есть свои яблоки не дольше, чем Х секунд. Потребуется также некий сверхбуратино, который будет сидеть рядом с карманом со спецяблоком и засекать для каждого буратины, сколько тот тратит времени на поедание яблок. Если какой-то буратино ест яблоки слишком долго, то он считается мёртвым. Тогда сверхбуратино отбирает у несчастного яблоки, кладёт их обратно в карман, выносит этого буратину за пределы кармана (на случай, если тот всего лишь притворился мёртвым, чтобы нелегально кушать яблоки незаметно для всех) и возвращает на место спецяблоко. Задача может усложняться до бесконечности, если мы допустим возможность смерти сверхбуратины.
Но даже при использовании такого алгоритма, могут появиться буратины, которые по своей лени не выполняют этот алгоритм, думая, что никаких других буратин в округе нет и будут ломиться прямо к карману, не обращая внимание на спецяблоко. И тогда яблоки всё равно будут появляться из никоткуда и исчезать вникуда.
Ошибки, связанные с доверием данным, которые пришли от пользователя, на примере Cookie
Вообще говоря, один и тот же буратино может прийти кушать яблоки более чем один раз. Но когда этот буратино придет кушать яблоки во второй раз, мы не можем так просто сказать, кушал ли этот буратино яблоки раньше или нет — это нужно отдельно как-то буратинам выдавать уникальные идентификаторы, заставлять их постоянно носить эти идентификаторы с собой, хранить базу идентификаторов и для каждого буратины помнить, ел ли он яблоки. Буратины могут умирать, поэтому старые идентификаторы во избежание переполнения базы данных идентификаторов должны удаляться из базы. Идентификаторы могут быть удалены по ошибке, если буратино жив, но долго не ел яблоки. В таком случае этот буратино будет считаться новым. Буратино будет так же считаться новым, если он потеряет свой идентификатор. Могут появиться буратины-хакеры, которые будут подделывать идентификаторы других буратин, чтобы кушать больше яблок, чем положено есть одному буратине.
Кстати, из-за буратин-хакеров автоинкремент нам не подходит: зная один любой идентификатор (например, свой), можно легко угадать идентификаторы нескольких других буратин.
Если что,
мопед не мой — у меня на такие размышления мозгов не хватит.
фигня какая-то. ситуация описана в задаче математически. т.е. ни каких "может быть", если это "может быть" отдельно не оговаривалось — их быть не может.
