Урок 69                                                                        Інформатика (АП)

Розв’язування задач на опрацювання рядкових величин.

Мета.

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

Розвиваюча. Розвивати логічне мислення, навички створення програм, самостійність, вміння застосовувати набуті знання до практичних завдань.

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

Тип уроку. Засвоєння нових вмінь і навичок.

Матеріали для роботи з учнями:

        Приклади розв’язування задач.

        Приклади розв’язування задач.

        Приклади розв’язування задач.

План

1. Перевірка домашнього завдання.
2. Актуалізація опорних знань.
3. Розв’язування задач.
4. Типові запитання до уроку.
5. Домашнє завдання.

Пам’ятка для учня!

1. Пригадайте правила техніки безпеки при роботі з ПК.
2. Через кожні 15 хв. виконуйте вправи для очей та для зняття м’язової втоми.

Хід уроку

1. Організаційний момент.

2. Перевірка домашнього завдання.

1. Наявність.
2. Питання.

3. Актуалізація опорних знань.

1. Презентація.
2. Опитування.

1. Чим відрізняється символьне значення від рядкового?
2. Поясніть структуру збереження в пам 'яті значення ряд­кової змінної.
3. Що таке довжина рядка? Як її визначити?
4. Які операції можна виконувати з символьними даними?
5. Як можна виконати злиття рядків?
6. За допомогою яких засобів можна отримати підрядок заданого ря­дка? Поясніть на прикладі.
7. Як можна видалити підрядок із заданого рядка? Поясніть на прикладі.
8. Як виконується вставка підрядка в заданий рядок? Поясніть на прикладі.
9. Як можна перетворити рядок у число і навпаки? Чи завжди ці опе­рації можливі? Поясніть на прикладі.
10. Обчисліть значення функцій:

а) chr(90);                       б) ord('z') - ord('y');                      в) ord(chr(13));

г) upcase('a');           д) upcase('A')

11. У аг. X, і: Byte; А, В, С: String; Знайдіть помилки:

а) A:=Length (В);

б) B:=Delete (А, X, І);

в) Insert (А, X, І).

12. Яких значень набудуть змінні після послідовного виконання опера­торів, якщо початкові значення А:='ми '; В:='вивчаємо'; С:='ТП';

а) С:=А+С+В;                                                    С-?

б) Х:= Length (С);                                            Х-?

в) В:= Copy (С, 4, 1) + Copy (С, 9,3); В-?

г)  Delete (С, З, 3);                                          С-?

д) Insert ('Не', С, 6);                                        С-?

е) Х:= Pos ('e'f С);                                             Х-?

є) For і:=1 То Length (С) Do If С[і]='е' Then Х:= Х+1; Х-?

4. Розв’язування задач на опрацювання рядкових величин.

Стандартні прийоми обробки рядків засновані на аналогії між рядком та одновимірним масивом символьних величин. Розглянемо методи обробки рядків на прикладі задач шифрування і дешифру­вання текстів.

Задачі шифрування

З давніх часів люди відчували потребу якось зашифровувати послання. Юлій Цезар був першим, про кого відомо, що він приду­мав власне шифр. Алфавіт розміщується на колі за годинниковою стрілкою (при цьому в українському алфавіті після А йде Б, а після Я - А). Для зашифровки букви тексту замінюються буквами, що стоять далі по колу на задане число позицій за годинниковою стріл­кою. Якщо, скажемо, вибране зміщення на 3, то замість і-тої букви використовується (і+3)-я буква. При розшифровці, навпаки, беруть букву, розміщену на задане число букв проти годинникової стрілки.

Шифр Цезаря розшифрувати легко. Відомі імовірності появи букв pі i=1..n, у мові повідомлення (n - число букв в алфавіті). По­рахуємо частоти появи кожної з букв fi в зашифрованому повідомленні. Якщо воно не дуже коротке, то fi повинні порівняно добре узгоджуватися з pі:fi=pі. Потім починаємо робити перебір по зміщеннях. Коли зміщення не вгадане, загальне розходження між pі i fi,  яке дорівнює

