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

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

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

Задача

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

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

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

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

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

К сожалению, ПМК обладает всего 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 (оценка)
МК161 92
Casio 9750 GII 96
DM42 12'35"
SHARP PC-G850S 23
HP35s 2010 (оценка)
HP50g UserRPL 282
HP50g SysRPL 5

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

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

Литература

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