Я готуюсь до курсу інформатики. Алгоритмізація та програмування



Сторінка7/9
Дата конвертації19.02.2016
Розмір1.47 Mb.
1   2   3   4   5   6   7   8   9

УРОК 26. Впорядкування таблиць

Мета уроку Дати поняття про методи впорядкування табличних величин. Навчити розв’язувати задачі, що потребують сортування.


Теоретичний матеріал
Дуже часто при розв’язуванні задач, пов’язаних з обробкою масивів, необхідно виконувати сортування його елементів за зростанням або спаданням. Такі задачі мають велике практичне значення. Розглянемо деякі з методів, що дають змогу впорядкувати елементи таблиць.
Всі існуючі методи сортування можна поділити на три групи
• обмінні сортування — виконується обмін між двома (найчастішесусідніми) елементами масивів, якщо відповідні елементи розташовані увихідному масиві невпорядковано; процес повторюється або певну кількість разів, або доки елементи в масиві не стануть впорядкованими;
методи прямого вибору — в масиві обирається елемент з певнимивластивостями (наприклад, мінімум або максимум), а потім вибранийелемент ставиться на своє місце;
• методи прямої вставки — послідовно вибираються елементи з масивуі після визначення їх місця у впорядкованому наборі даних вставляютьсябезпосередньо на своє місце.
Найбільш відомим обмінним сортуванням є метод «бульбашки».
В ньому при послідовному проході по масиву порівнюються два сусідніх елементи. Якщо їх розміщення є неправильним (наприклад, при впорядкуванні за зростанням лівий елемент більший за правий), виконується взаємообмін елементів. Процес повторюється щонайменше N-1 разів, де N— кількість елементів у масиві.
Найпростіший алгоритм «бульбашки» має наступний вигляд
Program Bubble; {Сортування за зростанням}
Const N=20;
Var Masarray[1..N] of integer;
i,jinteger; {i,j — змінні циклу)
Rez integer; {Rez — додаткова змінна для обміну елементів масиву між собою)
Begin
For i=1 to N do
For j=1 to N-l do
If Mas[j]>Mas[j+l] then
Begin
{Обмін елементів масиву через третю змінну)
Rez=Mas[j]; Mas[j]=Mas[j+1]; Mas[j+1]=Rez;
End;
End.
Метод можна модифікувати, зменшуючи діапазон сортування після кожного проходу, адже ясно, що після кожного проходу максимальний елемент масиву буде «спливати наверх», тобто займати спочатку останню позицію таблиці, потім передостанню і так далі

Програма, що реалізує описаний алгоритм має наступний вигляд


