ПАПА Простейшая Авторская Прикладная Алгоритмика ПАПА
Программа — Предельно короткий нарастающий
генератор простых чисел
Автор: Тарасенко Б.А. Программа разработана 5.08.89. Публикуется впервые. Реализуема
на калькуляторах МК-61 и МК-52. Назначение: учебная программа дпя кружков программиро-
вания и математических кружков любой возрастной категории, школьное учебное средство по
курсам математики и ОИВТ, личное вспомогательное средство любителя и профессионала по
курсу теории чисел. Заменяет собой таблицу простых чисел.
Входные данные: нечетные целые положительные числа в диапазоне от 5 до 10044017
включительно (10044017 — простое число).
В диапозоне от 10044019 до 29999873 включительно программа частично работоспособна,
т.е. некоторые простые числа интерпретируются как составные и генератором пропускаются.
Число 29999873 — последнее простое фиксируемое генератором. В диапазоне нечетных чи-
сел от 29999875 до 99999999 генератор полностью неработоспособен, программа "бесконечно"
зацикливается.
Длина программы: 24 шага. Количество клавшиных нажатий при записи программного тек-
ста и минимальное время этой записи в секундах — 46. Используется упрощенный алгоритм
Эратосфена, в котором множество простых допустимых делителей в диапазоне от 3 до 3169
расширено до всех нечетных чисел этого основного диапазона. Переменные величины и ис-
пользуемые для них регистры: Д = сРг5 — текущий нечетный делитель, И = сРгб — нечетное
испытуемое число, ЧАСТН = И/Д = cPrXI. Словесный псевдокод алгоритма: для нарастающих
значений Д из допустимого диапазона, начиная с Д = 3, вычислять ЧАСТН = И/Д; в случае ра-
венства И/Д и целой части от И/Д досрочно переходить на новое значение нарастающего не-
четного И, выполняя И:И + 2; если Д больше ЧАСТИ, считать И + П, где П — простое число и
осуществлять стоп-индикацию результата с последующим переходом на счет с новым значе-
нием И. ЗАМЕЧАНИЕ К АЛГОРИТМУ: проверка по равенству целого от И/Д и исходного И/Д
дает возможность несколько сократить текст программы и повысить ее быстродействие по
сравнению с аналогами (см. ВТиП 4/1988, программу # 018 в статье "Алгоритмический бук-
варь и карманная ЭВМ"), но при восьми значащих разрядах И и при конкретных его значениях,
отмеченных выше, алгоритм (программа) частично или полностью теряет работоспособность.
Оценка быстродействия программы: от 11 к 11 — за 9 сек, от 101 к 101 — за 21 сек, от
10044017 к 10044017 — за 2 часа 12 мин 23 сек, от 29999873 к 29999873 — за 3.5 час.
Далее приводится текст программы:
00 Х- + 6 46 / ♦ Фиксация в Ргб стартового испытуемого И
01 1 01 / + Клавишная константа единица, или КЛАВКО 1
02 Х- + П 5 45 / + Передача Д = сРгХ = 1 в Рг5, или Д: = 1, т.к. сРг5 = Д
03 К П -iX J Г J /+Д: + Д+1, начальная фаза генерации нового Д
04 К П- + X 5 Г5 /+Д: = Д+1, конец генерации Д; новД = старД + 2
05 П- + X 6 66 / ♦ Вызов из Ргб текущего значения И
06 П- + X 5 65 / + сРг$ — на РгХ, или Д; сРгХ = И — РгУ
07 -"- 13 / + И/Д; буквой К обозначена вспомог.переменн.
08 К ЦЕЛ 34 / + Выделение целой части К от И/Д
09 Ф Вх О / + Вызов на РгХ первоначального знач.И/Д из РгХ1
10 — 11 / + М = К-И/Д;М — вспомогательная переменная
11 Ф ХнрвнО 57 / ♦ М не равно нулю!
12 2 0 20 / + НЕТ, М равно нулю; переход на шаг 20
13 Ф Вх О / + Да, М не равно нулю; вызов на РгХ ЧАСТН = И/Д
14П- + Х5 65 / + Вызов на РгХ из Рг5 значения текущ. делит. Д
15 — 11 / ♦ ЧАСТН — Д = Т; ЧАСТН = И/Д, Т — вспом. перемени.
16 Ф ХмншО 5С / + Т меньше нуля?
17 0 3 03 / t НЕТ, Т больше или равно нулю; ход на шаг 03
18 П- + 6 66 / + ДА, Т меньше нуля, Д больше ЧАСТН; вызов И = П
19 С/П 50 / t Стоп-индикация простого числа П = И
20 К П-1 X 6 Г6 / + И: = И + 1, начальная фаза генерации нового И
21 К П- + X 6Г6 / + И: = И + 1, конец генерации; новИ = старИ + 2
22 БП 51 / ♦ Заголовок команды безусловного перехода
23 0 1 01 / + Ход на шаг 01 к новой серии вычислений
ИНСТРУКЦИЯ: В/О, НАБОР И, "И", С/П, "П", С/П, "П" и так далее
Соблюдать оговоренные границы диапазонов. При работе в пределах ограниченной рабо-
тоспособности пользоваться вспомогательной таблицей "необнаруживаемых" простых чисеп.
ПАПА Простейшая Авторская Прикладная Алгорнтмика ПАПА
Программа Угадай число
Автор: Бударевский Андрей Станиславович. Комментарии: Тарасенко Борис Алексеевич.
Авторский вариант разработан в 1990 году. Публикуется впервые. Прототипы есть. Реализует-
ся на калькуляторах МК-61, МК-52.
Назначение: учебно-развлекательная программа, тренирующая навыки устного счета и ло-
гичность мышления. Области применения: кружки программирования и математики, школьные
курсы математики и ОИВТ, обеспечение досуга любителя математики и программирования.
Основное содержание программы: нужно угадать число, сформированное программой с по-
мощью датчика случайных чисел, путем минимального, по возможности, количества попыток.
Количество попыток программой не фиксируется.
Длина программы: 24 шага. Количество нажатий клавиш при записи программного текста и
минимальное время этой записи в секундах — 42. Переменные величины и используемые
для них регистры: сРг4 — константа 100, сРгД — константа 8, сРгО — константа 41СЛО, ЧИС-
ЛО, сРг2 — константа 60ЛСЕ, или БОЛЬШЕ, cPrl — константа СЛ60, или СЛБО# или СЛАБО
(МЕНЬШЕ), сРгС — константа 17, или П, или ПРАВИЛЬНО, или ПОБЕДА. Время одного цикла
"отгадывания" — до 4 секунд (3 + 1)7 сРгА = отгад.числу.
00 П- + X О 60 / + Вызов из РгО сообщения ЧИСЛО для пуска ГСЧ
01 С/П 50 / + Останов и индикация запроса о вводе числа
02 ВСТЕК ОЕ / + Инициализирующее ГСЧ дробное число в РгУ
03 К СЧ ЗЛ / + Разовое псевдослучайное число из ГСЧ
04П- + Х4 64 / + Вызов из Рг# на РгХ константы 100
05 х 12 / + Выделение двух левых разрядов в целые
06 К ЦУЛ 34 / + Целое 2-разрядное "загаданное'' число
07 Х- + П А 4- / + Запоминаем для дальнейшего использования
08П- + Х0 60 /+ Сообщение "число", приглашение к вводу отг.
09 С/П 50 / + Стоп-индикация ЧИСЛО и ввод отгадки
10 П- + Х А 6- / + Вызов из РгА на РгХ загаданного числа
11 — 11 / + Разность между "загадкой" и "попыткой"
12ФХ = 0 5Е /+ Разность равна нулю?
13 16 16 / + НЕТ, сРгХнрвнО, ход на шаг 16
14 П- + ХС 6С / + ДА, сРгХ + О и ответ верный, число отгадано
15 С/П 50 / + Стоп-индикация сигнала ПОБЕДЫ, 17, вызванн.
16 Ф ХсншО 5С / + Разность меньше нуля?
17 2 1 21 / + НЕТ, сРгХбрвиО, ход на шаг 21
18П- + Х1 61 /+ ДА, сРгХмншО, вызов из Рг1 на РгХ СЛБО
19 С/П 50 / + Стоп-индикация сообщения СЛАБО, или МЕНЬШЕ
20 К БП Д 8Г / + Безусловный переход на шаг 08, т.к. сРгД = 8
21 П- + X 2 62 / + Вызов из Рг2 на РгХ сообщения БОЛЬШЕ
22 С/П 50 / + Стоп-индикация сообщения БОЛЬШЕ
23 К БП Д 8Г / + Безусловный переход на шаг 08 по сРгД = 8
>
ПОСТКОММЕНТАРИЙ: в программе "загадываются" двухразрядные числа не более 100.
ПОДГОТОВКА К РАБОТЕ: она сводится к ручному клавишному формированию кон-
стант и сообщений и к занесению их в соответствующие регистры: набрать 100, Х- + П 4, на-
брать 8, Х- + П Д, 1418801, ВСТЕК, 1414301, К ИЛИ, К ДРБ, ВП, 5, ВСТЕК, К ЦУЛ, Х- + П О, (вве-
дено сообщение ЧИСЛО), 160888, ВСТЕК, 160346, К ИЛИ, К ДРБ, ВП, 5, ВСТЕК, Х- + П 2, (введе-
но сообщение БОЛЬШЕ), 188601, ВСТЕК, 143601, К ИЛИ, К ДРБ, ВП, 4, ВСТЕК, К ЦЕЛ, Х- + П 1
(введено сообщение СЛАБО, или МЕНЬШЕ), 17, Х- + П С, (введено сообщение 17, или П, или
ПОБЕДА)
ОСНОВНАЯ ИНСТРУКЦИЯ К РАБОТЕ:
- В/О, С/П, "ЧИСЛО", ввод произвольного дробного числа, С/П, "ЧИСЛО", набор числа-
попытки не более 100, С/П, "БОЛЬШЕ или МЕНЬШЕ", С/П, "ЧИСЛО", набор следующей по-
пытки, С/П и так далее, пока не появится сообщение 17 (ПОБЕДА, или ПРАВИЛЬНО);
- для проведения нового цикла отгадывания нужно повторить полностью все ручные опе-
рации основной инструктивной части.
