UPDATE-4 07-01-2011 Рав Кав - с анонимной карточкой нельзя отменить "зарядку" Если у вас анонимная карточка Рав Кава вы не можете отменить его "зарядку", если, скажем, произошла какая-то ошибка. Точнее, вы можете это сделать только если сразу же заметили и если после вас не был использован другой Рав Кав.
UPDATE-5 21-01-2011 Рав Кав - это, всё-таки, не обычный проездной билет Если есть две программы на Рав Кав, нужно чтобы водитель дополнительно нажимал на кнопку, чтобы снять деньги за проезд. Имея деньги на электронном кошельке можно ездить по маршрутам, которые оплачиваются по разным тарифам. Можно иметь на Рав Каве более одного "проездного".
Замечание: За мной остался небольшой должок. У меня этот пост долго не был дописан, вот наконец дописал. В нём представлено два различных подхода к решению к одной и той же задаче, которая реально у меня возникла в жизни. Решил я её давно (обоими способами), а вот дописать пост до конца, заняло много времени. Первый способ решения - математический, ответ был получен быстро, хотя требует неких "специальных" знаний, второй - "инженерный", компьютерный, решение "в лоб", однако оно дало другой взгляд на проблему. В процессе компьютерного решения, я также столкнулся с "
проблемой округления".
В принципе
тема рав кава раскрыта, я написал про его
непрозрачность однако за мной остался не большой должок.
Напомню вкратце о чём речь. Раньше в автобусной компании Дан были среди прочего обычные (бумажные) проездные. Как мы выяснили все эти картисиёт никув предоставляли
скидку в 20%. Фактически, покупая обычный проездной, мы предоставляем
кредит Дану под 20% на некий неопределённый срок (зависит от того, сколько поездок в день мы будем делать). Когда нам пробивают дырку, нам "возвращают" деньги обратно. В самом деле, когда все поездки израсходованы, если бы не покупали бы проездной мы бы потратили на 20% больше. Минимальный тариф у Дана 5,8 шекелей за проезд. Обычный проездной предоставляет право на 10 поездок и стоит 46,4 шекеля.
Бумажные проездные уже ушли в прошлое, их заменили пластиковые карточки рав кав. Среди прочего она предоставляет возможность использовать
эрех цавур. По сути это
электронный кошелёк. Положить деньги в электронный кошелёк можно только кратно 30, 50 или 100 шекелям. В прошлом посте я рассмотрел сценарий при котором мы пользуемся исключительно минимальным тарифом по 5,8 шекеля. С обычными (бумажными) проездными, мы могли дать 50 шекелей,
получить сдачу $50-46,4=3,6$ шекеля и получить право на 10 проездов, плюс мы получили скидку в 20%. Теперь посмотрим, что будет, если мы попытаемся использовать эрех цавур, чтобы купить эти же 10 поездок исключительно по минимальному тарифу 5,8 шекеля. Как я
показал, фактически мы дали дополнительный кредит в размере 4,5 шекеля. Очевидно, что через 10 поездок мы не можем воспользоваться этими деньгами. Вопрос, которому посвящена эта заметка следующий: через сколько проездов дополнительный кредит на сдачу будет погашен полностью ?
Ниже есть продолжение.
Правильный ответ я дал в предыдущем посте, через 580 поездок, однако я не показал, что это является минимальным числом таких поездок. В выводах я лишь скромно указал, что через 10 поездок сдача не может быть получена, а в рассуждениях я показал, что через 580 поездок сдача будет нулевая.
Итак, дано: после каждых десяти поездок у нас остаётся 450 агорот. За одну поездку с нас снимают 580 агарот. Через сколько "десятков поездок" у нас останется ноль?
Давайте подумает что нам нужно найти. Если у нас останется положительная сумма кратная 580, т.е. такая которую можно представить в виде $580k'$ для некоторого натурального $к'$. то мы сможем её потратить. С другой стороны эта положительная сумма накапливается за каждые 10 поездок с помощью увеличения на 450, т.е. такая которую можно представить в виде $450k$ для некоторого натурального $к$. Если мы сможем найти такие натуральные $к'$ и $к$, что
$580k'=450k$
то ответом на вопрос задачи и будет число $к$. Очевидно, что нас интересует минимальное число десятков поездок, поэтому мы будем искать наименьшее значение $к$ и $к'$ для которых
$580k'=450k=m$
Однако, по определению наименьшего общего кратного или lcm от английского least common multiple, $m$ является lcm(450, 580), т.е. $m=lcm(450, 580)$
Таким образом, минимальное число десятков поездок $k=\frac{lcm(450, 580)}{450}$
$450=10*(3*3*5)$
$580=10*(2*29)$
Ни один из делителей числа 3*3*5 не присутствует в разложении числа 2*29. Ни один из делителей числа 2*29 не присутствует в разложении числа 3*3*5. Это значит, что
$lcm(450, 580)=10*(3*3*5)*(2*29)=2*5*3*3*5*2*29=2*2*3*3*5*29$
Напомню, что $450=10*(3*3*5)=2*5*3*3*5=2*3*3*5*5$. Тогда
$k=\frac{lcm(450, 580)}{450}=\frac{2*2*3*3*5*29}{2*3*3*5*5}=2*29=58$
т.е. через минимум 58 "десятков поездок" или 580 поездок у нас в кошельке накопиться такая сумма, что мы её сможем "проездить" до нуля.
Несмотря на то, что это решение исчерпывающие и на нём можно поставить точку, я предоставлю ещё одно "инженерное" решение, которое не оперирует такими "сложными" понятиями как lcm. Это решение, также прольёт свет на некоторые интересные особенности.
Построим таблицу Excel следующим образом: в колонке А будут идти поездки на автобусе сгруппированные по десяткам, 10, 20, 30 и так до 580. В колонке B будет "накопленная сдача за вычетом денег, потраченных на проезд", для первых десяти поездок это будет 4,5 шекеля, а для каждых последующих десяти поездок это будет сумма, которая осталось от предыдущих десяти поездок плюс 4,5 шекеля. В колонке C будем спрашивать накопилось ли у нас денег достаточных для проезда? Т.е. если в колонке B сумма больше чем 5,8 то ответ 1, накопилось на один проезд, иначе 0, не накопилось (т.к. первоначальная сумма $4,5<5,8$, и на каждом шаге прибавляется $4,5<5,8$ то у нас не может "накопится" на две поездки). В колонке D мы будем отнимать от "накопленной сдачи за вычетом проезда" стоимость одного проезда в 5,8 шекелей в том случае, если в колонке C находится 1 и просто переносить "накопленной сдачи за вычетом проезда", если в колонке C находится 0.
Заметим, что колонка D может быть посчитана как D=B-C*5,8. В самом деле, так как C принимает только два значения 0 или один имеем:
1) если C=0, то D=B-C*5,8=B-0*5,8=B и данная формула совпадает с формулой выше при C=0.
2) если C=1, то D=B-C*5,8=B-1*5,8=B-5,8 и данная формула совпадает с формулой выше.
Сделаем первые два шага вместе. Итак, после десяти поездок, A1=10, у нас осталось 4,5 шекеля, B1=4,5. Т.к. $4,5<5,9$ значит C1=0 и значит D1=B1-С1*5,8=4,5-0*5,8=4,5.
После двадцати поездок, у нас "накопится" 4,5 с прошлых десяти поездок (то что мы посчитали на предыдущем шаге, D1) плюс 4,5, т.е. B2=D1+4,5=4,5+4,5=9. Т.к. $9>=5,9$, значит C2=1 и значит D2=B2-С2*5,8=9-1*5,8=3,2.
Лист Excel выглядит таким образом:
Как хорошо из него видно, минимальное количество поездок равняется 580.
Вас не должно смущать, что в той графе стоит не ноль, а "очень маленькое число". Это произошло из-за проблемы округления точнее из-за особенностей хранения числа с плавающей запятой в памяти компьютера. Кому интересны подробности, касательно конкретно Excel милости прошу сюда.
Тех, кого всё-таки смущает, что мы не получил ноль, либо, кто хочет увидеть другое решение, вот вам два других способа. В любом случае, стоит посмотреть на график ниже.
Итак, в рассуждениях выше мы дошли до того, что, если мы сможем найти такие натуральные $к'$ и $к$, что
$580k'=450k$
то ответом на вопрос задачи и будет число $к$.
Однако, согласно определению равенства по модулю, это можно интерпретировать как
$450k \equiv 0 (mod 580)$
Ниже представлена таблица Excell, которая использует это формулы с маленькой модификацией. Добавлено деление на сто, чтобы перевести агорот, назад в шекели, а также "десятки поездок" "нормализованы", т.е. вместо колонки A со значениями 10,20,30, мы имеем колонку A со значениями 1,2,3. Таким образом, колонка A отображает "десятки поездок" (нужно число, записанное там, умножить на 10), а колонка B - сдачу в шекелях.
Это же таблица, представлена как график, на котором видно, как "сдача" меняется со временем.
Какую новую информацию даёт нам график? То, что "сдача" у нас то уменьшалась, то внезапно увеличивалась, можно легко увидеть и выше, а вот, что интересно, что локальные минимумы имеют тенденцию к уменьшению. Локальные минимумы достигаются в точках (3; 1,9), (7; 2,5), (12; 1,8), (16; 2,4), (21; 1,7), (25; 2,3), (30; 0). Таким образом, если мы считаем, что "два шекеля - это не деньги" (см. пост о вреде округления), то мы уже через 3 "десятка поездок", т.е. через 30 "вернём" себе сдачу. Также видно, что нечётные локальные минимумы упорядочены в порядке убывания, т.е. 1,9>1,8<1,7>0.
Второй способ избежать проблемы округления. Вернёмся к первому листу Excell-а. Отчего-же возникла неточность в конце вычислений? От того, что мы, чтобы вычислить значение в клетке D58, нам нужно было вычислить значение в клетках D1,...,D57, т.е. для клетки Dn, нам нужны знать точные значения D1,...,D(n-1). В каждом значении Di $0\lt i\lt n$, есть некоторая погрешность представления числа (попробуйте, представить число 0,1 в двоичной системе, учитывая, что у вас есть конечная память). Так вот, когда вы используете одно или несколько чисел, то это погрешность находится за гранью требуемой точности (вы показываете две цифры после запятой, погрешность гораздо дальше). Однако, когда вы используете n таких чисел, то погрешность "аккумулируется".
Напомню, как мы считали и сразу буду писать, как это можно посчитать по-другому.
В колонке А шли "десятки поездок": 10, 20, 30 и так до 580. В новом графике, я их "нормализую" в 1,2,3 и так до 58.
В колонке B была "накопленная сдача за вычетом денег, потраченных на проезд", для первой "десятки поездок" это было 4,5 шекеля, а для каждых последующей "десятки поездок" это была сумма, которая осталось от предыдущего "десятка поездок" плюс 4,5 шекеля. Заметим, что то же самое, мы можем получит просто умножив 4,5 на номер "десятка поездки", $4,5Ak$, для строки k.
В колонке C мы спрашивали накопилось ли у нас денег достаточных для проезда? Т.е. если в колонке B сумма больше чем 5,8 то ответ 1, накопилось на один проезд, иначе 0, не накопилось. Такой же результат даст следующая формула:
$\lfloor 4,5Ak/5,8 \rfloor$, где $\lfloor . \rfloor$ обозначает ближайшее целое число, округлённое вниз. Легко видеть, что значение этой формулы возрастает на единицу тогда и только тогда добавление, числа кратному 4,5 дало как минимум 5,8, т.е. именно тогда, когда денег накопилось на ещё один проезд.
Колонку D мы считал как D=B-C*5,8. Подставляя, альтернативное определение колонок, получим: $D=4,5Ak-\lfloor 4,5Ak/5,8 \rfloor * 5,8$. Легко видеть, что это формула зависит, только от Ak, таким образом мы можем переименовать колонку D в колонку B.
И последние замечание, математическое выражение $\lfloor 4,5Ak/5,8 \rfloor$ в Excell запишется как FLOOR(4,5*Ak/5,8;1), 1 - значит округлить (вниз) до ближайшего целого.
Вот собственно и всё.
UPDATE-4 07-01-2011 Рав Кав - с анонимной карточкой нельзя отменить "зарядку" Если у вас анонимная карточка Рав Кава вы не можете отменить его "зарядку", если, скажем, произошла какая-то ошибка. Точнее, вы можете это сделать только если сразу же заметили и если после вас не был использован другой Рав Кав.
UPDATE-5 21-01-2011 Рав Кав - это, всё-таки, не обычный проездной билет Если есть две программы на Рав Кав, нужно чтобы водитель дополнительно нажимал на кнопку, чтобы снять деньги за проезд. Имея деньги на электронном кошельке можно ездить по маршрутам, которые оплачиваются по разным тарифам. Можно иметь на Рав Каве более одного "проездного".
