Рекурсия
Рекурсивным называется объект, частично или полностью определяемый посредством самого себя. Например, каждый элемент последовательности Фибоначчи представляет собой сумму двух предыдущих элементов: f(1)=f(2)=1, f(k)=f(k-1)+f(k-2) Использование идентификатора функции (процедуры) в теле самой функции (процедуры) называется рекурсивным обращением к функции (процедуре) или рекурсией.
Под рекурсией понимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.
Порождение все новых копий рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество копий рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом.
Поскольку рекурсивный вызов выполняется до окончания выполнения функции – размер стека увеличивается при каждом вызове до тех пор, пока не будет достигнута точка, когда выполняется возврат. Размер стека пропорционален глубине рекурсии.
Прямая – когда функция вызывает саму себя
Косвенная – когда две и более функции вызывают друг друга (например, функция f(…) вызывает функцию g(…), которая, в свою очередь, вызывает функцию f(…)).
Рекурсивный вызов обязательно сопровождался некоторым условием: либо условием окончания, либо условием продолжения, поскольку безусловные рекурсивные вызовы приводят к бесконечным процессам.
Структура рекурсивной функции может принимать три разных формы
(в записи используется условие продолжения):форма с выполнением действий до рекурсивного вызова
(на рекурсивном спуске) форма с выполнением действий после рекурсивного вызова
(на рекурсивном возврате — подъеме) форма с выполнением действий как до (на рекурсивном спуске), так и после рекурсивного вызова (на рекурсивном возврате)
Рекурсивными алгоритмами имеет смысл пользоваться, если имеется явное рекурсивное определение обрабатываемых данных, поскольку преобразование естественной рекурсивной формы в итеративную – довольно сложная задача.
Сортировки
Выбором
Обменом
ООП
Объектно-ориентированное программирование (ООП ) – это методика разработки программ, в основе которой лежит понятие объекта, как некоторой структуры, описывающей объект реального мира и его поведение.
Класс – это сложная структура, включающая в себя описания данных, процедур и функций, которые могут быть выполнены над объектом.
Объект – это осязаемая сущность, которая четко проявляет свое поведение.
Методы - функции и процедуры класса, которые содержат исходный код, предназначенный для обработки внутренних данных объекта данного класса.
Инкапсуляция (по-русски: «сокрытие») — это свойство объектов скрывать некоторые свои данные и способы их обработки (методы) от окружающей его цифровой среды и, в частности, от кривых ручонок малоопытных программистов, оставляя «снаружи» только необходимые и/или требуемые свойства и функциональные возможности.
Наследование – механизм получения новых классов, посредством добавления полей, свойств и методов к уже существующим классам. При этом новый класс (потомок) наследует свойства и методы родительского класса (предка).
Полиморфизм – это возможность использовать одинаковые имена для методов, входящих в различные классы. Принцип полиморфизма обеспечивает при применении метода к объекту использование именно того метода, который соответствует классу объекта.
Тестирование и отладка программ
Принципы тестирования:
Ошибки в программе есть.
Тест – совокупность исходных данных и ожидаемых результатов.
Тестовые данные должны быть достаточно просты для проверки
Тесты готовят заранее, до выхода на машину
Первые тесты разрабатываются после получения задания на разработку программы до написания программного кода
Перед началом тестирования должны быть сформулированы цели. Которые должны быть достигнуты в ходе тестирования.
В процессе тестирования необходимо фиксировать выполненные тесты и реально полученные результаты.
Тесты должны быть одинаково тщательны как для правильных, так и для неправильных входных данных
Необходимо проверить два момента:
a) Программа делает то, что должна делать
b) Программа не делает то, чего делать не должна
Результаты теста необходимо изучить досконально и объяснить полностью
Недопустимо изменять программу для упрощения тестирования
После исправления программы необходимо повторное тестирование (по полной схеме!)
Ошибки «кучкуются», т.е. чем больше ошибок обнаружено в модуле, тем выше вероятность, что там есть ещё.
Окончательное тестирование должен проводить не автор программы.
Понятие полноты тестирования:
Исчерпывающее тестирование (т.е. перебор всех существующих вариантов) для нетривиальной программы невозможно.
Для уменьшения количества проверяемых вариантов необходима классификация: выделение сходных объектов по определённым признакам.
Критерии, по которым проводится классификация всех возможных вариантов выполнения программы с точки зрения её правильности называют критериями полноты тестирования.
Существует два подхода к формированию полноты тестирования: критерии чёрного ящика (без учёта внутреннего устройства программы) и критерии белого ящика (с учётом структуры программы).
Критерии чёрного ящика:
Тестирование функций
Тестирование классов входных данных
Тестирование классов выходных данных
Тестирование области допустимых значений (границ класса)
Тестирование длины набора данных
Тестирование упорядоченности набора данных
Необходимо проверять работу программы на допустимых, недопустимых и пограничных данных.
Критерии белого ящика:
Критерий покрытия операторов – такой набор данных, чтобы каждый оператор в программе был выполнен хотя бы 1 раз.
Критерий покрытия ветвей (решений) – такой набор данных, чтобы каждая ветвь в программе была выполнена хотя бы 1 раз.
Критерий покрытия путей – такой набор данных, чтобы каждый путь в программе был выполнен хотя бы 1 раз (слишком строгий – путей в циклических алгоритмах может быть бесконечно много).
Критерий покрытия условий – такой набор данных, чтобы каждое простое условие (слагаемое в дизъюнкции и сомножитель в конъюнкции) получило значение «истина» и значение «ложь» хотя бы 1 раз.
Ошибкоопасные ситуации:
Обращение к данным
Использование значения переменной (переменная не инициализирована)
Автоматическая инициализация переменных (неверная инициализация)
Индексация массива (выход за границу).
Изменение переменной внутри блока (побочный эффект – изменение глобальной переменной при выполнении подпрограммы)
Схожие имена переменных – не ошибка, но чревато опечатками
Ошибки, связанные с использованием динамической памяти.
Ошибкоопасные ситуации:
Вычисления
Выражение (неверный порядок действий, приоритет операций)
Логическое выражение (краткая и полная схема вычисления такого выражения)
Сравнение > (<) – риск потерять =
Сравнение > и >= (< и <=) – риск лишнего выполнения тела цикла
Деление (/0), извлечение квадратного корня, взятие логарифма и т.п.
Присваивание целой переменной вещественного значения
Ошибкоопасные ситуации:
Вычисления
Вычисления с плавающей точкой
n Погрешности округления (a:=1.0/3; b:=a*3, в результате a!=b)
n Потеря значимости – слишком маленькая мантисса в машинной арифметике обращается в нуль
Сравнение вещественных чисел
n Погрешности округления, так что лучше сравнивать по модулю разности с некоторым ε
Арифметические вычисления
n Переполнение (как вещественное, так и целое), в том числе и в промежуточных вычислениях.
Ошибкоопасные ситуации:
Передача управления
Развилки (пропущена ветвь «иначе»)
Вложенные условные операторы
Циклы: зацикливание в результате
n неправильно написанного условия продолжения/выхода
n отсутствия модификации в теле цикла параметра в условии продолжения/выхода
Ошибкоопасные ситуации:
Подпрограммы
Вызов подпрограммы
n Неверное количество параметров
n Неверные типы параметров
n Неверный порядок следования параметров.
Использование параметров внутри подпрограммы (неверные единицы измерения параметров – градусы/радианы, дюймы/сантиметры/метры и т.п.)
Использование формального параметра внутри подпрограммы для изменения значения соответствующего фактического параметра (неверный способ передачи параметра – по ссылке / по значению)
Использование внутри подпрограммы формальных параметров, передаваемых по ссылке (одна и та же переменная может быть использована одновременно для нескольких параметров, передаваемых по ссылке, то есть к одной и той же величине будут обращаться из подпрограммы одновременно по разным именам, на этой величине отразятся все изменения)
Использование внутри подпрограммы глобальной переменной и параметра, передаваемого по ссылке (одновременный доступ к одной и той же переменной через параметр, передаваемый по ссылке и через глобал) – не ошибка, но требует внимания.
Ошибкоопасные ситуации:
Файлы
Запись/чтение двоичных файлов (путаница между различными типами файлов, запись данных одного типа, а чтение – как другого типа)
Создание и просмотр файлов с помощью текстового редактора (некорректная обработка)
Запись в файл (отсутствие явного закрытия файла, как следствие – последняя порция информации из буфера обмена не попадёт на диск)
Порядок работы над программой:
Сначала подготавливаются тесты по критериям чёрного ящика – до написания программы. Тесты занести в таблицу тестов, в которой предусмотрены графы как для входных данных и ожидаемых результатов, так и для реальных результатов и отметки о совпадении
Пишется текст программы
Проверка текста программы исходя из ошибкоопасных ситуаций
Составляется таблица МГТ (минимально грубое тестирование) по критериям белого ящика
Прогнать тесты из п.1, с трассировочными таблицами
При необходимости программа корректируется, проверяются места корректировки на ошибкоопасность, повторить п.5.
Заполнить таблицу тестов и таблицу МГТ
Если таблица МГТ ещё не заполнена, добавить и провести необходимые тесты
Прогнать программу. При необходимости -- скорректировать программу, проверить места корректировки на ошибкоопасность
Заполнить таблицу тестов и таблицу МГТ.