Посчитать количество счастливых билетиков для 2, 4, 6, 8 и 10 цифрового значения.
Уверен, многие уже не раз делали эту банальную задачку, но, как правило, для 6-ти цифр (для тех, кто не понимает о чем пойдет речь).
Банальное решение:
var
sum = function(num){ // функция для получения суммы цифр
var
str = num.toString(),
arr = str.split(''),
s = 0;
arr.forEach(function(value){ s+=parseInt(value); });
return s;
},
luckyTickets = function(len){
var
lenMiddle = len/2,
maxSize = Math.pow(10,lenMiddle),
result = 0;
for(var i=0;i<maxSize;i++)
for(j=0;j<maxSize;j++)
if( sum(i) == sum(j) ) result++;
return result;
};
console.log( luckyTickets(8) ); // 4 816 030
Также можно посмотреть тут.
А если цифр 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 элементов предыдущего столбца, у которых индекс <= нужному значению. Количество счастливых билетов равно сумме каждого значения в квадрате в определенном столбце:
— для n=1 (2 цифры) -> 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;
Дальше наш ход.
var
getNextArr = function(prevArr){ // функция для построения следующего массива из предыдущего
var
newLen = prevArr.length + 9, // длинна следующего массива будет больше на 9
arr = []; // заготовка результата
for(var i=0; i<newLen; i++){
var q = 0; // заготовка нового значения
for(j=0; j<10; j++) // берем 10 нужных значений
if(prevArr[i-j]) // ...если они существуют в предыдущем массиве
q+=prevArr[i-j]; // добавляем
arr[i] = q; // или arr.push(q);
}
return arr;
},
luckyTickets = function(num){ // собственно сам счетчик
var
arr = [], // первый массив
result = 0; // то, что мы вернем
for(i=0;i<10;i++) arr.push(1); // впихиваем в первый массив 10 единиц
for(i=0;i<(num/2-1);i++) // нужное количество раз
arr = getNextArr(arr); // строим следующие массивы
arr.forEach(function(v){ result+=Math.pow(v,2); }); // сводим квадраты значений в получившемся массиве
return result;
};
Ну и проверить же нужно:
console.log( luckyTickets(300) ); // 8.014950093120178e+297 **
Собственно то, к чему все велось: время выполнения 106 ms (!!!), страшно представить, что бы случилось при использовании банального способа.
* все JavaScript-ы проверял на Node.js (x32)
** максимальная длинна номера билета — 310, Больше? — результат переходит в область Infinity.
*** это моя первая статья на Хабре за последние 3 года, прошу камнями не бросать.
Комментарии (14)
NiPh
09.09.2015 11:50+2Расскажите, взяли ли в итоге на работу )
*Увидев такую задачу на собеседовании, я наверно решил бы, раз уж речь идёт про nodejs, что гуглить формулу или пользоваться реализацией алгоритма на предрассчитанной таблице это не то, что требуется, и реализовал примитивное распределение задачи на нескольких нодах. Интересно что хотел работодатель.
zumers
09.09.2015 15:58+3нет… не взяли…
Посчитать количество счастливых билетиков для 2, 4, 6, 8 и 10 цифрового значения.
то есть перестарался, нужно было ТОЛЬКО для вариантов 2, 4, 6, 8 и 10, а скорость — да пофиг. Даже рад, что не взяли )
А теперь еще одна фирма предлагает работу и опять эта же задача (заразились, наверное), только уже на пхп (подумываю скинуть ссылку сюда, а чего мелочиться?)))
impwx
09.09.2015 11:51+3То есть сумма 10 элементов в предыдущего столбца, у которых индекс <= нужному значению.
Запрогать заполнение таблицы по алгоритму — несложно. Было бы интереснее узнать на пальцах, как он был выведен и почему работает именно так.
roman_kashitsyn
09.09.2015 12:51+2Было бы интереснее узнать на пальцах, как он был выведен и почему работает именно так.
Честно говоря, я не особо разбирался в подходе автора, но задачку бы решал, используя динамическое программирование.
Выразим частичное решение в виде 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, имеем основание для нашей рекуррентной формулы.
Надеюсь, нигде не ошибся.
wataru
09.09.2015 12:56+3Этот алгоритм — динамическое программирование. В таблице в 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.
zumers
09.09.2015 16:59www.ega-math.narod.ru/Quant/Tickets.htm
(упоминалось, там и детали и интересные рассказы =) )
uthunderbird
09.09.2015 13:24+1Хм. Мы на одном хакатоне делали игрушку, в которой игроку нужно было угадывать, является ли билет счастливым или нет. Если хотите, могу расписать то, каким образом мы выравнивали вероятность выпадения счастливых и несчастливых билетов, чтобы добиться исхода 50 на 50. Там был пусть и бесполезный (перебирать в ожидании счастливого было бы дешевле для шестизначных чисел), но довольно прикольный алгоритм. Хотя, скорее всего, далёкий от совершенства, поскольку алгоритмы — не сильная моя сторона.
p53
09.09.2015 20:20Монте-Карло? Выкидывать рандомные билетики пока не выпадет счастливый или rand(0,1) не станет меньше 0.055252/(1-0.055252)
uthunderbird
14.09.2015 11:31Нет. Всё хитрее и всегда требует ровно 3 рандомизации (можно, вроде, ужать в одну, мне просто лень было, и я этим особо не заморачивался). В общем, пожалуй опишу всё это дело.
FFormula
11.09.2015 09:25Совсем не давно я на вебинаре со своими учениками рассматривал как-раз такой способ решения задачи про счастливые билеты, с использованием Динамического программирования. Если кому-то интерсно подробное объяснение способа решения этой задачи, см. видео (с 7-ой минуты): https://www.youtube.com/watch?v=n2uT2sUUgmI
FFormula
11.09.2015 14:09Ещё раз повторюсь со ссылкой на видео, выше неверно её разместил.
Смотреть с 7-ой минуты.
Mrrl
04.10.2015 07:24Вчерашняя задача на 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
(интересно, правда ли это)
Sadler
Википедия говорит, что есть формула для вычисления в явном виде:
excoder
Хорошо подходит для юнит-тестов :)