1. Повторити теоретичний матеріал Основи програмування мовою pascal



Скачати 117.95 Kb.
Дата конвертації20.11.2016
Розмір117.95 Kb.

Школа олімнійського резерву ВІППО 23.05.2008

Завдання на літня канікули



1.Повторити теоретичний матеріал

Основи програмування мовою PASCAL

Тема 1. Мова програмування TURBO PASCAL

Поняття про мови програмування, їх класифікація. Мова програмування TURBO PASCAL. Середовище програмування. Можливості використання вбудованого редактора. Структура програми мовою TURBO PASCAL. Операції виведення. Постійні та змінні величини. Типи постійних i змінних величин. Операції введення-виведення та присвоєння. Стандартні математичні операції та функції. Запис математичних виразів. Оформлення екрану при роботі з програмою. Коментарі в програмі.

Тема 2. Базові структури мови програмування

Оператори управління. Оператор розгалуження та безумовного переходу. Проста і складена умови.

Оператор множинного вибору. Цикли. Організація циклів.



Тема 3. Робота з файлами

Текстові файли. Опрацювання текстових файлів.

Тема 4. Структуровані типи даних

Масиви. Одновимірний масив. Опрацювання елементів одновимірного масиву. Двовимірний масив. Опрацювання елементів двовимірного масиву. Організація пошуку елементів із заданими властивостями в масивах. Найпростіші алгоритми сортування масивів: метод “бульбашки”, метод прямої вибірки.

Рядкові дані. Процедури та функції опрацювання рядкових величин. Записи. Масиви записів.



Тема 5. Процедури та функції

Підпрограми. Процедури в мові TURBO PASCAL. Структура процедури. Підпрограми-функцiї. Структура функції. Поняття рекурсії.

Тема 6. Динамічне виділення пам’яті

Потреба у динамічному виділенні пам’яті. Виділення та звільнення пам’яті. Контроль за виділенням пам’яті.

Задачі на опрацювання великих обсягів даних. Опрацювання лінійних і двовимірних масивів невідомого розміру.



Тема 7. Опрацювання довгих чисел

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

Тема 8. Елементи обчислювальної геометрії

Основні формули аналітичної геометрії. Знаходження довжини відрізку в n-вимірному просторі. Відстань від точки до прямої. Координати точок перетину відрізків і прямих. Рівняння прямої, кола, площини.

Знаходження площі багатокутника. Метод триангуляції. Метод трапецій. Перевірка опуклості багатокутника. Векторна геометрія. Колінеарність векторів. Перевірка належності точок прямій.

Ліві та праві трійки векторів. Знаходження порядку обходу вершин опуклого багатокутника. Задача про Едемський сад. Задачі мінімізації в геометричній інтерпретації.


Тема 9. “Жадібні” алгоритми

Поняття “жадібного” алгоритму. Теоретичні основи “жадібних” алгоритмів. Переваги та недоліки “жадібних” алгоритмів. Класичні приклади “жадібних” алгоритмів. Задача про вкладання рюкзака. Розв’язання задач із застосуванням “жадібних” алгоритмів. Геометричні, транспортні, економічні задачі.

Тема 10. Синтаксичний розбір і лексичний аналіз виразів

Розділення виразів на складові частини. Опрацювання текстів і сортування окремих елементів тексту.

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

Постфіксна система запису математичних виразів (польська нотація). Алгоритм RРN-калькулятора.


Тема 11. Алгоритми на графах

Основні поняття теорії графів. Матричне подання графів. Матриця зв’язності та матриця відстаней на графі. Пошук найкоротших шляхів та оптимальних маршрутів у графах. Алгоритм Дейкстри. Метод Беллмона. Знаходження мінімального остовного дерева графа за алгоритмом Прима-Краскала. Перевірка зв’язності графів. Алгоритм Тарьяна знаходження найменшого спільного пращура. Поняття про NP-повні задачі. Аналіз алгоритмів розв’язання NP-повних задач. Задача про найменше вершинне покриття.

Тема 12. Комбінаторні задачі

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



2. Розв’язати задачі

Задача 1

Правильною дужковою послідовністю називається така послідовність, яка складається із збалансованих пар дужок, розташованих один до одного правильним чином (або одна пара строго усередині іншої, або зовні). Іншими словами, якщо узяти будь-який арифметичний вираз, і видалити з нього все, окрім дужок, вийде правильна дужкова послідовність. Будь-яку правильну дужкову послідовність можна отримати таким чином. Послідовність, яку таким чином отримати не можна, правильної не є.