Program Bubble; {Сортування за зростанням)
Const N=20
Var Masагay[1..N] of integer;
і,jinteger; {i,j — змінні циклу)
Rezinteger; {Rez - додаткова змінна для обміну елементів масиву між собою)
Begin
For i=1 to N do
For j=1 to N-i do
If Mas[j]>Mas[j+l] then
Begin
{Обмін елементів масиву через третю змінну}
Rez=Mas[j]; Mas[j]=Mas[j+1]; Mas[j+1]=Rez;
End;
End.
Зверніть увагу, що в цьому алгоритмі у вкладеному циклі, що безпосередньо здійснює порівняння елементів, змінна циклу змінюється за іншим законом, ніж у попередньому випадку від 1 до N-i, де і — змінна циклу зовнішньої команди повторення.
Другий метод модифікації алгоритму «бульбашки» полягає в тому, що ми вводимо додаткову змінну булівського типу (так званий прапорець), яка фіксуватиме при черговому проході була здійснена хоча б одна перестановка елементів чи ні. Адже очевидно, що якщо при черговому проході не відбулося жодної перестановки, то масив уже відсортований і процес перегляду можна припинити. Домовимось вважати прапорець «опущеним» (тобто рівним значенню false), якщо перестановки не відбулося, і «піднятим» (рівним true) — у протилежному випадку. Крім того, як і в попередньому випадку, після кожного проходу по масиву найбільший елемент «спливає» угору, тобто займає своє позицію. Тому вводимо додаткову змінну к, що фіксує праву границю впорядкованості, тобто при першому проході к = 1 і ми впорядковуємо всі елементи від 1 до N-1, на другому проході к = 2 і будуть впорядковуватись усі елементи від 1 до N- 2 (останній елемент уже впорядкований) і так далі. Програма має вигляд
Program Bubble; {Сортування за зростанням}
Const N=20;
Var Masarray[1..N] of integer;
i,j,kinteger; {i,j — змінні циклу, k — змінна, що фіксує праву границю впорядкування}
Rezinteger; {Rez — додаткова змінна для обміну елементів масиву між собою}
FlagBoolean; {Flag — змінна, що фіксує, відбулася перестановка чи ні}
Begin
k=1;
Repeat
Flag=false; {Робимо припущення, що масив відсортований, а потім перевіряємо, чи правильним було це припущення, тобто чи немає серед елементів таких, що неправильно розташовані, якщо такі елементи будуть, то ми їх переставляємо і Flag присвоюємо значення true}
For і=1 to N-k do
If Mas[i]>Mas[i+1]
then
begin
{Обмін елементів масиву через третю змінну}
Rez=Mas[i];
Mas[і]=Mas[i+1];
Mas[i+1]=Rez;
Flag=true;
End;
k=k-1;
Until Flag = false;
End.
Другим методом сортування є метод прямого вибору. Один з його різновидів полягає в тому, що вибирається мінімальний елемент масиву, а потім виконується його обмін з першим елементом таблиці. Після цього перший елемент вважається впорядкованим і процес повторюється для підмасиву, що містить на один елемент менше за початковий, тобто елементи з 2-го до останнього. Процес повторюється кожен раз для масиву, зменшеного на один елемент. Закінчується він тоді, коли невпорядкований підмасив стає довжиною в один елемент. Таким чином, загальна кількість повторень дорівнює, як і в попередньому випадку, N-1 (N— кількість елементів масиву). Програма методу наведена нижче
Program Selection;
Const N=20;
Var Masarray[1..N] of integer;
і,j, Min,N_Mininteger;
Begin
For i=1 to N-1 do
Begin
Min=Mas[x]; {Зберігання еталону мінімуму}
N_Min=i; {Зберігання номера мінімуму}
For j=i+l to N do
If Mas[j]<Min
then begin
Min=Mas[j]; {Перевизначекня еталону}
N_Min=j; {Зберігання номеру еталону}
end;
{Обмін місцями мінімуму та першого елементу підмасиву}
Mas[N_Min]=Mas[i];
Mas[i]=Min;
End;
End.
Зверніть увагу, що пошук мінімуму в програмі організований стандартно, тобто перший елемент береться за еталон, а потім порівнюється з усіма останніми і, якщо новий елемент виявляється меншим за еталон, то еталон переприсвоюється. Крім цього, в алгоритмі запам’ятовується місце знаходження цього мінімального елемента для того, щоб після виходу з циклу можна було обміняти місцями знайдений мінімум і перший елемент підмасиву. Але оскільки підмасив увесь час змінює свій розмір, за еталон береться перший елемент саме того підмасиву, який розглядається на наступному кроці, тобто г’-ий елемент початкового масиву (і — змінна зовнішнього циклу, що вказує на початок нового підмасиву на кожному кроці).
Метод прямої вставки забезпечує вставку кожного елементу невпоряд-кованого масиву на своє місце у вже впорядкований масив. Один з методів такого сортування полягає в наступному. На початку сортування масив розбивається на два підмасиви, лівий з яких повинен бути впорядкованим, а правий — ні. У невідомому масиві тільки один елемент можна вважати впорядкованим, тому спочатку ліва відсортована частина складається всього з одного елементу. Потім по черзі беруться елементи з другої невпорядкованої частини і для них знаходиться місце вставки в першу частину таке, щоб впорядкованість не порушувалась. Це означає, що при сортуванні за зростанням необхідно знайти таке місце в масиві, де лівий елемент буде меншим або рівним тому, що вставляється, а правий — більшим за той, що вставляється. Після цього в масиві необхідно зробити зсув елементів, щоб звільнити місце, на яке і вставити черговий елемент.
Щоб оптимізувати розглянутий алгоритм, можна поєднати зсув елементів з пошуком місця вставляння. Для цього перевірки виконуються в зворотному напрямку від елемента, що потрібно вставити до місця вставки (тобто справа наліво). Оскільки елемент, що вставляється, береться першим з невпорядкованої частини масиву, то ліворуч від нього всі елементи вже впорядковані. Тому фактично необхідно порівнювати даний елемент з усіма лівішими від нього і, якщо даний елемент менший за той, з яким порівнюється, то виконується обмін елементів. Елемент наче «пливе» ліворуч від свого початкового місця розташування, і процес цей припиняється, якщо знайдений елемент не більший за даний або ми досягай початку масиву. Наприклад, даний такий масив
12 -8 0 30 5 100
Розбиваємо його на дві частини. До першої входить єдиний впорядкований елемент {12}, а до другої—всі останні {-80305100}. Запишемо тепер процес впорядкування по етапах
І етап елемент, що впорядковується = - 8.
1) - 8 < 12, тому виконується обмін, тобто після першого кроку масив має вигляд
-8 12 0 30 5 100
На цьому цикл припиняє свою роботу, тому що досягнуто початку масиву (і= 1).
IIетап елемент, що впорядковується = 0.
1) 0 < 12, значить виконується обмін, тобто після першого кроку масивмає вигляд
-8 0 12 30 5 100
2) 0 > - 8, значить обмін не виконується, здійснюється вихід із циклу,масив залишається без змін.
III етап елемент, що впорядковується = 30.
1) 30 > 12, вхід до циклу не відбувається, масив залишається без змін.
IVетап елемент, що впорядковується = 5.
1) 5 < 30, виконується обмін, після перестановки масив має вигляд
-8 0 12 5 30 100
2) 5 < 12, здійснюється обмін, масив набуває вигляду
-8 0 5 12 30 100
3) 5 > 0, цикл припиняє свою роботу, масив залишається без змін.
V етап елемент, що впорядковується = 100.
1) 100 < 30, вхід до циклу не відбувається, тому що умова відразу хибна і масив залишається без змін. Програму наведено нижче
Program Insert;
Const N=20;
Var Masarray[1..N] of integer;
і,j,Rezinteger;
Begin
For i=2 to N do
Begin
j=i; {Цикл працює, доки лівий елемент більший за правий та доки не досягнуто початох масиву}
while (j>1) and (Mas[j]<Mas[j-1]) do
Begin
Rez=Mas[j]; Mas[j]=Mas[j-1]; Mas[j-1]=Rez; j=j-1;
End;
End;
End.
Домашнє завдання
• Створити блок-схему запропонованих алгоритмів сортування («бульбашка» — 1-й та 2-й методи, метод прямого вибору, метод прямої вставки).

