Файл: Лабораторная работа 1 Изучение среды разработки программ 3 Лабораторная работа 2 Исследование базовых типов данных языка Си 18.doc

n, требуется умножить на n факториал числа (n-1). Известно также, что 0!=1 и 1!=1.

Рассмотрим реализацию рекурсивной функции для вычисления факториала числа:

long fakt (long n)

{

if (n==0 || n==1) return 1;

return (n*fakt(n-1));

}

То же самое можно записать короче:

long fakt(long n)

{

return (n>1)?n*fakt(n-1):1;

}

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

Long fakt(int n)

{

long m=1;

for (int i=2;i<=n;i++)

m*=i;

return m;

}

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

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

2. 
   Программирование рекурсий
   

Рассмотрим еще один пример функции, с которой мы уже знакомились на практическом занятии №7 – функция определения длины строки strlen(s). Учитывая, что элементы любого массива расположены друг за другом и любой строковый массив заканчивается символом окончания строки «\0», то можно рекурсивно вызывать функцию определения длины строкового массива (или строки):

int lengh(char *a)

{

static int n=0;

n++; a++;

return (*a!='\0')?lengh(a):n;

}

Разберем работу этой рекурсивной функции.

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

---

main(), в которой происходит вызов рассмотренной рекурсивной функции:

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

{

char str[50]; int n=0;

cout<<"\Input the string: ";

cin>>str;

n=lengh(str);

cout<

return 0;

}

1   ...   14   15   16   17   18   19   20   21   22

---

ПРОГРАММА РАБОТЫ

1. 
   Реализовать программу вычисления факториала числа.
   
2. 
   Реализовать программу вычисления длины строки.
   
3. 
   Самостоятельно разработать и реализовать программу нахождения суммы чисел до заданного с использованием рекурсии.
   

Занятие 13

Практическое занятие № 8
Применение производных типов данных для решения прикладных задач

Цель занятия:

• 
  Совершенствование навыков разработки программ в среде программирования MS Visual C++
  
• 
  Совершенствование навыков описания и использования функций в программах
  
• 
  Получение начальных навыков в объявлении, инициализации и использовании производных типов данных
  

Время на выполнение работы: 4 часа
Учебные вопросы:

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

Подготовка к выполнению работы:

3. 
   Изучить рекомендованную литературу (базовые конструкции структурного программирования, массивы и указатели, функции, производные типы данных).
   
4. 
   Изучить материал настоящего руководства.
   

Материалы для подготовки к занятию:

4. 
   Конспект лекций
   
5. 
   [1] стр. 67-71.
   

ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

1. 
   Изучение порядка объявления и инициализации производных типов данных
   

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

В языке С++ структура является видом структуруа и обладает всеми его свойствами, но на данном этапе изучения языка С++ достаточно использовать структуры так, как они определены в языке Си:

struct [ имя_типа ]

{

тип_1 элемент_1;

тип_2 элемент_2;

. . .

тип_n элемент_n;

} [ список описателей ];

Элементы структуры называются полями структуры и могут иметь любой тип, кроме типа этой же структуры, но могут быть указателями на него. Если отсутствует имя типа

---

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

// Пример, описывающей анкетные данные о студентах

struct

{

char fam[20];

char name[15];

int age;

} stud[30], *ptr;

В данном примере описывается структура, содержащая три поля: символьный массив на 20 элементов с именем fam, символьный массив на 15 элементов с именем name и целочисленная переменная с именемage, которые предназначены для хранения информации о фамилии, имени и возрасте студента соответственно. В списке описателей задан массив из 30 экземпляров этой структуры и указатель на структуру (который тоже задает экземпляр структуры, который идентифицируется не по имени экземпляра, а по имени указателя, который хранит адрес начала памяти, выделенной на экземпляр структуры, но без имени экземпляра). Если список описателей отсутствует, описание структуры определяет новый тип, имя которого можно использовать в дальнейшем наряду со стандартными типами, например:

struct student

{

char fam[20];

char name[15];

int age;

};

int main()

{ . . .

student stud[30], *ptr;

. . .

return 0;

}

В данном примере описана глобальная структура данных типа структуры с заданием нового типа данных student. Задание же экземпляров этой структуры производится в рамках функции main().

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

student *ptr=new student; // экземпляр структуры

student *stud=new student[N];// массив экземпляров

// структур

Для инициализации структуры значениями используются те же методы, что и для обычных типов данных, но с небольшим дополнением: для доступа к полю структуры, экземпляр которой создан как обычная переменная или массив – через операцию «точка», а для обращения к полю структуры, экземпляр которой создан как указатель на структуру – через операцию «стрелка»:

stud[1].fam=”Сидоров”; // Доступ

stud[1].name=”Александр”; // по имени

stud[1].age=23; // экземпляра

prt->fam=”Петров”; // Доступ

ptr

---

->name=”Семен”; // через указатель

ptr->age=21; // на структуру

На практике инициализация полей структуры, описанной массивом экземпляров, осуществляется с использованием циклов с параметром:

for (int i; i

{

cout<<”\nВведите фамилию студента: “;

cin >>stud[i].fam;

cout<<”\nВведите имя студента: ”;

cin >>stud[i].name;

cout<<”\nВведите возраст студента: ”;

cin >>stud[i].age;

}

2. 
   Программирование с использованием производных типов данных
   

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

k=0;

for (j=0; j

if ( stud[j].age<=22 )

{

cout<<”\nФамилия: ”<

cout<<”\tИмя: ”<

cout<<”\tВозраст: ”<

k++;

}

if (k==0) cout<<”\nТаких студентов нет!”;

или о студентах, чья фамилия “Петров”:

k=0;

for (j=0; j

if ( strcmp(stud[j].fam, “Петров”)==0 )

{

cout<<”\nФамилия: ”<

cout<<”\tИмя: ”<

cout<<”\tВозраст: ”<

k++;

}

if (k==0) cout<<”\nТаких студентов нет!”;

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

В соответствии с модульным подходом к программированию целесообразно реализовывать вопросы поиска в отдельных функциях, например:

void ZaprosFamily(student *k, char *f);

int main()

{ . . .

char *family;

. . .

cout<<”\nВведите фамилию для поиска: ”;

cin >>family;

ZaprosFamily(kurs, family);

. . .

return 0;

}

void ZaprosFamily(student *k, char *f)

{

k=0;

for (j=0; j

if ( strcmp(k[j].fam, f)==0 )

{

cout<<”\nФамилия: ”<

cout<<”\tИмя: ”<

cout<<”\tВозраст: ”<

k++;

}

if (k==0) cout<<”\nТаких студентов нет!”;

return;

}

В этом примере в функцию передаются два указателя: один типа student, другой типа char. Что же это за указатели, почему они передаются и что значат?

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

Второй указатель есть указатель на тип данных char, то есть на символьный тип данных. Через этот указатель в функцию передается строка для поиска интересующей нас фамилии студента.

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

1   ...   14   15   16   17   18   19   20   21   22

---