- •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;}
- •Вложенные структуры условных операторов
- •Оператор выбора
- •Контрольные задания
- •2.8. Циклические вычислительные процессы
- •Операторы цикла с условием
- •Оператор цикла do...While
- •Оператор цикла с параметром
- •2.9. Базовые алгоритмы
- •Задача 1. Алгоритм организации счетчика
- •Задача 2. Алгоритм накопления суммы
- •Задача 3. Алгоритм накопления произведения
- •Задача 4. Алгоритм поиска минимального члена последовательности
- •Задача 5. Табулирование функции (или кратные циклы)
- •Задача 6. Вычисление сумм последовательностей
- •2.10. Указатели и массивы Указатели
- •Понятие массива
- •Общий вид описания массива
- •Одномерные массивы
- •Описание одномерного массива
- •Индексированные переменные
- •Ввод-вывод одномерных массивов
- •Обработка одномерных массивов
- •Задача 1. Организация счетчика
- •Задача 2. Накопление суммы и произведения
- •Задача 3. Поиск минимального и максимального элементов массива
- •Двухмерные массивы
- •Описание двухмерного массива
- •Ввод-вывод двухмерного массива
- •Обработка матриц
- •2.11. Подпрограммы Структура сложной программы
- •Функции
- •Общий вид описания функции
- •Обращение к функции
- •Пример программы с функцией
- •Механизм замены параметров
- •Параметры-массивы в функциях
- •Рекурсия
- •Примеры программирования задач с использованием подпрограмм
- •Задача 1
- •2.12. Текстовые данные
- •Символьный тип данных
- •Ввод-вывод символьных данных
- •Обработка символьных данных
- •Ввод-вывод строковых данных
- •Обработка строковых данных
- •Стандартные функции обработки строк
- •Сравнение строк:
- •Сцепление строк
- •Определение длины строки
- •Копирование строк
- •Поиск символа в стоке
- •Пример программы для задачи с текстовыми данными
- •Контрольные задания
- •2.13. Динамическое выделение памяти
- •Структуры данных Понятие структуры
- •Обработка структур
- •Пример задачи с использованием структурированных данных
- •2.15. Файлы данных Понятие файла
- •Работа с файлами
- •Открытие файла
- •Обработка открытого файла
- •Закрытие файла
- •Функции ввода/вывода
- •Работа с текстовыми файлами
- •Обработка бинарных файлов
- •Контрольные задания
- •Заключение
- •Оглавление
Рекурсия
В теле функции известны все объекты, описанные во внешнем блоке, т.е. все глобальные переменные и имя самой функции.
Таким образом, внутри любой функции можно вызывать любую доступную функцию, в том числе и саму себя. Ситуация, когда функция вызывает саму себя, называется рекурсия.
Рекурсия возможна благодаря тому, что при вызове функции создаются новые экземпляры локальных переменных, которые сохраняются во внутреннем стеке машины. Стек функционирует по принципу LIFO - Last In – First Out (последний вошел – первый вышел).
Переменные помещаются в стек одна за другой и выбираются из стека в обратном порядке.
Обязательным элементом всякого рекурсивного процесса является утверждение, определяющее условие завершения рекурсии. Оно называется опорным условием рекурсии.
Если опорное условие выполняется, то может быть задано некоторое фиксированное значение, заведомо достижимое в ходе вычисления. Это позволит организовать своевременную остановку рекурсивного процесса.
Рассмотрим пример вычисления факториала 5.
, где - это 4!
Т.е 5!=4!5
Факториал нуля равен 1. Отсюда формула вычисления N-факториала:
Реализуем вычисление факториала в виде функции:
#include "stdafx.h"
float fact(int n)
{
if (n==0)
return 1;
else
return (fact(n-1)*n);
}
void main()
{
printf("факториал 5=%f\n",fact(5));
}
Примеры программирования задач с использованием подпрограмм
При программировании задач возможны несколько вариантов. Выбор правильного (более эффективного и надежного) варианта зависит от опыта программиста
Задача 1
Даны два вектора: = {хi}; i =и={yi};i =. Вычислить значение:D = , где ; ;
тх, ту - максимальные компоненты векторов и соответственно;
sx, sy - средние значения компонент векторов и соответственно.
Решение:
#include "stdafx.h"
#include <math.h>
float Mod_Otkl (float *a, int n) /* функция для нахождения максимального компонента и среднего значения в любом массиве */
{
float ma, sa, Da;
int i;
ma =-10000;
sa=0;
for (i =0;i<n;i++)
{
if (a[i]>ma) ma= a[i];
sa += a[i];
}
sa = sa/n;
Da= fabs(ma - sa);
return Da;
}
void main()
{ float X[10],Y[10];
int i;
float Dx, Dy, D;
printf("Bведитe массив X:\n");
for (i =0;i<8;i++)
scanf("%f",&X[i]);
printf("Bведитe массив Y:\n");
for (i =0;i<10;i++)
scanf("%f",&Y[i]);
Dx = Mod_Otkl(X, 8); //вызов функции Mod_Otkl для массива X
Dy = Mod_Otkl(Y,10); //вызов функции Mod_Otkl для массива Y
D = Dx/Dy;
printf("D=%f\n",D);
}
Задача 2
Даны две матрицы: А = {a i j }5x6 и В = {b i j}4x7.
Вычислить разность: С = КА - KB, где КА и KB - количество положительных элементов в матрицах А и В соответственно.
#include "stdafx.h"
int CP(float D[7][7], int m, int n) /* функция для подсчета количества положительных элементов в матрице */
{ int i, j, KD;
KD=0;
for (i=0;i<m;i++)
for (j=0;j<n;j++)
if (D[i][j]>0) KD ++;
return KD;
}
int main()
{
float A[7][7], B[7][7];
int i,j, C;
printf("Введите матрицу А\n");
for (i=0;i<5;i++)
for (j=0;j<6;j++)
scanf("%f",&A[i][j]);
printf("Введите матрицу B\n");
for (i=0;i<4;i++)
for (j=0;j<7;j++)
scanf("%f",&B[i][j]);
C= CP(A, 5,6)- CP(B, 4, 7);
printf("C=%d\n", C);
return 0;
}
Задача 3
На плоскости декартовыми координатами заданы 10 точек:
{x1,y1},{x2,y2}, ...,{х10,у10}.
Вывести полярные координаты точки, имеющей наибольший полярный радиус. Вычисление полярных координат одной точки оформить подпрограммой. Расчетные формулы для вычисления полярных координат следующие:
, где а и b - координаты точки.
Решение:
#include "stdafx.h"
#include<math.h>
void PK(float a, float b, float *ro, float *fi) /* функция для расчета полярных координат точки */
{
*ro = sqrt(a*a + b*b);
*fi = atan(b/a);
}
int main()
{
float X[10], Y[10], R[10], F[10];
int i, n;
float max;
printf("Введите абсциссы 10 точек\n");
for (i=0;i<10;i++) scanf("%f",&X[i]);
printf(" Введите ординаты 10 точек\n");
for (i=0;i<10;i++) scanf("%f",&Y[i]);
max = 0;
for (i=0;i<10;i++)
{
PK(X[i],Y[i],&R[i],&F[i]);
if (R[i]>max) // поиск максимального радиуса
{
max =R[i];
n=i;
}
}
printf("romax=%f fimax=%f\n", R[n],F[n]);
return 0;
}
Задача 4
Для заданных квадратных матриц: A = {a i j}3x3 и В = {bi j}4х4 вычислить симметричные матрицы по правилу:
Решение:
#include "stdafx.h"
void SM(float Y[4][4], int n, float X[4][4])
{
int i,j;
for (i=0;i<n;i++)
for (j=i;j<n;j++)
{
X[i][j]=(Y[i][j] + Y[j][i])/2;
X[j][i] =X[i][j];
}
}
void main()
{
float A[4][4], B[4][4], C[4][4], D[4][4];
int i, j;
printf("Введите матрицу А\n");
for (i=0;i<3;i++)
for (j=0;j<3;j++) scanf("%f",&A[i][j]);
printf("Введите матрицу B\n");
for (i=0;i<4;i++)
for (j=0;j<4;j++) scanf("%f",&B[i][j]);
SM(A, 3,C);
SM(B, 4, D);
printf("Симметричная матрица С\n");
for (i=0;i<3;i++)
{for (j=0;j<3;j++) printf("%8.2f",C[i][j]);
printf("\n");
}
printf("Симметричная матрица D\n");
for (i=0;i<4;i++)
{for (j=0;j<4;j++) printf("%8.2f",D[i][j]);
printf("\n");
}
}