[Из песочницы] Счастливые билетики до 300 цифр
Началось все с тестового задания на вакансию «js-developer, Node.js-developer», и тут я выпал в осадок: задача на счастливые билетики.
Посчитать количество счастливых билетиков для 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
Также можно посмотреть тут.
А если цифр 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
Ну и проверить же нужно:
console.log( luckyTickets(300) ); // 8.014950093120178e+297 **
Собственно то, к чему все велось: время выполнения 106 ms (!!!), страшно представить, что бы случилось при использовании банального способа.
* все JavaScript-ы проверял на Node.js (x32)
** максимальная длинна номера билета — 310, Больше? — результат переходит в область Infinity.
*** это моя первая статья на Хабре за последние 3 года, прошу камнями не бросать.
