Завдання № 32. Перевірити монотонність послідовності цифр числа » Pascal - основи програмування

Основи програмування на мові Pascal

 

Спонсори

Завдання № 32. Перевірити монотонність послідовності цифр числа

Завдання № 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);

Код:


  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.

0032.-OctalSequence.rar [699 b] (cкачувань: 1)

скачать dle 10.4фильмы бесплатно Наступна сторінка » Завдання № 33. Отримати канонічний роз... Попередня сторінка » Завдання № 31. Сформувати реверсну зап...