bolk (bolk) wrote,
bolk
bolk

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

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

На что товарищ прислал мне ссылку на выписку из статьей о счастливых билетах журнала «Квант». Там, помимо перебора, предлагается несколько методов вычисления, в частности есть даже интеграл:
Вычисление через интеграл (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))
Выполняется вместе с запуском интерпретатора за треть секунды, если кому-то интересно, чуть медленнее интеграла.

Subscribe

  • Тарелки на берегу

    В прошедшие выходные мы с приятелем собрались в импровизированный поход на один из островов на Волге — порыбачить и отдохнуть. К сожалению…

  • «Ночной пылесос»

    Дочка, как наверное вообще все дети, не очень-то любит убираться в своей комнате. И чтобы заставить её перед сном навести хотя бы косметический…

  • Ортопедические стельки

    В своих поисках того как можно облегчить состояние травмированной когда-то на спортивной гимнастике спине, забрёл к ортопеду. Я подозревал, что…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments