Языки программирования. Лекция №6. Рекурсивные функции. Файловый ввод/вывод

1. Языки программирования

Лекция №6
1. Рекурсивные функции
2. Файловый ввод/вывод

2. 1. Рекурсивные функции

Рекурсивные функции - это функции, которые вызывают сами себя.
Такие функции довольно часто используются для обхода различных
представлений. Например, если нам надо найти определенный файл в
папке, то мы сначала смотрим все файлы в этой папке, затем смотрим
все ее подпапки и т.д.

3. 1. Рекурсивные функции

Пример:
Вычислить
факториал
числа
с
использованием
рекурсивной функции:
#include <iostream>
using namespace std;
long long factorial(int n)
{
if (n > 1)
return n * factorial(n - 1);
return 1;
}
int main()
{
int n = 5;
auto result = factorial(n);
cout << n << "! = " << result << "\n";
}

4. 1. Рекурсивные функции

В функции factorial задано условие, что если число n больше 1, то это
число умножается на результат этой же функции, в которую в качестве
параметра передается число n-1. То есть происходит рекурсивный
спуск. И так далее, пока не дойдем того момента, когда значение
параметра не будет равно 1. В этом случае функция возвратит 1.
Рекурсивная функция обязательно должна иметь некоторый
базовый вариант, который использует оператор return и к которому
сходится выполнение остальных вызовов этой функции. В случае с
факториалом базовый вариант представлен ситуацией, при которой n =
1. В этом случае сработает инструкция return 1;.

5. 1. Рекурсивные функции

Пример: Вычислить и вывести на консоль последовательность из n
первых чисел Фиббоначчи.
n-й член последовательности чисел Фибоначчи определяется по
формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1.
Значения f(0)=0 и f(1)=1, таким образом, определяют базовые варианты
для данной функции:

6. 1. Рекурсивные функции

#include <iostream>
using namespace std;
int fib(int n);
int main()
{
for (int i{}; i < 10; i++) {
int n = fib(i);
cout << n << "\t";}
cout << endl;
}
int fib(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
return fib(n - 1) + fib(n - 2);
}
0
8
1
13
1
21
2
3
34
5

7. 1. Рекурсивные функции

В разобранных примерах функция напрямую вызывала саму себя.
Но рекурсивный вызов функции также может быть косвенным.
Например, функция fun1() вызывает другую функцию fun2(), которая, в
свою очередь, вызывает fun1(). В этом случае функции fun1() и fun2()
также называются взаимно рекурсивными функциями.
Нередко рекурсивные функции можно представить в виде циклов. И
часто такие циклические конструкции более эффективны, чем
рексурсия.

8. 1. Рекурсивные функции

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

9. 1. Рекурсивные функции

