ЗАНЯТТЯ 29. Робота з рядковими величинами

End.

Begin

Begin

End.

Else

Begin

End.

Begin

Var

End.

Repeat

Begin

Begin

End.

Begin

Begin

Begin

End.

Begin

Begin

Begin

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 Mas:array[1..N] of integer;

і,j,Rez:integer;

For i:=2 to N do

j:=i; {Цикл працює, доки лівий елемент більший за правий та доки не досягнуто початох масиву}

while (j>1) and (Mas[j]<Mas[j-1]) do

Rez:=Mas[j]; Mas[j]:=Mas[j-1]; Mas[j-1]:=Rez; j:=j-1;

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,B:Masiv; {A — масив для зберігання початкової послідовності, В — відсортований масив}

і,j,count:byte; {i,j — змінні циклу, count — кільхість елементів, що залишились на своїх місцях)

Max:real; {Мах — максимальний елемент підмасиву}

N_max:byte; {N_max — номер максимального елементу}

Begin Randomize;

Clrscr;

For i:=1 to N do

Begin A[i]:=random*100-random*50; Write<A[i]:8:2); End;

B:=A; {Копіювання елементів масиву А в масив В}

For i:=1 to N-1 do

Max:=B[i]; {Зберігання еталону максимуму}

N_Max:=i; {Зберігання номера максимуму}

For j:=i+1 to N do

If B[j]>Max then

Max:=B[j]; {Перевизначення еталону}

N_Max:=j; {Зберігання номеру еталону}

end;

{Обмін місцями мінімуму та першого елементу підмасиву}

B[N_Max]:=В[і]; В[і]:=Мах;

End;

count:=0;

For і:»1 to N do

If A[i]=B[i]

then count:=count+1;

End;

Writeln;

Writeln(‘Кількість елементів, що не змінили місця ‘,count);

Readkey;

ЗАДАЧА №342(1)

Умова: Дано натуральне число п та послідовність дійсних чисел а1, а2... ап. Визначити усі числа, що входять у послідовність по 1-му разу.

Розв ‘язання: Пошук чисел, що входять у послідовність по одному разу, виконати важко, тому що для цього необхідно порівняти кожне число з кожним. Набагато простіше зробити це у відсортованому масиві, оскільки однакові числа в ньому будуть розташовані поруч. Тобто пропонуємо в даній задачі спочатку відсортувати масив (метод сортування будь-який, наприклад, «бульбашка»), а потім зробити по ньому прохід, порівнюючи сусідні елементи. Якщо вони не рівні, виконуємо підрахунок. Загальна кількість чисел, що входять у послідовність по одному разу, буде на одиницю більша, ніж отримане число в лічильнику.

Program Example_342_l;

Uses crt;

Const N = 100;

Type Masiv = array[1..N] of real;

Var A:Masiv; {A — масив для вихідної послідовності}

і,j,count:byte; {і,j - змінні циклу, count - кількість елементів, що входять у послідовність один раз}

k: integer; {к - змінна, що коригує праву границю сортування}

Flag:Boolean; {Flag - змінна, що фіксує, чи була перестановка}

Randomize;

Clrscr;

For i:=1 to N do

A[i]:=random(300)/ll-random*15;

Write(A[i]:8:2);

End;

k:=1;

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;

Домашнє завдання:

• Задача №339(2), №342(3,5), №367

ЗАНЯТТЯ 28. Поняття рядкової величини

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

Теоретичний матеріал

Рядок —це послідовність символів кодової таблиці комп’ютера (ASCII таблиця). При використанні у виразах рядок береться в одинарні лапки.

Кількість символів у рядку (довжина рядка) може динамічно змінюватися від 0 до 255. Для опису даних рядкового типу використовується ідентифікатор string, за яким вказується в квадратних дужках значення максимально допустимої довжини даного рядка. Якщо значення не вказується, то вважається, що довжина рядка складає 255 байт.

Змінну рядкового типу можна визначити безпосередньо в розділі опису змінних. Рядкові дані можуть використовуватися в програмі також у якості констант. Опис рядкового типу встановлює максимальну кількість символів, що може їх вмістити рядок.

