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

  Юрий  | 

  Обновл. 9 Июн 2019  | 

 7873

 ǀ   9 

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

Теория

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

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

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

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

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

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

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

Параметр по умолчанию — это параметр функции, который имеет значение по умолчанию. Если 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 (54 оценок, среднее: 4,94 из 5)
Загрузка...

Комментариев: 9

  1. Аватар Алексей:

    Немного заморочился. Конечно признаюсь — протупил с 3а.

  2. Аватар XHunter:

    Соответственно 3)б

  3. Аватар XHunter:

    Такой вариант функции 3)а предпочтительнее, т.к. только одно условие из трех выполняется в цикле

  4. Аватар Pere_Strelka:

    Появилась проблема: я не понимаю, как писать рекурсию. Т.е. я знаю, как она работает, понимаю, что это такое, но если встречу в коде рекурсию, то очень долго буду думать, что она вообще делает, а о том, чтобы написать хоть чуточку сложную рекурсию самому вообще не может быть речи. Эта тему важна? Может быть, есть какие-нибудь примеры, упражнения, чтобы начать понимать? Я хз.
    P.S. Может просто спать начать?)

    1. Аватар Никита:

      Как же я тебя понимаю! Аналогичная проблема.. Одно дело понять «формулу» , а другое дело уметь создавать её.. Сложна.
      Надо научится чтобы созданный маленький кусочек кода, делал то что тебе нужно. То есть твой вроде зацикленный код, на самом деле не стоит на месте , а делает шаг в нужном направлении.. Короче прочесть формулу это одно. А создавать ее самому — это другое.
      P.S. Я когда читаю рекурсивный код, то я туда «влезть» могу, а как дойду до базового случая , так выйти обратно (после return) — уже проблематично. Теряюсь . Это как фильм «Начало» и его Сон во сне во сне..)

  5. Аватар kmish:

  6. Аватар Andrey:

    Рекурсивная…

  7. Аватар Алена:

    Итеративная версия

  8. Аватар Алена:

    Рекурсивная версия

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

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