Является ли билет счастливым

Является ли билет счастливым

«Счастливость» билета можно определить несколькими методами. Наибольшее распространение получили три из них:

  • Московский — если на автобусном билете напечатано шестизначное число, и сумма первых трёх цифр равна сумме последних трёх, то этот билет считается счастливым.
  • Ленинградский, или Питерский (менее распространённый) — если сумма чётных цифр билета равна сумме нечётных цифр билета, то билет считается счастливым (в статье журнала «Квант» именно этот способ назван «московским»). Другой вариант — суммы каждой пары цифр равны.
  • Некоторые люди считают билет счастливым, если сумма его цифр является квадратом. Количество таких билетов с шестизначными номерами равно 99153.

Явные формулы

Точное количество счастливых билетов, определяемых как равенство сумм заданных трёх цифр сумме трёх остальных (Московская и Ленинградская системы) можно посчитать по формуле: [2] [3]

которая является частным случаем более общей формулы для нахождения количества 2n-значных счастливых билетов в m-ричной системе счисления (в обычных счастливых билетах используется десятичная система счисления с m=10):

Распределение билетов

В московском и ленинградском методах в среднем один из восемнадцати билетов является счастливым. Однако билеты распределены неравномерно, и вероятность встретить счастливый билет сильно зависит от первых его цифр.

Ниже представлено количество счастливых билетов в каждой тысяче.

Интересные факты

  • В популярной во времена СССР телепередаче Александра Маслякова «А ну-ка, девушки!», в одном из выпусков проводился конкурс между девушками-контролёрами, в ходе которого им нужно было пересчитать количество счастливых билетов в билетной кассе троллейбуса.

Примечания

  1. Фотография билета 000000 на Хабрахабре
  2. Интегралом — по счастливым билетам! // Квант. — 1978. — № 11. — С. 52-53.
  3. Подборка статей о счастливых билетах на ega-math.narod.ru

См. также

Ссылки

  • Счастливый билет on-line
  • Счастливый билетик в «76-82: Энциклопедия нашего детства»
  • Сайт, посвящённый явлению
  • Считаем счастливые билеты. Статьи из «Кванта»
  • Печенье «Счастливый билет»
  • С.К.ЛандоСчастливые билеты // Математическое просвещение. — МЦНМО, 1998. — № 2. — С. 127-132.

Wikimedia Foundation . 2010 .

Смотреть что такое "Счастливый билет" в других словарях:

билет — а, м. billet m.,> нем. Billett.1. Бумага с официальным распоряжением, приказом. Сл. 18. Кардинал и штатскии секретарь Леркари велел на сих днях господину Риццу .. билет вручить, в котором он ему объявляет, чтобы он без замедления дороги… … Исторический словарь галлицизмов русского языка

