Началось все с тестового задания на вакансию «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<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 года, прошу камнями не бросать.
ссылка на оригинал статьи http://habrahabr.ru/post/266479/
Добавить комментарий