УРОК 27. Програми впорядкування таблиць

Мета уроку Навчити розв’язувати задачі, що потребують для свого розв’язання впорядкування масивів.


На початку уроку бажано зробити опитування за попереднім матеріалом. Потім розглянути кілька задач на застосування методів впорядкування табличних величин,запропонувати учням самостійне розв ‘язування цих задач.
ЗАДАЧА №339(1)
Умова Дано натуральне число п та послідовність дійсних чисел а1, а2 ... ап. Після впорядкування цієї послідовності за спаданням визначити, скільки членів послідовності залишилося стояти на своїх місцях.
Розв’язання Для того, щоб визначити, скільки чисел залишилось на своїх місцях, нам необхідно зберігати як вихідний масив, так і відсортований, тому перш за все зарезервуємо два однакових одновимірних масиви А — вихідний масив та В — відсортований. Метод сортування масиву в даному випадку можна використовувати будь-який, наприклад, метод прямого вибору. Після виконання впорядкування проходом по обох масивах порівнюємо відповідні елементи вихідного та відсортованого масивів і, якщо вони збігаються, виконуємо підрахунок. Програма має вигляд.
Program Example_339_l;
Uses crt;
Const N = 100;
Type Masiv = array[1..N] of real;
Var A,BMasiv; {A — масив для зберігання початкової послідовності, В — відсортований масив}
і,j,countbyte; {i,j — змінні циклу, count — кільхість елементів, що залишились на своїх місцях)
Maxreal; {Мах — максимальний елемент підмасиву}
N_maxbyte; {N_max — номер максимального елементу}
Begin Randomize;
Clrscr;
For i=1 to N do
Begin A[i]=random*100-random*50; Write<A[i]82); End;
B=A; {Копіювання елементів масиву А в масив В}
For i=1 to N-1 do
Begin
Max=B[i]; {Зберігання еталону максимуму}
N_Max=i; {Зберігання номера максимуму}
For j=i+1 to N do
If B[j]>Max then
begin
Max=B[j]; {Перевизначення еталону}
N_Max=j; {Зберігання номеру еталону}
end;
{Обмін місцями мінімуму та першого елементу підмасиву}
B[N_Max]=В[і]; В[і]=Мах;
End;
count=0;
For і»1 to N do
Begin
If A[i]=B[i]
then count=count+1;
End;
Writeln;
Writeln(‘Кількість елементів, що не змінили місця ‘ ,count) ;
Readkey;
End.
ЗАДАЧА №342(1)
Умова Дано натуральне число п та послідовність дійсних чисел а1, а2 ... ап. Визначити усі числа, що входять у послідовність по 1-му разу.
Розв ‘язання Пошук чисел, що входять у послідовність по одному разу, виконати важко, тому що для цього необхідно порівняти кожне число з кожним. Набагато простіше зробити це у відсортованому масиві, оскільки однакові числа в ньому будуть розташовані поруч. Тобто пропонуємо в даній задачі спочатку відсортувати масив (метод сортування будь-який, наприклад, «бульбашка»), а потім зробити по ньому прохід, порівнюючи сусідні елементи. Якщо вони не рівні, виконуємо підрахунок. Загальна кількість чисел, що входять у послідовність по одному разу, буде на одиницю більша, ніж отримане число в лічильнику.
Program Example_342_l ;
Uses crt;
Const N = 100;
Type Masiv = array[1..N] of real;
Var AMasiv; {A — масив для вихідної послідовності}
і,j,countbyte; {і,j - змінні циклу, count - кількість елементів, що входять у послідовність один раз}
k integer; {к - змінна, що коригує праву границю сортування}
FlagBoolean; {Flag - змінна, що фіксує, чи була перестановка}
Begin
Randomize;
Clrscr;
For i=1 to N do
Begin
A[i]=random(300)/ll-random*15;
Write(A[i]82);
End;
k=1;
Repeat
Flag=false;
For i=1 to N-k do
Begin If A[i]<A[i+l] then
begin {Обмін елементів масиву через третю змінну}
Rez=A[i]; А[і]=А[і+1]; A[i+1]=Rez;
Flag=true;
end;
k=k-1;
End;
Until Flag = false;
count=0;
For i=1 to N-1 do
Begin If A[i]OA[i+l] then count =count+1; End;
count=count+l;
Writeln;
Write (‘Кількість елементів, що входять у послідовність 1 paз ‘) ;
Writeln(count);
Readkey;
End.
Домашнє завдання
• Задача №339(2), №342(3,5), №367

