Принципи технології програмування

На практиці сьогодні застосовуються декілька технологій програмування, найвідоміша з них – технологія структурного програмування. Це правила (засади), користування якими гарантує розробку якісного програмного продукту. Головними з них є:

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

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

• Структурне кодування – для розробки будь-якої програми достатніми є три алгоритмічні структури (конструкції): лінійна (поступове виконання дій одна за одною у порядку запису), розгалужена (виконання однієї з кількох альтернатив), циклічна (повторення дій).

Часто (головним чином початківцям у програмуванні) рекомендують користуватися KISS-принципом (Keep It Single Stupid) – треба робити програму якомога простішою; це полегшить вам (та можливо іншим) справу виправлення помилок і модифікації.

Досить корисними є й такі правила:

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

Вибір ідентифікаторів. Ідентифікатори (імена) об’єктів програми (констант, змінних, функцій, процедур та ін.) треба обирати близькими до реальної назви відповідного об’єкта.

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

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

Захист від некоректного введення. Введену користувачем інформацію програма повинна перевіряти на коректність (належність множині припустимих для введення даних) та давати можливість користувачу виправити можливі помилки введення.

Стійкість програми. Програма не повинна втрачати працездатність (переривати або аварійно закінчувати роботу) ні за яких умов (навіть, якщо дії користувача некоректні).

Варіанти завдань

1. Рівняння має вигляд F(X)=0. Вираз F(X) складається з цілих чисел, знаків арифметичних операцій ( + , – , * , / ) і змінної Х, що може входити у вираз лише один раз. Вираз задається в зворотному польському записі, де знак операції ставиться не між операндами, а після них.

Наприклад, для виразу 2+4/(Х–1)+7 зворотний польський запис має вигляд 7 2 4 Х 1 – / + + .

Написати програму, що розв’язує задане рівняння.

2. Послідовність натуральних чисел визначена своїм загальним членом .

Написати програму, що знаходить точне значення для будь-якого n із проміжку [0,150].

Для перевірки .

3. Для дійсних чисел Х₁, У₁, Z₁, Х₂, У₂, Z₂, Х₃, У₃, Z₃, Х₄, У₄, Z₄, Х₅, У₅, Z₅, Х₆, У₆, Z₆, таких що точки з координатами (Х₁, У₁, Z₁), (Х₂, У₂, Z₂), (Х₃, У₃, Z₃) – вершини першого трикутника, точки (Х₄, У₄, Z₄,), (Х₅, У₅, Z₅,), (Х₆, У₆, Z₆,) – вершини другого трикутника, визначити, чи розташовується перший трикутник цілком усередині другого.

4. На координатній площині дійсними координатами своїх вершин заданий опуклий чотирикутник. Якщо він є паралелограмом, то знайти площу тієї його частини, що розташована в обраній користувачем координатній чверті.

Для перевірки

Координати вершин								Результати
x1	y1	x2	y2	x3	y3	x4	y4
–2	3	2	3	2	–3	–3	4	Не паралелограм
–5	–2	1	4	5	4	–1	–2	Паралелограм	2 чверть	Площа 4.5

5. Розробити бібліотечний модуль програм для реалізації арифметичних дій над двома цілими числами ( + , – , * , / ) в системі числення з основою Р (числове значення Р встановлюється користувачем).

Навести приклади застосування модуля.

6. Скласти програму, що реалізує розв'язання системи лінійних алгебраїчних рівнянь наступними методами:

• методом простих ітерацій,

• методом Гаусса.

Для конкретних прикладів зробити порівняльний аналіз результатів.

7. Розробити бібліотечний модуль програм, що реалізують операції обробки матричної інформації:

• додавання,

• множення,

• транспонування,

• знаходження рангу.

Скласти комплекс тестів для ілюстрації роботи бібліотеки.

