Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Алгоритмизация и ОП / 6_ функций_рекурс

.doc
Скачиваний:
13
Добавлен:
09.02.2016
Размер:
68.61 Кб
Скачать

2.6 Лабораторная работа №6. Программирование с использованием функций. Рекурсивная функция

Цель работы: познакомиться с понятиями "функция", «рекурсивная функция» в языке программирования С, закрепить практические навыки программирования на примере реализации алгоритмов при помощи функций, рекурсивных функций, научиться применять метод последовательной детализации в практическом программировании, применять функции при решении задач.

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

Общие сведения

Особенностью языка программирования Си является то, что программы на Си строятся из блоков, называемых функциями.

Функция является отдельным именованным фрагментом программного кода на С, выполняющим конкретную специфическую задачу. Сама по себе функция напоминает отдельную программу на С.

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

Для объявления функции используется следующий синтаксис:

<тип> <имя функции> ([список параметров]) { <тело функции> }

Тип определяет возвращаемый тип функции. Имя функции служит для ее вызова в программе и ее правило определения совпадает с правилом определения имен переменных. Список параметров необходим для передачи функции каких-либо данных при ее вызове. Телов функции – это набор операторов, которые выполняются при ее вызове.

Пример задания функции.

double square(double x)

{x = x*x;

return x;

}

int main()

{ double sq1, sq2, arg = 5;

sq1=square(arg);

sq2=square(3);

return 0;

}

В данном примере задается функция с именем square, которая принимает один входной параметр типа double, возводит его в квадрат и возвращает вычисленное значение вызывающей программе с помощью оператора return.

Следует отметить, что работа функции завершается при вызове оператора return. Даже если после этого оператора будут находиться другие операторы, то они выполняться не будут.

В языке С допускается чтобы функция вызывала саму себя. Этот процесс называется рекурсией. В некоторых задачах программирования такой подход позволяет заметно упростить создаваемый программный код. Рассмотрим данный процесс на следующем примере.

Пример использования рекурсивных функций.

#include <stdio.h>

void up_and_down(int );

int main(void)

{up_and_down(1);

return 0;

}

void up_and_down(int n)

{printf(“Уровень вниз %d ”,n);

if(n < 4) up_and_down(n+1);

printf(“\n”);

printf(“Уровень вверх %d\n”,n);

}

Результатом работы этой программы будет вывод на экран следующих

строк:

Уровень вниз 1 Уровень вниз 2 Уровень вниз 3 Уровень вниз 4

Уровень вверх 4 Уровень вверх 3 Уровень вверх 2 Уровень вверх 1

Полученный результат работы программы объясняется следующим образом. Вначале функция main() вызывает функцию up_and_down() с аргументом 1. В результате аргумент n данной функции принимает значение 1 и функция printf() печатает первую строку. Затем выполняется проверка и если n < 4, то снова вызывается функция up_and_down() с аргументом на 1 больше n+1. В результате вновь вызванная функция печатает вторую строку. Данный процесс продолжается до тех пор, пока значение аргумента не станет равным 4. В этом случае оператор if не сработает и вызовется функция printf(), которая печатает пятую строку «Уровень вверх 4». Затем функция завершает свою работу и управление передается функции, которая вызывала данную функцию. Эта функция up_and_down() с аргументом n=3, которая также продолжает свою работу и переходит к оператору printf(), который печатает 6 строку «Уровень вверх 3». Этот процесс продолжается до тех пор, пока не будет достигнут исходный уровень, т.е. первый вызов функции up_and_down() и управление вновь будет передано функции main(), которая завершит работу программы.

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

Переменные, объявляемые внутри функции, называются локальными переменными. Имя и значение локальной переменной известны только функции, внутри которой переменная объявлена.

В дополнение к локальным переменным C позволяет вашим программам объявлять глобальные переменные, которые известны на протяжении всей программы (глобально для всех функций). Глобальная переменная объявляется в начале исходного файла вне какой-либо функции.

Задание А

Составить программу обработки матрицы с использованием функций. Каждый пункт задачи оформить в виде функции

Пример

Дана целочисленная матрица размером 8 на 8. Найти:

  1. такие k, что k-я строка матрицы совпадает с k-м столбцом;

  2. сумму элементов в тех строках, которые содержат хотя бы один отрицательный элемент.

Блок-схема решения задачи дана в Лабораторной работе №5

Программа имеет следующий вид

#include <stdio.h>

#define m1 8

#define n1 8

/* Объявление прототипов функций */

void func(int *mat, int m, int n);

void func2(int *mat, int m, int n);

int main(int argc, char* argv[])