УРОК 28. Поняття рядкової величини

Мета уроку. Дати поняття рядкових величин, вказівок та функцій опрацювання рядкових величин.


Теоретичний матеріал
Рядок—це послідовність символів кодової таблиці комп’ютера (ASCII таблиця). При використанні у виразах рядок береться в одинарні лапки.
Кількість символів у рядку (довжина рядка) може динамічно змінюватися від 0 до 255. Для опису даних рядкового типу використовується ідентифікатор string, за яким вказується в квадратних дужках значення максимально допустимої довжини даного рядка. Якщо значення не вказується, то вважається, що довжина рядка складає 255 байт.
Змінну рядкового типу можна визначити безпосередньо в розділі опису змінних. Рядкові дані можуть використовуватися в програмі також у якості констант. Опис рядкового типу встановлює максимальну кількість символів, що може їх вмістити рядок.
Формат опису
var
«ідентифікатор, . . . > string [<махсимальна довжина рядка>] ;
Приклад
ST string; {опис рядка довжиною 255 символів (відсутня довжина рядха в описі)}
ST1 string[50]; {опис рядка довжиною 50 символів)
Вирази, в яких операндами служать рядкові дані, називаються рядковими. Вони складаються із рядкових констант, змінних, покажчиків функцій і знаків операцій. Над рядками дозволяється виконувати операції зчеплення й операції відношення.
Операція зчеплення (+) застосовується для з’єднання кількох рядків в один результуючий рядок. Наприклад, ‘П’ +’ Е’ +’ О’ +’ М’ в ‘ПЕОМ’
Довжина результуючого рядка не повинна перевищувати 255 символів.
Операції відношення (=, <, >, о, <=, >=) здійснюють порівняння двох рядкових операндів і мають пріоритет нижчий, ніж операції зчеплення. Порівняння рядків робиться зліва направо до першого не співпадаючого символу. Більшим вважається той рядок, в якого перший неспівпадаючий символ буде мати більший номер у кодовій таблиці ASCII. Якщо рядки мають різну довжину, але в загальній частині збігаються, вважається меншим той рядок, у якого довжина менша. Рядки вважаються рівними, якщо вони рівної довжини і містять однакові символи.
Для присвоєння рядковій змінній значення результату рядкового виразу використовується оператор присвоювання (=). Якщо довжина змінної після виконання оператора присвоювання перевищує максимально допустимий при описі розмір, усі зайві символи праворуч усікаються (тобто втрачаються!). Допускається змішування в одному виразі операндів рядкового і літерного типів. Якщо при цьому літерній змінній присвоюється значення рядкового типу, довжина рядка має дорівнювати одиниці, інакше виникає помилка виконання. До окремих символів у рядку можна звернутися за номером (індексом) даного символу в рядку. Індекс визначається виразом цілого типу, що записується в квадратних дужках за ідентифікатором рядкової змінної або константи. Для обробки рядкових даних використовуються наведені нижче стандартні процедури та функції.
Процедури для роботи з рядками.
Delete(Str,Poz,N) — вилучення N символів рядка Str, починаючи з позиції Poz. Якщо Poz>255, виникає програмне переривання.
Insert(Strl,Str2,Poz) —вставка рядка Strl у Str2, починаючи з позиції Poz.
Str(Number,St) — перетворення числового значення величини Number і занесення результату в рядок St. Після Number може записуватися формат, аналогічний формату виведення. Якщо у форматі зазначена недостатня кількість розрядів, поле виведення розширюється до потрібної довжини.
Значення Number
Вираз
Результат
1500
Str(Number6,Str)
‘___1500’
4.8Е+03
Str(Number10,Str)
‘_____4800’
76854
Str(-Number3,Str)
‘-76854’
Val(St,Number,Cod) — перетворює значення St у величину цілого або дійсного типу і розміщує результат у Number. Значення St не повинно містити зайвих пробілів на початку і наприкінці рядка. Cod —ціла змінна, значення якої не дорівнює нулю, якщо під час перетворення виявлена помилка. Cod буде містити номер позиції першого помилкового символу, a Number не буде визначено.
Значення Str
Вираз
Результат
‘1450’
val(Str,Number,Cod)
1450 Cod=0
‘14.2Е+02’
val(Str,Number,Cod)
1420 Cod=0
‘14.5А+01’
val(Str,Number,Cod)
? Cod=5
Функції для роботи з рядками.
Lenght(St) — обчислює поточну реальну довжину в символах рядка St. Результат має цілий тип.
Copy(St,Poz,N) — копіює з St підрядок довжиною N символів, починаючи з позиції Poz. Якщо Poz > Lenght(St), то результатом буде пробіл; якщо Poz > 255, то виникне помилка при виконанні.
Pos(St1,St2) — виявляє першу появу в рядку St2 рядка St1. Результат має цілий тип і дорівнює номеру тієї позиції, де знаходиться перший символ рядка St1. Якщо в St2 рядок St1 не знайдений, результат дорівнює 0.
UpCase(Ch)—перетворює малу літеру на велику. Параметр і результат мають літерний тип. Обробляються тільки літери латинського алфавіту.
ЗАДАЧА № 377
Умова Нехай дано деякий текст. Обчислити, скільки разів повторюється наперед заданий символ а.
Розв ‘язання. Дня розв’язання задачі, по-перше, необхідна рядкова величина для зберігання тексту (для зберігання великого тексту можна зарезервувати масив). Для спрощення задачі будемо вважати, що текст має довжину не більше 255 символів, тобто для його зберігання достатньо одного рядка. Крім цього, нам необхідна змінна символьного типу для зберігання заданого символу а, кількість яких ми будемо обчислювати.
Оскільки рядок фактично можна вважати масивом символьних величин, для його обробки необхідно організувати цикл від першого до останнього символу рядка (length(St)), що буде переглядати кожен елемент рядка та порівнювати його з шуканим символом. У випадку збігу елементів, що порівнюються, лічильник збільшується на одиницю.
Програма, що реалізує описаний алгоритм, має наступний вигляд
Program Example_377;
Uses crt;
Var і,countword;
{і — змінна циклу, count — кількість знайдених символів}
achar; {a — шуканий символ}
Ststring; {St — даний текст}
Begin
Clrscr;
Write(‘Введіть текст ‘);
Readln(St);
Write(‘Введіть шуканий символ ‘);
Readln(a);
Count=0; (Початкове значення лічильника}
For i=1 to length(St) do
If St[i] = a Then count=count+l;
Writeln(‘Шуканих символів в тексті ‘,count);
Readkey; {Затримка зображення на екрані}
End.
ЗАДАЧА № 381
Умова У даному тексті замінити всі символи «» на символи «-» і навпаки.
Розв‘язання. Для виконання заміни в тексті одного символу іншим слід знайдений символ (або групу символів) спочатку вилучити процедурою insert, а потім з тієї ж самої позиції вставити бажаний символ (або групу символів). Зверніть увагу на те, що команди розгалуження повинні бути обов’язково вкладеними, тому що якщо ми знайдемо символ «»і виконаємо заміну, то на його місці з’явиться символ «-», який теж підлягає заміні (для символу «-» міркування будуть такими самими).
У результаті текст після закінчення роботи програми відтвориться у початковому вигляді. Програма має вигляд
Program Example_381;
Uses crt;
Var іword; {і - змінна циклу} Ststring; {St - даний текст}
Begin
Clrscr;
Write(‘Введіть текст ‘);
Readln(St);
For i=1 to length(St) do
If St[i] = ‘’ Then
Begin Delete (St, i, 1) ; Insert (‘-’St,1) ; End
Else
If St[i]=’-’ Then
begin Delete(St,i,1); Insert(‘’,St,1); end;
Writeln(‘Результуючий рядок ‘,St);
Readkey;
End.
ЗАДАЧА №382
Умова У даному тексті замінити всі символи «.» на послідовність символів «...». Якщо у тексті зустрічаються підряд три крапки, то залишати їх без змін.
Розв’язання В цій задачі після виконання замін збільшується довжина рядка, причому після шуканого символу становиться такий самий. Тому, якщо цикл організувати, як і в попередньому випадку, весь текст, починаючи з першої крапки, замшиться на крапки (подумайте чому). Тому в цій задачі доцільно скористатися циклом з передумовою, що дозволяє змінну циклу змінювати на будь-який крок (а не тільки на одиницю, як в циклі з параметром). Для того, щоб не виконувати заміну у випадку наявності трьох крапок в тексті, будемо перевіряти не тільки поточну, а й наступну за нею позицію (не забудьте при цьому про можливість виходу за межі рядка!!!). Останній символ рядка тут перевірятиметься окремо.
Зверніть увагу, що у випадку, коли довжина результуючого рядка буде складати більш ніж 255 символів, зайві символи будуть втрачатися. Для спрощення задачі ми їх не враховуємо, але для сильних учнів можна запропонувати організувати збереження цих символів у додатковому рядочку. Програма, що реалізує описаний алгоритм, має вигляд
Program Example_382 ;
Uses crt;
Var iword; {i - змінна циклу} St string; {St — даний текст}
Begin
Clrscr;
Write(‘Введіть текст ‘);
Readln(St); i=1;
While i<length(St) do
Begin
If (St[i]=’.’) and (St[i+1]<>’.’) Then
begin Insert(*..’,St,i+l); i=i+2; end;
i=i+1;
End;
If St[length(St)]=’.’ Then St=St+’..’;
Writeln(‘Результуючий рядок ‘,St);
Readkey;
End.
Домашнє завдання
• Прочитати сторінки 120—123 запропонованого підручника;
• Задачі № 378, № 380, № 385, № 389.

