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

Написал небольшую програмку на 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";

26 августа 2003 15:23

DiZzy (инкогнито)
26 августа 2003, 18:33

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

bolk (bolknote.ru)
26 августа 2003, 18:33, ответ предназначен DiZzy

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

Nefrot (инкогнито)
26 августа 2003, 22:18

А на PHP это как?

bolk (bolknote.ru)
26 августа 2003, 22:18, ответ предназначен 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 (инкогнито)
27 августа 2003, 02:12

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

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

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

bolk (bolknote.ru)
27 августа 2003, 02:12, ответ предназначен cax

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

мфд (инкогнито)
27 августа 2003, 04:22

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

bolk (bolknote.ru)
27 августа 2003, 04:22, ответ предназначен мфд

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

val (инкогнито)
27 августа 2003, 04:39

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

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

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

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

$count = -1; //000000 is unhappy

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

bolk (bolknote.ru)
27 августа 2003, 04:39, ответ предназначен val

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

val (инкогнито)
27 августа 2003, 04:41

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

bolk (bolknote.ru)
27 августа 2003, 04:41, ответ предназначен val

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

kbept (инкогнито)
27 августа 2003, 07:25

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

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

bolk (bolknote.ru)
27 августа 2003, 07:25, ответ предназначен kbept

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

tomato (инкогнито)
27 августа 2003, 09:37

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

val (инкогнито)
27 августа 2003, 11:29

kbept:

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

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

val (инкогнито)
27 августа 2003, 11:42

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

bolk (bolknote.ru)
27 августа 2003, 11:42, ответ предназначен val

Спасибо :)

kbept (инкогнито)
27 августа 2003, 13:57

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

bolk (bolknote.ru)
27 августа 2003, 13:57, ответ предназначен kbept

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

kbept (инкогнито)
27 августа 2003, 13:59

<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 (инкогнито)
27 августа 2003, 14:00

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

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

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

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