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

  Юрий  | 

  |

  Обновл. 29 Янв 2021  | 

 36405

 ǀ   28 

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

Теория

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

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

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

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

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

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

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

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

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

  1. Илья:

    С возвратом -1 и правда забавная история выходит. По идее, автор добавил дополнительную проверку, за что мне хотелось ему написать благодарность, но вышло иначе. При возврате «-1» из функции, совершенно без сомнений мы берём минус первый элемент массива (!), который, по прекрасному совпадению в адресной арифметике указывает на переменную x — несложно убедиться, выведя &x и &(array[-1]).

    x в этой ситуации, разумеется, равен самому себе и мы видим совершенно неверный вывод о том, что наш элемент на минус первом месте.

    Думаю, корректно будет сначала проверять на отрицательное значение, а затем уже — если оно неотрицательное — выводить его позицию. Подставлять индекс без проверки границ совершенно неправильная практика.

    1. myrrrca:

      спасибо за объяснение!

  2. Юрий:

    №3.а) итеративная версию функция:

    №3.b) рекурсивная версию функция:

    1. Дмитрий:

      Уважаемый Юрий , в вашем примере 3b в строке 3 есть ошибка. Правильно будет так: if(min>max)return -1;

      Т.к. если мы будем искать число,которое будет находиться в конце массива(т.е иметь индекс max ), то , пользуясь вашим примером , мы получим -1.

  3. warner12:

    Уважаемый автор, прошу изменить условие ветвления в функции main() последнего задания

    с "if (array[index] == x)"
    на "if (index >= 0)"

    в связи с тем, что обращение к элементу массива -1 приводит к непредсказуемым результатам у меня и у других членов сообщества.

  4. Jaroshevskii:

    Как-то так .

    Задание №3

    a)

    b)

    1. YuZo:

      Возвращать -1 это нормальная практика, именно это и используют обычно для обозначения ошибок или негативных результатов выполнения программы/функции (в данном случае если мы не можем найти искомый элемент значит результат будет по сути негативным, поэтому то и -1)

  5. Андрей:

    Поясните пожалуйста, почему вариант вычисления середины

    предпочтительнее

    При каких условиях может возникнуть переполнение, если использовать 2-й вариант?

    1. 4b6rat0r:

      Приветствую! Как я понял что определение 1.

      что и определение 2.

      Можно использовать в алгоритме двоичного поиска при условии что определение 1. действительно для чисел которые находяться в маленьком диапазоне. 0, 100, 1000, 10000. Определение 2. подходит для случаев когда переменные min и max находяться достаточно близко к границам максимально доступного диапазона хранимого в переменной типа int [-2147483648, 2147483647]

      Главным образом определение 2. связано со случаями когда нужно быть точно уверенными результат операции деления отрезка сможет вместить в себе диапазон int.

      Таким образом определение 1. должно точно обезопасить переменную foo от переполнения.

    2. Sergei:

      Переполнение может возникнуть при вычислении (max + min) (до деления на 2).

  6. nZver:

    Неужели я один столкнулся со следующей проблемой: в третьем тесте, вводимое пользователем в переменную х число сразу после ввода становится значением [-1]-го элемента массива, и любое введённое число, не входящее в массив в результате выводится как найденное по индексу [-1]. Если возвращать функцией любое другое отрицательное число (например -2) — программа отрабатывает как надо. (к слову, программа полностью совпадает с ответом 3.а и листингом в самом задании)

  7. Роман:

    Доброго времени суток. При реализации рекурсивной функции столкнулся с интересным момментом, который затрудняюсь для себя обяснить. Хотелось бы получить пояснение.

    Листинг:

    На выходе имеем -1 в случае, если элемент массива существует или ошибку переполнения стека Segmentation fault (core dumped) в случае, если искомого элемента в массиве не существует. Вопрос: почему выполняется оператор return -1, хотя по моей логике (очевидно ошибочной) он не должен выполниться никогда? В чем мое заблуждение?

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

      Надо проследить за ходом рекурсии. Например, входим в функцию из основной программы (первый, основной вызов). Начинается проверка условий, и, предположим, сработал самый первый if(array[averageIndex] > target). В этом случае рекурсивно вызывается binarySearch(array, target, min, averageIndex — 1). Повторно входим в функцию и опять начинается проверка условий. Пусть в этот раз не выполнился ни один if, и следовательно сработал последний else, который вернул averageIndex (return averageIndex;). Вопрос, куда мы вернулись и с чем? А вернулись в первый вызов, в точку откуда был вызван binarySearch(array, target, min, averageIndex — 1). Сразу надо отметить, что возвращаемое значение при таком вызове теряется, потому что оно не присвоено никакой переменной. Какое состояние функции первого вызова в этой точке? Видим, что других стейтментов в теле первого if нет и больше ничего выполнять не надо. А поскольку первый if выполнился, то дальнейшая цепочка else if — else пропускается и мы приходим в точку где у нас стейтмент return -1; Вспоминаем, что мы находимся в первом вызове и, следовательно, этот return возвращает -1 в основную программу как результат вызова функции

  8. Виктор:

  9. Дмитрий:

    Хорошие уроки. Спасибо за Ваш труд!
    У меня получилась такая версия :

  10. Аноним:

    Мой код по заданию немного отличается от ответов. Может кто поделиться мнением, какие версии лучше (правильнее) использовать?

  11. Sagynysh:

    3b
    правда, потупила

  12. Sagynysh:

    Моя версия 3а

  13. Константин:

    Не такой красивый, как в ответе, но свой вариант:

    3a:

    3b:

  14. Алексей:

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

  15. XHunter:

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

  16. XHunter:

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

  17. Pere_Strelka:

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

    1. Никита:

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

  18. kmish:

  19. Andrey:

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

  20. Алена:

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

  21. Алена:

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

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

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