УРОК 29. Робота з рядковими величинами

Мета уроку навчити розв’язувати задачі з використанням рядкових величин.


На початку уроку бажано провести опитування (письмово чи усно) по матеріалах попереднього уроку (означення та опис рядкових величин, стандартні процедури та функції для роботи з рядковими величинами). Далі рекомендується розглянути задачі з обробки рядкових величин.
ЗАДАЧА № 387
Умова Перевірити, чи однаково читається дане слово зліва направо і навпаки.
Розв’язання Для розв’язування цієї задачі слід спочатку отримати новий рядок, який є оберненим відносно даного, а потім порівняти даний та отриманий рядки. Якщо вони збігаються, слово—паліндром (читається в обох напрямках однаково, наприклад, «дід», «потоп», «Пилип» тощо), у протилежному випадку - ні. Програма, що реалізує алгоритм, має вигляд
Program Example_387;
Var іbyte; {і - змінна циклу}
St,Rezstring; {St - даний текст, Rez - результуючий (перегорнутий) рядок}
Begin Clrscr;
Write(‘Введіть текст ‘);
Readln(St);
Rez= ‘’; {Очищення рядка}
For і- length(St) downto 1 do
Rez = Rez+St[i]; {Перегортання рядка}
If Rez = St Then Writeln(‘Слово є паліндромом.’)
Else Writeln(“Слово не є паліндромом.’);
Readkey;
End.
ЗАДАЧА №389 (2)
Умова Визначити, скільки разів у даному тексті зустрічається послідовність символів «абв».
Розв’язання Організовуємо прохід по рядку за допомогою циклу з параметром, причому враховуємо, що слід перевірити три послідовно розташованих символи (зверніть увагу на можливість виходу за межі рядка!). Один з методів вибору кількох послідовних символів уже розглядався раніше (і-ий, і+1-ий та і+2-ий елементи), тому розглянемо інший метод, що полягає у використанні функції копіювання Copy. Нагадуємо, що ця функція містить у якості параметрів вихідний рядок, номер початку копіювання (виділення) та кількість вибраних символів, тобто для вибору трьох символів з будь-якого місця рядка Л ця функція буде мати вид
Cоpy(St,i,3) .
Порівнюючи виділені (скопійовані) символи з еталоном, нарощуємо лічильник при виконанні поставлених умов. Програма має вигляд
Var іbyte; {і - змінна циклу}
Ststring; {St - даний текст}
Countbyte; {Count - лічильник послідовностей}
Begin
Clrscr;
Write(‘Введіть текст ‘);
Readln(St);
Count=0; {Початкове значення лічильника}
For i=1 to length(St)- 2 do
If Copy(St,i,3) = ‘абв’ Then count=count+1;
Writeln(‘Кількість шуканих послідовностей ‘,count);
Readkey;
End.
ЗАДАЧА № 394
Умова Нехай дано формулу. Визначити коректність формули щодо кількості відкритих та закритих дужок. Вважається, що закриті дужки не стоять перед відкритими. Якщо дужки у формулі відсутні - повідомити про це.
Розв’язання Для визначення коректності формули слід підрахувати кількість відкритих та закритих дужок, причому баланс дужок вважається вірним не тільки якщо ці значення дорівнюють одне одному, а й якщо відкрита дужка передує закритій. Останнє перевіряється тим, що кількість відкритих дужок має завжди бути більшою або рівною кількості закритих.
Звідси випливає, що для розв’язку даної задачі зручно скористатися циклом з передумовою, який буде слідкувати за досягненням кінця рядка, та відслідковувати правильність розташування відкритих та закритих дужок.
Щоб визначити, чи є в формулі дужки взагалі, достатньо перевірити на нуль кількість одних чи других дужок. Визначимо змінні count_left та count_right як кількість відповідно лівих (відкритих) та правих (закритих) дужок, тоді програма, що реалізує описаний алгоритм, має вигляд
Program Example_394;
Var іbyte; {і - змінна циклу}
Ststring; {St - даний текст}
count_left, count_rightbyte; {count_left - лічильник лівих дужок, count_right - лічильник правих дужок}
Begin
Clrscr;
Write(‘Введіть формулу ‘);
Readln(St);
Count_left=0; {Початкове значення лічильника)
Count_right=0;
і= 1;
While (i<=length(St)) and (Count_left>=Count_right)) do
Begin
If St[i] = ‘(‘ Then count_left=count_left+1;
If St[i] = ‘)’ Then count_right=count right+1;
і =i+l ;
End;
If (oount_left=0) and (count_right=0)
Then wrіteln(ЛФормула не має дужок.’)
Else
If count_left=count_right then Writeln( ‘Формула коректна’)
else writeln(‘Формула не коректна.’);
Readkey;
End.
Домашнє завдання
• Повторити сторінки 120—123 запропонованого підручника;
• Задачі № 384 (1), 388, 389 (1,3,4), 390, 396, 399,406 (1,2,4).
1   2   3   4   5   6   7   8   9


База даних захищена авторським правом ©refs.in.ua 2016
звернутися до адміністрації

    Головна сторінка