Проверить монотонность последовательности цифр числа

Формулировка. Дано натуральное число 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):

deltai = ai – ai+1,

где ai – член заданной последовательности с индексом i. Нетрудно понять, что эта формула определяет разность между двумя соседними элементами: например, если i = 5 (то есть, мы рассматриваем пятую разность), то формула будет выглядеть так: delta5 = a5 – a6. При этом стоит учитывать множество всех значений, которые может принимать i. Например, для последовательности (1) i может принимать значения от 1 до 5 включительно, для последовательности (2) – от 1 до 4 включительно. Легко проверить, что для всех других i формула (I) не имеет смысла, так как в ней должны участвовать несуществующие члены последовательности.

Найдем все deltai для последовательности (1): delta1 = 3 – 4 = –1, delta2 = 4 – 5 = –1, delta3 = 5 – 8 = –3, delta4 = 8 – 9 = –1,delta5 = 9 – 11 = –2.

Как видим, они все отрицательны. Нетрудно догадаться, что это свойство сохраняется для всех строго возрастающих последовательностей.

Выпишем все deltai для последовательности (2), не расписывая при этом саму формулу: 1, 4, 1, 2. Видим, что все они положительны.

Кстати, весьма примечательно, что в математическом анализе определение монотонной функции дается в терминах, подобных используемым в нашей формуле (I), которая рассматривается там несколько более гибко, а deltai при этом называется приращением и имеет несколько иное обозначение.

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

Из всех этих рассуждений делаем вывод о том, что числовая последовательность является строго монотонной (то есть, строго возрастающей или строго убывающей) тогда и только тогда, когда deltai имеют один и тот же знак для всех i. Таким образом, мы вывели понятие, которое можно проверить с помощью последовательности однотипных действий, то есть, циклической обработки.

Теперь нам необходимо попробовать унифицировать проверку знакопостоянства всех delta для последовательностей обоих видов. Для этого рассмотрим произведение каких-либо двух delta в последовательностях (1) и (2). Примечательно, что оно положительно как произведение чисел одного знака. Таким образом, мы можем в любой последовательности взять delta1 и получить произведения его со всеми остальными delta (обозначим эту формулу как (II)):

p = delta1 * deltai

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

Теперь перенесем эти рассуждения из математики в программирование и конкретизируем их на последовательность цифр восьмеричной записи числа. Обозначим идентификатором delta результат вычисления формулы (I) для двух текущих соседних членов последовательности.

Каким же образом двигаться по разрядам числа n и обрабатывать все delta?

Сначала мы можем получить последнюю цифру числа n (назовем ее b), отбросить ее и получить предпоследнюю цифру n(назовем ее a), отбросить ее тоже, а затем вычислить delta = a – b. Кстати, отметим, что при таком подходе мы будем для всех i находить deltai, двигаясь по ним справа налево. Начальному фрагменту этих действий соответствует следующий код:

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 – таким образом, все было бы готово для исследования знака по произведению. В связи с этим основной цикл будет выглядеть так:

while n <> 0 do begin

b := a;

a := n mod 8;

n := n div 8;

…

end;

На месте многоточия и будет проверка знакопостоянства произведений. Воспользовавшись формулой (II), мы заменимdeltai в качестве текущего на саму разность a – b, чтобы не задействовать дополнительную переменную. В итоге, если теперь delta * (a – b) <= 0, то выходим из цикла:

if delta * (a — b) <= 0 then break;

Теперь рассмотрим развитие событий по завершении цикла:

1) Если произойдет выход по завершению цикла, то есть «закончится» число в связи с превращением его в 0 на некотором шаге, то значения a, b и delta будут содержать значения, подтверждающие строгую монотонность последовательности, что можно проверить с помощью вывода значения булевского выражения на экран.

2) Если в теле цикла произошел выход через условный оператор, то эти переменные будут содержать значения, с помощью которых выявлено условие нарушения строгой монотонности. Это значит, что по выходе из цикла ответ можно выводить в формате:

writeln(delta * (a — b) > 0);

Код:

  1. program OctalSequence;
  2. var
  3. n, a, b: word;
  4. delta: integer;
  5. begin
  6. readln(n);
  7. b := n mod 8;
  8. n := n div 8;
  9. a := n mod 8;
  10. n := n div 8;
  11. delta := a — b;
  12. while n <> 0 do begin
  13. b := a;
  14. a := n mod 8;
  15. n := n div 8;
  16. if delta * (a — b) <= 0 then break
  17. end;
  18. writeln(delta * (a — b) > 0)
  19. end.

Кстати, что будет при вводе числа n, меньшего 8, ведь его восьмеричная запись однозначна? Хотя наша цепочка делений еще до входа в цикл требует двух цифр в записи числа!

Посмотрим, как поведет себя программа при вводе числа n из единственной цифры k: сначала k идет в b (строка 9), затем отбрасывается в n (строка 10), которое теперь равно 0, затем в a идет число 0, так как 0 mod 8 = 0 (строка 11). При этом строка 12 уже ничего не дает, так как n, которое сейчас равно нулю, присваивается значение 0 div 8 = 0. Далее вычисляется delta = –k (строка 13), затем игнорируется цикл, так как n = 0 (строки 14 – 19), затем выводится на экран значение выражения –k * –k > 0 (строка 20), которое истинно для любого действительного k кроме нуля, который и не входит в условие нашей задачи, так как n натуральное.

Как видим, вырожденный случай прошел обработку «сам собой» и для него не пришлось разветвлять программу, что выражает несомненный плюс.