Это сайт — моя персональная записная книжка. Интересна мне, по большей части, история, своя жизнь и немного программирование.

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

Написал небольшую програмку на 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";
Ctrl →Win ADOM
22 комментария
DiZzy 2003

По-моему проще вычислить все это «руками» с помощью производящих ф-ий. (Если не ошибаюсь, там используются so-called «многочлены Лорана»). У Вас же математическое образование, или мне показалось?

Евгений Степанищев (bolknote.ru) 2003

Комментарий для DiZzy:

Проще написать четыре строки на Perl и подождать 3 секунды. Нет? Каждый иструмент следует применять в подходящем месте.

Nefrot 2003

А на PHP это как?

Евгений Степанищев (bolknote.ru) 2003

Комментарий для 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>

cax 2003

Знаем-знаем эту задачку. А ты попробуй узнать это дело не для n=3, а для билетов с номером произвольной длины.

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

Ещё помню, что для 40 или 50-значных билетов у меня это на Ямахе-MSX работало секунд 10, а прямой перебор работал бы до тех пор, пока во вселенной не погасли бы все звёзды.

Евгений Степанищев (bolknote.ru) 2003

Комментарий для cax:

Да понятно всё с прямым перебором, но зачем тратить время, если мощность компьютера (который загружен дай бог на 10%), позволяет сделать перебор?

мфд 2003

for (0…999999)

А скажи мне, уважаемый товарищ, как часто у вас в Казани вручают пассажирам билеты с номером «000000»?

Евгений Степанищев (bolknote.ru) 2003

Комментарий для мфд:

Ни разу не видел. А что, это говорит о том, что таких нет? Возможно он достаётся тем, кто едет в 5 утра.

val 2003

Sorry за прошлый пост. мфд == val, конечно

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

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

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

$count = -1; //000000 is unhappy

for ($a=0;$a=0)&&($f

Евгений Степанищев (bolknote.ru) 2003

Комментарий для val:

Дык я же не говорил о эффективной по времени работы реализации. Я создал такую, которая отняла у меня минимум сил, остальное сделала машина, пока я занимался другими делами. Это — эффективное решения, с точки зрения расхода моего времени.

val 2003

Как говорил мой наставник по программированию: \«не создавайте сущность буз потребности\». Вы же не кондуктор, чтобы всю ленту перематывать в поиске счастливых номеров, а программист.

Евгений Степанищев (bolknote.ru) 2003

Комментарий для val:

Я умею программировать, но, кроме того, у меня очень мало времени, поэтому я решил задачу как решил :)

kbept 2003

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

Часто такой фигнёй занимаюсь в транспорте, ежели далеко ехать. Практически всегда складывается, как ни странно, одно время как-то даже собирали «нескладные».

Евгений Степанищев (bolknote.ru) 2003

Комментарий для kbept:

Вот и скажи. :) Мне-то неинтересно. Сделать можно всё.

tomato 2003

kbept
это задачки для интеллектуалов:)
а вот сделать алгоритм, корторый бы это делал, наверное, интересно

val 2003

kbept:

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

рекурсия. аккуратная рекурсия и ничего более.

val 2003

2bolk:

Я умею программировать, но, кроме того, у меня очень мало времени, поэтому я решил задачу как решил :)

100%. Я преклоняюсь перед программистом Bolkом. На мой взгляд вы не просто умеете программировать, а умеете программировать чертовски здорово.

Евгений Степанищев (bolknote.ru) 2003

Комментарий для val:

Спасибо :)

kbept 2003

Кстати, получается красивая картинка:
  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

Евгений Степанищев (bolknote.ru) 2003

Комментарий для kbept:

Что-то в этом есть, да :)

kbept 2003

<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

kbept 2003

<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>