Задача вычисления количества счастливых билетов известна давно. Ее задавали практически любому школьнику, обучающемуся программированию. В интернете можно найти множество ее решений на разных языках программирования. Все эти варианты сводятся к перебору всех существующих билетов и проверке их на «счастливость». Получается миллион вариантов.
Но данную задачу можно решить и другим способом, перебрав всего тысячу вариантов.
Напомню, что счастливыми являются билеты, сумма первых трёх цифр номера которых равна сумме последних трёх цифр номера. Например, билет с номером «546780» является счастливым, так как сумма первых трёх цифр (5+4+6) равна сумме последних трёх цифр (7+8+0). Задача состоит в определении того, сколько всего существует счастливых билетов.
Во всех примерах она решается в лоб, но что если пойти иным путем? Вначале ответим на другой вопрос. Сколько существует различных комбинаций трех цифр (троек), которые в сумме дают n ? Для ответа на этот вопрос нужно перебрать все возможные тройки (тысяча вариантов).
Сумма любых троек находится между нулем (0+0+0) и 27 (9+9+9). Поэтому можно подготовить массив сумм:
{n _0 , n _1 , n _2 , n _3 , …., n _25 , n _26 , n _27 }
где n _ i – количество троек, дающих в сумме i . При этом сумма цифр равна индексу этого элемента в массиве.
Хорошо, мы подготовим такой массив, но как это связано с билетами? Рассмотрим частный случай. Всего существует n _25 троек, дающих в сумме 25. Для каждой такой тройки существует n _25 троек, при объединении с каждой из которых будет получаться счастливый номер. Поэтому существует n _25 *n _25 счастливых билетов, сумма первых трёх цифр которых равна 25. Аналогично и для других сумм. Таким образом, общее количество счастливых билетов равно:
n _0 *n _0 + n _1 *n _1 + …. + n _26 *n _26 + n _27 *n _27
Ниже приводится полный исходный код приложения, реализующего данный алгоритм.
#include
Код хорошо прокомментирован, поэтому вопросы возникнуть не должны.
Если посмотреть на массив сумм, то можно сделать два наблюдения.
1. Он симметричен:
n_13 = n_14 ,
n_12 = n_15 ,
n_11 = n_16 ,
n_10 = n_17 ,
………………
n _1 = n _26 ,
n _0 = n _27 .
2. Больше всего существует билетов, сумма первых трёх цифр которых равна 13 и 14 (их по 75).
Массив сумм из 28 элементов подготавливается за один проход перебора троек. Поэтому для подсчета количества счастливых билетов достаточно перебрать 1000 вариантов.
О том, что такое "счастливый билет" - прекрасно знают большинство студентов. Да и школьники частенько тоже. Правда, какие именно они бывают и что с ними делать - здесь мнения чаще всего расходятся.
Прежде всего, "счастливым по-студенчески"
считается билет, ответы на который ты знаешь. Тут даже и к бабке не ходи - повезло тебе на экзамене, вытянул счастливый билет и сдал с первого раза, хоть из ста вопросов только эти два и выучить-то успел. Да так бойко отвечал, что уставший от "бе-каний и ме-каний" преподаватель даже слушать тебя до конца не стал - отправил с пятёркой в зачётке и с наставлениями остающимся: "Вот! Смотрите и учитесь, как надо сдавать предмет! Берите пример с этого хорошего человека!"
Вот это я понимаю, - "счастливый билет"
!
Но бывают билеты, они же - талоны на проезд, которые считаются либо счастливыми, либо красивыми. Второе - крайне редко. Чаще всего их называют именно "счастливый"! Какие же билеты считаются таковыми?
Во-первых, и это крайне-редкий случай, счастливым считается билет, цифры номера которого одинаковы или расположены симметрично.
Например: 555555
или 252252
. Тут полная симметрия.
Но бывает симметрия неполная или зеркальная. Например так: 251251
- числа здесь расположены симметрично, а вот цифры - нет.
В любом случае, вышеприведённые примеры - это действительно "счастливые"
билеты. Много ли их встречается? Ну, думаю, вы без труда сосчитаете, что очень и очень мало - тысяча на миллион, или каждый тысячный билет. Вероятность попадания такого билета в руки пассажира крайне мала. Мне за мою жизнь пока что выпало всего два таких билетика, хоть езжу в общественном транспорте я довольно часто,
А счастья-то хочется? Поэтому, изворотливыми и догадливыми пассажирами в скуке пути тут же были придуманы другие варианты "счастья". Например, просто одинаковые цифры в номере, расположенные в произвольном порядке: 251521
, например. Симметрии здесь и нет, но зато все цифры присутствуют. Дальше - больше. Счастливым стал считаться билетик, сумма троек цифр которых одинакова. Например, 474195:
4+7+4=15= 1+9+5
1. Примеры билетов, "счастливых по сумме" :
Опять же всем известно, что подобные билеты встречаются хоть и не каждый день, но всё-таки довольно часто. Примерно каждый 18-й билет - "счастливый по сумме". И если ездить постоянно, то встречаются они хотя бы раз в неделю. Как-то я провёл небольшой эксперимент: не выкидывал, а складывал эти билетики в карман сумки, чтобы сосчитать в конце месяца. Давно это было, не помню уже сколько точно, но в месяц у меня их тогда собралось не менее десяти штук. Учитывая, что муниципальным транспортом я езжу в среднем два-три раза в день (остальное время - маршрутки, а там у нас билетов почему-то выдавать не принято), получается, что каждая 6-9 поездка "вознаграждается" вот таким вот нехитрым счастьем. Ну, или один билетик в три дня. Но это, видать, у меня просто удачный месяц попался, потому что каждый 18-й билет должен попадаться как бы пореже.
И действительно, бывают времена, когда за месяц и ни одного не попадётся. Так что же делать? А голь на выдумки хитра. Например, есть билеты, "счастливые по-московски"
(они же - "по-ленинградски"
) - это когда считаются не тройки цифр, а их пары. Например, сумма каждого чётного числа с нечётными: 63
49
86
.
Здесь:
3+9+6= 18= 6+4+8
А как вы думаете, можно ли помимо сложения, применять операцию вычитания ? Конечно же можно! Главное, определиться для себя, как вычитать - по порядку или от большего к меньшему: 720821 . Здесь:
7-2-0=5= 8-2-1
Но... не принято у нас как-то "вычитать счастье". Лучше, когда его прибавляют или даже умножают!
Поэтому я придумал для себя ещё один вид счастливых билетов: "счастливый по умножению"!
Достаточно перемножить цифры в тройках, чтобы получить себе дополнительный "умножительный"
заряд бодрости. Например: 338924.
Здесь:
3*3*8=72= 9*2*4
Пользуйтесь на здоровье! А то что же вы всё суммируете да суммируете... Умножать тоже можно!
Upd: Более того, можно не просто умножать! Вот, в комментариях docbrowns заметил, что можно ещё и в степень возводить! Например 261812 :
(2^6)^1 = 64 = (8^1)^2
А это ещё во много раз увеличивает как шансы "найти счастье", так и занимательность поездки.
2. Пример билета, "счастливого по умножению"
а-ля :
Если вы пользуетесь общественным транспортом, присмотритесь внимательней к пассажирам. Очень, очень часто можно заметить, как при получении билетика они начинают изучать его цифры. Каждый ищет счастья... А что же потом с ним делать? Один раз я услышал разговор двух девчонок, ехавших на зачёт: "Ух-ты! У меня счастливый билетик!" - воскликнула одна. "Съешь его! Зачёт тогда сдашь!!!" - тут же отозвалась вторая. Право, я смеялся. Уж лучше они надеялись на тот счастливый "по-студенчески"
билет, который я упомянул вначале. А ещё лучше - чтобы все полсотни билетов курса были для них счастливыми. Но... они предпочитают съесть троллейбусный, чем учить лекционные.
Ребята! Не надо есть талончики! Это совсем даже не полезно. И счастья вам не принесёт. Относитесь к счастливым билетам проще - раз он вам выпал
, значит счастье не придёт, нет - вы уже счастливый
или, проще, везучий
человек! Вот и всё. Это всего лишь повод слегка улучшить себе настроение. Не верьте в приметы - они далеко не всегда основаны на фактах, а часто ещё и вред могут принести, особенно если начнёте есть четырёхлистные цветочки с земли или бумажные талончики из вторсырья да в автобусе! Как в том анекдоте: съел счастливый билет, и тут же счастье привалило - контролёр зашёл!
Относитесь к "счастливым билетам" как к способу слегка скоротать время поездки арифметическими упражнениями, и как к дополнительному поводу порадоваться в ней.
Кстати, папам и мамам на заметку: очень полезно рассказать о подобных упражнениях детям. Они в школе не очень любят устный счёт, так пусть хоть в троллейбусах развлекаются, суммируя или умножая цифры. Да и взрослым не повредит: как подряд, так и через одно, усваивая понятия чётность, симметрия, кратность... Да и о вычитании с делением тоже можно не забывать. В любом случае, для развития ребёнка такие весёлые задачки не повредят.
А если с билетиком вам не повезло - не расстраивайтесь! По улице ездит столько автомобилей со "счастливыми номерами"!
Удачи вам, и счастья!
"Счастливый билет"
Все мы бываем в транспорте. По пути на работу, домой, к месту отдыха и
т. д. И очень часто мы покупаем проездной билет, имеющий в большинстве
случаев шестизначный номер. Сложив первые три цифры номера билета и
сравнив их с суммой второй тройки цифр мы и определяем «счастливость»
данного билета. Со «счастливым» номером все более или менее понятно и
большинству известно. А другие, отличные от нуля цифры? Ясно, что
разница цифр варьируется от 0 до 27. Так и родилась эта табличка…
Действие билета тривиально (кстати, есть его совсем не обязательно!) -
билет действует в течение суток с момента активации или до приобретения
следующего билета с ничего не значащим номером. Активация билета
происходит после сосчитывания номера и осознания его значения - так
сказать, магический ритуал.
(Примечание. Если следующий билет имеет самостоятельное значение, а
предыдущий еще не погашен - одно значение накладывается на другое. Ну,
например - вы взяли билет с разницей в цифрах = 1 = - что означает
свидание. Пересели на другой транспорт, никого знакомого не встретив -
то есть билет еще активен и не «сработал». Взяли новый билетик - а у
него разница цифр = 7 = - то есть извести. Так что или может произойти
два события, или они сольються в одно - на свидании вы еще получите
известие («Я беременна! » - шутка…). Ну и так далее. Комбинации из
последовательности трех чисел авторами не испытывались - нет больших
статистических данных при езде с тремя пересадками - редкость,
понимаете).
Данная схема определена опытным путем. Как в любом экспериментальном
деле, возможны погрешности. Присылайте ваши наблюдения и они будут
учтены в следующий раз.
Разница цифр Значение Толкование
0 Удача Какое-либо задуманное дело закончится удачно или же вам в
чем-то явно повезет.
1 Свидание Вы встретите человека, которого будете рады увидеть (встреча
личная, не по работе).
2 Встреча У вас состоится деловая встреча.
3 Повтор Что-то придется повторить, а иначе - не получится.
4 Предупреждение Будьте внимательны! Сегодня вы можете опоздать к пункту
назначения! Не расслабляйтесь и все будет успешно. Но если зазеваетесь -
опоздание гарантировано!
5 Приятность Приятная встреча или событие улучшат вам настроение!
6 Неприятность Неприятная встреча или событие могут испортить вам
настроение. Не переживайте сильно!
7 Известие Вы от кого-нибудь получите весточку!
8 Хаос Что-то сегодня не сможет срастись, состыковаться, завершиться…
9 Завершение Какое-то начатое дело сегодня закроется окончательно.
10 Начало Сегодня вы начнете новый проект или вас осенит новая мысль,
идея.
11 Прогулка Ну или пробка, или просто придется прогуляться…
12 Дюжина Возможно распитие спиртных напитков…
13 Чертова дюжина Возможно распитие спиртных напитков до непотребного
состояния…
14 Ничего не значит
15 Ничего не значит
16 Ничего не значит
17 Ничего не значит
18 Ничего не значит
19 Ничего не значит
20 Ничего не значит
21 Ничего не значит
22 Ничего не значит
23 Ничего не значит
24 Ничего не значит
25 Повтор Что-то придется повторить, а иначе - не получится.
26 Встреча У вас состоится деловая встреча.
27 Свидание Вы встретите человека, которого будете рады увидеть
(встреча личная, не по работе).
Сколько существует способов заплатить 50 центов? Мы считаем, что платить можно пенни 1 , никелями 5 , даймами 10 , четвертаками 25 и полудолларами 50 . Дьёрдь Пойа популяризовал эту задачу, продемонстрировав поучительный способ её решения с помощью производящих функций.
Запишем бесконечную сумму, представляющую все возможные способы размена. Начать проще всего со случая, когда имеется меньше разновидностей монет, поэтому положим для начала, что у нас нет никаких монет, кроме пенни. Сумму всех способов заплатить некоторое количество пенни (и только пенни) можно записать в виде
поскольку каждый вариант выплаты включает некоторое количество никелей, выбираемых из первого множителя, и некоторое количество пенни, выбираемых из P . (Заметьте, что N не равняется сумме 1 + 1 + 5 + (1 + 5 ) 2 + (1 + 5 ) 3 + ..., поскольку эта сумма включает многие виды выплат более чем по одному разу. Например, член (1 + 5 ) 2 = 1 1 + 1 5 + 5 1 + 5 5 трактует 1 5 и 5 1 , как если бы они были различными, но мы хотим перечислить все множества монет по одному разу безотносительно к их порядку.)
Аналогично, если допустить ещё и даймы, то получим бесконечную сумму
Наша задача состоит в том, чтобы найти, сколько слагаемых в C сто́ят ровно 50 центов.
Задача решается с помощью простого трюка. Заменим 1 на z , 5 на z 5 , 10 на z 10 , 25 на z 25 и 50 на z 50 . Каждое слагаемое тогда заменится на z n , где n стоимость исходного слагаемого в пенни. Например, слагаемое 50 10 5 5 1 превратится в z 50+10+5+5+1 = z 71 . Каждый из четырёх возможных способов заплатить 13 центов, а именно, 10 1 3 , 5 1 8 , 5 2 1 3 и 1 13 , сведётся к z 13 ; следовательно, коэффициентом при z 13 после z -подстановки будет 4.
Пусть P n , N n , D n , Q n и C n обозначают число способов заплатить сумму в n центов, если можно использовать монеты не старше, соответственно, 1, 5, 10, 25 и 50 центов. Наш анализ показал, что эти числа суть коэффициенты при z n в соответствующих степенных рядах
| P = | 1 + z + z 2 + z 3 + z 4 + ... , |
| N = | (1 + z 5 + z 10 + z 15 + z 20 + ...)P , |
| D = | (1 + z 10 + z 20 + z 30 + z 40 + ...)N , |
| Q = | (1 + z 25 + z 50 + z 75 + z 100 + ...)D , |
| C = | (1 + z 50 + z 100 + z 150 + z 200 + ...)Q . |
Очевидно, что P n = 1 для всех n ≥0 . По кратком размышлении легко доказать, что N n = [n /5] + 1: для того чтобы составить сумму в n центов из пенни и никелей, мы должны взять 0, или 1, или..., или [n /5] никелей, после чего останется лишь единственный способ выбрать требуемое число пенни. Итак, значения P n и N n легко вычисляются, однако с D n , Q n и C n дело обстоит гораздо сложнее.
Один из подходов к исследованию этих формул основан на замечании, что 1 + z m + z 2m + ... есть просто 1/(1 z m ). Следовательно, мы можем записать
Теперь, приравнивая коэффициенты при z n в этих уравнениях, получим рекуррентные соотношения, из которых желаемые коэффициенты легко вычисляются:
Например, коэффициент при z n в D = (1 z 25)Q равен Q n Q n 25 ; поэтому должно быть Q n Q n 25 = D n , как и записано выше.
Можно было бы раскрыть эти соотношения и выразить Q n , например, в виде Q n = D n + D n 25 + D n 50 + D n 75 + ..., где сумма обрывается, когда индексы становятся отрицательными. Однако, исходная, неитеративная форма удобна тем, что каждый коэффициент вычисляется с помощью всего одного сложения, как в треугольнике Паскаля.
Используем эти соотношения, чтобы найти C 50 . Во-первых, C 50 = C 0 + Q 50 , так что нам нужно знать Q 50 . Далее, Q 50 = Q 25 + D 50 и Q 25 = Q 0 + D 25 ; поэтому нас также интересуют D 50 и D 25 . Эти значения D n в свою очередь, зависят от D 40 , D 30 , D 20 , D 15 , D 10 и D 5 и от N 50 , N 45 , ..., N 5 . Таким образом, чтобы определить все нужные коэффициенты, достаточно выполнить простые вычисления:
| n | 0 | 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | 50 |
| P n | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| N n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| D n | 1 | 2 | 4 | 6 | 9 | 12 | 16 | 25 | 36 | ||
| Q n | 1 | 13 | 49 | ||||||||
| C n | 1 | 50 | |||||||||
В самом низу таблицы находится ответ C 50: имеется ровно 50 способов дать 50 центов «на чай».
А что можно сказать о замкнутой форме для C n ? Перемножение всех уравнений даёт нам компактное выражение для производящей функции
которая является рациональной функцией от z , знаменатель которой имеет степень 91. Таким образом, мы можем разложить знаменатель на 91 множитель и выразить C n в «замкнутом виде», состоящем из 91 слагаемого. Но такое ужасное выражение не лезет ни в какие ворота. Нельзя ли в этом частном случае найти что-либо лучшее, а не применять общий метод?
А вот и первый проблеск надежды: если в C (z ) заменить 1/(1 z ) на (1 + z + z 2 + z 3 + z 4)/(1 z 5):
то степень знаменателя «сжатой» функции Č (z ) уже только 19, так что эта функция гораздо лучше исходной. Новое выражение для C (z ) показывает, в частности, что C 5n = C 5n +1 = C 5n +2 = C 5n +3 = C 5n +4 ; и действительно, это соотношение легко объяснить: чаевые в 53 цента можно дать ровно столькими же способами, как и чаевые в 50 центов, поскольку количество пенни по модулю 5 заранее известно.
Однако даже для Č (z ) не существует простого выражения, основанного на корнях знаменателя. Вероятно, простейший способ вычисления коэффициентов Č (z ) получится, если заметить, что каждый сомножитель в знаменателе является делителем 1 z 10 . Следовательно, мы можем записать
Вот, для полноты картины, развернутое выражение для A (z ):
(1 + z
+ ... + z
9) 2 (1 + z
2 + ... + z
8)(1 + z
5) =
= 1 + 2z
+ 4z
2 + 6z
3 + 9z
4 + 13z
5 + 18z
6 + 24z
7 +
+ 31z
8 + 39z
9 + 45z
10 + 52z
11 +57z
12 + 63z
13 + 67z
14 + 69z
15 +
+ 69z
16 + 67z
17 + 63z
18 + 57z
19 + 52z
20 + 45z
21 + 39z
22 + 31z
23 +
+ 24z
24 + 18z
25 + 13z
26 + 9z
27 + 6z
28 + 4z
29 + 2z
30 + z
31 .
И, в завершение, воспользовавшись тем, что
получаем следующее выражение для коэффициентов Č n при степенях z n в разложении функции Č (z ), в котором n = 10q + r и 0≤r <1 0:
| Č 10q +r = | ∑ | A j | ( | k
+ 4 k |
) | = | ||||||||||||||||
| j
, k
10k +j =n |
||||||||||||||||||||||
| = A r | ( | q
+ 4 q |
) | + A r +10 | ( | q
+ 3 q |
) | + A r +20 | ( | q
+ 2 q |
) | + A r +30 | ( | q
+ 1 q |
) | . |
Здесь фактически содержится 10 различных случаев, по одному на каждое значение r ; но это всё же неплохая замкнутая формула в сравнении с альтернативами, включающими степени комплексных чисел.
Используя это выражение, можем узнать, например, значение C 50q = Č 10q . Здесь r =0 , и мы имеем
для суммы в 1 доллар получается
| ( | 6 4 |
) | + 45 | ( | 5 4 |
) | + 52 | ( | 4 4 |
) | = 292 способа; |
а для миллиона долларов это число составит
| ( | 2000004 4 |
) | + 45 | ( | 2000003 4 |
) | + 52 | ( | 2000002 4 |
) | + 2 | ( | 2000001 4 |
) | = |
= 66666793333412666685000001.