Нехай можливі дужки двох типів: круглі і квадратні. Напишіть програму, яка перевіряє дану сдужкову послідовність на правильність.

Вхідні дані. На вхід програмі подається рядок, що складається тільки з круглих і квадратних дужок. Довжина рядка не перевершує 250 символів.

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

Приклад введення

Приклад вивеведення

()()[]([()[]])

YES

([)]

NO

(((()))

NO


Задача 2

Розглянемо правильні дужкові послідовності (див. задачу 1), що складаються тільки з круглих дужок. Розглянемо всі послідовності, в яких рівно N пара дужок і упорядкуємо їх в лексикографічному порядку (послідовність А йтиме раніше послідовності B у тому випадку, коли існує число i, що перші (i  1) символів цих послідовностей співпадають, а i-ий символ в послідовності А – відкриваюча дужка, а в B – закриваюча).

Напишіть програму, яка по даних числах N і K будуватиме K-у правильну дужкову послідовність з N пар дужок.

Вхідні дані:

Вводяться два числа – N і K(1≤N≤30, 1≤K≤1012).



Вихідні дані:

Ваша програма повинна виводити K-у правильну дужкову послідовність з N пар дужок. Якщо такої послідовності не існує (K більше кількості правильних скобових послідовностей з N пар дужок), виведіть слово ERROR.



Приклад введення

Приклад вивеведення

3 1

((()))

3 2

(()())

3 3

(())()

3 4

()(())

3 5

()()()

3 6

ERROR


Задача 3

В державі є N (0 компаній (компанії пронумеровані числами від 1 до K (0

Вимагається знайти мінімальну суму грошей, якій потрібно розташовувати, щоб добратися з міста А в місто B, якщо заборонено двічі підряд проїздити по дорозі, належній одній компанії, але протягом шляху можна кілька разів проїздити по дорогах, що належать одній компанії, якщо між цим проїздити по дорозі (дорогам) інших компаній.

Вхідні дані: Спочатку задаються числа N, K, M, далі задається M четвірок чисел Xi, Yi, Ci, Ti, де Ci і Ti – відповідно вартість проїзду (0K), якій належить автотраса, провідна від міста Xi в місто Yi. Далі йдуть числа А і B – номери початкового і кінцевого міст відповідно. Всі дороги односторонні, тобто наявність дороги з міста X в місто У не означає наявності дороги у зворотному напрямі, а якщо дорога з У в X існує, то вона не зобов'язана належати тій же компанії, що і дорога з X в У. Між будь-якими двома містами в одному напрямі може бути не більше однієї автотраси.

Вихідні дані: Ваша програма повинна вивести одне число — мінімальну суму грошей, які потрібні, щоб проїхати з міста А в B, або число –1 (мінус один), якщо проїхати неможливо.

Приклад введення

Приклад виведення

5 3 6

1 2 4 1


2 1 3 2

2 3 3 3


3 4 3 2

3 5 5 1


4 5 1 2

1 5


12

3 2 3

2 3 3 2


3 1 2 2

1 2 2 1


2 1

-1


Задача 4 «Dobriy Vitya Strikes Back»

На літніх зборах 2008 року викладачі готові прочитати N різних лекцій. Але, на жаль, збори проходитимуть тільки протягом M днів. З гуманістичних міркувань в день не можна прочитати більше однієї лекції. Викладачі приїжджають і виїжджають по ходу зборів, таким чином, деякі лекції не можуть бути прочитані в деякі дні. Щоб якнайкраще підготувати збірну команду до виступу на міжнародній олімпіаді, було вирішене прочитати максимальну кількість лекцій.

Керівник передав учасникам зборів план, які лекції в який день можуть бути прочитаний. Учасники не знають, який з можливих планів зборів буде вибраний. Але вони зацікавилися, які лекції обов'язково будуть прочитані.

Вхідні дані: На вхід подаються спочатку два числа — N і M (1<=N<=200, 1<=M<=200). Наступні N рядків містять описи лекцій, по одній на рядку. Для кожної лекції, указуються номери днів, в які може бути прочитаний дана лекція. Числа в рядку розділяються одним або декількома пропусками. Дні і лекції нумеруються з одиниці.

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

Приклад вхідного файлу


Приклад вихідного файлу

4 3

2

1 3



2

1 2 3


2 4


Задача 5. Два опуклі многокутники р і Р на площині задано координатами вершин (x1,y1), (x2,y2)... (xm,ym); (X1,Y1), (X2,Y2)... (XM,YM). Вершини перераховані в довільному порядку. Написати алгоритм, що визначає відстань між багатокутниками.

Задача 6. Аналіз циклів

В символьному масиві А[1:N] записана програма на мові БЕЙСІК. В кожному елементі масиву міститься один оператор, його номер рівний номеру елемента масиву. Цикли з лічильниками оформляються в мові БЕЙСІК так: на початку циклу знаходиться оператор FOR <ім’я змінної-лічильника>=<вираз> TO <вираз> STEP <вираз>, в кінці циклу - оператор NEXT < ім'я лічильника >. Ім'я змінної складається з одного або двох символів: перший - латинська буква, другий - латинська буква або цифра.

Написати алгоритм, який би перевірив правильність взаємного розташування циклів в заданій програмі. Оператори переходів не використовуються. Передбачається, що кожний оператор FOR і NEXT окремо написаний правильно; у всіх операторах циклу в програмі початкове, кінцеве значення і крок лічильника задані числами, знак кроку співпадає із знаком різниці кінцевого і початкового значень.

Задача 7. Пошук числа

Дана впорядкована за збільшенням лінійна таблиця натуральних чисел А[1] <...< А[N]. Знайти якнайменше натуральне число, не уявне у вигляді суми деяких чисел з таблиці. Сума може складатися і з одного доданку; кожний елемент таблиці може входити в неї не більше одного разу. Прийнятне рішення повинне вкладатися в С*N дій, де С - постійна, не залежна від N.



Задача 8. K-е розміщення

Скласти алгоритм, який отримає на вході число K і видасть на виході К-те по порядку N-значне число, у якого ніякі дві цифри не рівні між собою. Першим таким чотиризначним числом є 0123.


Задача 9. Зв'язність графа

В Антарктиді розташовані N метеорологічних станцій. Кожна станція сполучена з іншими станціями лініями зв'язку. Через стихійну біду багато ліній зв'язку виявилися порушеними. Написати алгоритм, що визначає, між якими парами станцій зв'язок неможливий навіть через ланцюжки інших станцій. Справність лінії зв'язку між I-той і K-той станцією можна з'ясувати за допомогою логічної функції ЄЗВ’ЯЗОК(I,К).



Задача 10. Доміно

Набір узагальненого доміно складається з М кісток, на кожній кістці нанесено два цілі числа від 0 до N; будь-яка пара чисел може зустрічатися в наборі 0, 1 або кілька разів. Значення кісток задані в таблиці ДОМІНО[1:M,1:2]. Скласти алгоритм, що визначає, чи можна побудувати зі всіх кісток набору ланцюг за правилами доміно.



Задача 11. На клітчастому папері намалювали коло цілого радіусу R з центром на перетині ліній. Знайти кількість кліток, цілком лежачих усередині цього кола.

Задача 12. Є N спортсменів. Написати програму, яка знаходить всі різні склади команд з К спортсменів, де К <= N.

Задача 13. Кожний з N учасників чаювання з казки, що нескінченно продовжується, "Аліса в країні чудес" має свій визначений певний період перебування за столом протягом доби (наприклад, Заєць – з 23:00 до 8:00). Вважається, що момент закінчення чаювання для учасника не входить в період його перебування за столом. (такий проміжок в математиці позначається так: [23:00, 8:00) ). Написати програму, яка по заданих періодах визначає час доби, протягом якого за столом одночасно знаходяться всі учасники чаювання.

Задача 14. Телефонні номери для шахістів.

Для представлення телефонних номерів членам шахового клубу телефонна компанія вирішила з'ясувати, скільки різних 'шахових номерів' є в її розпорядженні. Телефонний номер складається з 7 цифр і не може починатися з 0 і з 8.

Написати програму, що обчислює кількість різних таких номерів, які можна набрати на кнопковому телефонному апараті ходом різних фігур: а) коня; б) слона; в) тура; г) ферзя; д) короля.

