Інформатика – Поглиблений рівень

Прочитайте!

Процес створення комп’ютерної програми для вирішення будь-якої практичної задачі складається з декількох етапів:

• формалізація і створення технічного завдання на вихідну задачу;
• розробка алгоритму вирішення задачі;
• написання, тестування, наладка і документування програми;
• отримання розв’язку вихідної задачі шляхом виконання програми.

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

Алгоритм – це механізм, який не тільки повинен гарантувати те, що вирішення колись буде знайдене, але й те, що буде знайдене саме оптимальне, тобто найкраще вирішення. Крім того, алгоритм повинен мати наступні п’ять якостей:

1. Обмеженість в часі – робота алгоритму обов’язково повинна завершитись через деякий розумний період часу.
2. Правильність – алгоритм повинен знаходити правильне, а не будь-яке рішення.
3. Детермінованість – скільки б разів не виконувався алгоритм з однаковими вхідними даними, результат повинен бути однаковим.
4. Скінченність – опис роботи алгоритму повинен мати скінчену кількість кроків.
5. Однозначність – кожний крок алгоритму повинен інтерпретуватися однозначно.

Алгоритм повинен задовольняти наступні протиріччя:

•  Бути простим для розуміння, перекладу в програмний код і наладки.
• Ефективно використовувати комп’ютерні ресурси і виконуватися швидко.

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

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

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

Більшість алгоритмів надає вибір між швидкістю виконання і ресурсами. Задача може виконуватися швидше, використовуючи більше пам’яті, або навпаки – повільніше з меншим обсягом пам’яті.

Прикладом в даному випадку може слугувати алгоритм знаходження найкоротшого шляху. Задавши карту вулиць міста у вигляді мережі, можна написати алгоритм, що обчислює найкоротшу відстань між будь-якими двома точками цієї мережі. Замість того, щоб кожного разу заново перераховувати найкоротшу відстань між двома заданими точками, можна наперед прорахувати її для всіх пар точка і зберегти результати в таблиці. Тоді, щоб знайти найкоротшу відстань для двох заданих точка, достатньо буде просто взяти готові значення з таблиці. При цьому отримують результат, практично, миттєво, але це зажадає великий обсяг пам’яті. Карта вулиць для великого міста може містити сотні тисяч точок. Для такої мережі таблиця найкоротших відстаней містила б більше 10 мільярдів записів. В цьому випадку вибір між часом виконання і обсягом необхідної пам’яті очевидний.

При порівнянні різних алгоритмів важливо розуміти, як складність алгоритму співвідноситься із складністю вирішуваної задачі. При розрахунках за одним алгоритмом сортування тисячі чисел може зайняти 1 секунду, а сортування мільйона – 10 секунд, тоді як розрахунки за іншими алгоритмами можуть зайняти 2 і 5 секунд відповідно. У цьому випадку не можна однозначно сказати, яка із двох програм краща – це буде залежати від вихідних даних.

Працюємо за ПК!

Завдання 1. Складіть програму для обчислення суми n перших натуральних чисел: S=1+2+…+n.

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

• якою може бути найбільша висота піраміди, якщо ви знаєте кількість рядів;
• скільки деталей віддали другу, та яка кількість деталей використана;
• якщо використано всі деталі – вивести повідомлення про це.

Завдання 3.  Дано чотирицифрове натуральне число n (n<9999). Визначте, чи є воно паліндромом («перевертнем»), з урахуванням чотирьох цифр. Наприклад, паліндромами є числа: 2222, 6116, 0440.

Підказка. Отже, у нас чотиризначне число, тому змінна оператора for змінюється від 1 до 4. У змінної з ім’ям m зберігається «залишок» числа, в початковий момент часу він дорівнює введеному числу. В змінної з ім’ям r формуємо значення числа- «перевертня». Основними операціями є: r=r*10 + m%10 (додавання чергової] цифри до числа «перевертня») і m=m//10 (зміна числа, що перевіряється). Процедура трасування наведена в таблиці. Після її виконання написання програми не являє складнощів.

Розглянемо алгоритм розв’язування задачі:

• ввести значення n та m присвоїти значення n;
• за допомогою циклу обчислити r;
• використавши команду розгалуження вивести результат.

Завдання для самостійного виконання

Задача 4. Мама попросила Васю полити всі молоді деревця у саду. Вася знає, що поки дерева маленькі, їх потрібно дуже добре поливати. А ось скільки поливати – невідомо. Але Вася – дуже розумний хлопчик. Він уважно прочитав весь підручник ботаніки для середньої школи і вияснив, що для гарного росту дерев достатньо виливати під дерево щоденно по 0,5 літри води для кожного листка. На щастя Васі виявилось, що листки на деревах ростуть ярусами, причому на верхньому ярусі два листка, на другому – чотири, на наступному – шість, і так далі, на кожному наступному ярусі на два листки більше у порівнянні з попереднім. А на самій верхівці росте ще один листочок. Хитрий Вася послав молодшу сестричку Машеньку підрахувати кількість ярусів на кожному дереві, а Вас просить написати програму, яка для кожного дерева обрахує кількість літрів води для його поливу.

Завдання 5. Складіть програму для обчислення факторіала. (Факторіал натурального числа n – добуток натуральних чисел від одиниці до n включно, позначається n!)