Билет — на самолёт Туркменских Авиалиний Билет (фр. billet, от средневекового billetus записка, письмо, свидетельство; удостоверение … Википедия

билет — сущ., м., употр. часто Морфология: (нет) чего? билета, чему? билету, (вижу) что? билет, чем? билетом, о чём? о билете; мн. что? билеты; (нет) чего? билетов, чему? билетам, (вижу) что? билеты, чем? билетами, о чём? о билетах 1. Билет это документ… … Толковый словарь Дмитриева

счастливый — прил., употр. очень часто Морфология: счастлив и счастлив, счастлива и счастлива, счастливо и счастливо, счастливы и счастливы; счастливее; нар. счастливо, счастливо 1. Счастливым называют того, кто испытывает большую радость, счастье, потому что … Толковый словарь Дмитриева

Читайте также:  Как найти скорость относительно земли

Билет (фильм) — Билет The Ticket Жанр драма Режиссёр … Википедия

Счастливый случай — It Could Happen To You Жанр комедия Режиссёр Эндрю Бергман В главных ролях Николас Кэйдж Бриджит Фонда … Википедия

БИЛЕТ — БИЛЕТ, а, муж. 1. Документ, удостоверяющий право пользования чем н. разовый или на определённый срок. Железнодорожный б. Сезонный, месячный б. (для проезда на сезон, на месяц). Единый проездной б. (для проезда на разных видах городского… … Толковый словарь Ожегова

СЧАСТЛИВЫЙ — СЧАСТЛИВЫЙ, ая, ое; счастлив и счастлив. 1. Полный счастья, такой, к рому благоприятствует удача, успех; выражающий счастье. Счастливая жизнь. Счастливое детство. Если хочешь быть счастливым, будь им (шутл.). Счастлив, как дитя. Счастливое лицо.… … Толковый словарь Ожегова

счастливый — I см. счастливый; ого; м. II ая, ое; сча/стлив, а, о. см. тж. счастливый, счастливая, счастливые, счастливо, счастливо 1) чем, с инф., с придат. дополнит. Такой, который испы … Словарь многих выражений

билет — а; м. [франц. billet] 1. Документ, удостоверяющий право пользования чем л., посещения чего л., участия в чём л. Трамвайный, троллейбусный, железнодорожный б. Месячный, проездной б. (такой документ многоразового пользования для проезда в… … Энциклопедический словарь

Первая внутригородская автобусная линия появилась на улицах Москвы ровно 85 лет назад. Автобусы сразу стали неотъемлемой частью жизни жителей столицы, и неудивительно, что у горожан даже появились "суеверия", связанные с ними. Самое распространенное поверье, и одновременно развлечение, тренирующее ум, — вычисление счастливого билетика.

Автобусные гурманы

Автобусный билет считался счастливым, если сумма первых трех цифр его номера равнялась сумме последних трех цифр. Например, билет 456834 — счастливый: сумма первых и последних трех цифр составляет 15.

Еще "более счастливыми" считались билеты, в которых совпадает не только сумма цифр, но и их "номинал", как, например, в билете под номером 351513. А самые счастливые проездные билеты — те, в которых все цифры слева и справа совпадают, например 333333.

Чтобы счастье было более полным, а загаданное желание наверняка исполнилось, счастливые билеты полагалось съесть. Но обычно они становились частью коллекции, которая порой собиралась годами.

Дальняя дорога?

Несчастливые билеты могли использоваться для гаданий. Для этого обычно все цифры складывались между

собой до однозначного числа. Например, если номер билета 123456, то полагалось произвести следующее вычисление: 1 + 2 + 3 + 4 + 5 + 6. В результате получается число 21, то есть 2 + 1. Конечное число — 3.

Для каждой цифры было определенное значение. Например, 3 – к любви, 8 — к веселью, 9 — к свиданию и т. д.

Читайте также:  Sql create function пример

Согласно другому распространенному способу гадания, нужно было отдельно сложить первые три и последние три цифры номера билета, а затем вычислить разницу. Или, в другом варианте, выяснить, какой цифры не хватает для того, чтобы билет стал счастливым. По получившемуся числу и определялось будущее.

Математическое состязание

Те, кто в гадания не верили, играли в своеобразную игру, предназначенную для двух и более человек. Каждый складывал все цифры на своем билетике, затем суммы сравнивали. Те, у кого получилась меньшая сумма, получал от тех, у кого сумма была больше, щелбаны. Количество щелбанов определялось разницей в результатах.

По такому же принципу (или сводя номера к одному числу) играли не только на щелбаны, но и на деньги — на копейки или даже рубли.

Началось все с тестового задания на вакансию «js-developer, Node.js-developer», и тут я выпал в осадок: задача на счастливые билетики.

Посчитать количество счастливых билетиков для 2, 4, 6, 8 и 10 цифрового значения.

Уверен, многие уже не раз делали эту банальную задачку, но, как правило, для 6-ти цифр (для тех, кто не понимает о чем пойдет речь).

Банальное решение:

Также можно посмотреть тут.

А если цифр 10? 30? 200? Беда! Приходиться ооочень долго ждать результата: аналог в PHP (5.3) «умирал», даже когда я давал 10 цифр и set_time_limit (3600).

Теперь вернемся в мир JS. Несмотря на то, что простые циклы в Node.js выполняются быстрей, чем в PHP, время выполнения меня все равно не устраивало (1 029 458 ms).

А теперь хватит этого унылого текста, переходим к альтернативному решению.

Сама зацепка оказалась в журнале «Квант», № 12 (1976), с.68–70 (электронный вариант ).

Там же можно увидеть вывод — таблица, с помощью которой можно легко узнать «количество счастья» в билетах из 2 (n=1), 4 (n=2), 6 (n=3) и 8 (n=4) цифрами.

Как заполнить таблицу — изображено ниже:

То есть сумма 10 элементов предыдущего столбца, у которых индекс 1^2 + 1^2 +… + 1^2 = 10;
— для n=2 (4 цифры) -> 1^2 + 2^2 +… + 1^2 = 670;
— для n=3 (6 цифр) -> 1^2 + 3^2 +… + 75^2 +… + 1^2 = 55 252;
— для n=4 (8 цифр) -> 1^2 + 3^2 +… + 670^2 +… + 1^2 = 4 816 030;

Ну и проверить же нужно:

Собственно то, к чему все велось: время выполнения 106 ms (. ), страшно представить, что бы случилось при использовании банального способа.

* все JavaScript-ы проверял на Node.js (x32)
** максимальная длинна номера билета — 310, Больше? — результат переходит в область Infinity.
*** это моя первая статья на Хабре за последние 3 года, прошу камнями не бросать.

Выясняем с помощью теста, что подарить коллегам

  • Скопировать ссылку
  • Facebook
  • Twitter
  • ВКонтакте
  • Telegram
  • Pocket

Похожие публикации

  • 27 ноября 2016 в 19:08
Читайте также:  С помощью чего можно монтировать видео

Настольный пульт управления на JavaScript/Node.js для робота на Ардуине

Тонкости Javascript/Node.js. Увеличиваем производительность в десятки раз

Выразительный JavaScript: Node.js

Вопросы и ответы

Как решить проблему в minio?

Как это называется?

Удаляются файлы после установки npm пакета?

Как выложить проект node.js и mysql на хостинг?

Как в POST форме правильно передать данные, если использую внешний диалог подтверждения?

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Комментарии 19

Расскажите, взяли ли в итоге на работу )

*Увидев такую задачу на собеседовании, я наверно решил бы, раз уж речь идёт про nodejs, что гуглить формулу или пользоваться реализацией алгоритма на предрассчитанной таблице это не то, что требуется, и реализовал примитивное распределение задачи на нескольких нодах. Интересно что хотел работодатель.

Посчитать количество счастливых билетиков для 2, 4, 6, 8 и 10 цифрового значения.

То есть сумма 10 элементов в предыдущего столбца, у которых индекс

Было бы интереснее узнать на пальцах, как он был выведен и почему работает именно так.

Честно говоря, я не особо разбирался в подходе автора, но задачку бы решал, используя динамическое программирование.
Выразим частичное решение в виде M(n, k) — число сочетаний из n цифр, дающих в сумме k (похоже, именно она приведена в тексте поста). Предположим, мы знаем ответ для задачи размера n — 1. Найдём решение для задачи размера n.

Половина билетика выглядит следующим образом:

Нам нужно найти все такие d, что новая сумма равна k.

Далее нужно заметить, что верхняя граница для k всегда ограничена сверху 9 * n, и ответ

M(n, k) возводим в квадрат потому, что одна и таже сумма встречается в двух половинках билета.

Зная, что M(1, k) = 1 для 0

Этот алгоритм — динамическое программирование. В таблице в n-ом столбце в k-ой строке подсчитано количество чисел длины n имеющих сумму цифр k (ведущие нули разрешены). Обозначим это количество через f(k,n) Пересчет такой таблицы тоже очень прост — последняя цифра может быть любой от 0 до 9. Количество таких билетов с последней цифрой i, длинной n, суммой всех цифр k — f(k-i,n-1). Если просуммировать по всем i, как раз будет формула — сложить 10 значений в предыдущем столбце, на той же строке и выше.

Отсюда же понятно, почему количество всех счастливых билетов — сумма квадратов чисел в столбце. Каждый билет составлен из двух половинок, половинки должны иметь одинаковую сумму. Квадраты получается потому, что можно взять любое число длины n с заданной суммой и в левую и в правую половину счастливого билета, поэтому f(k,n)*f(k,n) и будет количество счастливых билетов длины 2n с суммой в каждой половине k. Теперь остается только просуммировать по всем k.

Ссылка на основную публикацию
Этот номер недавно использовался вконтакте сколько ждать
При регистрации страницы или привязке номера ВК пишет: «Этот номер недавно использовался» или «К этому номеру уже привязана страница. Пожалуйста,...
Шарик равноускоренно скатывается по наклонной плоскости
За каждую секунду, путь пройденный шариком,увеличивается на 20см. Следовательно за 4 секунду он пройдет 70см. Ответ:(2) Если ответ по предмету...
Шарнирная стойка для дрели
Стойка для дрели с тисками FIT 37861 Стойка для дрели Калибр 96203 Стойка для дрели RedVerg DS-43 Стойка для дрели...
Эффект памяти аккумуляторов что это
Wikimedia Foundation . 2010 . Смотреть что такое "Эффект памяти аккумулятора" в других словарях: Эффект памяти — аккумулятора Эффект памяти...
Adblock detector