Програмування С, С++теорія та практика (частина 2)
Задачі на складання ефективних алгоритмів
Краще підготовлені студенти можуть обирати (за узгодженням з викладачем) задачі з даного розділу замість тих, що пропонуються для основної групи студентів. Завдання згруповані за відповідними номерами лабораторних робіт першого семестру - №1, №3 та №5, та відповідають їх тематиці. Деякі з цих задач, або їх елементи пропонувалися на різних олімпіадах з програмування.
Л .1.1. На площині задано координати двох протилежних вершин квадрата. Необхідно знайти координати двох інших його вершин, якщо сторони квадрата паралельні осям координат.
Л.1.2. Скласти програму скорочення дробу виду т , де т, п, -
п
натуральні числа.
Л.1.3. Задано два цілих числа а і Ь, причому а не дорівнює Ь. Знайти серед них менше, не використовуючи операторів вибору, умовних операторів, циклів. Дозволяється використовувати тільки арифметичні операції.
Л.1.4. На інтервалі [1000;9999] знайти всі прості числа для кожного з яких сума першої та другої цифри рівна сумі третьої та четвертої цифри.
Л.1.5. Людина піднімається по сходах, ступаючи на наступну сходинку, або перестрибуючи через одну чи дві сходинки. Знайти, скількома способами вона зможе піднятися на И-у сходинку. Масивів не використовувати.
Л.1.6. Переставити цифри числа N так, щоб одержати найбільш можливе число, вивести його на екран. Реалізувати алгоритм без використання масивів.
Л.1.7. Знайти всі трьохзначні числа, рівні сумі факторіалів своїх цифр.
Л.1.8. Нехай Аі...АМ - послідовність цілих чисел. Позначимо максимальний та мінімальний елементи цієї послідовності як тах та тіп відповідно. Обчислимо суму елементів цієї послідовності 8 = Аі + А2 + ... АМ. Замінимо кожний елемент послідовності на різницю 5і та цього елемента: А1 = 8 - А1. Таку дію повторимо К разів. Написати програму, яка за послідовністю АІ (вводиться з клавіатури), отриманою в результаті К-кратного повторення цієї операції обчислює різницю тах - тіп. Масивів не використовувати.
Л.1.9. В квадратній дошці розміром NxN клітинок вирізано дві клітинки з координатами А(х1,у1), В(х2,у2). Визначити чи можна повністю покрити дощечками розміром 1x2 всі клітинки дошки. Координати вирізаних клітинок вводяться з клавіатури. Масиви не
використовувати
Л.1.10. Надрукувати всі числа від 1 до N у вигляді квадратної таблиці розміром розташувавши їх за наступною схемою без
використання масиву :
|
1 |
3 |
6 |
10 |
|
2 |
5 |
9 |
13 |
|
4 |
8 |
12 |
15 |
|
7 |
11 |
14 |
16 |
Л .1.11. Клієнт банка забув чотиризначний шифр свого сейфа, але пам'ятав, що цей шифр - просте число, добуток його цифр рівний N. Яка найменша кількість спроб гарантує йому відкриття сейфу. На екран вивести всі необхідні спроби та їх кількість. Л.1.12. Обчислити кількість чисел в системі числення з основою К, які містять < N знаків, таких, що їх запис не містить двох підряд розміщених нулів. Числа N і К вводяться з клавіатури. Масивів не використовувати.
Л.3.1. У масиві А[1.^] кожний елемент рівний 0,1,2 або 3. Не використовуючи додаткової таблиці, переставити елементи масиву так, щоб спочатку розташовувались усі трійки, потім двійки, одиниці, врешті, всі нулі. Число N та всі елементи масиву вводяться з клавіатури.
Л.3.2. Дано рядок (вводиться з клавіатури), що містить шлях до файла або каталогу, записаний за згодами, прийнятими в М8 БО8. Перетворити даний рядок таким чином, щоб він містив шлях в форматі ОС Шіх.
Л.3.3. Скласти функцію для підрахунку кількості різних чисел у масиві, що містить N елементів.
Л.3.4. Паліндромом називається симетричний рядок, який однаково читається як зліва направо, так і справа наліво. Потрібно написати функцію, яка буде визначати, чи є введений рядок паліндромом.
Л.3.5. Користувачу, що зареєструвався на РТР-сервері для отримання доступу до файлів на ньому потрібно набрати в РТР-браузері команду вигляду: йр://логін:пароль@адреса_сервера. Написати програму, яка з введеного рядка виділяє логін, пароль, адресу РТР-сервера і друкує цю інформацію на екран.
Формат вхідних даних: йр://и8егпате:рагоі@йр.8егуег.иа Формат вихідних даних:
Адреса сервера: йр.кегуег.иа Логін: икегпаше Пароль: рагої
Л.3.6. Дано ігрове поле розміром МxN клітинок. У верхній лівій клітинці (клітинка старту) знаходиться фішка. У нижньому правому кутку знаходиться клітинка фінішу. Фішку дозволяється рухати вниз або вправо на будь-яку кількість клітинок. Написати програму, яка за числами Мі N буде обчислювати кількість шляхів, якими можна перемістити фішку з клітинки старту в клітинку фінішу. Для прикладу, зображеного на малюнку (М=2, N=4) відповідь 4.
Л.3.7. За заданими координатами вершин многокутника перевірити, чи є він опуклим. Кількість вершин та координати вводяться з клавіатури. Примітка : координати вершин не обов'язково впорядковані за порядком обходу.
Л.3.8. Задано ціле додатне число N (N<1000000000). Записати це число словами у вигляді рядкової величини.
Наприклад : 1024 - тисяча двадцять чотири
2 - два.
Л.3.9. Написати функцію, яка буде обчислювати визначник матриці А^х^. Передбачити можливість введення елементів матриці з клавіатури та можливість заповнення матриці випадковими числами.
Л.3.10. Магічним квадратом порядку N називається таке розташування цілих чисел у матриці що суми елементів у кожному рядку,
кожному стовпці і двох діагоналях співпадають. Скласти функцію для побудови магічного квадрату порядку N ^ - непарне число), використовуючи числа від 1 до N . Число N вводиться з клавіатури.
8 1 6
3 5 7
4 9 2
Л.3.11. Написати програму, яка буде обчислювати всі цифри п! при и<100.
Л.3.12. Скласти програму, яка буде обчислювати значення 264 - 1 зі збереженням всіх цифр.
Л.5.1. Дано текстовий файл, в якому містяться різні слова довжиною від одного та більше символів, відокремлені довільним числом пробілів. Побудувати частотний словник слів тексту у вигляді підсумкової таблиці з двох колонок, вказавши, скільки разів зустрічається кожне із слів тексту.
Л.5.2. Дано файл, в якому зустрічаються теги <і> та </і>. Замінити кожне входження "<і>" на "<курсив>", а кожне входження "</і>" на "<кінець курсиву>".
Примітка : в програмі передбачити, що літера "і" може бути як малою, так і великою. Вхідні дані зчитуются з файла ЬАВ5_1.ТХТ і записуються у файл ЬАВ5_1.ОШ\
Л.5.3. У прямокутнику розміром Мх^ розбитому на одиничні клітинки міститься "змійка" (неперервна ламана лінія шириною в одну клітинку, яка може згинатися лише на 90 градусів). "Змійка" може утворювати замкнутий або розімкнутий контур. "Змійка" себе не перетинає і ніде не дотикається різними частинками. Інформація про розташування "змійки" задається матрицею А [М;М]. Значення А[і;Л==1, якщо клітинка належить "змійці" і А[у]==0, якщо не належить. Значення М, N та матриця зчитується з файла ЬАВ5_2.ТХТ, а результати записуються у файл ЬАВ5_2.ОШ\ Визначити, чи утворює "змійка" замкнутий контур.
Приклад вхідного файла:
6 16
1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0
1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
Приклад вихідного файла:
Змійка утворює замкнутий контур.
|
Ш |
Л.5.4. У прямокутнику розміром Мх]\Г, розбитому на одиничні клітинки містяться "кутики". "Кутик" - смужка товщиною 1 клітинку, зігнута у довільному місці на 90 градусів. "Кутики" ніде не накладаються і ніде не дотикаються.
Інформація про розташування кутиків задається прямокутною матрицею А[М;М]. Значення А[і;_]]==1 означає, що клітинка належить деякому кутику, а А[і;_]]==0 означає, що клітинка не належить кутику. Вхідні дані М, И, матриця А зчитуються
з файла ЬАВ5_3.ТХТ. Написати програму, яка визначає кількість кутиків. Результати записати у файл ЬАВ5_3_ОШ\
Приклад вхідного файла :
8 12
0 0 0 0 1 1 1 0 1 0 0 0
0 1 1 0 1 0 0 0 1 0 1 1
0 1 0 0 1 0 1 0 1 0 0 1
0 1 0 0 1 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 1 1 1 1
0 0 0 0 1 0 1 0 0 0 0 0
0 0 0 0 1 0 1 1 1 0 1 1
0 0 0 0 1 0 0 0 0 0 0 1
Приклад вихідного файла:
Всього 6 кутиків.
Л.5.5. Організувати файл бази даних на вільну тему (ім'я файла - ЬАВ5_5.БАТ). Передбачити можливість редагування інформації в БД. Організувати пошук інформації за кількома полями.
Л.5.6. Дано рядок, що складається із слів, розділених пробілом. Написати програму, що знищує зайві пробіли. Пробіл вважається зайвим, якщо він стоїть на початку рядка, стоїть в кінці рядка, або слідує за пробілом. Рядок зчитується з файла ЬАВ5_6.ТХТ, а результати записуються у файл ЬАВ5_6.ОШ\
Л.5.7. У файлі знаходиться текст програми на мові Сі. Потрібно написати програму, що буде видаляти коментарі в тексті програми. Як відомо, коментар - це послідовність символів, які знаходяться між "/*"
і "*/". Коментар може бути багаторядковим, тобто починатися в одному рядку, а закінчуватися в іншому рядку. Вхідні дані необхідно прочитати з файла ЬАВ5_7.ТХТ, а результати записати у файл ЬАВ5_7.0ЦТ.
Л.5.8. Напишіть програму, що здійснює перенесення занадто довгих рядків. Слова розбивати не можна (слово, яке не можна розмістити, варто перенести цілком на новий рядок). Ширина рядка дорівнює 80. Вхідні дані прочитати з файла ЬАВ5_8.ТХТ, результати записати у файл ЬАВ5_8.ОЦТ.
Л.5.9. Задано шаблон з круглих дужок і знаків запитання. Потрібно визначити, скількома способам можна замінити знаки запитання круглими дужками так, щоб вийшов правильний вираз із дужок. Перший рядок файла ЬАВ5_9.ТХТ містить заданий шаблон. У вихідний файл ЬАВ5_9.ОЦТ вивести знайдену кількість способів.
Приклад вхідного файла.
????(?
Приклад вихідного файла.
2
Л.5.10. Шахова асоціація вирішила обладнати всіх своїх співробітників такими телефонними номерами, які набиралися б на кнопочному телефоні ходом шахового коня. Наприклад, ходом шахового коня набирається телефон 340-49-27. При цьому телефонний номер не може починатися ні з цифри 0, ні з цифри 8. Написати програму, яка визначає кількість телефонних номерів довжини N які набираються ходом шахового коня.
7 8 9
4 5 6
1 2 3
0
Приклад вхідних даних (ЬАБ5_10.ТХТ):
2
Приклад вихідних даних (ІАБ5_10.0ПТ):
16
Л.5.11. Під час друку великих документів може виникнути потреба друкувати не весь документ, а тільки деякі його сторінки. Серед аргументів програми друку є рядок з послідовністю номерів сторінок. Потрібно надрукувати не окремі сторінки, а діапазони сторінок і, можливо, вказувати початок і кінець діапазонів, а не послідовні числа. Завдання:
Напишіть програму, яка буде перетворювати списки сторінок у відповідну послідовність номерів сторінок.
Приклад вхідних даних (ЬАБ5_11.ТХТ):
1,4-5,7-7,10-20
Приклад вихідних даних (ІАБ5_11.0ПТ):
1,4,5,7,10,11,12,13,14,15,16,17,18,19,20
Л.5.12. Прямокутник, сторони якого виражені натуральними числами а і Ь, розділений на квадрати розміром 1х1. Знайти число квадратів, які перетинає діагональ прямокутника.
Вхідні дані : ЬАВ5_12.ТХТ Вихідні дані : ЬАВ5_12.ОШ'
Л.5.13. У файлі 8ТАТЕ.БАТ міститься деяка кількість назв міст (по одній в кожному рядку). Утворіть з даного набору слів замкнений ланцюжок, в якому кожне наступне слово починається з літери, якою закінчувалося попереднє, використавши найбільшу кількість слів. Всі слова у файлі різні і у ланцюжку можна використовувати не більше одного разу. Програма 8ТАТЕ.С повинна на екран та у перший рядок файлу 8ТАТЕ.8ОЬ вивести кількість використаних слів, а далі - всі використані слова у потрібній послідовності (по одному слову в кожному рядку). У випадку, коли ланцюжок утворити неможливо, у файл 8ТАТЕ.8ОЬ необхідно записати лише одне число 0.
Приклад вхідних та вихідних даних.
|
|
||||
|
|||||
Л.5.14. Написати програму-архіватор, яка буде перетворювати інформацію, що записана у файлі таким чином, щоб вона займала якомога менший розмір та програму, яка відновлює початковий файл за архівним.
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86