буде великим, а коли зміщення вгадане - малим. Мінімізація (s) по всіх s=1,2,...,n дає ключ до розшифровки коду Цезаря.

Пізніше були вигадані інші, набагато важчі для зламу ши­фри. Термінологія тут така: законний адресат розшифровує повідомлення, а «ворог», не маючи ключа, зламує шифр. Ство­рення шифрів і законне ними користування - це об'єкт криптографії, злам шифрів - це криптоаналіз, криптологія ж поєднує криптографію і криптоаналіз. Криптоаналіз заснований на використанні теорії чисел і теорії порівнянь і практично не­можливий без використання комп'ютера.

Але й робота шифрувальників - чисто автоматична. Виходить, її можна доручити комп'ютеру. До того ж, як відомо, професіонали прагнуть зменшити кількість людей, що знають ключ до шифру.

Розглянемо найпростіші способи шифрування текстів.

Приклади алгоритмів шифрування

Приклад11. Шифр Цезаря. Метод шифрування полягає у виборі цілого числа n від 1 до 32. Потім у повідомленні кож­на буква замінюється на букву, що стоїть від неї на n букв праворуч. Для того, щоб імітувати зсув букв по колу на п букв, буква з номером к замінюється на букву з номером m, що обчи­слюється за формулами:

Алгоритм шифрування:

• задається «коло» - рядок А, що містить букви українського ал­фавіту, кому і пробіл;
• з клавіатури вводиться S - рядок, який треба зашифрувати, і n - значення зсуву;
• рядку S1, у якому буде формуватися зашифроване повідом­лення, присвоюється значення порожнього рядка;
• для кожного символу рядка S обчислюється К - позиція симво­лу S [i] у рядку А.
• якщо n+k<=33, то до рядка S1 додається символ A[k+n], інак­ше - символ A [k+n-33].

Завдання. Зашифрувати фразу зі зсувом N=3:

"о, відкриттів чудових скільки”

Програма шифрування:

   Const А = 'абвгдеєжзиіїйклмнопрстуфхцчшщьюя, 1;

   Var 5,S1: String; N, к, і : Integer;

Begin

  WriteLn ('введіть значення зсуву=> ');   ReadLn (N);

  WriteLn ('введіть повідомлення для шифрування=> ');

  ReadLn (S);

  S1:=";

  For і:=1 То Length(s) Do Begin

K:= Pos (S[i],A);

if N+K<=33 Then Sl:= Sl+A[K+N]

Else Sl:=Sl+A[K+N-33]

      End;

WriteLn (S1);

ReadLn

End.

Результат: свгекжнуйххкегьцжсейшгфнко,нй

Для дешифрування до програми вносимо зміни:

WriteLn ('введіть повідомлення для дешифрування^');

ReadLn(S);

S1: = ";

{А - рядок, що містить літери українського алфавіту, кому і пробіл}

For і:=1 То Length(s) Do Begin

K:=pos (s[i], A);

If K-N>0 Then S1:= Sl+A[K-N] Else S1:=Sl+A[K-N+33]

     End;

Приклад 12. Заміна кодами. Метод шифрування оснований на тому,лцо у пам'яті машини символи зберігаються у вигляді цілих чисел (кодів символів). У таблиці кодів 256 значень (0..255). За до­помогою функції Ord можна одержати код символу, тим самим зашифрувавши текст послідовністю АSCII-кодів.

Алгоритм шифрування:

• з клавіатури вводиться S - рядок, який треба зашифрувати;
• рядку S1, у якому буде формуватися зашифроване повідом­лення, присвоюється значення порожнього рядка;
• для кожного символу рядка S обчислюється код символу 0rd(S[i]) і перетворюється в рядок S2 за допомогою про­цедури Str.
• до рядка S1 додається рядок S2 і пробіл.

Завдання. Зашифрувати фразу

"готує Майкрософта дух".

Програма шифрування:

Var S, Sl, S2 : String; N, K, і : integer;

