Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 19
Википедия говорит, что есть формула для вычисления в явном виде:
Расскажите, взяли ли в итоге на работу )
*Увидев такую задачу на собеседовании, я наверно решил бы, раз уж речь идёт про nodejs, что гуглить формулу или пользоваться реализацией алгоритма на предрассчитанной таблице это не то, что требуется, и реализовал примитивное распределение задачи на нескольких нодах. Интересно что хотел работодатель.
*Увидев такую задачу на собеседовании, я наверно решил бы, раз уж речь идёт про nodejs, что гуглить формулу или пользоваться реализацией алгоритма на предрассчитанной таблице это не то, что требуется, и реализовал примитивное распределение задачи на нескольких нодах. Интересно что хотел работодатель.
нет… не взяли…
то есть перестарался, нужно было ТОЛЬКО для вариантов 2, 4, 6, 8 и 10, а скорость — да пофиг. Даже рад, что не взяли )
А теперь еще одна фирма предлагает работу и опять эта же задача (заразились, наверное), только уже на пхп (подумываю скинуть ссылку сюда, а чего мелочиться?)))
Посчитать количество счастливых билетиков для 2, 4, 6, 8 и 10 цифрового значения.
то есть перестарался, нужно было ТОЛЬКО для вариантов 2, 4, 6, 8 и 10, а скорость — да пофиг. Даже рад, что не взяли )
А теперь еще одна фирма предлагает работу и опять эта же задача (заразились, наверное), только уже на пхп (подумываю скинуть ссылку сюда, а чего мелочиться?)))
То есть сумма 10 элементов в предыдущего столбца, у которых индекс <= нужному значению.Запрогать заполнение таблицы по алгоритму — несложно. Было бы интереснее узнать на пальцах, как он был выведен и почему работает именно так.
Было бы интереснее узнать на пальцах, как он был выведен и почему работает именно так.
Честно говоря, я не особо разбирался в подходе автора, но задачку бы решал, используя динамическое программирование.
Выразим частичное решение в виде M(n, k) — число сочетаний из n цифр, дающих в сумме k (похоже, именно она приведена в тексте поста). Предположим, мы знаем ответ для задачи размера n — 1. Найдём решение для задачи размера n.
Половина билетика выглядит следующим образом:
[n - 1 цифра] d
Нам нужно найти все такие d, что новая сумма равна k.
M(n, k) = [Sum; 0 <= d <= 9; M(n - 1, k - d)]
Далее нужно заметить, что верхняя граница для k всегда ограничена сверху 9 * n, и ответ
S(n) = [Sum; 0 <= k <= 9*n; M(n, k) * M(n, k)]
M(n, k) возводим в квадрат потому, что одна и таже сумма встречается в двух половинках билета.
Зная, что M(1, k) = 1 для 0 <= k <= 9, имеем основание для нашей рекуррентной формулы.
Надеюсь, нигде не ошибся.
Этот алгоритм — динамическое программирование. В таблице в 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.
Отсюда же понятно, почему количество всех счастливых билетов — сумма квадратов чисел в столбце. Каждый билет составлен из двух половинок, половинки должны иметь одинаковую сумму. Квадраты получается потому, что можно взять любое число длины n с заданной суммой и в левую и в правую половину счастливого билета, поэтому f(k,n)*f(k,n) и будет количество счастливых билетов длины 2n с суммой в каждой половине k. Теперь остается только просуммировать по всем k.
www.ega-math.narod.ru/Quant/Tickets.htm
(упоминалось, там и детали и интересные рассказы =) )
(упоминалось, там и детали и интересные рассказы =) )
Хм. Мы на одном хакатоне делали игрушку, в которой игроку нужно было угадывать, является ли билет счастливым или нет. Если хотите, могу расписать то, каким образом мы выравнивали вероятность выпадения счастливых и несчастливых билетов, чтобы добиться исхода 50 на 50. Там был пусть и бесполезный (перебирать в ожидании счастливого было бы дешевле для шестизначных чисел), но довольно прикольный алгоритм. Хотя, скорее всего, далёкий от совершенства, поскольку алгоритмы — не сильная моя сторона.
Совсем не давно я на вебинаре со своими учениками рассматривал как-раз такой способ решения задачи про счастливые билеты, с использованием Динамического программирования. Если кому-то интерсно подробное объяснение способа решения этой задачи, см. видео (с 7-ой минуты): https://www.youtube.com/watch?v=n2uT2sUUgmI
Вчерашняя задача на Project Euler показала ещё один способ посчитать счастливые билеты — без перебора и динамики.
Для 6-значных билетов по основанию 10 число билетов равно
C532 — 6 C522 + 15 C512 = 55252.
Здесь первое слагаемое — количество наборов из 6 неотрицательных чисел с суммой 27. Потом из него вычитаются наборы, в которых сумма 27, но одна из цифр больше 9, а потом — прибавляются наборы, в которых две цифры больше 9 — мы их вычли дважды (это метод включения — исключения).
При большом числе знаков от формулы мало толку, зато она поможет для очень больших систем счисления.
Например, число 10-значных счастливых билетов в системе счисления по основанию N=1012 равно
C95N+4 — 10 C94N+4 + 45 C93N+4 — 120 C92N+4 + 210 C9N+4 = 430417768959435626102292971505731922398589065255874862213403880070546737326388888888888888888889000000000000
(интересно, правда ли это)
Для 6-значных билетов по основанию 10 число билетов равно
C532 — 6 C522 + 15 C512 = 55252.
Здесь первое слагаемое — количество наборов из 6 неотрицательных чисел с суммой 27. Потом из него вычитаются наборы, в которых сумма 27, но одна из цифр больше 9, а потом — прибавляются наборы, в которых две цифры больше 9 — мы их вычли дважды (это метод включения — исключения).
При большом числе знаков от формулы мало толку, зато она поможет для очень больших систем счисления.
Например, число 10-значных счастливых билетов в системе счисления по основанию N=1012 равно
C95N+4 — 10 C94N+4 + 45 C93N+4 — 120 C92N+4 + 210 C9N+4 = 430417768959435626102292971505731922398589065255874862213403880070546737326388888888888888888889000000000000
(интересно, правда ли это)
О какой задаче на Project Euler идет речь? Благодарю.
C532 — 6 C522 + 15 C512 = 55252 — это коэффициент перед x27 в разложении на множители выражения
(1+x2+x3+x4+...+x9)6.
И этот коэффициент равен количеству счастливых билетов.
О каких числах идет речь? 0,1,2,..., 27?
Я вычислил коэффициент перед x27 в разложении
(1+x2+x3+x4+...+x27)6
У меня получилось 201 376, что равно C532. Но как это доказать не понимаю.
Благодарю.
(1+x2+x3+x4+...+x9)6.
И этот коэффициент равен количеству счастливых билетов.
Здесь первое слагаемое — количество наборов из 6 неотрицательных чисел с суммой 27
О каких числах идет речь? 0,1,2,..., 27?
Я вычислил коэффициент перед x27 в разложении
(1+x2+x3+x4+...+x27)6
У меня получилось 201 376, что равно C532. Но как это доказать не понимаю.
Благодарю.
Слагаемое +x потеряли. Но неважно.
Коэффициент при x^27 — число способов, которыми мы выбираем мономы из 6 множителей. Сумма их степеней равна 27. Задачу свели к исходной :)
Чтобы найти количество разложений, сделаем так. Возьмём строчку из 32 точек, и заменим 5 из них на звёздочки. Строчка разделится на 6 частей длиной от 0 до 27, сумма которых равна 27. Очевидно, что каждому разложению числа 27 на 6 слагаемых будет соответствовать свой набор звёздочек и наоборот. Отсюда и C532.
Коэффициент при x^27 — число способов, которыми мы выбираем мономы из 6 множителей. Сумма их степеней равна 27. Задачу свели к исходной :)
Чтобы найти количество разложений, сделаем так. Возьмём строчку из 32 точек, и заменим 5 из них на звёздочки. Строчка разделится на 6 частей длиной от 0 до 27, сумма которых равна 27. Очевидно, что каждому разложению числа 27 на 6 слагаемых будет соответствовать свой набор звёздочек и наоборот. Отсюда и C532.
C формулой стало понятно. Есть 27 предметов, их надо разместить в 6 ящиках.
В разложении на множители (1+x+x2+x3+..+x9)n коэффициенты перед 1,x,x2,...,x9 вычисляются по формуле
Cn-1i+n-1, где i меняется от 0 до 9. Если выписать первые члены то получим 1,n, n*(n+1)/2!,n*(n+1)(n+2)/3!…
Для предельного случая, когда старшая степень x в скобках равна бесконечности, получаем выражения коэффициентов разложения функции 1/(1-x)n.
В разложении на множители (1+x+x2+x3+..+x9)n коэффициенты перед 1,x,x2,...,x9 вычисляются по формуле
Cn-1i+n-1, где i меняется от 0 до 9. Если выписать первые члены то получим 1,n, n*(n+1)/2!,n*(n+1)(n+2)/3!…
Для предельного случая, когда старшая степень x в скобках равна бесконечности, получаем выражения коэффициентов разложения функции 1/(1-x)n.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Счастливые билетики до 300 цифр