- •Конспект лекций Часть 2 Оглавление
- •Часть 2 1
- •8. Указатели
- •8.1. Указатели Понятие указателя
- •Работа с указателями
- •Арифметика указателей
- •Ошибки при работе с указателями
- •If (p1) // Если указатель не равен 0, то все в порядке
- •8.2. Указатели и массивы
- •9. Функции и структура программы
- •9.1. Создание и использование функций Процедурный подход к разработке программ
- •Определение функций в программе
- •Завершение работы функции (инструкция return)
- •If ( Ошибка )
- •Список параметров функций
- •Обращение к функциям в программе
- •Передача данных по значению
- •Передача данных с помощью указателей
- •Передача данных по ссылке
- •Перегружаемые функции
- •Параметры по умолчанию
- •Функции с переменным числом параметров
- •Рекурсивное использование функций
- •Передача функций в качестве параметров
- •Встраиваемые функции (inline - функции)
- •Прототипы функций
- •9.2. Структура программы. Глобальные и локальные данные (области видимости и время жизни) Структура программы
- •Глобальные и локальные данные
- •Классы памяти
- •Доступ к полям структур
- •Указатели на структуры
- •Структурные параметры функций
- •Битовые поля структур
- •10.2. Объединения Обычные объединения
- •Анонимные объединения
- •10.3. Перечисления
- •Void WriteColor (тип_Спектр c )
- •11. Организация ввода/вывода и работа с файлами
- •11.1. Потоки для работы с файлами Общие сведения
- •Пример работы с файлом
- •Создание потока, открытие и закрытие файла
- •Запись и чтение данных в текстовых файлах
- •Запись и чтение данных в двоичном режиме
- •If ( !File ) // Проверили удалось ли открыть файл
- •Как обнаружить конец файла?
- •Прямой доступ при работе с файлами
- •If ( !File ) // Проверили удалось ли открыть файл
- •Статус потоков ввода-вывода
- •Некоторые другие функции управления потоками ввода-вывода
- •Примеры по работе с файлами
- •12. Работа с динамической памятью Распределение памяти при работе программы
- •Динамическое выделение и освобождение памяти в стиле c
- •Возможные ошибки при работе с динамической памятью
- •Динамические массивы
- •Продолжение следует …
Рекурсивное использование функций
Функции внутри своего тела могут вызывать сами себя. Такой вызов называется рекурсией. На основе рекурсии можно строить очень интересные алгоритмы обработки данных.
Рассмотрим функцию возведения вещественного значения D в целую положительную степень P. Очевидная реализация этой функции основана на использовании цикла:
double Pow (double D, unsigned P)
{
double R = 1;
for (unsigned I = 0; I < P; ++ I)
R *= D;
return R;
}
А вот та же самая функция, реализованная на основе рекурсии:
double Pow (double D, unsigned P)
{
if (P)
return Pow ( D, P – 1 ) * D;
else
return 1;
}
Основанием для рекурсии в этом примере послужило следующее рекуррентное соотношение:
Более сложный пример рекурсии основан на следующем рекуррентном соотношении (обычная реализация этого примера приведена в разделе 5.1 конспекта):
Через рекурсию это рекуррентное соотношение реализуется так:
double T (unsigned n, double x)
{
switch (n)
{
case 0:
return 1;
case 1:
return x;
default:
return 2 * x * T (n - 1, x) - T (n - 2, x);
}
}
Как видно из этих примеров алгоритм, реализуемый через рекурсию, выглядит более компактным и понятным по сравнению с обычной реализацией. С точки зрения эффективности, реализацию этих примеров через рекурсию вряд ли можно считать более эффективной, чем обычную реализацию. Это объясняется дополнительными затратами времени на многократный вызов функций и дополнительными затратами памяти (стека) на передачу аргументов.
Однако в ряде случаев использование рекурсии позволяет достичь существенного положительного эффекта.
Рассмотрим следующий пример: необходимо написать функцию для вычисления биномиальных коэффициентов:
n >= 0, 0 <= m <= n.
Значение биномиального коэффициента определяет число различных вариантов выбора m объектов из n объектов (как говорят, число сочетаний из n по m).
Основные свойства биномиальных коэффициентов:
Максимальное значение биномиального коэффициента достигается при m = n / 2.
Очевидная реализация функции основана на использовании циклов для вычисления числителя и знаменателя биномиального коэффициента и нахождения частного от их деления:
unsigned C(int n, int m)
{
if (m > n / 2)
m = n - m;
unsigned a = 1, b = 1;
for (int i = n; i >= n - m + 1; -- i)
a *= i;
for (int i = 1; i <= m; ++ i)
b *= i;
return a / b;
}
Нетрудно заметить, что этот алгоритм быстро приводит к выходу значений числителя или знаменателя за пределы диапазона значений типа данных unsigned. И действительно, эксперименты с этим вариантом функции показывают, что точное вычисление биномиальных коэффициентов возможно только при n < 17.
Найдем следующее соотношение:
.
То есть:
.
Тогда справедливо следующее рекуррентное соотношение, позволяющее вычислять очередное значение биномиального коэффициента через его предыдущее значение:
Это рекуррентное соотношение реализуется с помощью следующей рекурсивной функции:
unsigned int C(unsigned int n, unsigned int m)
{
if (m > n / 2)
m = n - m;
if (m == 0)
return 1;
else
return C(n, m - 1) * (n - m + 1) / m ;
}
Этот вариант функции позволяет точно вычислять значения биномиальных коэффициентов при n < 31. Диапазон решения расширен почти в два раза.