Begin

  ReadLn (S);

  S1: = ";

  For i:=l To Length (S) Do Begin Str (Ord (S[i]), S2);

                                                        S1:= S1+S2+' ';

End;

   WriteLn (Sl)

End.

Результат:

131 174 226 227 243 32 140 160 169 170 224 174 225 174 228 226 160 32 164 227 229

Алгоритм дешифрування:

• з клавіатури запитується S - зашифрований рядок, що склада­ється з кодів і пробілів між ними;
• рядку S1, у якому буде формуватися вихідне повідомлення, присвоюється значення порожнього рядка;
• переглядається рядок S; якщо S[i] містить цифру, то вона до­дається до підрядка S2; якщо S[i] дорівнює пробілу, то підрядок S2 перетворюється в число п процедурою Val;
• до рядка Sl додається символ, код якого дорівнює n.

Внесення змін у програму для дешифрування:

WriteLn ('введіть зашифроване повідомлення=>');

ReadLn (S);   S1: = ";

For і:=1 То Length (S) Do

if S [і] о ' ' Then S2:= S2+S[i]

Else Begin

Val (S2, N, K);

S1:=Sl+Chr (N);

S2: = ";

End;

WriteLn (S1);

Приклад 13. Кодування за ключовою фразою. Вибирається ключова фраза, тобто фраза, у якій є всі букв^і алфавіту, розділові знаки і пробіл. Кожен символ даного тексту замінюється на номер цього символу в ключовій фразі. Отриманий набір чисел передаєть­ся адресату, який за номерами букв у ключовій фразі відновлює вихідний текст.

Алгоритм шифрування:

• задається ключова фраза - рядок А;
• з клавіатури запитується S - рядок, який треба зашифрувати;
• рядку Sl, у якому буде формуватися шифроване повідомлення, присвоюється значення порожнього рядка;
• для кожного символу рядка S обчислюється К - позиція пер­шого входження S [і ] у рядок А;
• число К переводиться в рядок S2 за допомогою процедури Str;
• дофядка Sl додається рядок S2 і пробіл.

Завдання: зашифрувати повідомлення

"Та Інтел, син складних помилок,"

Програма шифрування:

Const        А =

'...чи   вмію  я   знаходити   за  допомогою електронно-обчислювальної   машини   значення   функцій, а  ще також об'єми багатогранників?!’;

Var S, Sl, S2 : String; N, K, i: integer;

