Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач icon

Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач




Скачати 45.12 Kb.
НазваДеркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач
Дата29.09.2012
Розмір45.12 Kb.
ТипЗадача

Деркач Надія Йосипівна,

вчитель інформатики

Чернівецького ліцею №1

математичного та

економічного профілів

Використання символьних множин при розв’язуванні олімпіадних задач

При проведенні олімпіад з інформатики зустрічаються задачі з використанням рядкових величин. Якщо рядкова величина містить не більше, ніж 256 символів, то для розв’язування таких задач зручно працювати із символьними множинами. Нагадаємо деякі функції для роботи з символьними змінними, а також операції з множинами.

Функція chr(i) повертає символ, порядковий номер якого в таблиці ASCII-кодів дорівнює і (і – ціле, результат – символ). Наприклад, chr(66)=’B’.

Функція ord(c) дає порядковий номер вказаного символу; с – символ, результат – цілий. Наприклад, ord(’B’)=66.

Функція succ(c) дає наступний для с символ. Наприклад, succ(’B’)= ’С’.

Функція UpCase(c) перетворює символ с з маленької літери на велику, всі інші символи залишає без змін. Наприклад, UpCase(’b’)= ’B’.

Операція входження елемента у множину:

<елемент> in <множина>.

Результат виконання – тип boolean.

А тепер розглянемо декілька задач.

Задача 1. (Всеукраїнська олімпіада з інформатики, 2004-2005 н.р. ІІ етап). Задано текст, який містить латинські літери, пробіли та розділові знаки

. , ! ? - : ;

Визначити, скільки різних символів використано для його запису. Вважати, що великі і маленькі літери не розрізняються, а текст складається не більше, ніж з 256 символів.

Наприклад, для запису тексту «This is correct test!» використано 10 різних символів.

Алгоритм

Якщо текст складається не більше, ніж з 256 символів, то працювати будемо зі змінними типу string i set of char. Сформуємо символьну множину, в яку запишемо всі символи заданого тексту, перетворивши перед цим всі маленькі латинські літери на великі за допомогою функції UpCase. Далі, переглянувши в циклі всі літери від ’A’ до ’Z’, обчислимо кількість літер, що належать утвореній множині. Окремо перевіримо входження у множину розділових знаків та символу «пробіл» і додамо їх кількість до обчисленої вже кількості літер.

Програма

Program count_symbol;

Var t : string; i, k : byte; c : char; s : set of char;

begin

readln(t); s := []; k := 0;

for i := 1 to length(t) do

begin

t [ i ] := UpCase ( t [ i ] );

s := s + [ t [ i ] ] ;

end;

for c := ’A’ to ’Z ’ do

if c in s then inc(k);

if ’ ’ in s then inc(k);

if ’.’ in s then inc(k);

if ’,’ in s then inc(k);

if ’!’ in s then inc(k);

if ’?’ in s then inc(k);

if ’-’ in s then inc(k);

if ’:’ in s then inc(k);

if ’;’ in s then inc(k);

writeln(k);

end.

Задача 2. Шифр Цезаря. (Всеукраїнська олімпіада з інформатики, 2006-2007 н.р. ІІ етап). Відомий римський полководець Гай Юлій Цезар використовував спеціальний шифр для кодування своїх повідомлень. Шифр полягав у тому, що кожна літера латинського алфавіту з повідомлення замінялась на зсунуту на три позиції за алфавітом, наприклад, літера ’a’ замінялась на літеру ’d’, а літера ’z’ на літеру ’c’. Потрібно написати програму, яка б зашифровувала у повідомленні всі маленькі латинські літери, залишаючи решту символів без змін.

^ Вхідні дані: В єдиному рядку файла caezar.dat знаходиться текст, який треба зашифрувати. Довжина тексту для кодування не перевищує 10000 символів.

Вихідні дані: В файлі caezar.sol знаходиться зашифрований текст.

^ Приклади вхідних та вихідних файлів:

caezar.dat

caezar.sol

you remember

brx uhphpehu

Алгоритм

Комп’ютер дуже підходить для шифрування і розшифровки текстів. Є багато способів шифрування. Один з найпростіших – шифр Цезаря. Щоб знайти шифр символу с, треба виконати такий оператор:

if c = 'x' then c := 'a' else

if c = 'y' then c := 'b' else

if c = 'z' then c := 'c' else

c := succ(succ(succ(c)));

Але те ж саме можна здійснити за допомогою одного оператора присвоювання:

с := chr ( ( ord ( c ) – ord ( 'a' ) + 3 ) mod 26 + ord ( 'a' ) );

Цей оператор більш універсальний: напишемо замість константи 3 будь-яку іншу константу і одержимо новий шифр. 26 – кількість літер латинського алфавіту.


Програма

program Caezar;

var c : char; i : integer; f1, f2 : text; s : set of char;

begin

assign ( f1, 'caezar.dat' ); reset ( f1 );

assign ( f2, 'caezar.sol' ); rewrite ( f2 );

s := [ 'a'..'z' ];

while not eof ( f1 ) do

begin

read ( f1, c );

if c in s then

c := chr ( ( ord ( c ) – ord ( 'a' ) + 3 ) mod 26 + ord ( 'a' ) );

write ( f2, c );

end;

writeln ( f2 );

close ( f1 );

close ( f2 );

end.

Спробуйте скласти програму для розшифровки тексту, зашифрованого за допомогою коду Цезаря.

Схожі:

Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач iconУроки з інформатики та математики у знз
Зелінська Олена Петрівна, вчитель інформатики Кельменецького ліцею, спеціаліст вищої категорії, вчитель-методист
Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач iconМетодичні рекомендації щодо розв`язання олімпіадних задач з програмування
Часто трапляється, що розв’язуючи задачу з програмування доводиться розглядати декілька випадків у залежності від вхідних даних,...
Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач iconРозв`язок олімпіадних завдань ( типу „ситуаційні задачі”)
Вони сприяють правильній організації мислення, що прискорює розв`язок задач, на відміну від „стихійного” методу розв`язку
Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач iconТ. Г. Шевченка Програма вступного випробування з хімії для вступу на навчання для здобуття освітньо-кваліфікаційного рівня "бакалавр" Пояснювальна записка
При розв'язуванні розрахункових задач дозволяється користуватись мікрокалькулятором
Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач iconПередмова
Методи варіаційного числення знаходять широке застосування в різних галузях науки та виробництва при постановці та розв'язуванні...
Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач iconБаранецька Оксана Георгіївна, вчитель інформатики Чернівецького ліцею №3 медичного профілю одномірні масиви
Для зберігання та обробки в програмах складних видів даних використовують структуровані типи. Вони утворюються об’єднанням простих...
Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач iconІнститут інформатики пропонує вступ у 2014 році на державну і контрактну форми навчання
Спеціаліст інформатики, вчитель інформатики, адміністратор навчальних комп’ютерних систем, вчитель математики, економіки, фізики,...
Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач icon«Основи математичного моделювання фінансових потоків економічних агентів транзитивної економіки»
Аукових досліджень, під час виконання магістерських дипломних та дисертаційних досліджень, оволодіння сучасними програмними засобами...
Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач iconМіністерство освіти і науки, молоді та спорту України Східноєвропейський національний університет імені Лесі Українки
Лесі Українки у 2013 р складається з трьох розділів. Перший з них містить перелік основних математичних понять і фактів, якими повинен...
Деркач Надія Йосипівна, вчитель інформатики Чернівецького ліцею №1 математичного та економічного профілів Використання символьних множин при розв’язуванні олімпіадних задач iconЗакон розподілу функції випадкових величин
Тому при розв’язуванні задач такого типу необхідно знати закони розподілу випадкових величин, що фігурують в постановці задачі. Звичайно...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи