Тест "Счастливые билеты" для ПМК
В книге "Систематический подход к программированию"[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.
0→s
For 0→x to 9
For 0→y to 9
For 0→z to 9
For 0→a to 9
For 0→b to 9
For 0→c to 9
If (x+y+z)= (a+b+c) :then
s+1→s
IfEnd
Next
Next
Next
Next
Next
Next
s˛
Результат: (s = 55252) 1 час 36 мин
C оптимизацией
0→s
For 0→x to 9
For 0→y to 9
For 0→z to 9
For 0→a to 9
For 0→b to 9
0→k
For 0→c to 9
If (x+y+z)= (a+b+c):then
1→k :s+1→s: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