Begin

    WriteLn ("введіть повідомлення для шифрування=> ');

    ReadLn (S);

    S1:-";

    For i:=l To Length (s) Do Begin

                                    K: = Pos (S[i], A); Str (K, S2); Sl:= S1+S2+' ';

End;

  WriteLn (S1)

End.

Результат:

21 16 6 9 15 21 37 38 86 6 52 5 15 6 52 40 38 16 19 15 5 8 6 29 18 8 5 38 40 16 8 86

Алгоритм дешифрування:

• з клавіатури вводиться К - кількість кодів у шифрованому рядку;
• з клавіатури вводиться К кодів N шифрованого повідомлення;
• символ ключової фрази S2 з номером N додається до рядка S1.

Внесення змін у програму для дешифрування:

For і:=1 То к Do Begin

ReadLn (N); S1:=S1+S2[N]

End;

WriteLn (Sl);

Приклад 14. Заміна глухих приголосних на дзвінкі. Дуже легко перекладати з української мови на тарабарську, якщо кожен глухий приголосний замінювати відповідним йому дзвінким приго­лосним і навпаки. Голосні звуки, розділові знаки і пробіли не змінюються. Одна й та сама програма підходить і для шифрування, і для дешифрування.

Алгоритм шифрування:

• задаються S2 - рядок, що містить дзвінкі приголосні звуки українського алфавіту, S3 - рядок, що містить глухі при­голосні;
• з клавіатури вводиться рядок S - секретний текст;
• рядку Sl, у якому буде формуватися шифроване повідомлення, присвоюється значення порожнього рядка;
• для кожного символу рядка S обчислюється К2 - позиція сим­волу S [і ] у рядку S2, і КЗ - позиція символу S [і ] у рядку S3;
• якщо буква позначає дзвінкий приголосний, то К2<>0, К3=0, до рядка Sl додається символ "глухого" рядка S3 з номером К2;
• якщо буква позначає глухий приголосний, то КЗоО, К2=0, до рядка Sl додається символ "дзвінкого" рядка S2 з номером КЗ;
• якщо К2=0 і «3=0, то символ не позначає приголосного звуку і додається до рядка Sl, не змінюючись.

Завдання: розшифрувати фразу:

«і покцащт, бакаторзіф ткух».

Програма шифрування:

Var S, Sl, S2, S3 : String;

N, Kl, K2, КЗ, і : integer;

Begin

WriteLn ('введіть повідомленням ');        ReadLn (S);

S1: = ";   S2:= 'бвгджзлмнр1; S3:= 'пфхтшсцчщк';

For i:=l To Length (S) Do Begin

K2:= Pos (S[i],S2);

K3:= pos (S [i],s3);

If (K2=0) And (K3<>0) Then Sl:= Sl+S2[K3]

Else  If  (K2<>0) And (K3=0) Then Sl:=Sl+S3[K2] Else Sl:=Sl+S[i] 

End;

Writel n (S1);

ReadLn

End.

Результат: І Борланд, парадоксів друг.

5. Створення та реалізація програми.

Задача. Зашифрувати повідомлення способом вставки після кожного символу деякої букви.

1. Дана програма шифрування довільного тексту способом вста­вки після кожного символу однієї й тієї ж букви:

Var S,   sl: String;   к, і : Integer; a :Char;

Begin

WriteLn ('Повідомлення для шифрування => ');

ReadLn (s);

WriteLn ('Символ для вставки =>"’);

ReadLn (А); Sl:='';

К:= Length (S);

For і:=1 то K Do

Sl := Sl + S[i] + a;

         WriteLn (Sl);

End.

2. Змініть програму таким чином, щоб символ для вставки дода­вався після кожного другого символу даного тексту.
3. Змініть програму таким чином, щоб після кожного третього символу даного тексту додавався рядок В: Stri ng [3].
4. Змініть програму таким чином, щоб символ для вставки виби­рався випадковим чином: N:= Random (256); a:=Chr (N);
5. Додайте до програми блок дешифрування повідомлення, яке зашифроване шляхом вставки символу після кожного символу ви­хідного тексту.

WriteLn ('Повідомлення для шифрування => '); ReadLn (S1);

S:= ";

For і:=1 To Length (Sl) Do

If i Mod 2<>0 Then S:= S+Sl[l];

WriteLn (S);

6. Додайте до програми можливість вибору (шифрувати або роз­шифровувати) за допомогою меню.

6. Питання до уроку.

Var A,S,S1:string; і, К: integer; C:char;

Запишіть оператор, що реалізує таку дію:

1. Підрахувати кількість символів С в рядку S.
2. Змінній А присвоїти значення підрядка рядка S с 5-го символу по 8-й.
3. Видалити з рядка S 3-й символ.
4. Сформувати рядок S1, що виходить з рядка S видаленням кожно­го 2-го символу.
5. Сформувати рядок S1, що виходить з рядка S вставкою букви 'а' після кожного символу.
6. Визначити позицію першого входження підрядка S1 у рядок S.
7. S= 'паскаль'. Який рядок є зайвим ?

а) S1='паабсвкгадлеьж';

б) S1=’175 160 225 170 160 171 236';

в) S1='n17а65с34к22а12л34ь56'.

8. Яка операція є зайвою?

а) Copy (S,4,5);

б) Insert (S1,S,5);

в) Delete (S,4,5).

9. Запишіть оператор, який призведе до такої зміни рядка S:

а)   S='інформатика'; -> ? -> S='форма';

б)   S='інформатика'; -> ?  -> S=’інтика';

10. Розгадайте фразу і заповніть пропуски в програмі для її розшифрування:

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

1. Повторити “Рядкові величини”
2. Виконати вправу:

Вправа «Опрацювання рядкових даних»

