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

 

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

 

Теоретические сведения

В теле функции доступны все объекты, описанные в этой функции или как глобальные, в том числе и имя самой функции. Таким образом, внутри тела функции возможен вызов самой функции. Функции, использующие вызовы "самих себя", называют рекурсивными. Допустима также косвенная рекурсия, при которой, например, функция А вызывает функцию В, та, в свою очередь, вызывает С, которая вызывает первоначальную функцию А.

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

double Factorial (int number)

{

if (number>1) return number*Factorial(number-1);

reurn 1;

}

Функция Factorial() возвращает значение типа double и объявляет единственный параметр number типа int. Функция начинается с оператора if, который проверяет значение параметра number. Если number больше 1, функция возвращает значение number, умноженное на факториал number-1.

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

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

#include <stdio.h>

void A(int c);

void B(int c);

Main()

{

A(‘Z’);

puts(“”);

}

void A(int c)

{

if (c>’A’)

B(c);

putchar(c);

}

void B(int c)

{

A(--c);

}

Основная функция начинает рекурсию в строке 8, вызывая функцию А() с аргументом ‘Z’. Функция А() проверяет свой параметр с. Если с в алфавитном порядке больше ‘A’, то происходит вызов функции В(), которая немедленно вызывает опять-таки функцию А(), передавая ей предшественника параметра с. Это заставляет функцию А() снова проверить параметр с и снова вызвать В(), пока значение с не сравняется с ‘A’.

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

Задание:

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

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

 

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

1. Что такое рекурсия?

2. Какие виды рекурсии вам известны?

3. Что нужно иметь в виду, планируя рекурсивные вызовы?

4. Каковы механизмы рекурсивных вызовов и рекурсивных возвратов?

 

Лабораторная работа №22

 

Программирование с использованием структур

 

Цель работы: ознакомиться с понятием структуры в языке С и научиться применять структуры при написании программ.

 

Теоретические сведения

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

Традиционным примером структуры является учетная карточка работающего: «служащий» описывается набором таких атрибутов, как: фамилия, имя, отчество, адрес, зарплата и т. д. Некоторые из этих атрибутов сами могут оказаться структурами: Ф.И.О. имеет несколько компонентов, как и адрес, и даже зарплата.

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

Рассмотрим структуру, описывающую дату. Она состоит из нескольких частей: день, месяц, год, день года и имя месяца.

struct date {

int day;

int month;

int year;

int yearday;

char monthname[4];

};

Описание структуры, состоящие из заключенного в фигурные скобки списка описаний, начинается с ключевого слова struct.

За ним может следовать необязательное имя (иногда называемое ярлыком структуры или тегом) – date. Такой ярлык именует структуры этого вида и его можно использовать в дальнейшем как сокращенную запись подробного описания.

Элементы или переменные, упомянутые в структуре, называются членами. Ярлыки и члены структур могут иметь такие же имена, что и обычные переменные. Член определенной структуры может быть указан в выражении с помощи конструкции вида: имя структуры.член.

Операция указания члена структуры «.» связывает имя структуры и имя члена.

Структуры могут быть вложенными. Например, учетная карточка служащего может выглядеть так:

struct person{

char name[ namesize ];

char address [ adrsize ];

long zipcode; /*почтовый индекс*/

double salary; /*зарплата*/

struct date birthday; /* дата рождения */

struct date hiredate; /* дата поступления на работу */

};

Структура person содержит 2 структуры типа date. Если определить экземпляр структуры

struct person emp;

то

Emp.birthdate.mouth

будет ссылаться на месяц рождения.

Операция указания члена структуры «.» ассоциируется слева направо.

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

Например, пусть нужно выполнять действия над комплексными числами. Поскольку комплексное число может быть представлено двумя вещественными, то можно воспользоваться структурой.

#define COMPLEX struct complex type

COMPLEX{

float real;

float image;

};

Такое макроопределение COMPLEX позволяет описывать комплексные переменные в естественной форме.

Если переменные с1, с2 и с3 описаны как комплексные, то операция умножения с1 на с2 для получения с3 может быть реализована следующим образом:

COMPLEX c1, c2, c3;

c3.real = c1.real * c2.real – c1.image*c2.image;

c3.image= c1.image*c2.real + c1.real*c2.image;

Структурную переменную можно инициализировать подобно переменным или массивам. Например, можно инициализировать структурную переменную типа COMPLEX следующим образом:

COMPLEX с1 = { 1.15; -3.1 };

Можно создать указатель на структуру, например:

COMPLEX *ptс1;

В этом случае для размещения по этому адресу структуры нужно выделить память следующим образом:

ptc1 = (COMPLEX*) malloc(sizeof(float*2));

Теперь к полям структуры, хранящейся по адресу ptc, можно получить доступ с помощью операции доступа к полям структуры по указателю ->:

ptc1->real = 12.5;

ptc1->image=-3.7;

Задание:

1. Задать структуру, определяющую дату. Ввести данные в эту структуру. Напечатать содержимое структуры.

2. Задать структуру, характеризующею книгу в библиотеке. Ввести данные в эту структуру. Напечатать содержимое структуры.

 

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

1. Что такое структура и для чего она служит?

2. Как описывается структура?

3. Как инициализируется структура?

 

 

Лабораторная работа №23

Массивы структур

 

Цель работы: ознакомиться с понятием массива структур, научиться использовать их в программах.

Теоретические сведения

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

Объявить массив структур просто. При объявлении массива структурных переменных в квадратных скобках нужно ввести количество резервируемых структур.

Struct store

{

int employees;

int registers;

doublе sales;

}stores[1000];

При помощи этого кода быстро и компактно создается 1000 структур с информацией о магазинах, каждая из которых содержит 3 элемента. Обращение к элементам происходит следующим образом:

stores[8].sales=10;

или

(*(stores+8)).sales=10;

Двойные скобки требуются потому, что приоритет операции "." выше, чем "*".

 

Задание:

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

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

1. Для чего используются массивы структур?

2. Что такое тег?

3. Как происходит обращение к информации из элемента массива стуктур?

 

Лабораторная работа №24

 

Передача структур в функции и структуры
как возвращаемые значения функций

 

Цель работы: изучить правила передачи структур в функции и научиться использовать структурные переменные как возвращаемые значения функций.

 

Теоретические сведения

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

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

Например, программа, которая использует структуру, описывающую студента:

#include <stdio.h>

#include<string.h>

struct students{

char name[25];

int age;

float average;

};