Счастливые билеты
Написал небольшую програмку на 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";
По-моему проще вычислить все это «руками» с помощью производящих ф-ий. (Если не ошибаюсь, там используются so-called «многочлены Лорана»). У Вас же математическое образование, или мне показалось?
Комментарий для DiZzy:
Проще написать четыре строки на Perl и подождать 3 секунды. Нет? Каждый иструмент следует применять в подходящем месте.
А на PHP это как?
Комментарий для Nefrot:
А что тут сложного?
<code>
set_time_limit(0);
for ($c = $i = 0; $i<1000000; $i++)
{
$a = str_pad($i, 6, ’0’, STR_PAD_LEFT);
if ($a[0]+$a[1]+$a[2] == $a[3]+$a[4]+$a[5]) $c++;
}
echo $c;
</code>
Знаем-знаем эту задачку. А ты попробуй узнать это дело не для n=3, а для билетов с номером произвольной длины.
На моей памяти это самая популярная задачка была для олимпиад, её и в «Кванте» разбирали. Правда, мой вариант был эффективнее, но я всё равно его не помню. Помню только, что очки за задание пришлось выбивать на апелляции, т. к. проверяющие нифига в программе не поняли.
Ещё помню, что для 40 или 50-значных билетов у меня это на Ямахе-MSX работало секунд 10, а прямой перебор работал бы до тех пор, пока во вселенной не погасли бы все звёзды.
Комментарий для cax:
Да понятно всё с прямым перебором, но зачем тратить время, если мощность компьютера (который загружен дай бог на 10%), позволяет сделать перебор?
А скажи мне, уважаемый товарищ, как часто у вас в Казани вручают пассажирам билеты с номером «000000»?
Комментарий для мфд:
Ни разу не видел. А что, это говорит о том, что таких нет? Возможно он достаётся тем, кто едет в 5 утра.
Sorry за прошлый пост. мфд == val, конечно
Спасибо Болку за то, что напоминает любимые школьные задачки.
Но есть одна претензия по поводу реализации. Пример на пхп работает у меня порядка 35-40 секунд на в2к пхп, на редхате хостинговом — 15 секунд.
Предлагаемый нижу код справляется с задачей соответственно за 0,7 сек (локальный пхп) и 0,4-0,5 на редхате.
$count = -1; //000000 is unhappy
for ($a=0;$a=0)&&($f
Комментарий для val:
Дык я же не говорил о эффективной по времени работы реализации. Я создал такую, которая отняла у меня минимум сил, остальное сделала машина, пока я занимался другими делами. Это — эффективное решения, с точки зрения расхода моего времени.
Как говорил мой наставник по программированию: \«не создавайте сущность буз потребности\». Вы же не кондуктор, чтобы всю ленту перематывать в поиске счастливых номеров, а программист.
Комментарий для val:
Я умею программировать, но, кроме того, у меня очень мало времени, поэтому я решил задачу как решил :)
Лучше скажи сколько билетов «складываются» в сотню. И сколькими способами.
Например:
билет: 564891
одно решение: (-5+6)^4+8+91=100
Часто такой фигнёй занимаюсь в транспорте, ежели далеко ехать. Практически всегда складывается, как ни странно, одно время как-то даже собирали «нескладные».
Комментарий для kbept:
Вот и скажи. :) Мне-то неинтересно. Сделать можно всё.
kbept
это задачки для интеллектуалов:)
а вот сделать алгоритм, корторый бы это делал, наверное, интересно
kbept:
я такие алгоритмы писал в 10 классе на паскале.
рекурсия. аккуратная рекурсия и ничего более.
2bolk:
100%. Я преклоняюсь перед программистом Bolkом. На мой взгляд вы не просто умеете программировать, а умеете программировать чертовски здорово.
Комментарий для val:
Спасибо :)
Кстати, получается красивая картинка:
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:
Что-то в этом есть, да :)
<code>
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
<code> 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);</code>