Пример: алгоритм быстрой сортировки с использованием рекурсии
#include <iostream>
using namespace std;
void sort(int *numbers, int
start, int end);
void swap(int* numbers, int
first, int second);
#include <ios
using namespa
void sort(int
void swap(int
second);
int main()
{
int nums[
sort(nums
for (int

10. 1. Рекурсивные функции

Пример: алгоритм быстрой сортировки с использованием рекурсии
Быстрая сортировка — эффективный алгоритм сортировки на месте,
который обычно работает примерно в два-три раза быстрее, чем
Сортировка слиянием а также сортировка кучей при хорошей
реализации. Быстрая сортировка — это сортировка сравнением, то
есть она может сортировать элементы любого типа, для которых
“меньше, чем” и “отношение” определено.
Быстрая сортировка в среднем дает O(n.log(n)) сравнения для
сортировки n элементов. В худшем случае получается O(n2)
сравнения, хотя такое поведение встречается очень редко.

11. 1. Рекурсивные функции

Как работает быстрая сортировка?
Быстрая сортировка — это «разделяй и властвуй» алгоритм. Как и
все алгоритмы «разделяй и властвуй», он сначала делит большой
массив на два меньших подмассива, а затем рекурсивно сортирует
подмассивы. По сути, весь процесс включает три этапа:
1. Выбор опоры: Выберите элемент, называемый опорным, из
массива (обычно это самый левый или самый правый элемент
раздела).

12. 1. Рекурсивные функции

2. Разделение: Переупорядочите массив таким образом, чтобы все
элементы со значениями меньше опорного располагались перед
опорным. Напротив, все элементы со значениями больше, чем
точка опоры, идут после нее. Равные значения могут идти в
любом направлении. После этого разбиения стержень занимает
свое конечное положение.
3. Повторять: Рекурсивно примените описанные выше шаги к
подмассиву элементов с меньшими значениями, чем у опорного, и
отдельно к подмассиву элементов с большими значениями, чем у
опорного.

13. 1. Рекурсивные функции

Базовым случаем рекурсии являются массивы размером 1, которые не
нужно сортировать. На следующей диаграмме показано, как мы
выбираем крайний левый элемент в качестве опорного на каждом
этапе алгоритма быстрой сортировки, разбиваем массив по опорному
элементу и повторяемся в двух подмассивах, которые мы получаем
после процесса разделения:

14. 1. Рекурсивные функции

15. 1. Рекурсивные функции

Пример: алгоритм быстрой сортировки с использованием рекурсии
int main()
{
int nums[]{ 15, 0, 7, -3, -17, 12, 2
};
sort(nums, 0, size(nums) - 1);
for (int num : nums)
{
cout << num << "\t";
}
cout << endl;
}

16. 1. Рекурсивные функции

Пример: алгоритм быстрой сортировки с использованием рекурсии
void sort(int* numbers, int start, int end)
{
// начальный индекс должен быть меньше конечного индекса
для массива из 2 и более элементов
if (start >= end)
return;
// проверяем все элементы относительно элемента с индексом
start
int current{ start };

17. 1. Рекурсивные функции

Пример: алгоритм быстрой сортировки с использованием рекурсии
for (int i{ start + 1 }; i <= end; i++)
{
// если i-ый элемент меньше начального
if (numbers[i] < numbers[start])
{
swap(numbers, ++current, i); // меняем его с левым
}
}
swap(numbers, start, current); // Меняем выбранный (start)
и последний обмененный элементы

18. 1. Рекурсивные функции

Пример: алгоритм быстрой сортировки с использованием рекурсии
if (current > start)
{
sort(numbers, start, current - 1); //Сортируем
элементы слева
}
if (end > current + 1)
{
sort(numbers, current + 1, end); // Сортируем
элементы справа
}
}

19. 1. Рекурсивные функции

Пример: алгоритм быстрой сортировки с использованием рекурсии
void swap(int* numbers, int first, int second)
{
auto temp{ numbers[first] };
numbers[first] = numbers[second];
numbers[second] = temp;
}
-17
-3
0
2
7
12
15

20. ПРОСТОЙ ФАЙЛОВЫЙ ВВОД - ВЫВОД

Запись текстового файла
Для файлового вывода С++ использует аналог cout.
Для осуществления файлового вывода:
• Вы должны включить заголовочный файл fstream. Заголовочный
файл fstream определяет класс ofstream для обработки вывода.
• Вы должны объявить один или более объектов типа ofstream. Вы
должны учитывать пространство имен std, например, вы можете
использовать директиву using или префикс std:: для таких элементов,
как ofstream.

21. Для осуществления файлового вывода (прод.):

• Вы должны ассоциировать конкретный объект ofstream с
определенным файлом. Одним из способов сделать это является
применение метода open ( ) .
• По окончании работы с файлом вы должны использовать метод close( )
для закрытия файла.
• Вы можете использовать ofstream с операцией > > для чтения данных
различных типов.

22. Для осуществления файлового вывода (пример):

Ofstream outFile;
outFile.open("fish.txt");
double wt=125.8;
outFile.precision(2);
outFile<<wt<<endl;
outFile.close();
outFile может использовать те же методы ,
что и cout. Он может применять не только
операцию < < , но также разнообразные
методы форматирования, такие как setf( ) и
precision( ). Эти методы влияют только на
объект, который их вызывает.
Когда вы открываете существующий файл для вывода, по умолчанию он
усекается до нулевой длины и его старое содержимое утрачивается.
Бывает, что попытка открыть файл для вывода не удается. Например,
файл с указанным именем может уже существовать и иметь
ограничения доступа=>нужно проверять, удалась ли попытка открытия.

23. ПРОСТОЙ ФАЙЛОВЫЙ ВВОД - ВЫВОД

Чтение текстового файла
Файловый ввод базируется на консольном вводе. Для файлового ввода
С++ использует аналог cin.
Для осуществления файлового ввода:
• Вы должны включить заголовочный файл fstream. Заголовочный
файл fstream определяет класс ifstream для обработки вывода.
• Вы должны объявить один или более объектов типа ifstream. Вы
должны учитывать пространство имен std, например, вы можете
использовать директиву using или префикс std:: для таких элементов,
как ifstream.

24. Для осуществления файлового ввода (прод.):

• Вы должны ассоциировать конкретный объект ifstream с
определенным файлом; одним из способов сделать это является
применение метода open ( ) .
• Завершив работу с файлом, вы должны вызвать метод close( ) , чтобы
закрыть его.
• Вы можете использовать объект ifstream с операцией < < для чтения
данных различных типов.
• Вы можете использовать объект ifstream с методом get( ) для чтения
отдельных символов и с методом getline( ) - для чтения целых строк.

25. Для осуществления файлового ввода (прод.):

• Вы можете использовать объект ifstream с такими методами, как
eof( ) и fail( ), чтобы отслеживать успешность попыток ввода.
• Сам объект ifstream, когда присутствует в проверочных условиях ,
преобразуется в булевское значение true, если последняя попытка
чтения была успешной, и false - в противном случае.
Что случится, если вы
несуществующий файл?
попытаетесь
открыть
для
ввода

26. Открытие несуществующего для ввода файла?

Эта ошибка приведет к тому, что все последующие попытки
использовать объект ifstream для ввода будут обречены на провал.
Предпочтительный способ проверки того, удалось ли открыть файл,
заключается в применении метода is_open ( ). Вы можете использовать
для этого код вроде следующего:
ifstream inFile;
inFile.open ( "bowling.txt" );
if ( !inFile.is_open ( ) )
{ exit ( EXIT_FAILURE ) ;
}

27. Открытие несуществующего для ввода файла?

Метод is_ open ( ) возвращает true, если файл открыт успешно,
поэтому выражение !inFile.is_open ( ) вернет true, если попытка не
удастся. Прототип функции exit( ) находится в заголовочном файле
cstdlib , где также определена константа EXIT_FAILURE как значение
аргумента, используемого для взаимодействия программы с
операционной системой. Функция exit ( ) прерывает программу.
Метод is_open ( ) относительно новый в С++. Если ваш компилятор не
поддерживает его, вы можете применить вместо него метод good ( ) .
good ( ) не проверяет возможные проблемы настолько тщательно, как
это делает is_open ( ).

28.

ПРИМЕР
Программа открывает файл, указанный пользователем, читает из файла
числа, после чего сообщает количество прочитанных значений, их
сумму и их среднюю величину. Здесь важно правильно спроектировать
входной цикл.
28

29.

Простой файловый ввод - вывод
29

30.

Простой файловый ввод - вывод
30

31. Причины неудач при попытке открыть файл.

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

32. Несколько вещей, которые нужно проверять при чтении файла.

Программа не должна пытаться читать после достижения EOF. Метод
eof ( ) возвращает true, когда последняя попытка чтения данных
столкнулась с EOF.
Программа может столкнуться с несоответствием типа. Например,
программа из листинга ожидает файла, содержащего только числа.
Метод fail ( ) возвращает true, когда последняя попытка чтения
сталкивается с несоответствием типа. ( Этот метод также возвращает
true при достижении EOF.)

33. Несколько вещей, которые нужно проверять при чтении файла.

Что-нибудь может пойти не так - например, файл окажется
поврежденным или случится сбой оборудования. Метод bad ( ) вернет
true, если самая последняя попытка чтения столкнется с такой
проблемой. Вместо того чтобы проверять все эти условия
индивидуально, проще применить good ( ), которая возвращает true,
если все идет хорошо: whi1e ( inFile.good ( ) ) / / пока ввод работает и
не достигнут EOF
Затем при желании можно воспользоваться другими методами , чтобы
определить, почему именно был прерван цикл.

34.

if ( inFile.eof ( ) )
cout << "Достигнут конец файла . \ n " ;
elseif ( inFile.fail ( ) )
cout<<"Ввод прекращен из-за несоответствия данных.\n";
else
cout < < " Ввод прекращен по неизвестной причине .\n";
/ / стандартный дизайн цикла чтения
inFile > > value ; / / получить первое значение
while ( inFile.good ( ) ) / / пока ввод хорош и нет EOF
{ / / здесь находится тело цикла
inFile > > value ; / / получить следующее значение
}

35.

Этот код находится сразу после цикла, поэтому он исследует, почему
цикл был прерван. Поскольку eof ( ) проверяет только EOF, а fail ( )
проверяет как EOF, так и несоответствие типа, здесь вначале проверятся
именно EOF. Таким образом , если выполпение дойдет до elseif , то
достижение конца файла ( EOF) , как причина выхода из цикла, будет
исключена, и значение true , полученное от fail ( ) , недвусмысленно
укажет на несоответствие типа. Важно также понимать, что good ( )
сообщает лишь о самой последней попытке чтения ввода. Это значит,
что попытка чтения должна непосредственно предшествовать вызову
good ( ) . Стандартный способ обеспечения этого - иметь один оператор
ввода непосредственно перед началом цикла, перед первой проверкой
условия цикла, а второй - в конце цикла, непосредственно перед
следующей проверкой условия цикла:

36.

Код можно несколько сократить, используя тот факт, что выражение
inFile >> value возвращает сам inFile, а этот inFile, помещенный в
контекст, в котором ожидается значение bool, вычисляется как
inFile.good ( ) - то есть как true или false. Поэтому вы можете заменить
два оператора ввода одним, используя его в качестве условия цикла. То
есть предыдущую структуру цикла можно заменить следующей:
/ / сокращенный дизайн цикла чтения пропускает предшествующий
циклу ввод
while ( inFile >> value ) / / читать и проверить успешность
{ / / здесь находится тело цикла
/ / пропускает ввод в конце цикла
}

37.

Этот дизайн по-прежнему следует принципу попытки чтения перед
проверкой, потому что для того, чтобы оценить выражение inFile >>
value, программа сначала пытается выполнить его, читая число в
переменную value.

38. РЕЖИМЫ ДОСТУПА К ФАЙЛАМ

Режим файла описывает, как файл будет использоваться: для
чтения, записи, добавления информации и так далее.
Когда вы ассоциируете поток с файлом либо инициализацией объекта
файлового потока именем файла, либо с помощью метода open ( ) , вы
можете предоставить второй аргумент, описывающий режим файла:
ifstream fin ( «путь», режим ) ; / / конструктор с аргументом режима
ofstream fout ( ) ;
fout.open («путь», режим ) ; / / open ( ) с аргументом режима

39. РЕЖИМЫ ДОСТУПА К ФАЙЛАМ

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

40. РЕЖИМЫ ДОСТУПА К ФАЙЛАМ

41.

РЕЖИМЫ ДОСТУПА К ФАЙЛАМ
41

42.

42

43.

44.

44

45.

45