Завдання № 44. Перевірити, чи є послідовність пилкоподібної » Pascal - основи програмування

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

 

Спонсори

Завдання № 44. Перевірити, чи є послідовність пилкоподібної

Завдання № 44. Перевірити, чи є послідовність пилкоподібної
Формулювання. Дана послідовність з трьох і більше натуральних чисел, обмежена введенням нуля. Перевірити, чи є ця послідовність пилкоподібної.
Примітка: пилкоподібної називається послідовність чисел, в якій кожен член, що має сусідні члени, менше або більше їх.
Приклад такої послідовності 14 18 грудня 10 липня 2. Покажемо, що дана послідовність відповідає визначенню: її 1-й член (14) ми не розглядаємо, оскільки він має лише один сусідній член; 2-й член (12) менше сусідніх: 1-го (14) і 3-го (18); 3-й член (18) більше 12 і 7, 7 менше 18 і 10, 10 більше 7 і 2, а останній елемент 2 ми також не розглядаємо. Цей запис можна формалізувати, якщо між кожними двома сусідніми членами послідовності по-ставити знак відносини між їх величинами («>» або «<»). У зв'язку з цим наведений вище приклад можна проілюструвати так: 14> 12 <18> 7 <10> 2. При цьому характерно направле-ня значків, що показує, що кожен елемент або менше, або більше сусідніх. При цьому якщо ми випишемо самі знаки порівняння, то отримаємо символьне поєднання> <> <>. А якщо ви-писати ці символи в стовпчик, стає зрозуміло, чому така послідовність названа пі-лообразной.
Рішення. Досліджуємо властивості пилкоподібної послідовності. У визначенні сказано, що всі її елементи (крім двох крайніх) менше або більше сусідніх. Конкретизуємо це поняття: будь-яку трійку поруч стоять елементів (лівий елемент, центральний елемент, правий елемент) в даній послідовності ми будемо називати «зубом».
Наприклад, для зазначеного вище прикладу зубами будуть трійки 14 18 грудня, 12 18 липня, 18 7 10 і 7 жовтня 2. Кожен зуб задовольняє умові, даному у визначенні, отже, по-следовательность є пилкоподібної. Очевидно, що якщо всі зуби в деякій послідовно-ності задовольняють даній умові, то ця послідовність є пилкоподібної.
Знайдемо деякі властивості «правильних зубів», тобто таких, які відповідають заданий-ному визначенню. Для цього формалізуємо міркування над елементами зуба, позначивши їх як L (лівий елемент, від англ. Left - лівий), M (середній елемент, від англ. Medium - середній), R (пра-вий елемент, від англ. Right - правий ).
Відомо, що середній елемент в зубі може бути або менше, або більше крайніх, в свя-зи з чим для обох випадків виникає ряд наступних нерівностей:
I випадок (середній елемент менше крайніх):
Тут знак позначає кон'юнкцію (логічне «і»), а позначає логічне следо-вання (тобто, з виразу, яке стоїть лівіше знака, слід вираз, що стоїть правіше знака).
II випадок (середній елемент більше крайніх):
Отже, в обох випадках ми склали дві різниці, які для зручності позначили (1) і (2). У I-му випадку (1) і (2) завжди строго більше 0, а в II-му випадку - строго менше 0.
Складемо твір виразів (1) і (2) і позначимо його як (3): (M - L) * (M - R). У I-му випадку воно завжди позитивно як добуток від'ємних чисел, в II-му випадку - також завжди позитивно як добуток позитивних чисел.
Що ж слід з цього виразу? А те, що якщо результат його обчислення - позитивними ве число, то трійка елементів L, M, R утворює «правильний зуб». І як ми пам'ятаємо, якщо всі трійки сусідніх елементів послідовності утворюють «правильні зуби», то вона є пилкоподібної.
Так як в умові завдання на вхід подається як мінімум три елементи, ми можемо прочитати їх в одному операторі:
read (L, M, R);
Потім ми входимо в цикл з передумовою R <> 0. У цьому циклі ми повинні досліджувати кожну трійку L, M, R по властивості (3):

 while R <> 0 do begin
  if (L - M) * (R - M) <= 0 then break;
  L: = M;
  M: = R;
  read (R)
end;

На кожному кроці циклу ми спочатку досліджуємо вже наявну трійку (оператор 1 в тілі циклу), і якщо вираз (3) виявляється одно або менше нуля, то виходимо з циклу, так як знайшли «неправильний зуб», який порушує умову пилкоподібної послідовності, в си-лу чого подальша перевірка безглузда. Потім нам потрібно «зрушити» послідовність: наприклад, якщо в змінних L, M, R у нас відповідно зберігалися 4-й, 5-й і 6-й елементи послідовності, які ми вже перевірили, то за допомогою оператора L: = M ми переносимо 5-й елемент в L, а за допомогою M: = R переносимо 6-й елемент в M. Далі ми вводимо 7-й елемент в R, після чого в трійці L, M, R у нас містяться відповідно 5-й, 6-й і 7-й елементи, провер-ка яких на відповідність умові буде проведена на наступному кроці циклу.
На останньому кроці циклу послідовність буде в черговий раз «зрушена» і в R буде введено число 0, після чого повинен бути виведений результат. У зв'язку з цим можливо два вари-анта потрапляння на цей етап:
a) у циклі був здійснений вихід через break. А це означає, що в змінних L, M, і R в даному випадку якраз знаходиться «неправильний зуб» і можна обійтися висновком значен-ня виразу (L - M) * (R - M)> 0, яке якраз дасть значення false:
 writeln ((L - M) * (R - M)> 0);

b) послідовність була перевірена до кінця, і вихід з циклу був здійснений по вво-ду в R нуля. Але тут потрібно врахувати, що при цьому в трійці L, M, R тепер знаходиться "не-існуючий зуб» (так як 0 не входить в саму послідовність і не повинен враховувати-тися при перевірці), який може і не бути «правильним» .
Найпростіший вихід в цьому випадку - якщо змінна R дорівнює 0, то замінити R на L. Це призведе до того, що в виводиться на екран вираженні (3) ми перемножуємо ні (1) і (2), а (1) і ( 1), що спричинить висновок true, оскільки ми отримуємо твір однакових ненульових чисел, яке завжди позитивно. Значить, перед виведенням вираження на екран необхідна наступна вставка:
if R = 0 then R: = L;

Код:


  1. program Saw;
  2. var
  3. L, M, R: integer;
  4. begin
  5. read(L, M, R);
  6. while R <> 0 do begin
  7. if (L - M) * (R - M) <= 0 then break;
  8. L := M;
  9. M := R;
  10. read(R)
  11. end;
  12. if R = 0 then R := L;
  13. writeln((L - M) * (R - M) > 0)
  14. end.

0044.-Saw.rar [593 b] (cкачувань: 2)

скачать dle 10.4фильмы бесплатно Наступна сторінка » Завдання № 45. Перевірити, чи є послідо... Попередня сторінка » Завдання № 43. Перевірити, чи починаєть...