|
 КИРИЛЛ ТКАЧЕНКО, инженер 1-й категории, ФГАОУ ВО «Севастопольский государственный университет», tkachenkokirillstanislavovich@gmail.com
Программная реализация решения
головоломки «Господин S и господин P» по Арсаку в 1С
 Предлагается программная реализация головоломки «Господин S и господин P» по Арсаку. Используется язык программирования 1С, рассматривается работа с подпрограммами, циклами, ветвлением, одномерными массивами
Обучению языку программирования 1С посвящено немало публикаций. Особняком стоит подход на основе решения головоломок [1]. Рассмотрим непростую головоломку – «Господин S и господин P» [2]. Она довольно известна, имеет множество программных решений [3, 4]. По этой причине использование языка 1С для построения программы, находящей решение головоломки, выглядит целесообразным.
Головоломка имеет следующее условие. Были выбраны два целых положительных числа, каждое из которых не меньше двух и не больше 99. Значение суммы этих двух целых положительных чисел было сообщено господину S и только ему, значение их произведения – господину P и только ему. В ходе диалога между S и P господин S утверждает, что господин P не знает этих двух чисел. Тогда господин P понимает, что теперь он знает эти два числа. Вслед за ним господину Sтакже становятся ясны значения этих чисел.
Пусть искомые два числа есть А и Б. В соответствии с этим диалогом необходимо породить возможные пары чисел А и Б таким образом, чтобы выполнялись три условия:
- Значение суммы Д + Е невозможно представить в виде суммы некоторых двух простых чисел.
- Значение произведения В * Г имеет единственное представление в виде суммы некоторых двух целых положительных чисел Д + Е, удовлетворяющих условию I.
- Значение суммы А + Б имеет единственное представление в виде произведения двух целых положительных чисел В * Г, удовлетворяющих условию II.
В силу того, что условие III ссылается на II, а II – на I, проверку удобно осуществлять в порядке условий III, II, I.
Программный модуль управляемого приложения начинается с определения переменных ВЕРХ_ГРАН, целочисленной переменной для хранения верхней границы рассмотрения чисел, равной 99, и ПростыеЧисла – целочисленного одномерного массива, в котором будут располагаться простые числа на отрезке от 2 до 99:
Перем ВЕРХ_ГРАН;
Перем ПростыеЧисла;
Процедура Инициализация() производит установку начальных значений переменных. В частности, порождение списка простых чисел. Для построения списка простых чисел хорошо подходит решето Эратосфена [5, 6]. Процедура начинается с определения переменных Решето, в которой будут располагаться отметки о простоте чисел, а также А, Б – счетчики циклов и индексные переменные:
Процедура Инициализация()
Перем Решето;
Перем А, Б;
Верхняя граница рассмотрения чисел равна 99:
ВЕРХ_ГРАН = 99;
Создаются новые массивы Решето и ПростыеЧисла:
Решето = Новый Массив();
ПростыеЧисла = Новый Массив();
Вначале считается, что все числа в решете – простые. Для удобства адресации элементов массива заполнение начинается с нуля:
Для А = 0 По ВЕРХ_ГРАН Цикл
Решето.Добавить(Истина);
КонецЦикла;
Построение решета не относится непосредственно к головоломке, простые числа первой сотни можно задать значениями в программном коде (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97). С первого простого числа, равного 2, по границу рассмотрения кратные числа отмечаются как составные:
Для А = 2 По ВЕРХ_ГРАН Цикл
Если Решето[А] Тогда
Б = А + А;
Происходит увеличение кратного числа на шаг, равный рассматриваемому простому числу:
Пока Б <= ВЕРХ_ГРАН Цикл
Решето[Б] = Ложь;
Б = Б + А;
КонецЦикла;
КонецЕсли;
КонецЦикла;
Значения всех числа, отмеченных как простые, переносятся в массив простых чисел:
Для А = 2 По ВЕРХ_ГРАН Цикл
Если Решето[А] Тогда
ПростыеЧисла.Добавить(А);
КонецЕсли;
КонецЦикла;
КонецПроцедуры
Функция Простое(А) возвращает значение истина, если число А является простым, то есть содержится в массиве ПростыеЧисла:
Функция Простое(А)
Возврат ПростыеЧисла.Найти(А) <> Неопределено;
КонецФункции
Функция УсловиеI(Сум) проверяет условие I для значения Сум. Определяется целочисленная переменная А – слагаемое:
Функция УсловиеI(Сум)
Перем А;
Для всех возможных значений А, когда А может являться слагаемым, проверяется условие простоты для слагаемых суммы Сум. Если оно выполняется, то условие I для Сум не выполняется и возвращается значение Ложь:
Для А = 2 По Цел(Сум / 2) Цикл
Если Простое(А) И Простое(Сум - А) Тогда
Возврат Ложь;
КонецЕсли;
КонецЦикла;
Иначе условие I для Сум выполняется и получаем Истина:
Возврат Истина;
КонецФункции
Функция УсловиеII(Произв) проверяет условие II для значения произведения Произв. Определяются целочисленные переменные А и Б – множители, а также Количество – количество раз, когда выполнялось для текущей проверяемой суммы условие I:
Функция УсловиеII(Произв)
Перем А, Б;
Перем Количество;
Вначале это количество равно 0:
Количество = 0;
Для всех возможных значений первого целочисленного множителя А, если он является множителем, то определяется второй целочисленный множитель Б:
Для А = 2 По Цел(Sqrt(Произв)) Цикл
Если Произв % А = 0 Тогда
Б = Цел(Произв / А);
Если второй множитель Б принадлежит отрезку [2; ВЕРХ_ГРАН] и для суммы А + Б выполняется условие I, то инкрементируется количество выполнения условия I:
Если (2 <= Б) И (Б <= ВЕРХ_ГРАН) И УсловиеI(А + Б) Тогда
Количество = Количество + 1;
КонецЕсли;
КонецЕсли;
КонецЦикла;
Условие II выполняется, когда условие I выполняется единственный раз:
Возврат Количество = 1;
КонецФункции
Функция УсловиеIII(Сум) проверяет условие III для значения суммы Сум. Определяются целочисленные переменные А – слагаемое; НайденноеА – найденное, удовлетворяющее условию II, значение А; Количество – количество найденных значений А:
Функция УсловиеIII(Сум)
Перем А;
Перем НайденноеА;
Перем Количество;
Вначале НайденноеА и Количество равны 0:
НайденноеА = 0;
Количество = 0;
Если для значения суммы Сум выполняется условие I, то для всех допустимых значений слагаемого А:
Если УсловиеI(Сум) Тогда
Для А = 2 По Цел(Сум / 2) Цикл
Если для произведения слагаемых выполняется условие II, то значение слагаемого А считается найденным и инкрементируется количество выполнения условий II:
Если УсловиеII(А * (Сум - А)) Тогда
НайденноеА = А;
Количество = Количество + 1;
КонецЕсли;
КонецЦикла;
КонецЕсли;
Если условие II выполняется единственный раз, возвращается найденное значение слагаемого, иначе возвращается 0:
Возврат ?(Количество = 1, НайденноеА, 0);
КонецФункции
Процедура Решение() осуществляет поиск решения головоломки. Целочисленные переменные Сум – рассматриваемая сумма, А – слагаемое по условию III, строковая переменная Рез – отображаемый результат:
Процедура Решение()
Перем Сум;
Перем А;
Перем Рез;
Для возможных значений суммы Сум, если существует слагаемое А, удовлетворяющее условию III, то есть также всем условиям I, II, III, результат – найденная пара целых положительных чисел А и (Сум – А) – сообщается пользователю:
Для Сум = 2 По ВЕРХ_ГРАН Цикл
А = УсловиеIII(Сум);
Если А > 0 Тогда
Рез = "" + А + ", " + (Сум - А);
Сообщить(Рез);
КонецЕсли;
КонецЦикла;
КонецПроцедуры
Процедура Главная() производит инициализацию переменных и нахождение решения:
Процедура Главная()
Инициализация();
Решение();
КонецПроцедуры
Происходит вызов главной процедуры:
Главная();
В результате работы программы была получена только одна пара целых положительных чисел – 4 и 13 (см. рис.1).
Рисунок 1. Результат работы программы
Полный текст работы программы находится на сайте журнала http://samag.ru.
Полученная программа нахождения решения головоломки позволит полнее и глубже начинающему разработчику 1С освоить работу с подпрограммами, циклами, ветвлением, одномерными массивами. eof
- Ткаченко К. Программная реализация в 1С варианта головоломки «Песенка спета» по Арсаку. // «Системный администратор», № 4, 2018. – С. 47-49. URL: http://samag.ru/archive/article/3631.
- Арсак Ж. Программирование игр и головоломок / Ж. Арсак. – М.: Наука, 1990. – 224 с.
- Sum and Product Puzzle // Wikipedia. URL: https://en.wikipedia.org/wiki/Sum_and_Product_Puzzle (дата обращения: 22.10.2018).
- Sum and Product Puzzle // Rosetta Code. URL: http://rosettacode.org/wiki/Sum_and_Product_Puzzle (дата обращения: 21.10.2018).
- Перминов О.Н. Программирование на языке Паскаль / О.Н. Перминов. – М.: Радио и связь, 1988. – 224 с.
- Sieve of Eratosthenes // Rosetta Code. URL: http://rosettacode.org/wiki/Sieve_of_Eratosthenes (дата обращения: 07.11.2018).
Ключевые слова: 1С, головоломка, программирование.
Facebook
Мой мир
Вконтакте
Одноклассники
Google+
|
Программная реализация решения головоломки «Господин S и господин P» по Арсаку в 1С