{int i, j,matrix[n1][m1];

/* Объявляем и инициализируем матрицу 8х8 */

/* генератором случайных чисел заполняем матрицу */

for (i = 0; i < m1; i++)

for (j = 0; j < n1; j++)

matrix[i][j]=rand()%10-1;

printf("\n Сгенерированная матрица имеет вид:\n ");

/* вывод матрицы */

for (i = 0; i < m1; i++)

{ for (j = 0; j < n1; j++)

printf(“%d “,matrix[i][j]);

printf("\n ");

}

func1(&matrix[0][0], 8, 8);

func2(&matrix[0][0], 8, 8);

system("PAUSE");/* задержка экрана*/

return 0;

}

void func1(int *mat, int m, int n)

{ int i, j, p; /* Счетчик и признак совпадения */

for (i = 0; i < m; i++)

{ p = 1;

for (j = 0; j < n; j++)

{

/* Сравниваем элемент i-й строки j-го столбца с элементом j-й строки i-го столбца. В случае их несоответствия присваеваевам Флагу значение Ложь и прерываем цикл по j конструкцией break */

if (mat[i * m + j] != mat[j * m + i])

{ p =0;

break;

}

}

printf("\n \t\t\tРЕЗУЛЬТАТ ФУНКЦИИ №1");

/* выводим на экран номер соответствующей строки */

if (p==1) printf("i=%d ", i);

} if (p==0) printf("\n нет одинаковых строк и столбцов ");

}

void func2(int *mat, int m, int n)

{

int i, j; /* Счетчик и переменная для хранения суммы */

int p1, iSumm; /* признак нахождение отрицательного элемента и переменная для хранения суммы */

printf("\n\n");

printf("\n \t\t\tРЕЗУЛЬТАТ ФУНКЦИИ №2\n");

for (i = 0; i < m; i++)

{ /* Присваеваем переменным исходные значения */

p1 = 0;

iSumm = 0;

for (j = 0; j < n; j++)

{/* При нахождение хотя бы одного отрицательного элемента присваиваем p1 = 1, обозначающее необходимость вывода Суммы на экран */

if (mat[i * m + j] < 0) p1 = 1;

/* Суммируем значения элементов i-й строки */

iSumm += mat[i * m + j];

}

/* В случае нахождения в строке хотя бы одного отрицательного элемента выводим на экран сумму элементов i-й строки */

if (p1) printf("Summ of elements of row #%d = %d\n", i, iSumm);

}

}

Результат выполнения программы:

Сгенерированная матрица имеет вид

2 7 2 7 1 4 0 3

1 0 7 6 0 -8 3 5

2 7 1 8 1 4 9 3

9 2 8 5 2 0 0 6

7 1 1 3 9 3 9 1

8 2 4 9 1 -6 4 9

0 3 9 0 9 4 8 8

1 8 3 2 8 2 8 0

РЕЗУЛЬТАТ ФУНКЦИИ №1

Совпавшие строки и столбцы

k = 2

k = 6

РЕЗУЛЬТАТ ФУНКЦИИ №2

Сумма элементов строки #1 = 14

Сумма элементов строки #5 = 31

Варианты задания А

Варианты задания А соответствуют вариантам задания А лабораторной работы №5

Задание Б

Выполнить упражнения из раздела «Лабораторная работа №3 Программирование циклических алгоритмов», используя рекурсивную функцию, вычисляющую факториал

Задание: Составить программу вычисляющую:

Блок-схема решения задачи дана в Лабораторной работе №3

Программа имеет следующий вид

#include <stdio.h>

#include <math.h>

   long   fact( int m)

  { if  (m<=1)   return (1);

     else  return (m * fact ( m -1 )); // функция fact вызывает саму себя

   } 

int main()

{

int n, x, f, i;

float S;

printf ("\n Введите значение n\n n=");

scanf ("%d", &n);

printf ("\n Введите значение x\n x=");

scanf ("%d", &x);

S=0;

for (i=1; i<=n; i++)

{

f=fact(i);

S=S+(cos(i*x)/ f);}

printf ("\n Сумма S=%f", S);

getch();

return 0;

}

Результат выполнения программы:

Введите значение n

n=4

Введите значение x

x=1

Сумма S=0.139995

Варианты задания Б

Варианты задания Б соответствуют вариантам задания А лабораторной работы №3

Контрольные вопросы

  1. Для чего нужны в программе процедуры и функции?

  2. В чем отличие между процедурой и функцией?

  3. Чем отличаются формальные и фактические параметры?

  4. Чем отличаются параметры-значения и параметры-переменные?

  5. Как объявляются глобальные и локальные переменные? Каково правило видимости этих переменных?

  6. Почему при обращении к процедуре, аргумент, передаваемый параметру-переменной, может быть только переменной, а не константой или выражением?

  7. Завершается ли работа функции при вызове оператора return?

  8. Как называется функция, которая вызывает саму себя?

46