8. На площині задана квадратна область К і кінцева множина Т точок цієї області. Для цієї області відомі ще дві точки А та В. Будь-яка трійка точок із множини Т однозначно визначає трикутник і, як наслідок, описану навколо нього окружність. Скласти програму для розв’язування наступних задач.

• зобразити всі такі окружності, що цілком входять до області К:

• зобразити червоним кольором окружності, що мають спільні точки з прямою АВ,

• зобразити синім кольором окружності, що не мають спільних точок з прямою АВ;

• виділити лінією подвійної товщини всі окружності, що не мають спільних точок з іншими;

• з'ясувати, чи визначає множина Т опуклий багатокутник, і, якщо так, зобразити його.

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

• використання перетворень над розширеною матрицею;

• використання алгебраїчних доповнень.

Виконати програмне порівняння часу та точності обчислень для матриць порядків 2 – 10.

10. Скласти програму знаходження числа  з точністю ε, наступними методами:

• метод Монте-Карло (метод статистичних випробувань);

• розкладання в ряд за формулою .

Зробити порівняльний аналіз точності.

11. Скласти програми впорядкування масивів з дійсними елементами швидкими методами сортування – Шелла та Хоара – з використанням статичної та динамічної пам'яті. Зробити порівняльний аналіз ефективності.

12. Скласти програму розв'язання системи лінійних алгебраїчних рівнянь наступними методами:

• методом Гаусса з вибором головного елемента,

• методом Крамера.

Програмно реалізувати порівняння результатів і часу їхнього одержання.

13. Скласти програму розв'язання системи лінійних алгебраїчних рівнянь двома методами:

• методом оберненої матриці,

• методом Гаусса.

Реалізувати аналіз точності і витрат часу на одержання результатів.

14. Біноміальні коефіцієнти.

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

15. Скласти програму, яка для множини натуральних чисел a₁,a₂,a₃,…,a_n у виразі (((a₁?a₂)?a₃)?….a_n) кожен знак ? замінює на один із знаків арифметичних операцій ( +, – , * , / ) так, щоб результат обчислення дорівнював цілому числу А. Досить зазначити один розв'язок (або повідомити про відсутність такого). При діленні залишати тільки цілу частину.

16. Скласти пакет програм роботи з натуральними числами для розв’язування наступних задач.

Для натурального числа А (може бути досить великим) знайти всі менші за А:

• паліндроми;

• досконалі числа (досконалим називається число, що дорівнює сумі усіх своїх дільників, виключаючи саме число);

• числа Армстронга (n-значне число називається числом Армстронга, якщо воно дорівнює сумі n-х степенів своїх цифр, наприклад, 153=1³+5³+3³)

• числа Мерсенна (просте число називається числом Мерсенна, якщо воно може бути представлене у вигляді 2p-1, де p – просте число).

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

18. Скласти пакет програм для обробки простих дробів (кожен дріб задається двома натуральними числами – чисельником і знаменником):

• реалізувати арифметичні дії над простими дробами;

• одержати в порядку зменшення послідовність простих нескоротних дробів, що знаходяться на проміжку [0,1], знаменники яких не перевищують числа А;

• одержати десятковий запис простого дробу з заданою точністю.

19. Для матриці А знайти обернену матрицю А^-1, користуючись наступною ітераційною формулою , де – одинична матриця, . Ітераційний процес закінчується, якщо для заданої похибки виконується умова .

20. Скласти бібліотеку програм для розв’язання матричних рівнянь (А+Х=В, А-Х=В, А*Х=В, А/Х=В). Розробити приклади тестів для ілюстрації роботи бібліотеки.

21. Календарі.

У сонячному календарі рік складається з 12 місяців із кількістю днів відповідно: 31,28(29),31,30,31,30,31,31,30,31,30,31.

В другому місяці 29 днів, якщо номер року ділиться на 4 без залишку, інакше в ньому 28 днів.

У місячному календарі рік складається з 12 місяців із кількістю днів відповідно: 29,29,29,30,29,30,29,30,30,29,30,29.

