Тест "Счастливые билеты" для ПМК

| рубрика «Испытания» | автор st

В книге "Систематический подход к программированию"[1, стр. 100] из популярной серии "Библиотечки программиста" приводились примеры реализации алгоритма поиска "счастливых" билетов. Книгу я использовал в процессе учёбы, поэтому некоторые моменты осели на чердаке памяти. Спустя почти 30 лет появилась идея использовать алгоритм перебора для оценки качества генерируемого компиляторами кода. Заметно выросшие вычислительные мощности ЭВМ вынуждают увеличивать сложность перебора на два порядка (до 8 цифр) для замера времени, которое в варианте для 6 цифр находится в пределах миллисекунды.

Теперь тот же тест в оригинальном виде может быть использован и для оценки быстродействия современных калькуляторов.

Задача

Билеты для проезда на транспорте нумеруются шестизначными цифрами. "Счастливым" считается билет, сумма первых трех цифр которого совпадает с суммой трех оставшихся цифр. Требуется найти общее количество "счастливых" билетов в серии 000000..999999.

Для проверки корректности тестовой программы, полученный результат должен быть равен 55252 с учетом номера 000000 или на единицу меньше без учета.

Перебор без оптимизации

Наиболее простым вариантом является перебор всех 106 вариантов с вычислением и сравнением соответствующих сумм разрядов на каждом шаге. Полный перебор всех вариантов является обязательным условием теста без алгоритмической оптимизации.

Программы для МК61/52

К сожалению, ПМК обладает всего 4 регистрами циклов, поэтому два оставшихся приходится реализовывать условными переходами. Для сокращения времени счета, условные переходы используются для внешнего и первого циклов из шести. Также мы используем не меняющий результат интервал 1..10 вместо 0..9 для каждого разряда. Программа выглядит так:

   00    01    02    03    04    05    06    07    08    09
00 0     П7    1     0     П8    П5    ИП8   П4    ИП8   П3
10 ИП8   П2    ИП8   П1    ИП8   П0    ИП0   ИП1   +     ИП2
20 +     ИП3   -     ИП4   -     ИП5   -     Fx=0  33    ИП7
30 1     +     П7    FL0   16    FL1   14    FL2   12    FL3
40 10    ИП4   1     -     П4    Fx=0  08    ИП5   1     -
50 П5    Fx=0  06    ИП7   С/П

Запуск: В/0, С/П

Для старых моделей МК61/52 время счет должно составлять долгие часы, поэтому просто оценим его, взяв время выполнения самого нижнего цикла и умножив его на 105. Вводим следующую программу:

   00    01    02    03    04    05    06    07    08    09
00 ИП8   П0    ИП0   ИП1   +     ИП2   +     ИП3   -     ИП4
10 -     ИП5   -     Fx=0  19    ИП7   1     +     П7    FL0
20 03    С/П

В регистры заносим: 1 П1 П2 П3 П4 П5, 0 П7, 10 П8.

Запуск: В/0, С/П

На моём МК52 время счета нижнего цикла составило 40 секунд (результат: 1 билет). Соответственно, общее потребное время можно оценить как 40*105 секунд, что составит порядка 1111 часов или 46 дней! Не думаю, что имеет смысл делать реальный тест на таком вычислительном оборудовании.

Другие модели

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

Оптимизация

Кроме теста на производительность, задача является полем для аналитической оптимизации. Например, в нижний цикл имеет смысл входить только если сумма-разность предыдущих пяти разрядов больше нуля.

Результаты

Без алгоритмической оптимизации

Программа без алгоритмической оптимизации должна производить полный перебор всех вариантов номеров от 0 до 999999.

Модель ПМК Время счёта, мин:сек
МК52 66667 (оценка)
HP35s 2010 (оценка)
HP50g UserRPL 282
Casio 9750 GII 96
МК161 92
SHARP PC-G850S 23
DM42 12:35
HP50g SysRPL 5
HP Prime G2 0:24,5

С оптимизацией

Модель ПМК Время счёта, мин:сек
Casio 9750 GII 56:05
Casio fx-9860G SD 49:07
Casio fx-9860G Slim 46:48
SHARP PC-G850S 13:22

Программы для других моделей

МК-161

МК-161 (версия прошивки 1.20), полный тест: 1 час 32 мин (92 мин). Результат предоставил Vitasam.

Casio 9750 GII

Программы и результаты предоставил Ardo_79.

0s
For 0x  to 9
For 0y  to 9
For 0z  to 9
For 0a  to 9
For 0b  to 9
For 0c  to 9
If (x+y+z)= (a+b+c) :then
s+1s
IfEnd
Next
Next
Next
Next
Next
Next
s˛

Результат: (s = 55252) 1 час 36 мин

C оптимизацией

0s
For 0x  to 9
For 0y  to 9
For 0z  to 9
For 0a  to 9
For 0b  to 9
0k
For 0c  to 9
If (x+y+z)= (a+b+c):then
1k :s+1s:Break
IfEnd
Next
If k= 1 and c=0:  then
Break
IfEnd
Next
If k= 1 and c=0 and b=0:  then
Break
IfEnd
Next
Next
Next
Next
s˛