Формат опису:

«ідентифікатор,... >: 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	Вираз	Результат
	Str(Number:6,Str)	‘___1500’
4.8Е+03	Str(Number:10,Str)	‘_____4800’
	Str(-Number:3,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 і,count:word;

{і — змінна циклу, count — кількість знайдених символів}

a:char; {a — шуканий символ}

St:string; {St — даний текст}

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; {Затримка зображення на екрані}

ЗАДАЧА № 381

Умова: У даному тексті замінити всі символи «:» на символи «-» і навпаки.

Розв‘язання. Для виконання заміни в тексті одного символу іншим слід знайдений символ (або групу символів) спочатку вилучити процедурою insert, а потім з тієї ж самої позиції вставити бажаний символ (або групу символів). Зверніть увагу на те, що команди розгалуження повинні бути обов’язково вкладеними, тому що якщо ми знайдемо символ «:»і виконаємо заміну, то на його місці з’явиться символ «-», який теж підлягає заміні (для символу «-» міркування будуть такими самими).

У результаті текст після закінчення роботи програми відтвориться у початковому вигляді. Програма має вигляд:

Program Example_381;

Uses crt;

Var і:word; {і - змінна циклу} St:string; {St - даний текст}

Clrscr;

Write(‘Введіть текст: ‘);

Readln(St);

For i:=1 to length(St) do

If St[i] = ‘:’ Then

Begin Delete (St, i, 1); Insert (‘-’St,1); End

If St[i]=’-’ Then

begin Delete(St,i,1); Insert(‘:’,St,1); end;

Writeln(‘Результуючий рядок: ‘,St);

Readkey;

ЗАДАЧА №382

Умова: У даному тексті замінити всі символи «.» на послідовність символів «...». Якщо у тексті зустрічаються підряд три крапки, то залишати їх без змін.

Розв’язання: В цій задачі після виконання замін збільшується довжина рядка, причому після шуканого символу становиться такий самий. Тому, якщо цикл організувати, як і в попередньому випадку, весь текст, починаючи з першої крапки, замшиться на крапки (подумайте чому). Тому в цій задачі доцільно скористатися циклом з передумовою, що дозволяє змінну циклу змінювати на будь-який крок (а не тільки на одиницю, як в циклі з параметром). Для того, щоб не виконувати заміну у випадку наявності трьох крапок в тексті, будемо перевіряти не тільки поточну, а й наступну за нею позицію (не забудьте при цьому про можливість виходу за межі рядка!!!). Останній символ рядка тут перевірятиметься окремо.

Зверніть увагу, що у випадку, коли довжина результуючого рядка буде складати більш ніж 255 символів, зайві символи будуть втрачатися. Для спрощення задачі ми їх не враховуємо, але для сильних студентів можна запропонувати організувати збереження цих символів у додатковому рядочку. Програма, що реалізує описаний алгоритм, має вигляд:

Program Example_382;

Uses crt;

Var i:word; {i - змінна циклу} St: string; {St — даний текст}

Clrscr;

Write(‘Введіть текст: ‘);

Readln(St); i:=1;

While i<length(St) do

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;

Домашнє завдання

• Прочитати сторінки 120—123 запропонованого підручника;

• Задачі № 378, № 380, № 385, № 389.

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

На початку заняття бажано провести опитування (письмово чи усно) по матеріалах попереднього заняття (означення та опис рядкових величин, стандартні процедури та функції для роботи з рядковими величинами). Далі рекомендується розглянути задачі з обробки рядкових величин.

ЗАДАЧА № 387

Умова: Перевірити, чи однаково читається дане слово зліва направо і навпаки.

Розв’язання: Для розв’язування цієї задачі слід спочатку отримати новий рядок, який є оберненим відносно даного, а потім порівняти даний та отриманий рядки. Якщо вони збігаються, слово—паліндром (читається в обох напрямках однаково, наприклад, «дід», «потоп», «Пилип» тощо), у протилежному випадку - ні. Програма, що реалізує алгоритм, має вигляд:

Program Example_387;

Var і:byte; {і - змінна циклу}

St,Rez:string; {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;

Дата добавления: 2014-10-22