Цифри на кнопковому телефонному апараті мають наступне розташування:

1 2 3

4 5 6


7 8 9

0

Задача 15. Обчисліть, в якій координатній четверті розташований трикутник, освічений прямий, заданої рівнянням y=ax+b, і осями координат.



Задача 16. В таблиці а[1:100] записані нулі і одиниці. Замінити 0 на 1, а 1 на 0

Задача 17. Задані n точок на площині з координатами (x[1], у[1]... (x[n], у[n]). Побудувати алгоритм з'єднання їх незамкнутої ламаної без перетинів. В результаті цього виконання повинна бути отриманий таблиця i[1],...,i[n], яка вказує порядок з'єднання точок.

Задача 15. Послідовність 1001011001101001... будується так спочатку пишеться 1, потім повторюється така дія: вже написану частину приписують справа із заміною 0 на 1 і навпаки, тобто 1 -- 10 --- 1001 --- 10010110 --- ...

Скласти програму, що обчислює n-ний член цієї послідовності по заданому n.



Задача 16. "Караван".

Географічна карта місцевості задана квадратною сіткою певного масштабу. У вузлах сітки відома висота над рівнем моря. Між сусідніми вузлами висота змінюється плавно. Караван переміщається тільки по лініях сітки. (Переміщення по діагоналі забороняється). Шлях між двома сусідніми точками з кутом нахилу більше 45 градусів вважається непрохідним. Провести караван з крапки А(X1,Y1) в крапку B(X2,Y2) по дорозі з якнайменшим перепадом висоти або повідомити про відсутність розв’язку.

Примітка: Перепадом висот на маршруті називається різниця висот між найвищою і найнижчою точками маршруту.

Задача 17. Для кожного цілого додатного числа n розглядатимемо всілякі його утворення у вигляді суми одного або декількох цілих позитивних доданків. Скласти таблицю, в якій для кожного n вказано число таких утворень (без урахування порядку, так що, наприклад, уявлення 3=2+1 і 3=1+2 вважаються однаковими. Наприклад, для n=4 таких утворень 5 (4, 3+1, 2+2, 2+1+1, 1+1+1+1). (Чим далі заповнена таблиця, тим вище оцінюватися робота).

Задача 18. Розстановка дужок називається правильною, якщо за кожною відкриваючою дужкою слідує своя закриваюча дужка і кожній закриваючій дужці передує своя відкриваюча дужка. Скласти алгоритм визначення правильності розстановки дужок.

Приклади


Правильні розстановки Неправильні розстановки

() () ( ()

( () () ) )(

(((()())())()) (()(()())

[()] ([)]

{[{()]}[][] {{}]



Задача 20. Натуральне число, записане в десятковій системі счислення, називається надпростим, якщо воно залишається простим при будь-якій перестановці своїх цифр. Визначити, чи є дане число надпростим.
Задача 21. Самотній король довго бродив по нескінченній шахівниці. Відома послідовність з n його ходів (вгору, вниз, вліво, управо, вверх-вліво і т.п.) Скласти алгоритм, що визначає, чи побував король двічі на одному і тому ж полі за мінімальне можливе при заданому n кількість обчислень.
Задача 22. В прямокутній (0,1)-матриці, розміром NxM (N - число рядків, M - число стовпців; N = 1,2...,15; M = 1,2...,15) підрахувати число ізольованих 0-областей, тобто областей, що складаються з одних нулів, мають сусідні нулі по горизонталі, вертикалі або діагоналі. 0-область може складатися тільки з одного нульового елемента. Наприклад, для (0,1)-матриці виду:

0 0 0 1 0

0 1 1 1 1

0 1 0 1 0

0 1 1 0 1

0 1 0 1 0



число ізольованих 0-областей рівно 3.
Задача 23. На вхідний пристрій комп'ютера в довільному порядку поступають цифри 1, 2 або 3, утворюючи послідовність. Ознакою закінчення послідовності служить число 0. Побудувати алгоритм, що визначає наявність у введеній послідовності трьох рядів однакових цифр, що складаються тільки з одиниць, тільки з двійок і лише з трійок, і мають довжину, рівну заданій. Примітка: Послідовність може бути настільки довгою, що вона цілком не поміщається в пам'яті комп'ютера.
Задача 24. Скласти програму, яка в повному записі числа 77! (77 факторіал) вкаже в порядку спадання номера розрядів, що містять цифру 7. Примітка: розряди числа нумеруються в наступному порядку: розряд одиниць має номер 1, десятків - 2, сотень - 3 і т.д.





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

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