[Из песочницы] Счастливые билетики до 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<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 года, прошу камнями не бросать.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.