Решение задачи №4188
Условие задачи №4188:
Условие: Дано натуральное число n. Проверить, представляют его ли цифры его восьмеричной записи строго монотонную последовательность. При этом последовательность из одной цифры считать строго монотонной.Примечание: в математике строго возрастающие и строго убывающие последовательности называются строго монотонными. В строго возрастающей последовательности каждый следующий член больше предыдущего.
Например: 1, 3, 4 ,7, 11, 18. В строго убывающей последовательности каждый следующий член меньше предыдущего.
Например: 9, 8, 5, 1.
Решение
Описание отсутствуетЗдесь нам нужно будет последовательно получить разряды восьмеричной записи числа, двигаясь по записи числа справа налево. Как мы уже знаем, последний разряд числа в восьмеричной системе счисления есть остаток от деления этого числа на 8.
Попытаемся определить несколько общих свойств строго возрастающих (обозначим пример как 1) и строго убывающих (обозначим как 2) последовательностей (для наглядности будем сразу брать восьмеричные последовательности):
1) 3, 4, 5, 8, 9, 11.
2) 8, 7, 3, 2, 0.
Для начала введем в рассмотрение некоторую формулу, обозначим ее как (I):
\[\Delta _i = a_i-a_{i+1}\]
где ai – член заданной последовательности с индексом i. Нетрудно понять, что эта формула определяет разность между двумя соседними элементами: например, если i = 5 (то есть, мы рассматриваем пятую разность), то формула будет выглядеть так: Δ5 = a5 – a6. При этом стоит учитывать множество всех значений, которые может принимать i. Например, для последовательности (1) i может принимать значения от 1 до 5 включительно, для последовательности (2) – от 1 до 4 включительно. Легко проверить, что для всех других i формула (I) не имеет смысла, так как в ней должны участвовать несуществующие члены последовательности.
Найдем все Δi для последовательности (1): Δ1 = 3 – 4 = –1, Δ2 = 4 – 5 = –1, Δ3 = 5 – 8 = –3, Δ4 = 8 – 9 = –1, Δ5 = 9 – 11 = –2.
Как видим, они все отрицательны. Нетрудно догадаться, что это свойство сохраняется для всех строго возрастающих последовательностей.
Выпишем все Δi для последовательности (2), не расписывая при этом саму формулу: 1, 4, 1, 2. Видим, что все они положительны.
Кстати, весьма примечательно, что в математическом анализе определение монотонной функции дается в терминах, подобных используемым в нашей формуле (I), которая рассматривается там несколько более гибко, а Δi при этом называется приращением и имеет несколько иное обозначение.
Можно обобщить сказанное тем, что последовательность приращений показывает, на какую величину уменьшается каждый член исследуемой последовательности чисел, начиная с первого. Понятно, что если каждый член числовой последовательности уменьшается на положительную величину, то эта последовательность строго убывает и т. д.
Из всех этих рассуждений делаем вывод о том, что числовая последовательность является строго монотонной (то есть, строго возрастающей или строго убывающей) тогда и только тогда, когда Δi имеют один и тот же знак для всех i. Таким образом, мы вывели понятие, которое можно проверить с помощью последовательности однотипных действий, то есть, циклической обработки.
Теперь нам необходимо попробовать унифицировать проверку знакопостоянства всех Δ для последовательностей обоих видов. Для этого рассмотрим произведение каких-либо двух Δ в последовательностях (1) и (2). Примечательно, что оно положительно как произведение чисел одного знака. Таким образом, мы можем в любой последовательности взять Δ1 и получить произведения его со всеми остальными Δ (обозначим эту формулу как (II)):
\[p = \Delta _1 \cdot \Delta _i\]
Если все p положительны, то последовательность строго монотонна, а если же возникает хотя бы одно отрицательное произведение p, то условие монотонности нарушено.
Теперь перенесем эти рассуждения из математики в программирование и конкретизируем их на последовательность цифр восьмеричной записи числа. Обозначим идентификатором Δ результат вычисления формулы (I) для двух текущих соседних членов последовательности.
Каким же образом двигаться по разрядам числа n и обрабатывать все Δ?
Сначала мы можем получить последнюю цифру числа n (назовем ее b), отбросить ее и получить предпоследнюю цифру n (назовем ее a), отбросить ее тоже, а затем вычислить Δ = a – b. Кстати, отметим, что при таком подходе мы будем для всех i находить Δi, двигаясь по ним справа налево. Начальному фрагменту этих действий соответствует следующий код:
1 2 3 4 5 | b := n mod 8; n := n div 8; a := n mod 8; n := n div 8; delta:= a - b; |
Теперь мы можем войти в цикл с предусловием n < > 0. В каждом шаге цикла мы должны присвоить переменной b число a, затем считать следующий разряд в a и отбросить этот разряд в n. Таким способом мы «сдвигаем» текущую пару: например, на 1-ом шаге в примере (2) мы до входа в цикл использовали бы цифры 2 (в переменной a) и 0 (в переменной b), затем при входе в цикл скопировали бы 2 в b и 3 в a – таким образом, все было бы готово для исследования знака по произведению. В связи с этим основной цикл будет выглядеть так:
1 2 3 4 5 6 | while n <> 0 do begin b := a; a := n mod 8; n := n div 8; ...end; |
На месте многоточия и будет проверка знакопостоянства произведений. Воспользовавшись формулой (II), мы заменим Δi в качестве текущего на саму разность a – b, чтобы не задействовать дополнительную переменную. В итоге, если теперь Δ ⋅ (a – b) ≤ 0, то выходим из цикла:
1 | if delta * (a - b) <= 0 then break; |
Теперь рассмотрим развитие событий по завершении цикла:
1) Если произойдет выход по завершению цикла, то есть «закончится» число в связи с превращением его в 0 на некотором шаге, то значения a, b и Δ будут содержать значения, подтверждающие строгую монотонность последовательности, что можно проверить с помощью вывода значения булевского выражения на экран.
2) Если в теле цикла произошел выход через условный оператор, то эти переменные будут содержать значения, с помощью которых выявлено условие нарушения строгой монотонности. Это значит, что по выходе из цикла ответ можно выводить в формате:
1 | writeln(delta * (a - b) > 0); |
Конечный код программы:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | program OctalSequence; var n, a, b: word; delta: integer; begin readln(n); b := n mod 8; n := n div 8; a := n mod 8; n := n div 8; delta := a - b; while n <> 0 do begin b := a; a := n mod 8; n := n div 8; if delta * (a - b) <= 0 then break end; writeln(delta * (a - b) > 0)end. |
Кстати, что будет при вводе числа n, меньшего 8, ведь его восьмеричная запись однозначна? Хотя наша цепочка делений еще до входа в цикл требует двух цифр в записи числа!
Посмотрим, как поведет себя программа при вводе числа n из единственной цифры k: сначала k идет в b (строка 9), затем отбрасывается в n (строка 10), которое теперь равно 0, затем в a идет число 0, так как 0 mod 8 = 0 (строка 11). При этом строка 12 уже ничего не дает, так как n, которое сейчас равно нулю, присваивается значение 0 div 8 = 0. Далее вычисляется Δ = –k (строка 13), затем игнорируется цикл, так как n = 0 (строки 14 – 19), затем выводится на экран значение выражения –k ⋅ (–k) > 0 (строка 20), которое истинно для любого действительного k кроме нуля, который и не входит в условие нашей задачи, так как n натуральное.
Как видим, вырожденный случай прошел обработку «сам собой» и для него не пришлось разветвлять программу, что выражает несомненный плюс.
