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

Написал небольшую програмку на Perl для подсчёта количества счастливых билетов в последовательности от 000000 до 999999. Их оказалось 55252.
for (0...999999)
{
    $a = ('0' x (6-length $_)) . $_;
    $c++ if substr($a, 0, 1)+substr($a, 1, 1)+substr($a, 2, 1) ==
            substr($a, 3, 1)+substr($a, 4, 1)+substr($a, 5, 1);
}
print "$c\n";

Комментарии 22

DiZzy № 1
По-моему проще вычислить все это «руками» с помощью производящих ф-ий. (Если не ошибаюсь, там используются so-called «многочлены Лорана»). У Вас же математическое образование, или мне показалось?
Евгений Степанищев автор № 2
Проще написать четыре строки на Perl и подождать 3 секунды. Нет? Каждый иструмент следует применять в подходящем месте.
cax № 5
Знаем-знаем эту задачку. А ты попробуй узнать это дело не для n=3, а для билетов с номером произвольной длины.

На моей памяти это самая популярная задачка была для олимпиад, её и в «Кванте» разбирали. Правда, мой вариант был эффективнее, но я всё равно его не помню. Помню только, что очки за задание пришлось выбивать на апелляции, т.к. проверяющие нифига в программе не поняли.

Ещё помню, что для 40 или 50-значных билетов у меня это на Ямахе-MSX работало секунд 10, а прямой перебор работал бы до тех пор, пока во вселенной не погасли бы все звёзды.
Евгений Степанищев автор № 6
Да понятно всё с прямым перебором, но зачем тратить время, если мощность компьютера (который загружен дай бог на 10%), позволяет сделать перебор?
мфд № 7
>for (0…999999)

А скажи мне, уважаемый товарищ, как часто у вас в Казани вручают пассажирам билеты с номером «000000»?
Евгений Степанищев автор № 8
Ни разу не видел. А что, это говорит о том, что таких нет? Возможно он достаётся тем, кто едет в 5 утра.
val № 9
Sorry за прошлый пост. мфд == val, конечно

Спасибо Болку за то, что напоминает любимые школьные задачки.

Но есть одна претензия по поводу реализации. Пример на пхп работает у меня порядка 35-40 секунд на в2к пхп, на редхате хостинговом — 15 секунд.

Предлагаемый нижу код справляется с задачей соответственно за 0,7 сек (локальный пхп) и 0,4-0,5 на редхате.

$count = -1; //000000 is unhappy

for ($a=0;$a=0)&&($f
Евгений Степанищев автор № 10
Дык я же не говорил о эффективной по времени работы реализации. Я создал такую, которая отняла у меня минимум сил, остальное сделала машина, пока я занимался другими делами. Это — эффективное решения, с точки зрения расхода моего времени.
val № 11
Как говорил мой наставник по программированию: \"не создавайте сущность буз потребности\". Вы же не кондуктор, чтобы всю ленту перематывать в поиске счастливых номеров, а программист.
Евгений Степанищев автор № 12
Я умею программировать, но, кроме того, у меня очень мало времени, поэтому я решил задачу как решил :)
val № 17
2bolk:
>Я умею программировать, но, кроме того, у меня очень мало времени, поэтому я решил задачу как решил :)

100%. Я преклоняюсь перед программистом Bolkом. На мой взгляд вы не просто умеете программировать, а умеете программировать чертовски здорово.
kbept № 13
Лучше скажи сколько билетов «складываются» в сотню. И сколькими способами.
Например:
билет: 564891
одно решение: (-5+6)^4+8+91=100

Часто такой фигнёй занимаюсь в транспорте, ежели далеко ехать. Практически всегда складывается, как ни странно, одно время как-то даже собирали «нескладные».
tomato № 15
kbept
это задачки для интеллектуалов:)
а вот сделать алгоритм, корторый бы это делал, наверное, интересно
val № 16
kbept:

я такие алгоритмы писал в 10 классе на паскале.

рекурсия. аккуратная рекурсия и ничего более.
kbept № 19
Кстати, получается красивая картинка:
set_time_limit(0);
header («Content-type: image/png»);
$im = @imagecreate (100, 100);
$bgcolor = imagecolorallocate ($im, 255, 255, 255);
$color = imagecolorallocate ($im, 0, 0, 0);

for ($i = 0; $i
kbept № 21
set_time_limit(0);
header («Content-type: image/png»);
$im = @imagecreate (100, 100);
$bgcolor = imagecolorallocate ($im, 255, 255, 255);
$color = imagecolorallocate ($im, 0, 0, 0);

for ($i = 0; $i
kbept № 22
set_time_limit(0);
header («Content-type: image/png»);
$im = @imagecreate (100, 100);
$bgcolor = imagecolorallocate ($im, 255, 255, 255);
$color = imagecolorallocate ($im, 0, 0, 0);

for ($i = 0; $i<1000; $i++) {
for ($j = 0; $j<1000; $j++) {
$a = str_pad($i, 3, '0', STR_PAD_LEFT);
$b = str_pad($j, 3, '0', STR_PAD_LEFT);
if ($a[0]+$a[1]+$a[2] == $b[0]+$b[1]+$b[2]) {
imagesetpixel ($im, $i, $j, $color);
}
}
}

imagepng ($im);