Першому числу першого місяця першого року місячного календаря відповідає шістнадцяте число сьомого місяця 622 року сонячного календаря.

Написати програму, переведення дат із місячного календаря в сонячний і назад в межах 1000 – 2100 рр. сонячного календаря.

Для перевірки 25.10.1300 (Л) = 6.10.1878 (С)

22. Введено текст із слів, розділених пробілами. Повторюваних слів немає. Довжина тексту не перевищує 80 символів. Усі літери в словах – великі. Знайти найменшу довжину частини тексту таку, що будь-яке слово тексту можна однозначно ідентифікувати за його початком знайденої довжини.

Наприклад, для тексту "СИВИЙ СТАРИЙ СЕРДИВСЯ" маємо відповідь – знайдена довжина 2 символи.

23. Операція множення матриць не відповідає властивості комутативності: , але відповідає властивості асоціативності: . Для обчислення добутку матриць А₁А₂А₃…А_k відомих розмірів (m₁,n₁), (m₂,n₂), (m₃,n₃)…(m_k,n_k) розташувати дужки в добутку так, щоб мінімізувати кількість множень елементів матриць.

Наприклад, для m₁=100, n₁=1, m₂=1, n₂=100, m₃=100, n₃=1 обчислення (А₁А₂)А₃ потребує 20000 множень, А₁(А₂А₃) потребує 200 множень.

24. Дослідити проблему компактного збереження інформації. Скласти програму архівації текстових файлів, використовуючи один із відомих методів стиску (наприклад, метод Хафмана).

25. Розробити програму для гри “Морський бій”. Правила гри стандартні. Один гравець – Людина, другий гравець – Комп’ютер. Поведінку гравця Комп’ютер спланувати самостійно. Рекомендовано використовувати графічний режим, роботу з мишею.

26. Дослідити проблему перекладу текстової інформації з однієї мови на іншу. Скласти програму для пакетного перекладу простих текстових файлів у двох напрямках: з мови А на мову Б та назад.

27. Скласти програму розв’язання транспортної задачі (Мінімізувати транспортні витрати для перевезення продукції від N виробників до M споживачів, якщо відомою є матриця вартостей перевезення від кожного виробника до кожного споживача) з використанням методу потенціалів. Організувати виведення результатів на екран та у файл.

28. Скласти програму, яка для цілого числа Р (2  P  16) формує та забезпечує друкування на екрані деякого визначеного користувачем діапазону таблиці множення чисел у системі числення з основою Р.

29. Скласти програму для розв’язання наступної задачі:

П'ятниця 13-е вважається особливо нещасливим днем григоріанського календаря. Для двох дат, що є границями проміжку часу, підрахувати, кількість таких днів. Границі проміжку вказуються довільно.

Примітки:

Високосний рік – рік, номер якого ділиться на 4, за винятком тих, номер яких ділиться на 100 і не ділиться на 400.

Григоріанський календар почався в п'ятницю 15.10.1582 р.

30. Скласти пакет програм для обробки кінцевої множини чисел, що розв’язує наступні задачі:

• знайти всі локальні мінімуми і вивести їхні номери;

• елементи розташувати в порядку зменшення їхньої частоти;

• генерувати послідовність перестановок заданої множини;

• генерувати усі підмножини заданої множини.

31. Написати програму, яка зображує координатну площину з початком координат у центрі екрана і параболу . У правому нижньому куту екрана виводиться формула, що описує графік функції у вигляді: . Користувач може перетворювати графік, змінюючи на 0.1 та на –0.1 значення а (натисканнями на “+” та “–“ відповідно), b, c (натисканнями на клавіші управління курсором). Процес супроводжується одночасною зміною вигляду аналітичної формули у правому нижньому куту екрана.

32. Лічилка.

