- •1. Основы алгоритмизации и программирования
- •1.1. Этапы подготовки и решения задач на эвм
- •1.2. Алгоритмы и способы их описания Понятие алгоритма
- •Способы описания алгоритмов
- •Структурные схемы алгоритмов
- •1.3. Компиляция и интерпретация программ
- •1.4. Стили программирования
- •Процедурное программирование
- •Функциональное программирование
- •Логическое программирование
- •Объектно-ориентированное программирование
- •2.1. Пример готовой программы.
- •2.2. Структура основной программы
- •2.3. Алфавит языка
- •2.4. Константы и переменные Константы
- •Переменные
- •Примеры записи имен переменных
- •2.5. Арифметические выражения
- •Примеры вычисления арифметических выражений
- •Стандартные функции
- •Примеры программирования арифметических выражений
- •Контрольные задания
- •1. Составить описания для заданных переменных
- •2.6. Линейные вычислительные процессы
- •Оператор присваивания
- •Странные операторы присваивания
- •Функции ввода-вывода
- •Функции ввода исходных данных с клавиатуры
- •Потоковый ввод данных числового типа
- •Функция форматного ввода
- •Операторы вывода данных на экран Потоковый вывод
- •Форматный вывод
- •Контрольные задания
- •2.7. Разветвляющиеся вычислительные процессы
- •If (логическое выражение) p1; else p2;
- •Логические выражения
- •Порядок выполнения операций в логических выражениях
- •Условные операторы
- •Короткий условный оператор
- •Полный условный оператор
- •If (логическое выражение) { p1;} else {p2;}
- •Вложенные структуры условных операторов
- •Оператор выбора
- •Контрольные задания
- •2.8. Циклические вычислительные процессы
- •Операторы цикла с условием
- •Оператор цикла с параметром
- •2.9. Базовые алгоритмы
- •Задача 1. Алгоритм организации счетчика
- •Задача 2. Алгоритм накопления суммы
- •Задача 3. Алгоритм накопления произведения
- •Задача 4. Алгоритм поиска минимального члена последовательности
- •Задача 5. Табулирование функции (или кратные циклы)
- •Задача 6. Вычисление сумм элементов последовательностей
- •2.10. Указатели и массивы
- •2.10.1. Указатели
- •2.10.2. Понятие массива
- •Одномерные массивы
- •Описание одномерного массива
- •Индексированные переменные
- •Ввод-вывод одномерных массивов
- •Обработка одномерных массивов
- •Задача 1. Организация счетчика
- •Задача 2. Накопление суммы и произведения
- •Задача 3. Поиск минимального и максимального элементов массива
- •Двухмерные массивы
- •Описание двухмерного массива
- •Ввод-вывод двухмерного массива
- •Обработка матриц
- •2.11. Подпрограммы Структура сложной программы
- •Функции
- •Общий вид описания функции
- •Int I,j; //локальные переменные
- •Обращение к функции
- •Пример программы с функцией
- •Механизмы замены параметров
- •Параметры-массивы в функциях
- •Примеры программирования задач с использованием подпрограмм Задача 1
- •Рекурсия
- •2.12. Текстовые данные
- •Символьный тип данных
- •Ввод-вывод символьных данных
- •Обработка символьных данных
- •Ввод-вывод строковых данных
- •Обработка строковых данных
- •Стандартные функции обработки строк
- •Сравнение строк:
- •Сцепление строк
- •Определение длины строки
- •Копирование строк
- •Поиск символа в стоке
- •Пример программы для задачи с текстовыми данными
- •Контрольные задания
- •2.13. Динамическое выделение памяти
- •Структуры данных Понятие структуры
- •Обработка структур
- •Пример задачи с использованием структурированных данных
- •2.15. Файлы данных Понятие файла
- •2.15.1. Работа с файлами в стиле с
- •Объявление файловой переменной
- •Открытие файла
- •Закрытие файла
- •// Обработка открытого файла
- •Обработка открытого файла
- •Функции ввода/вывода
- •Работа с текстовыми файлами
- •Обработка бинарных файлов
- •Контрольные задания
- •Заключение
- •Оглавление
Рекурсия
В теле функции известны все объекты, описанные во внешнем блоке, т.е. все глобальные переменные и имя самой функции.
Таким образом, внутри любой функции можно вызывать любую доступную функцию, в том числе и саму себя. Ситуация, когда функция вызывает саму себя, называется рекурсия.
Рекурсия возможна благодаря тому, что при вызове функции создаются новые экземпляры локальных переменных, которые сохраняются во внутреннем стеке машины. Стек функционирует по принципу LIFO - Last In – First Out (последний вошел – первый вышел).
Переменные помещаются в стек одна за другой и выбираются из стека в обратном порядке.
Обязательным элементом всякого рекурсивного процесса является утверждение, определяющее условие завершения рекурсии. Оно называется опорным условием рекурсии.
Если опорное условие выполняется, то может быть задано некоторое фиксированное значение, заведомо достижимое в ходе вычисления. Это позволит организовать своевременную остановку рекурсивного процесса.
Рассмотрим пример вычисления факториала 5.
, где - это 4!
т.е 5!=4!5
Факториал нуля равен 1. Отсюда формула вычисления N-факториала:
Реализуем вычисление факториала в виде функции:
#include "stdafx.h"
float fact(int N) //рекурсивная функция вычисления факториала числа N
{
Обращение функции к самой себе
if (N==0)
return 1;
else
return (fact(N-1)*N);
}
void main()
{ int N=15;
printf("факториал 15=%f\n",fact(N)); /* обращение к функции fact для вычисления факториала 15 */
}
Аппарат рекурсии можно применять для решения различных задач, где необходимо многократное повторение однотипных действий.
Пример: Вычислить количество нулей в массиве А[10].
# include "stdafx.h"
const int n=10;
int kol(int i,int *A)
{ if (i==n) return 0;
else {
if(A[i]==0) return kol(i+1,A)+1;
else return kol(i+1,A);
}
}
int main()
{ int y[]={1,0,2,5,4,0,1,3,0,4,3};
int x=kol(0,y);
printf("количество нулей=%d\n",x);
}
Технология сборки библиотеки
Библиотека пользователя, как и любая стандартная библиотека языка С и С++, собирается из двух видов файлов: заголовочного файла и файла с кодами функций.
Заголовочный файл (иногда головной файл, англ. header file), или подключаемый файл, в языках программирования С и C++ - это файл с расширением .h. Заголовочный файл в общем случае может содержать любые конструкции языка программирования, но на практике в него помещают объявления идентификаторов, которые должны быть объявлены более чем в одном файле вашей программы, объявления структур, прототипы функций, перечисления, макросы препроцессора. Основная цель использования заголовочных файлов — вынесение описания нестандартных типов и функций за пределы основного файла с кодом. Заголовочный файл используется путём включения его текста в использующий его файл директивой препроцессора #include. Чтобы избежать повторного включения одного и того же кода, используются директивы #ifndef, #define, #endif.
На этом же принципе построены стандартные библиотеки языка С и С++: в заголовочном файле перечисляются содержащиеся в библиотеке функции и используемые ею структуры/типы. При этом исходный текст библиотеки может находиться отдельно от текста программы, использующей функции библиотеки или вообще быть недоступным.
Пусть создаваемая нами библиотека состоит из заголовочного файла mylib.h и файла mylib.cpp.
В заголовочном файле mylib.h содержатся прототипы функций, которые описаны в данном параграфе.
Перечислим все эти функции:
maximum(). Находит и возвращает наибольшее из двух чисел.
Form_matrix(). Заполняет матрицу, адрес которой передается ей в качестве параметра, случайными числами.
ST(). Возводит любое число в степень n.
Z(). Меняет значение переданного ей параметра на случайное число.
Sum(). Вычисляет среднее арифметическое вектора, адрес и размер которого передаются в качестве параметров.
Product(). Вычисляет произведение двух матриц, адреса и размеры которых передаются в качестве параметров. Возвращает матрицу соответствующего размера.
SM(). Безтиповая функция вычисляет симметричную матрицу из исходной матрицы.
PK(). Безтиповая функция переводит декартовые координаты точки в полярные.
CP().Типизированная функция для подсчета количества положительных элементов в любой матрице.
Mod_Otk(). Типизированная функция находит максимальный компонент и среднее значение в любом массиве.
fact(). Рекурсивная функция вычисляет факториал числа n.
Текст файла mylib.h:
#ifndef MYLIB_H // если MYLIB_H еще не определили, то определяем
#define MYLIB_H
const nmax = 50; // максимальная размерность матрицы
int maximum(int a, int b);//прототип функции maximum
void Form_matrix(int A[][M], int m, int n); /*прототип функции Form_matrix */
float ST(float x, int n); //прототип функции ST
void Z (int у); //прототип функции Z
void Z (int *у); //прототип функции Z
int Sum ( int A[], int N ); //прототип функции Sum
void product(int А[][nmax], int В[][nmax],int С[][nmax], int m, int n, int k); //прототип функции product
void SM(float Y[4][4], int n, float X[4][4]); /*прототип функции SM */
void PK(float a, float b, float *ro, float *fi); /*прототип функции PK */
int CP(float D[7][7], int m, int n); //прототип функции CP
float Mod_Otk(float *a, int n); //прототип функции Mod_Otk
float fact(int N); //прототип функции fact
#endif /* MYLIB_H */
Файл mylib.cpp является созданной нами библиотекой, в которой содержатся реализации всех перечисленных выше функций.
В целях экономии текст файла mylib.cpp приведем не полностью.
Текст файла mylib.cpp:
#include "stdafx.h"
#include "stdlib.h"
{
int Sum ( int A[], int N )//заголовок функции Sum
{
int i, sum; //локальные переменные
sum = 0;
for ( i = 0; i < N; i ++ )
sum += A[i];
return sum/N; //возвращаемое значение
}
void product(int А[][nmax], int В[][nmax],int С[][nmax], int m, int n, int k) //заголовок функции product
{ /* m - число строк в матрице А; n - число строк в матрице В и число столбцов в матрице А; k - число столбцов в матрице В. */
for (int i=0; i< m; i++) for (int j=0; j< k; j++)
{ С[i][j]=0; for (int l=0; l< n; l++)
С[i][j] + = А[i][l]*В[l][j]; } }
float fact(int N) //рекурсивная функция вычисления факториала числа N
{
if (N==0)
return 1;
else
return (fact(N-1)*N);
…
}
Текст файла, использующего созданную библиотеку
#include "mylib.h"//подключение заголовочного файла библиотеки mylib
// главная функция выполняет основную работу программы
int main()
{
int a[nMax][nMax],b[nMax][nMax]; //объявление матриц
…
// здесь могут быть обращения к функциям библиотеки
return 0;
}