Розділ №7. Підсумковий тест

  Оновл. 1 Вер 2021  | 

 1571

 ǀ   1 

Ще один розділ позаду! Попереду серце цього туторіалу — об’єктно-орієнтоване програмування, ми майже дійшли! Залишилася лише одна сходинка — підсумковий тест.

Теорія

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

   передачу по значенню для базових типів даних і енумераторів;

   передачу по (константному) посиланню для структур, класів або в тих випадках, коли потрібно, щоб функція змінювала значення аргументу;

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

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

За допомогою вбудованих функцій виклик функції можна замінити на код цієї функції.

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

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

Вказівники на функції дозволяють передати одну функцію в якості аргументу іншій функції.

Динамічна пам’ять виділяється з купи.

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

std::vector можна використовувати в якості стеку.

Рекурсивна функція — це функція, яка викликає саму себе. Для всіх рекурсивних функцій повинна бути умова завершення.

Синтаксична помилка виникає, коли ви пишете код, який порушує правила граматики мови C++. Компілятор такі помилки легко ловить.

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

Стейтмент assert використовується для виявлення помилкових припущень, але його недолік полягає в тому, що при помилковому твердженні виконання програми негайно зупиняється.

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

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

Тест


Завдання №1

Напишіть прототипи функцій для наступних випадків. Використовуйте const при необхідності.

a) Функція з іменем max(), яка приймає два значення типу double і повертає більше з них.

Відповідь №1.а)

b) Функція swap(), яка міняє місцями два цілих числа.

Відповідь №1.b)

c) Функція getLargestElement(), яка приймає динамічно виділений масив цілих чисел і повертає найбільше число таким чином, що caller може змінити значення елементу, що повертається (не забудьте про параметр-довжину).

Відповідь №1.c)

Завдання №2

Що не так з наступними програмами?

a)

Відповідь №2.а)

Функція doSomething() повертає посилання на локальну змінну, яка буде знищена при завершенні виконання doSomething().

b)

Відповідь №2.b)

Рекурсивна функція sumTo() не має умови завершення. Значення змінної value в кінцевому підсумку стане від’ємним, і функція виконуватиметься нескінченно, аж до виникнення переповнення стеку.

c)

Відповідь №2.c)

Дві функції divide() не відрізняються одна від одної ніяк, так як мають одне і те ж ім’я і однакові параметри.

d)

Відповідь №2.d)

Масив занадто великий для розміщення в стеці. Його потрібно динамічно виділити.

e)

Відповідь №2.e)

argv[1] може і не існувати взагалі. Якщо ж він існує, то це буде рядок C-style, який не може бути конвертований в ціле число через операцію присвоювання.

Завдання №3

Кращим алгоритмом для визначення того, чи існує значення у відсортованому масиві, є бінарний пошук.

Бінарний пошук працює наступним чином:

   Дивимося на центральний елемент масиву.

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

   Якщо центральний елемент менше елементу, який ми шукаємо, то відкидаємо все, що знаходиться ліворуч від центрального елементу.

   Якщо центральний елемент дорівнює елементу, який ми шукаємо, то повертаємо індекс цього елементу.

   Якщо перебрали весь масив і не знайшли шуканого значення, то повертаємо контрольне значення з повідомленням not found.

Оскільки в кожній ітерації ми можемо відкидати відразу половину масиву, то швидкість виконання цього алгоритму досить висока. Навіть з масивом в мільйон елементів для визначення того, чи існує конкретне значення в цьому масиві чи ні, знадобиться не більше 20 ітерацій! Однак бінарний пошук працює тільки в відсортованому масиві.

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

Розглянемо приклад роботи цього алгоритму з масивом {4, 5, 7, 10, 11, 14, 19, 20, 25} і шуканим значенням 7. Спочатку min = 0, max = 8, так як ми перебираємо весь масив (всього елементів 9, але індекс останнього елементу — 8).

   Ітерація №1: Обчислюємо середнє значення між min (0) і max (8), яке дорівнює 4. Елемент №4 має значення 11, яке більше нашого шуканого значення. Оскільки масив відсортований, то ми знаємо, що всі елементи, які знаходяться праворуч від індексу 4 (і індекс 4 теж) є більше нашого шуканого числа. Тому min залишаємо в спокої, а max змінюємо на 3.

   Ітерація №2: Обчислюємо середнє значення між min (0) і max (3), яке дорівнює 1. Елемент №1 має значення 5, яке менше нашого шуканого значення. Оскільки масив відсортований, то ми знаємо, що всі елементи, які знаходяться ліворуч від індексу 1 (і індекс 1 теж) — менше нашого шуканого числа. Отже, min змінюємо на 2, а max залишаємо в спокої.

   Ітерація №3: Обчислюємо середнє значення між min (2) і max (3), яке дорівнює 2. Елемент №2 має значення 7, яке є нашим шуканим числом. Повертаємо елемент №2.

Використовуючи наступний код:

a) Напишіть ітеративну версію функції binarySearch().

Відповідь №3.а)

b) Напишіть рекурсивну версію функції binarySearch().

Відповідь №3.b)

Оцінити статтю:

1 Зірка2 Зірки3 Зірки4 Зірки5 Зірок (45 оцінок, середня: 5,00 з 5)
Завантаження...

Коментарів: 1

  1. Костянтин :

    Досить дивний метод перевiрки результату пошуку

    Потрибно перевiряти контрольне значення, в данному випадку -1.
    Згiдно з уроком 77, в масиві довжиною N елементи будуть пронумеровані від 0 до N-1. Якшо вибрати елемент масива з iндексом -1, то ми отримаємо смiття.
    Хоча в данному випадку компiлятор розташовуе в стеку змiнну x перед масивом, тому iндекс -1 масива буде вказувати на змiнну x. Це призводить до дивних речей, вираз array[index] == x завжди повертатиме true навiть коли шуканого значення там немає.

Залишити відповідь

Ваш E-mail не буде опублікований. Обов'язкові поля відмічені *