Глава 7. Итоговый тест

  Юрий Ворон  | 

    | 

  Обновлено 2 Фев 2018  | 

 2232

Еще одна глава пройдена! Впереди самое сердце этого туториала – объектно-ориентированное программирование, мы почти добрались! Осталась всего лишь одна ступенька — итоговый тест.

Теория

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

  передачу по значению для фундаментальных типов данных и перечислителей;

  передачу по ссылке (константной) для структур, классов или когда нужно, чтобы функция изменяла значение аргумента;

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

Возврат значений по ссылке, по адресу или по значению. В большинстве случаев используется возврат по значению, однако возврат по ссылке или по адресу также может быть полезен при работе с динамически выделенными данными, структурами или классами. Если используете возврат по ссылке или по адресу, убедитесь, что не возвращаете чего-то, что выйдет из области видимости.

С помощью встроенных функций вызов функции можно заменить на непосредственный код этой функции.

Перегрузка функций позволяет создать несколько функций с одним и тем же именем, но при условии, что параметры этих функций будут разные. Возвращаемое значение не считается параметром.

Параметр по умолчанию — это параметр функции, который имеет значение по умолчанию. Если caller не передает значение для параметра, то будет использоваться значение по умолчанию. У вас может быть несколько параметров со значениями по умолчанию. Они всегда должны находиться справа от обычных параметров. Параметр по умолчанию может быть установлен только в одном месте. Обычно его размещают в предварительном объявлении функции. Если же предварительного объявления нет, то его размещают в определении функции.



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

Динамическая память выделяется из Кучи.

Стек вызовов отслеживает все активные функции (те, которые были вызваны, но еще не завершены) от начала программы и до текущей точки выполнения. Стек имеет ограниченный размер. std::vector можно использовать в качестве стека.

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

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

Семантическая ошибка возникает, когда код синтаксически правильный, но выполняет не то, что нужно программисту. Среди семантических ошибок распространены логические ошибки и ложные предположения. Оператор assert используется для обнаружения ложных предположений, но его недостаток заключается в том, что при ложном утверждении выполнение программы немедленно прекращается.

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

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

Тест

Задание №1

Напишите прототипы функций для следующих случаев. Используйте const при необходимости.

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

Ответ а)

b) Функция swap(), которая меняет местами два целых числа.

Ответ b)

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

Ответ c)

Задание №2

Что не так со следующими программами?

a)

Ответ а)

doSomething() возвращает ссылку на локальную переменную, которая будет уничтожена при завершении выполнения doSomething.

b)

Ответ b)

Рекурсивная функция sumTo() не имеет условия завершения. Значение переменной value в конечном счете станет отрицательным, и функция будет выполняться бесконечно вплоть до возникновения переполнения стека.

c)

Ответ c)

Две функции divide не отличаются друг от друга никак, так как имеют одно и то же имя и одинаковые параметры.

d)

Ответ d)

Массив слишком велик для размещения в стеке. Его следует выделять динамически.

e)

Ответ 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.

Ответ а)

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

Ответ b)

Оценить статью:

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (17 оценок, среднее: 4,94 из 5)
Загрузка...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

ВОЛШЕБНАЯ ТАБЛЕТКА ПО С++