Счастливые билетики до 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 года, прошу камнями не бросать.
Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 19

    +18
    Википедия говорит, что есть формула для вычисления в явном виде:
    image
      +4
      Хорошо подходит для юнит-тестов :)
      +2
      Расскажите, взяли ли в итоге на работу )

      *Увидев такую задачу на собеседовании, я наверно решил бы, раз уж речь идёт про nodejs, что гуглить формулу или пользоваться реализацией алгоритма на предрассчитанной таблице это не то, что требуется, и реализовал примитивное распределение задачи на нескольких нодах. Интересно что хотел работодатель.
        +3
        нет… не взяли…
        Посчитать количество счастливых билетиков для 2, 4, 6, 8 и 10 цифрового значения.

        то есть перестарался, нужно было ТОЛЬКО для вариантов 2, 4, 6, 8 и 10, а скорость — да пофиг. Даже рад, что не взяли )
        А теперь еще одна фирма предлагает работу и опять эта же задача (заразились, наверное), только уже на пхп (подумываю скинуть ссылку сюда, а чего мелочиться?)))
        +3
        То есть сумма 10 элементов в предыдущего столбца, у которых индекс <= нужному значению.
        Запрогать заполнение таблицы по алгоритму — несложно. Было бы интереснее узнать на пальцах, как он был выведен и почему работает именно так.
          +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, имеем основание для нашей рекуррентной формулы.

          Надеюсь, нигде не ошибся.
            +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.
              0
              www.ega-math.narod.ru/Quant/Tickets.htm
              (упоминалось, там и детали и интересные рассказы =) )
              +1
              Хм. Мы на одном хакатоне делали игрушку, в которой игроку нужно было угадывать, является ли билет счастливым или нет. Если хотите, могу расписать то, каким образом мы выравнивали вероятность выпадения счастливых и несчастливых билетов, чтобы добиться исхода 50 на 50. Там был пусть и бесполезный (перебирать в ожидании счастливого было бы дешевле для шестизначных чисел), но довольно прикольный алгоритм. Хотя, скорее всего, далёкий от совершенства, поскольку алгоритмы — не сильная моя сторона.
                0
                Монте-Карло? Выкидывать рандомные билетики пока не выпадет счастливый или rand(0,1) не станет меньше 0.055252/(1-0.055252)
                  0
                  Нет. Всё хитрее и всегда требует ровно 3 рандомизации (можно, вроде, ужать в одну, мне просто лень было, и я этим особо не заморачивался). В общем, пожалуй опишу всё это дело.
                0
                Совсем не давно я на вебинаре со своими учениками рассматривал как-раз такой способ решения задачи про счастливые билеты, с использованием Динамического программирования. Если кому-то интерсно подробное объяснение способа решения этой задачи, см. видео (с 7-ой минуты): https://www.youtube.com/watch?v=n2uT2sUUgmI
                  0
                  Ещё раз повторюсь со ссылкой на видео, выше неверно её разместил.

                  Смотреть с 7-ой минуты.
                  0
                  Вчерашняя задача на 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
                  (интересно, правда ли это)
                    0
                    О какой задаче на Project Euler идет речь? Благодарю.
                      0
                      528 — Constrained Sums
                      0
                      C532 — 6 C522 + 15 C512 = 55252 — это коэффициент перед x27 в разложении на множители выражения
                      (1+x2+x3+x4+...+x9)6.
                      И этот коэффициент равен количеству счастливых билетов.

                      Здесь первое слагаемое — количество наборов из 6 неотрицательных чисел с суммой 27

                      О каких числах идет речь? 0,1,2,..., 27?

                      Я вычислил коэффициент перед x27 в разложении

                      (1+x2+x3+x4+...+x27)6

                      У меня получилось 201 376, что равно C532. Но как это доказать не понимаю.

                      Благодарю.
                        0
                        Слагаемое +x потеряли. Но неважно.
                        Коэффициент при x^27 — число способов, которыми мы выбираем мономы из 6 множителей. Сумма их степеней равна 27. Задачу свели к исходной :)
                        Чтобы найти количество разложений, сделаем так. Возьмём строчку из 32 точек, и заменим 5 из них на звёздочки. Строчка разделится на 6 частей длиной от 0 до 27, сумма которых равна 27. Очевидно, что каждому разложению числа 27 на 6 слагаемых будет соответствовать свой набор звёздочек и наоборот. Отсюда и C532.
                          0
                          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.

                    Only users with full accounts can post comments. Log in, please.