Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Задача № 32. Проверить монотонность последовательности цифр числаФормулировка. Дано натуральное число 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); Код:
Кстати, что будет при вводе числа 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 натуральное. Как видим, вырожденный случай прошел обработку «сам собой» и для него не пришлось разветвлять программу, что выражает несомненный плюс.
|