1. Іноді хочеться щось сказати, але так, щоб ніхто нічого не зрозумів. Найкраще в таких випадках скористатися спеціа­льним шифром: вимовляти слова в зворотному порядку. Наприклад, слово "пилосос" вимовляється як "сосолип". Складіть програму шифрування таким методом слів украї­нської мови. Скористайтесь фрагментом програмного коду, який переписує рядок Sy рядок S1 в зворотному порядку:

S1:=’’;

For і:=Length(S) DowTo 1 Do S1:= S1 + S[i];

2. Змініть програму таким чином, щоб вона "шифрувала" сло­ва до тих пір, поки не введено порожній рядок (натиснуто Enter без введення символу)..

Repeat

{введення рядка S, формування і виведення рядка S1}

….................................................................

 Until S=’’;

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

Slovol, Slovo2 : Array [1..20] of string[20];

4. Слова речення S занесіть до масиву Slovol, а слова, які за­писані в зворотному порядку, занесіть до масиву Slovo2.

Для заповнення масиву Slovol скористайтеся таким фрагментом програмного коду:

і:=0;

Repeat

    K:=0; і:=і+1;

{копіювання частішії рядка S до розділового пробілу}

   K:=Pos (‘,’, S);

   Slovol[i]:=Copy (S, 1, K-l);

   Delete (S, 1, K);

Until K=0;

{занесення до масиву останнього слова рядка S}

N:=i;

Slovol[i]:=S;

5. Виведіть зашифроване речення (елементи масиву Slovo2) на екран.
6. Переконайтеся в тому, що ці ж програми придатні і для дешифрування.

6. Підготуватися до оцінювання.

«Опрацювання рядкових величин»

1. До якого типу даних можна віднести значення зазначених вели­чин та виразів?

а)        345;                               е) Pred ('D');

б)        7';                                є) Suce ('h');

в)        'abed1;                     ж) Pos ('2а', '32а');

г)         '123+34';                         з) upease (Т).

д)        Length ('56');

2. Яке значення буде мати змінна Z після виконання команд?

а) Z: = '34' + '34-4';

б) A: = 'abc'; D:='de'; Z:=Concat (D,А);

в) Х:=,123'; Y:='qwert'; Z:=Length (X)+Length (Y);

г)X:='-23.34'; Val (X,Z,Cod); Z:=Z+0.34;

д)  У:=255; Str (Y,R); Z:=Copy (R^^D+'OO1 ;

е)  N: = '3456'; Delete (N,3,2); insert ('lOl',N,2); Z:=Length (N);

є)S: = '9876503', R:=S[6]+S[6]+V+S[5]; Val (R,Z,cod).

3. Розглядаючи рядок як масив символів, запрограмуйте на Пас­калі такі процедури і функції:

a) Length;        б) Copy;   в) Pos;   г) Insert;   д) Delete.

4. Використовуючи для копіювання слово "інформатизація", скла­діть слова "цитата" і "заміна".
5. У заданому тексті замініть всі літери 'А' на літери 'О'.
6. У заданому тексті порахуйте загальну кількість букв 'Д' та 'К’.
7. У заданому тексті порахуйте кількість букв, які співпадають з першою буквою тексту.
8. Задано рядок символів. Переставте місцями першу половину рядка з другою. Наприклад: Л='123абв'; перетворений рядок Л='абв123'; Л='1234абв'; перетворений рядок Л='абв4123':
9. Визначте, чи є заданий рядок паліндромом. Паліндром - це текст, який читається однаково в прямому і зво-ротному поряд­ку (наприклад, «корок», «піп»)
10. Запишіть програму для розшифрування речення: «тутасю, чома в бете букі великі зати?»
11. Складіть програму для шифрування тексту шифром Цезаря при відомому значенні зсуву.
12. Практичне завдання. Var С: аггау[1. .6] of string [6];

Надрукуйте:

а)  усі слова зі списку, відмінні від 'привіт';

б) текст, що складається з останніх букв слів;

в)  усі слова зі списку, що містять рівно 2 букви 'д'.