Описание
решения Всероссийской олимпиадной задачи
математического
типа
для
10-ых и 11-ых классов в среде MS Excel
Задача C.
Переворот и сложение (расчет палиндрома)
Входной файл:
Выходной файл:
Время:
Память:
|
input.txt
output.txt
не более 10 сек
не более 64 Мб
|
Функция изменения порядка и сложения начинает
с числа, меняет порядок его цифр на противоположный и складывает получившееся
число с начальным. Если сумма не является палиндромом (то есть не дает одно и
то же число, будучи прочитанной слева направо и справа налево), мы повторяем
эту процедуру до тех пор, пока она им не станет.
Например, если мы начнем с числа 195, то
получим 9339 в качестве итогового палиндрома после четвертого сложения:
Этот метод сходится к палиндрому за несколько
итераций практически для всех целых чисел. Но существуют интересные исключения.
196 является первым числом, для которого не было обнаружено палиндрома. Но тем
не менее не было доказано, что такого палиндрома не существует.
Вы должны написать программу, которая для заданного
числа выдает итоговый палиндром (если он существует) и число итераций/сложений,
которые потребовались, чтобы его найти.
Вы можете считать, что все числа, задаваемые
в качестве тестовых данных, сойдутся к ответу за менее чем 1000 итераций
(сложений) и приведут к итоговому палиндрому, не превышающему 4 294 967 295.
Вход
Первая строка содержит целое
число N (0 < N < 100), задающее число тестовых случаев, а каждая из
следующих N строк содержит одно целое число Р, чей палиндром вы должны найти.
Выход
Для каждого из N целых чисел
выведите строку, содержащую минимальное число итераций, необходимых для
нахождения палиндрома, один пробел и затем собственно итоговый палиндром.
Пример
input.txt
|
output.txt
|
3
195
265
750
|
4 9339
5 45254
3 6666
|
Алгоритмизация
задачи
Наряду
с решением данной задачи средствами языков программирования, которые изучаются
в общеобразовательных школах России, таких как QBasic,
Pascal,
Delphi,
VBA, C++ , приводится алгоритм решения задачи в среде Microsoft
Excel.
Предлагается
комплексный подход к решению задачи, заключающийся в использовании возможностей
электронной таблицы и языка программирования Visual Basic Application.
В
помощь учителям информатики и ученикам средних школ и гимназий, а также с целью
демонстрации алгоритмических возможностей MS Excel, предлагается данный
материал.
Исходные
значения из входного файла построчно заносятся в зону ввода. Результат
формируется в зоне вывода.
Во
избежание ошибочного ввода исходных данных не в зону ввода и повреждения
формул, используется возможность MS Excel защиты листа паролем. Ввод исходных
данных возможен только в зону ввода.
Допускается
ввод любого числа, в т.ч. "0" (нуля). При вводе ошибочного значения (например,
текстового) выдается сообщение об ошибке, ввод нужно повторить.
Формы ввода
начального значения и вывода результата расчета.
Введите число (не более 10 цифр)
|
|
Результат расчета
(зона вывода)
|
|
|
не забудьте в конце ввести Enter
(зона ввода)
|
|
|
|
|
Число итераций
|
Палиндром
|
|
|
|
295
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Панели для задания
условий расчета и кнопки выполнения алгоритмов расчета.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Устанавливать начальные значения (да / нет) :
|
да
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Введите число циклов от 1 до 1000
|
|
|
|
Число
циклов :
|
100
|
|
|
|
|
|
|
|
|
|
|
|
|
|
"Число циклов" определяет число циклов
|
|
|
|
расчета между Палиндромами.
|
|
|
|
|
|
|
|
|
|
Описание
алгоритма решения задачи.
Таблицы
для решения задачи, а также формулы, используемые при расчете, приведены ниже.
Из
введенного в зону ввода числа В8 последовательно выделяются отдельные цифры и
записываются в зону В13:М13, а затем в зону В15:М15. Такая поразрядная запись
числа позволяет манипулировать с числом, в т.ч. "переворачивать" его
наоборот. Перевернутое исходное число записывается в зону В19:М19.
В
зоне В17:М17 записываем "сцепленные" разряды исходного числа
для обеспечения возможности выполнения арифметических действий с числом.
В
зоне В21:М21 записываем "сцепленные" разряды "перевернутого"
числа для обеспечения возможности выполнения арифметических действий над
ним.
Если
"исходное" и "перевернутое" числа равны, т.е. В17=В21, то
получен палиндром.
Если
нет палиндрома, суммируем "исходное" и "перевернутое" числа
и записываем в клетку В8 в качестве исходного числа.
А
В
8
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
M
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2
|
9
|
5
|
|
|
|
|
|
|
|
|
|
|
|
|
ПСТР(B8;$Q$8;$Q$10)
|
ПСТР(B8;$AB$8;$Q$10)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2
|
9
|
5
|
|
|
|
|
|
|
|
|
|
|
|
|
B13
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
295
|
|
|
|
СЦЕПИТЬ(B15;C15;D15;E15;F15;G15;H15;I15;J15;K15;L15;M15)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5
|
9
|
2
|
|
|
|
ЕСЛИ(M15="";"";M15)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
592
|
|
|
|
СЦЕПИТЬ(B19;C19;D19;E19;F19;G19;H19;I19;J19;K19;L19;M19)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Разность
|
297
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Палиндром
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ЕСЛИ(B17=B21;"Палиндром";"")
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
887
|
|
|
|
B17+B21
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Цикл
операций повторяется до тех пор, пока не получим палиндром.
Благодаря
процедурам VBA расчет можно выполнять как пошагово, с просмотром промежуточных
результатов, так и автоматически в цикле. Число итераций расчета палиндрома формируется
в клетке А8.
Средствами
VBA разработана процедура анализа вводимых данных и, в случае ввода
некорректных значений, выводятся сообщения об ошибках.
Для
работы с макросами и процедурами VBA необходимо включить данную функцию в MS
Excel (для MS Excel
2007) :
-
кликните левой кнопкой мыши на значок в
левом верхнем углу MS Excel,
-
выберете "Параметры Excel",
-
установите "галочку" в параметрах "Показывать вкладку
"Разработчик" на ленте
-
нажмите "Ок".
В
ленте команд появится закладка "Разработчик", с возможностью активации
конструктора VBA.
В результате
решения задачи:
1. Рассчитан
палиндром.
2. Определено
количество итераций переворота и сложения для получения палиндрома.
В расчетах
использовались некоторые функции MS Excel,
а именно:
ПСТР(B8;$Q$8;$Q$10)
СЦЕПИТЬ(B15;C15;D15;E15;F15;G15;H15;I15;J15;K15;L15;M15)
ЕСЛИ(M15="";"";M15)
ЕСЛИ(B17=B21;"Палиндром";"")
Тексты
процедур VBA задачи приведены ниже.
Если
в MS Excel макросы не работают, нужно их включить.
Для
включения макросов в MS Excel
2007 проделайте следующее:
-
кликните левой кнопкой мыши на значок в левом верхнем
углу MS Excel,
-
выберете "Параметры Excel",
-
кликните команду "Центр управления безопасностью",
-
кликните команду "Параметры центра управления безопасностью",
-
кликните команду "Параметры макросов",
-
установите режим включить все макросы.
Формулы
для расчета.
Тексты
процедур VBA задачи.
Процедура установки начальных значений.
Вызывается при нажатии кнопки
"Начальные значения".
Private Sub CommandButton2_Click()
' проверка наличия ошибки в заданных параметрах
On Error GoTo Error ' При ошибке,
переход на вывод сообщения
GoTo bigin: ' Если нет
ошибки - переход на начало логики
Error: ' Вывод
сообщения об ошибке
Range("b4").Value = "Ошибка данных,
введите снова"
Range("b4").Select
GoTo End2: ' Завершение процедуры
bigin:
' типы данных :
Dim big As Long ' currency : 15 позиций целых и
4 после запятой,
' или
Integer: -32768 до 32767
' или
Long: целое число не более 10 знаков
Range("b4:m4").Select
Range("B8:M8").Select
big = Range("b4").Value '
Присвоение переменной big значения ячейки
Range("b8").Value = big '
Присвоение ячейке значения переменной big
Range("a8").Select
ActiveCell = 0 ' Присвоение
активной ячейке значения 0
End2:
Range("b4:m4").Select
Application.CutCopyMode = False ' Сброс
End Sub
Процедура расчета цикла задачи пошагово.
Вызывается при нажатии кнопки "Расчет
задачи пошагово".
Private Sub CommandButton1_Click()
Range("n8:p8").Select
Selection.Copy ' Мигает активная ячейка
Range("B8").Select
ActiveSheet.Paste
Range("a8").Select
Selection.Copy ' Мигает активная ячейка
x = Selection
x = x + 1
Range("a8").Select
ActiveCell = x
Range("b4:m4").Select
Application.CutCopyMode = False ' Сброс
End Sub
Процедура расчет палиндрома автоматически.
Вызывается при нажатии кнопки "Расчет
циклов автоматически".
Private Sub CommandButton3_Click()
On Error GoTo Error ' При ошибке переход на вывод сообщения
GoTo Cyrcl: ' Если нет ошибки - переход дальше
Error: ' Вывод сообщения
об ошибке
Range("ae20").Value = "Задано
неверное значение"
GoTo End3: ' Завершение
процедуры
Cyrcl:
' Установить начальные значения ?
If Range("ai12").Value =
"да" Then
Call CommandButton2_Click ' вызов процедуры
установки начальных значений
If Range("b4").Value = "Ошибка данных, введите снова" Then
GoTo End3
' Завершение процедуры
Else
End If
' Расчет цикла
Range("ae20").Value =
"" ' Очистка зоны сообщения
Dim x As Integer
Dim wa As Integer
Dim i As Integer
If (Range("ag18").Value = " " Or
Range("ag18").Value = "") Then
Range("ae20").Value = "Задано неверное число
циклов"
Application.CutCopyMode = False ' Сброс
Exit Sub '
Выход из процедуры
Else
wa = Range("ag18").Value ' В
ячейке должно быть число !!!
If (wa < 1 Or wa > 1000) Then
Range("ae20").Value = "Задано неверное число циклов"
Application.CutCopyMode = False ' Сброс
Exit Sub '
Выход из процедуры
Else
End If
End If
For i = 1 To wa
Range("n8:p8").Select
Selection.Copy
Range("b8").Select
ActiveSheet.Paste
Range("a8").Select
Selection.Copy
x = Selection
x = x + 1
Range("a8").Value = x
If Range("b25").Value <>
"" Then
Application.CutCopyMode = False ' Сброс
Exit Sub '
Выход из процедуры
Else
End If
Next i
End3:
Range("b4:m4").Select
Application.CutCopyMode = False ' Сброс
End Sub
Заключение
Предложенное
решение задачи в среде MS Excel
призвано продемонстрировать широкие возможности редактора "Электронная
таблица" и Visual Basic Application по алгоритмизации и программированию.
Считаю возможным и
допустимым использовать не только в чистом виде языки программирования, но и программный
комплекс MS Excel и VBA при решении олимпиадных задач.
Решение задач в среде
MS Excel с использованием VBA формирует навыки логического мышления,
математического подхода и искусства программирования.
MS Excel в сочетании с языком Visual Basic Application
является мощным инструментом для развития математических и логических
способностей одаренных детей – участников олимпиад.
Ссылка на решение задачи в среде MS
Excel
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.