По колу розташовано N людей. Користуючись певною лічилкою (її вводить користувач, наприклад, Мені лічилочку лічити – тобі з кола виходити) та починаючи з довільного місця (його вказує користувач) програма відраховує по колу людей. Той, на кому лічилка закінчилася – виходить з кола (коло зменшується). Скласти програму виведення послідовності виходу з кола з графічною інтерпретацією цього процесу.

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

34. Деяка функція без особливостей задана на інтервалі [a,b] таблицею. Використовуючи інтерполяційний поліном Лагранжа, формули центральних (або кінцевих) прирощень, побудувати наближення функції, а також її першої та другої похідних. Вивести графічне зображення координатних осей, вхідних точок та отриманих кривих на дисплей.

35. Розробити програму, що проводить обчислення над комплексними числами та інтерпретує цей процес графічно.

36. Скласти програму знаходження розв'язку (хоча б одного) рівняння f(x)=0 на відрізку [a,b] методом Ньютона (дотичних), супроводжуючи кожну ітерацію повідомленням про результати обчислень і графічною ілюстрацією.

37. Найкоротший шлях.

На екрані квадратне поле 1010. Випадково вибирається квадрат і у ньому встановлюється кулька (початкова позиція). На поле випадковим способом установлюється випадкове число перешкод –квадратів, рух через які заборонено. Користувач визначає координати будь-якого незайнятого квадрата (кінцева позиція). Скласти програму, що шукає найкоротший шлях кульки (або встановлює його неможливість) від початкової позиції до кінцевої і позначає її рух по знайденому шляху. Кулька може пересуватися тільки на одну клітинку по горизонталі та по вертикалі.

38. Скласти програму розв’язання системи двох рівнянь (у загальному випадку нелінійних) на інтервалі [a,b] графічним методом.

39. Скласти бібліотечний модуль програм для реалізації операцій над векторами з геометричною інтерпретацією результатів. Навести приклади застосування модуля.

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

• сумарна відстань від цієї точки до заданих точок мінімальна;

• відстані від цієї точки до заданих точок однакові між собою.

Рішення супроводжувати графічною інтерпретацією.

41. Деяка функція без особливостей задана на інтервалі [a,b] таблицею. Побудувати наближення функції, використовуючи:

• поліном Лагранжа;

• МНК (метод найменших квадратів);

• метод сплайнів.

Вивести графіки отриманих кривих на дисплей.

42. Програмно змоделювати на екрані ПК броунівський рух кінцевої множини молекул довільної (але однакової) форми у замкненому просторі. Реалізувати можливість зміни параметрів середовища.

43. Вхідними даними є множина з M N-вимірних векторів. Видалити з нього мінімальну кількість векторів так, щоб серед тих, що залишилися не було ортогональних.

44. У матриці, що складається з елементів 0 та 1, знайти кількість “островів”. “Островом” будемо звати компактну фігуру з поряд розміщених одиниць, яка обмежена замкненою лінією з нулів. Будемо вважати, що верхня, нижня, ліва та права границі матриці (тобто перший та останній стовпець, перший та останній рядок) складаються з нулів.

45. У матриці, що складається з нулів та одиниць, знайти найбільший квадрат, що цілком складається з одиниць.

46. Задача про ранець.

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

47. Свій літопис історик вів таким чином – кожен запис файлу зроблено за форматом

ДЕНЬ(арабськими)/МІСЯЦЬ(римськими)/РІК(арабськими)/Опис події.

Наприклад, 1/IX/2004/День знань.

Упорядкувати записи в літописі за зростанням дати.

48. Задача про два станка.

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

49. Гра “Життя”.

Поле складається з нескінченної кількості клітинок. На полі розташовано декілька “живих” клітинок. Процес зміни поколінь працює за такими правилами:

• Жива клітинка, що має двох або трьох сусідів залишається жити.

• Жива клітинка, що має більш за трьох сусідів гине від перенаселення.

• Жива клітинка, що має менш за двох сусідів гине від одинокості.

• У пустій клітинці, що має рівно три сусіди, народжується нове життя.

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