Счастливые билеты

Мы тут недавно с одним товарищем разговорились про точное количество «счастливых» билетов. В ответ я вспомнил, что как-то очень давно считал их количество на Перле — тогда короткие программы я предпочитал писать на нём. В алгоритмом я не заморачивался — там простой перебор, в комментариях есть указание, что выполняется он за три секунды.

На что товарищ прислал мне ссылку на выписку из статьей о счастливых билетах журнала «Квант». Там, помимо перебора, предлагается несколько методов вычисления, в частности есть даже интеграл: Вычисление через интеграл (12.78КиБ)
Вычисление количества шестизначных счастливых билетов через интеграл

Вообще статьи интересные, умели же раньше писать! Кстати, стало интересно насколько сейчас плох старый-добрый перебор на современных мощностях и интерпретаторах. Взял код из своей заметки в блоге, на пятом Перле и ПХП7 — 0,9 и 0,5 секунды соответственно, вместе с запуском интерпретатора.

Вариант на R, который я наскорую написал по мотивам второй статьи из подборки выглядит вот так:
N <- function (n, k) {
	if (n == 1)
		ifelse(k >= 0 & k <= 9, 1, 0)
	else
		sum(sapply(0:9, function (l) N(n-1, k-l)))
}

lucky <- function (n) {
	0 -> s
	for (k in 0:999) {
		N(3, k) -> v

		if (v == 0) {
			break
		}

		s + v * v -> s
	}

	s
}

print (lucky(3))
Выполняется вместе с запуском интерпретатора за треть секунды, если кому-то интересно, чуть медленнее интеграла. Можно было бы переписать его аккуратнее — накапливать значение N, а не вычислять заново каждый раз.
19 мая 2017 13:16

Dmitry V.Abramov (imap.livejournal.com)
19 мая 2017, 22:51

С возвращением к! Или это временный всплеск?

bolknote.ru (bolknote.ru)
20 мая 2017, 08:28, ответ предназначен Dmitry V.Abramov (imap.livejournal.com):

Трудно сказать :) Как пойдёт :)

Ваше имя или адрес блога (можно OpenID):

Текст вашего комментария, не HTML:

Кому бы вы хотели ответить (или кликните на его аватару)