Результат: (s = 55252) 56 мин 05 сек

Casio fx-9860G Slim

Результат: (s = 55252) 46 мин 48 сек ( Программа аналогична Casio fx-9750G II c оптимизацией)

Casio fx-9860G SD

Результат: (s = 55252) 49 мин 07 сек ( Программа аналогична Casio fx-9750G II c оптимизацией)

SHARP PC-G850S

Программы и результаты предоставил Ardo_79.

main() {
int  x,y,z,a,b,c,n=9;
long  s=0;
for(x=0;x<=n;x++) {
   for(y=0;y<=n;y++) {
      for(z=0;z<=n;z++) {
         for(a=0;a<=n;a++) {
            for(b=0;b<=n;b++) {
               for(c=0;c<=n;c++) {
             if (x+y+z==a+b+c)
                  s++;
               }
             }
           }
         }
       }
     }
    printf (s=%d “,s);
}

Результат: (s = 55252) 22 мин 54 cек

С оптимизацией

main() {
int  x,y,z,a,b,c,k=0,n=9;
long  s=0;
for(x=0;x<=n;x++) {
   for(y=0;y<=n;y++) {
      for(z=0;z<=n;z++) {
         for(a=0;a<=n;a++) {
            for(b=0;b<=n;b++) {
            k=0;
               for(c=0;c<=n;c++) {
     if (x+y+z==a+b+c){
         k=1;s++;break;}
    }
         if ((k==1)&(c==0))
         break;
   }
          if ((k==1)&(b==0)&(c==0))
         break;
 }
         }
       }
     }
    printf (s=%d “,s);
}

Результат: (s = 55252) 13 мин 22 cек

HP35s

Программу и результаты предоставил Vitasam.

01 LBL H      15 RCL W      29 STO Z
02 9e-3       16 IP         30 ISG Y
03 STO A      17 RCL V      31 GTO H010
04 STO Z      18 IP         32 RCL A
05 STO Y      19 +          33 STO Y
06 STO W      20 x!=y?      34 ISG W
07 STO V      21 GTO H026   35 GTO H010
08 0          22 RCL T      36 RCL A
09 STO T      23 1          37 STO W
10 RCL Z      24 +          38 ISG V
11 IP         25 STO T      39 GTO H010
12 RCL Y      26 ISG Z      40 VIEW T
13 IP         27 GTO H010   41 RTN
14 +          28 RCL A
T = 670.0000

Для 4-значных билетов: 20 минут, т.е. для 6-значных билетов, в идеальном случае: 20х100 минут или 33,5 часа

HP 50g

Программы и результаты предоставил tca.

UserRPL

<<
  TICKS #0d
  #0d #9d FOR A
    #0d #9d FOR B
      #0d #9d FOR C
        #0d #9d FOR D
          #0d #9d FOR E
            #0d #9d FOR F
              A B C + +
              D E F + +
              IF == THEN
                #1d +
              END
            NEXT
          NEXT
        NEXT
      NEXT
    NEXT
  NEXT
  SWAP TICKS SWAP - B->R 8192. /
  400 2 BEEP
>>

Результат: (16963.7645264) 282 минуты

SysRPL

"::
 CLKTICKS BINT0
 { NULLLAM NULLLAM }
 BIND
 BINT10 ZERO_DO
 INDEX@
 BINT10 ZERO_DO
 DUP INDEX@ #+
 BINT10 ZERO_DO
 DUP INDEX@ #+
 BINT10 ZERO_DO
 DUP INDEX@ #-
 BINT10 ZERO_DO
 DUP INDEX@ #-
 BINT10 ZERO_DO
 DUP INDEX@ #= IT :: 1GETLAM #1+ 1PUTLAM ;
 LOOP
 DROPLOOP
 DROPLOOP
 DROPLOOP
 DROPLOOP
 DROPLOOP
 1GETLAM
 2GETLAM
 ABND
 CLKTICKS
 SWAP bit- HXS>% % 8192 %/
;
@"

Результат: (320.372192383) 5 минут 20 секунд

Если условие переписать:

 DUP INDEX@ #= IT :: 1GETLAM #1+ 1PUTLAM ISTOP@ INDEXSTO ;

то результат: (282.681762695) 4 минуты 43 секунды

HP Prime G2

Программу и результат предоставил tca.

Прямым перебором

EXPORT PROG()
BEGIN
S:=0;
Q:=9;
 FOR X FROM 0 TO Q DO
  FOR Y FROM 0 TO Q DO
   FOR Z FROM 0 TO Q DO
    FOR A FROM 0 TO Q DO
     FOR B FROM 0 TO Q DO
      FOR C FROM 0 TO Q DO
       IF X+Y+Z==A+B+C THEN
        S:=S+1;
       END;
      END;
     END;
    END;
   END;
  END;
 END;
S;
END;

Результат 24,5 сек.

Литература

  • Вьюкова Н.И., Галатенко В.А., Ходулев А.Б. Систематический подход к программированию. Под ред. Ю.М. Банковского. - М.: Наука, 1988. - 208 с. Серия: Библиотечка программиста.

blog comments powered by Disqus