Условие задачи: подсчитать среднюю оценку для произвольного количества оценок.
Создать проект консольного приложения и вести имя проекта TPlab1_4. Создается исходный файл TPlab1_4.cpp, который будет содержать одну пустую функцию main():
int t_main(int args, _TCHAR* argv[])
{return 0;}.
Проект должен содержать файл заголовков TPlab1_4.h и файл кодов TPlab1_4.cpp.
Создать файл TPlab1_4.h, ввести текст файла и сохранить его:
//файл заголовков TPlab1_4.h
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <iomanip>
using std::setprecision;;
Добавить в файл кодов TPlab1_4.cpp подключение файла заголовков и текст функции main:
//файл кодов TPlab1_4.cpp
#include "stdafx.h"
#include "TPlab1_4.h"
int _tmain(int argc, _TCHAR* argv[])
{
//блок объявлений и инициализации переменных
Int kol, //счетчик введенных оценок
Oc; //оценка
Float sum, //сумма оценок
Sr; //средняя оценка
sum=0; //установка суммы в исходное положение
kol=0; //инициализация переменной цикла
//блок обработки
cout<<"Vvedite <ocenky> ili <-1> end: ";
cin>>oc;
while (oc!=-1)
{
sum+=oc;
kol++;
cout<<"Vvedite <ocenky> ili <-1> end: ";
cin>>oc;
}
sr=sum/kol;
//блок выода результатов
if (kol!=0)
cout<<"Srednjaja ocenka: "<<setprecision(4)<<sr<<endl;
else cout<<"Net ocenok"<<endl;
Return 0; //признак успешнего завершения
}
Пример 4. «Структура повторения for»
Условие задачи: некто внес заданный вклад под заданный процент годовых; рассчитать сумму на счете в конце каждого года на протяжении заданного количества лет.
Создать проект консольного приложения и ввести имя проекта TPlab1_5. Создается исходный файл TPlab1_5.cpp, который будет содержать одну пустую функцию main():
int t_main(int args, _TCHAR* argv[])
{return 0;}.
Проект должен содержать файл заголовков TPlab1_5.h и файл кодов TPlab1_5.cpp.
Создать файл TPlab1_5.h, ввести текст файла и сохранить его:
//файл заголовков TPlab1_5
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
using std::ios;
#include <iomanip>
using std::setw;
using std::setiosflags;
using std::setprecision;
#include <cmath>
Добавить в файл кодов TPlab1_5.cpp подключение файла заголовков и текст функции main():
//файл кодов TPlab1_5.cpp
#include "stdafx.h"
#include "TPlab1_5.h"
int _tmain(int argc, _TCHAR* argv[])
{
//блок объяления переменных и ввода данных
Double vclad, //первоначальный вклад
Stavka, //ставка годового дохода (дробь)
Depozit; //сумма на депозите в конце i-го года
Int god; //число лет
cout<<"Vvod vclada: ";
cin>>vclad;
cout<<"Vvod stavki: ";
cin>>stavka;
cout<<"Vvod chisla let: ";
cin>>god;
//блок обработки и вывода данных
cout<<"God"<<setw(20)<<"Summa depozita"<<endl;
//depozit=vclad*(1.0+stavka)^i); i=1,...,god
for(int i=1; i<=god; i++)
{
depozit=vclad*pow(1.0+stavka, i);
cout<<setw(4)<<god;
cout<<setw(20)<<setiosflags(ios::fixed|ios::showpoint)
<<setprecision(2)<<depozit<<endl;
}
return 0;
}
Пример 5. «Структура повторения с постусловием
Do/while»
Условие задачи: распечатать оценки студентов.
Создать проект консольного приложения и ввести имя проекта TPlab1_6. Создается исходный файл TPlab1_6.cpp, который будет содержать одну пустую функцию main():
int t_main(int args, _TCHAR* argv[])
{return 0;}.
Проект должен содержать файл заголовков TPlab1_6.h и файл кодов TPlab1_6.cpp.
Создать файл TPlab1_6.h, ввести текст файла и сохранить его:
//файл заголовков TPlab1_6
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
Добавить в файл кодов TPlab1_6.cpp подключение файла заголовков и текст функции main():
#include "stdafx.h"
#include "TPlab1_6.h"
int _tmain(int argc, _TCHAR* argv[])
{
int kol, f, ocenka;
cout<<"Vvesti kol-bo studentov: ";
cin>>kol;
cout<<"Ocenki studentov"<<endl;
cout<<"Nomer"<<"\tOcenka"<<endl;
int i=1;
do
{
cout<<i<<'\t';
cin>>ocenka;
}
while(++i<=kol);
return 0;
}
Контрольные вопросы
1. Сколько имеется управляющих структур?
2. Перечислите структуры ветвления.
3. Перечислите структуры повторения.
4. Объясните оператор break.
5. Объясните оператор continue.
Тема 7. Адресные типы данных
7.1. Указатели
В языке С++ существуют два способа доступа к переменным и функциям: по имени переменной или функции и по адресу с помощью указателей.
Указатель - это переменная, содержащая адрес другой переменной или функции. Использование указателей позволяет упростить алгоритм и повысить его эффективность за счет простого доступа к большим объемам данных с помощью указателя. В стек копируется не весь объем данных, а только одно число -адрес первого байта данных.
Для инициализации указателя адресом переменной служит операция & (операция адресации или операция взятия адреса). Для доступа к переменной через указатель используется операция * (операция разадресации, или разыменования, или обращения по адресу, или косвенной адресации).
Пример:
int tabn1,tabn2,*p=&tabn1;//объявление и инициализация
tabn1=1000; //указателя p адресом переменной tabn1
tabn2=*p;//tabn2=1000; Выражение *p означает, что нужно извлечь
// значение по адресу, равному значению указателя p
Операция разадресации может быть использована также в левой части оператора присваивания для того, чтобы данные были запомнены по адресу, который содержит указатель.
Пример:
int tabn,*p=&tabn;
tabn=1000;
*p=2000;// Значение tabn изменится на 2000
Над указателями можно выполнять следующие операции:
- операции адресации(&) и разадресации(*);
- операция присваивания(=);
- арифметические операции(+,-,++,--);
- операции сравнения.
При выполнении арифметических операций с указателями предполагается, что указатель указывает на массив объектов. Таким образом, если указатель объявлен как указатель на type, то прибавление к нему целого значения перемещает указатель на соответствующее количество объектов type. Если type имеет размер 4 байта, то прибавление целого числа 5 к указателю этого типа перемещает указатель в памяти на 20 байтов.
Указатели - это удобный способ обработки больших объемов данных: массивов, структур, объединений.
Использование ключевого слова const определяет, что указатель и/ или указываемая переменная не должны изменяться. Если необходимо, чтобы указываемая переменная не изменялась, нужно записать const перед типом указателя.
Пример:
int tabn1, tabn2;
const int *p=&tabn1; //p - указатель на константу типа int
*p=1000; //Присвоение объекту tabn1, на который указывает
// указатель на константу p, недопустимо
p=&tabn2; //Присвоение указателю на константу допустимо
Если необходимо, чтобы сам указатель не изменялся, нужно записать const после обозначения типа указателя.
Пример:
int * const p=&tabn1; //Указатель-константа на int
*p=1000; //Присвоение объекту tabn1, на который указывает
// указатель на константу p, допустимо
p=&tabn2; // Присвоение указателю на константу недопустимо
Адрес именной константы не может быть присвоен указателю-константе, даже если ее значение не будет изменено.
Пример:
const int kol=25;
int * const p=&kol; //Недопустимо
const int *p=&kol; //Допустимо
Преимущества указателей следующие:
· экономия памяти, более компактное размещение данных с использованием массивов указателей;
· эффективное выполнение программы при использовании указателей в качестве параметров функции при передаче агрегированных данных за счет того, что в стек копируется не весь объем данных, а только одно число -адрес первого байта данных;
· возможность изменения значений переменных вызывающей функции при изменении значений параметров вызываемой функции, т.е. возможность возврата значений помимо оператора return;
Альтернативой указателям являются ссылки.
7.2. Ссылки
Ссылка- это переменная, которая является альтернативным именем другой переменной. Ссылка при объявлении должна быть инициализирована и только один раз. После инициализации ее значение изменять нельзя, т.е. нельзя, чтобы такая ссылка ссылалась на другую переменную. Отличие ссылки от указателя рассмотрим на примере.
Пример: ссылка указатель
int tabn=1000; int tabn=1000;
int &r=tabn; int *p=&tabn;
cout<<r<<'\n';//r=1000 cout<<*p<<'\n';//*p=1000
tabn=2000; tabn=2000;
cout<<r<<'\n';//r=2000 cout<<*p<<'\n';//*p=2000
r=3000; *p=3000;
cout<<tabn<<'\n';//tabn=3000 cout<<tabn<<'\n';//tabn=3000
Результаты примеров с ссылкой и указателем одинаковы. Но использование ссылки по сравнению с указателем более удобно, так как ссылка пишется как обычная переменная и не требует операций адресации(&) и разадресации(*). Ссылка r определяет местоположение в памяти переменной tabn. При изменении значения tabn (tabn=2000;) объект ссылки получает это новое значение. При изменении значения ссылки (r=3000) переменная tabn получает это новое значение. Более точнее можно сказать следующее об операциях над ссылкой. Операция присваивания ссылке r значения 3000 не изменяет ссылку, т.е. ссылка r всегда ссылается на int tabn, а операция присваивания применяется к переменной tabn.
Таким образом, операции выполняются не над ссылками, а над переменными, на которые они ссылаются. Ссылку образно можно рассматривать, как константный указатель, который всегда разадресован. Необходимо подчеркнуть, что ссылка не является копией переменной, а является вторым именем (алиасом, псевдонимом) этой переменной.
Ссылки используются в качестве формальных параметров функций при передаче агрегированных данных (структур, объединений). При вызове функции автоматически вычисляется адрес фактического параметра (переменной вызывающей функции) и помещается в стек, затем копия адреса присваивается формальному параметру (ссылке). Аналогично выполняется возврат значения функции по ссылке.
Преимущества ссылок заключаются в следующем:
· эффективное выполнение программы при использовании ссылок в качестве параметров функций при передаче агрегированных данных (как и указатели);
· возможность изменения значений переменных вызывающей функции при изменении значений параметров вызываемой функции, т.е. возможность использования ссылок для возврата значений помимо оператора return (как и указатели);
· по сравнению с указателями, ссылки более удобны при программировании, т.к. используются обычные имена переменных и не требуются операции адресации и разадресации.
Контрольные вопросы
1. Объясните понятие указатель.
2. Охарактеризуйте операции адресации и разадресации.
3. Расскажите об использовании ключевого слова const.
4. В чем проявляются преимущества указателей?
5. Объясните понятие ссылка.
6. В чем проявляются преимущества ссылок?
Тема 8. Структуры данных фиксированного размера
8.1. Массивы
Массив - это поименованная совокупность данных, состоящая из фиксированного числа элементов одинакового типа.
При объявлении массива резервируется память.
Примеры объявления массивов:
int a[5]; //объявление массива kol для 5 элементов типа int
int b[10], c[20]; //объявление двух массивов
char imf[7]; //объявление массива символов
При объявлении массива можно одновременно выполнить его инициализацию набором значений, заключённых в фигурные скобки. Массивы символов можно инициализировать строкой символов, указанной в двойных кавычках.
Примеры:
int a[5]={10, 20, 30, 40, 50};
int a[]={10, 20, 30, 40, 50};//можно не указывать размер массива
char imf[]=”akt.dat”;//объявление и инициализация
Доступ к элементам массива осуществляется с помощью индексированной переменной, например, a[i]:
,где i -целое положительное число от 0 до 4 (количества элементов минус 1).
Пример:
int a[5];//первый элемент - a[0],...,пятый элемент - a[4]
В языке С++ предусмотрено понятие только одномерного массива. Многомерные массивы представляются как массив, состоящий из элементов типа массив.
Пример объявления и инициализации двумерного массива:
int a[2][3]={{1, 2, 3},{4, 5, 6}};
Первый индекс указывает номер строки, а второй – номер столбца.
Доступ к элементам двумерного массива осуществляется с помощью индексированной переменной, например, a[i][j]:
, где i – целое число 0, 1; j – целое число 0, 1, 2.
Операции над элементами массива варьируются в зависимости от типа его элементов.
Массивы и указатели тесно связаны и могут быть использованы почти одинаково. Имя массива можно считать как константный указатель. При обработке массивов лучше использовать нотацию массивов, а не нотацию указателей. Программировать становится легче, программа становится более понятной, хотя и несколько длиннее.
Элементами массива могут быть указатели. Примером использования такой структуры данных является массив строк, в котором каждый элемент является указателем на первый символ строки.
Приведем пример массива указателей из функции menu главы 5:
char* m[]={«Акты работ», «Расценки», «Ведомости», «Выход»};
Хотя размер массива m фиксирован, он обеспечивает доступ к строкам символов любой длины. Эта гибкость – один из примеров мощных возможностей структурированных данных в С++.
Если этот массив строк разместить в двумерном массиве, то такая структура данных должна иметь фиксированное количество столбцов, равное самой длинной строке. В этом случае затраты памяти будут значительны.
Пример 6. «Типовые операции над массивами»
Условие задачи: ввести два массива, отсортировать их, и затем произвести их слияние..
Создать проект консольного приложения и ввести имя проекта TPlab2_4.
Создается исходный файл TPlab2_4.cpp, который будет содержать всего одну пустую функцию main():
int t_main(int args, _TCHAR* argv[])
{return 0;}.
Проект должен содержать файл заголовков TPlab2_4.h и файл кодов TPlab2_4.cpp.
Создать файл TPlab1_2.h, ввести текст файла и сохранить его:
//файл заголовков TPlab2_4.h
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
const int nmax=100;
const int nmaxr=200;
void vvod(int n, float m[]);
void sort(int n, float m[]);
void slijanie(int n1, float m1[], int n2, float m2[], float m[]);
void vyvod(int n, float m[]);
Добавить в файл кодов TPlab2_4.cpp тексты функций:
//файл кодов TPlab2_4.cpp
#include "stdafx.h"
#include "TPlab2_4.h"
int _tmain(int argc, _TCHAR* argv[])
{
int k, k1, k2;
float a1[nmax], a2[nmax], a[nmaxr];
cout<<"Vvedite chislo elementov massiva 1: ";
cin>>k1;
vvod(k1, a1);
sort(k1, a1);
cout<<"Vvedite chislo elementov massiva 2: ";
cin>>k2;
vvod(k2, a2);
sort(k2, a2);
k=k1+k2;
slijanie(k1, a1, k2, a2, a);
vyvod(k, a);
return 0;
}
void vvod(int n, float m[])
{
for(int i=0; i<n; i++)
{
cout<<"Vvedite element "<<i+1<<": ";
cin>>m[i];
}
return;
}
void sort(int n, float m[])
{
int i=0;
int perest=1;
while(i<=n-1 && perest)
{
perest=0;
for(int j=n-1; j>0; j--)
if(m[j-1]>m[j])
{
perest=1;
float b=m[j-1];
m[j-1]=m[j];
m[j]=b;
}
i++;
}
return;
}
void slijanie(int n1,float m1[],int n2,float m2[],float m[])
{
int i, i1, i2;
i=i1=i2=0;
while(i1<n1 && i2<n2)
if(m1[i1]<m2[i2])
{
m[i]=m1[i1];
i++;
i1++;
}
Else
{
m[i]=m2[i2];
i++;
i2++;
}
if(i1==n1)
{
for(int k=i2; k<n2; k++)
{
m[i]=m2[k];
i++;
}
}
Else
{
for(int k=i1; k<n1; k++)
{
m[i]=m1[k];
i++;
}
}
return;
}
void vyvod(int n, float m[])
{
cout<<"Resultat: "<<endl;
for(int i=0; i<n; i++)
cout<<m[i]<<" ";
return;
}
8.2. Типы данных, определяемые пользователем
К типам, определяемым пользователем, относятся структуры, объединения и перечисления.
Структуры
Структура - это поименованная совокупность данных, состоящая из фиксированного числа компонентов разных типов. Компоненты структуры называются полями.
Пример:
struct tip_rab //Объявление типа структура tip_rab
{
int tabn;
char fio[20];
float zarp;
};
tip_rab rab1,rab2,brigada[10];//Объявление переменных типа
//структура tip_rab
Типы полей структуры - это любые типы, включая тип структура. Таким образом, возможно создание иерархической структуры данных.
Доступ к полям структуры осуществляется с помощью составного идентификатора: per.pole
,где pole – идентификатор (имя) поля структуры;
символ (.) - операция выбора поля структуры.
Пример:
rab1.tabn=1200;
Пример указателей на структуры:
tip_rab rab; //Объявление переменной типа структура tip_rab
tip_rab *p; //Объявление указателя p на тип tip_rab
p=&rab; //Инициализация указателя p адресом rab
//или tip_rab *p=&rab;//Объявление и инициализация указателя
Доступ к полям структуры осуществляется помимо операции (.)-операции прямого выбора поля структуры (rab.tabn), с помощью операции (->) -операции косвенного выбора поля структуры или операции указателя поля (p->tabn). p->tabn==(*p).tabn.
Определение адреса поля структуры выполняется с помощью операции адресации: &prab->tabn, где операция -> имеет более высокий приоритет.
Над целыми структурами, имеющими один и тот же идентификатор типа, возможна операция присваивания.
Пример:
rab1=rab2;
Операции над полями структуры вариируются в зависимости от типа полей. Тип структура является основным типом данных в экономических и управленческих задачах. В качестве параметров функций используются ссылки на тип структура.
Пример:
//Вызываемая функция //Вызывающая функция
void vyvod(tip_rab &x) tip_rab rez;
{ //rez имеет значение
cout<<x.tabn<<'\n'...
<<x.fio<<'\n' vyvod(rez);
<<x.zarp<<'\n';
}
Если необходимо заблокировать изменение переменной rez от функции vyvod, то необходим модификатор const: const tip_rab &x.
Объединения
Объединение - это поименованная совокупность данных, состоящая из фиксированного числа компонентов разных типов, но активным может быть только один компонент. Многие синтаксические и функциональные свойства объединений совпадают со структурами.
Пример:
union tip_rab //Объявление типа объединение
{
int tabn; //Размер 2 байта
char fio[20]; //размер 20 байт
float zarp; //размер 4 байта
};
tip_rab rab1,rab2;//Объявление переменных типа tip_rab
Размер объединения равен размеру своего максимального компонента, в нашем примере - 20 байт. Одновременно в памяти может находиться значение только одного компонента. Переменная rab1 может одновременно хранить в 20 байтах либо значение int, либо массив char, либо значение float. Значение какого типа, хранимого в памяти в данный момент, контролируется только самим программистом. Операция sizeof (rab1) возвращает значение 20, но когда rab1 содержит объект типа int, 18 байтов остаются неиспользованными (туда помещаются символы-заполнители), а когда rab1 содержит объект типа float, - то 16 байтов.
Доступ к полям объединения такой же, как и в структуре. Объединение может быть инициализировано только одним значением. Объединения соответствуют типам вариантных записей языков Паскаль и Модула-2. Используется как компонент структуры при создании записей с переменной частью.
Перечисления
Перечисление - это упорядоченная последовательность идентификаторов пользователя (перечисляемых констант), принимаемых переменной, причём каждому идентификатору назначается целое значение.
Упорядоченность идентификаторов пользователя определяется возрастающей последовательностью целочисленных значений идентификаторов.По умолчанию идентификаторы инициализируются значениями 0,1 и т.д.
Примеры:
enum selector {vyhod,sozd,prosm,ud,zam};//vyhod=0,sozd=1,...
enum dni {pn,vt,sr,cht,pt,sb,vs};//pn=0,vt=1,...
selector sel1;//Объявление переменной типа selector
dni d; //объявление переменной типа dni
При объявлении перечисления можно явно инициализировать идентификаторы пользователя целыми значениями.
Пример:
enum dni {pn=1,vt,sr,cht=pn+7,pt,sb,vs};//pn=1,vt=2,sr=3,
//cht=8,pt=9,sb=10,vs=11
Пример неименованного перечисления:
enum {false,true}; //символические константы false=0,true=1
Над переменной перечисляемого типа возможны операции:
операция присваивания, например, sel1=sozd; d=vs;
операции отношения, например, if (sel1==sozd)...;
любые операции, выполняемые над типом int.
Преимущество перечислений - возможность использования идентификаторов, несущих смысл, вместо числовых значений, в результате чего облегчается программирование и повышается читабельность программы.
Контрольные вопросы
1. Дайте понятие массива.
2. Как осуществляется доступ к элементам массива?
3. Как проинициализировать массив при его объявлении?
4. Перечислите типы данных, определяемые пользователем.
5. Дайте понятие структуры.
6. Как осуществляется доступ к элементам структуры?
7. Дайте понятие объединения.
8. Дайте понятие перечисления.
Тема 9. Функции (процедуры)
9.1. Определение, прототип и вызов функции
Функция – это поименованный блок программы, состоящий из последовательности операторов. Функция состоит из заголовка и тела (текста) функции. Составными частями тела функции являются объявления локальных переменных, определения типов, операторы. Перед вызовом функции в соответствующем файле кодов должно быть либо объявление функции (прототип функции), либо определение функции (текст функции). Компилятор осуществляет контроль типов данных оператора вызова функции и параметров функции.
Прототип функции – это заголовок функции без тела функции. Прототип функции обычно помещают в заголовочный файл, который подключают к соответствующему файлу кодов с помощью директивы компилятора #include.
Примеры прототипов:
int poisk_ind(char tabn[10], int nomer); //принимает 2 значения
//типа массив и int, возвращает значение типа int
int poisk_ind(char*, int); //можно без имен переменных
void init(); //не принимает и не возвращает значений
float sr_oc(int n); //принимает значение типа int,возвр. тип float
Прототип функции сообщает компилятору тип возвращаемых данных, количество параметров и их тип, порядок их следования. Компилятор использует прототип функции для проверки правильности вызовов функции
Определение функции – это заголовок и тело функции. Пример из программы п.2.1:
//файл кодов lab1_f2.cpp, см. программу
#include "lab1_f.hpp" //подключение файла заголовков
float sr_oc(int n) //заголовок функции; float - тип y
{
...
return(y); //возврат значения (y) в функцию main
}
В заголовке определения функции, в круглых скобках, имеется список формальных параметров: имена переменных с типами данных.
Основными составными частями тела функций являются операторы и локальные переменные. В теле функции действуют переменные списка формальных параметров, локальные переменные, объявленные в теле функции, и, если есть, глобальные переменные, объявленные в файле кодов.
Операторы бывают простыми и составными. К простым операторам относятся оператор присваивания, оператор вызова функции, оператор return, прерывающий выполнение функции и возвращающий значение выражения. Составной оператор – это оператор, состоящий из последовательности простых операторов. Согласно синтаксису можно различить следующие составные операторы: условные операторы и операторы циклов. В теле составных операторов используется простой оператор break, прерывающий их выполнение. В теле операторов цикла используется оператор continue, передающий управление на конец цикла.
9.2. Передача параметров
Оператор вызова функции служит для вызова вызываемой функции в теле вызывающей функции. Он может быть представлен двумя способами:
· как простой оператор без возврата значений через return;
· как операнд в выражении при возврате значений через return.
Пример:
//файл кодов lab1_f1.cpp
#include "lab1_f.hpp" //подключение файла заголовков
main()
{//...
sr=sr_oc(kol); //оператор вызова функции sr_oc
cout<<"Ваша средняя оценка:"<<sr;
getch();
}
В операторе вызова функции, в круглых скобках, имеется список фактических параметров вызывающей функции: выражения или имена переменных без типов данных. Значения фактических входных параметров перед вызовом функции должны быть определены. Оператор вызова функции передает управление вызываемой функции, и копии фактических параметров через стек присваиваются формальным параметрам вызываемой функции. Аналогично копии результатов вызываемой функции пересылаются и присваиваются фактическим параметрам вызывающей функции. Управление передается обратно в вызывающую функцию.
9.3. Программирование рекурсивных алгоритмов
Обычно одни функции вызывают другие функции согласно иерархической структуре программы. Но существуют ситуации, когда полезно иметь функцию, которая вызывает сама себя.
Рекурсивная функция – это функция, которая вызывает сама себя.
Рассмотрим понятие рекурсии на классическом примере – расчете факториала целого числа.
Факториал n! равен n*(n-1)*(n-2)*…*1,причем 1!=1 и 0!=1. Пусть надо вычислить 3!=3*2*1, что можно свести к 3*(2!). Рекурсивная задача разбивается на этапы, где вызывается рекурсивная функция, которая вычисляет n*(n-1)!: 3! -> 3*2! -> 2*1! -> 1.
Рекурсивная функция последовательно делит задачу на две части: одну часть (* - умножение) она может решить, а вторую часть ((n-1)!) она не может решить. Для выполнения рекурсии необходимо, чтобы вторая часть была похожа на исходную задачу, но быть несколько меньше. И тогда рекурсивная функция вызывает новую копию самой себя. Это называется рекурсивным вызовом или шагом рекурсии. Процесс рекурсии приводит к формированию все меньших и меньших задач и заканчивается, когда функция достигает базовую задачу (1!=1). Затем функция последовательно возвращает в обратном порядке значения рекурсивных вызовов оператору вызова, пока не будет возвращено окончательное решение: (1) -> (2*1=2) -> (3*2=6).
Пример 7. «Рекурсивные алгоритмы»
Условие задачи: создать рекурсивную функцию вычисления факториала.
Создать проект консольного приложения и ввести имя проекта TPlab2_2.
Создается исходный файл TPlab2_2.cpp, который будет содержать всего одну пустую функцию main():
int t_main(int args, _TCHAR* argv[])
{return 0;}.
Проект должен содержать файл заголовков TPlab2_2.h и файл кодов TPlab2_2.cpp.
Создать файл TPlab2_2.h, ввести текст файла и сохранить его:
//файл заголовков TPlab2_2.h
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
int fact(int);
Добавить в файл кодов TPlab2_2.cpp подключение файла заголовков и текст функции main():
//файл кодов TPlab2_2.cpp
#include "stdafx.h"
#include "TPlab2_2.h"
int _tmain(int argc, _TCHAR* argv[])
{
int res, n;
cout<<"Vvedite celoe chislo: ";
cin>>n;
res=fact(n);
cout<<n<<"!="<<res<<endl;
return 0;
}
Int fact(int n)
{
if (n<=1)
return 1;
Else
return n*fact(n-1);}
Пусть требуется вычислить 3!. Вызывается функция fact(3). При входе в функцию формальному параметру n присваивается значение фактического параметра 3 и выполняется выражение 3*fact(2), т.е. опять вызывается функция fact для вычисления fact(2). При входе в функцию формальному параметру n присваивается значение 2 и выполняется выражение 2*fact(1), т.е. опять вызывается функция fact для вычисления fact(1). При входе в функцию формальному параметру n присваивается значение 1 и выполняется выражение 1*fact(0), т.е. опять вызывается функция fact для вычисления fact(0). На этом завершается выполнение выражения 1*fact(0), что возвращает значение fact(1)=1; потом завершается выполнение выражения 2*fact(1), что возвращает значение fact(2)=2, и затем завершается вычисление 3*fact(2), что дает искомый результат 3*2=6.
Контрольные вопросы
1. Дайте понятие функции.
2. Что такое определение, прототип и оператор вызова функции?
3. Зачем нужен прототип функции?
4. Какие существуют способы передачи параметров функции?
5. Охарактеризуйте выполнение оператора вызова функции.
6. Дайте понятие рекурсивной функции.
7. Объясните понятие шага рекурсии.
Тема 10. Динамические структуры данных
10.1. Списки: основные виды и способы реализации
Ранее были рассмотрены структуры данных фиксированного размера: массивы, структуры. Размер таких наборов данных зафиксирован при компиляции и не может быть изменен.
Динамические структуры данных – это наборы данных, размеры которых нарастают и сокращаются во время выполнения программы. Рассмотрим основные виды динамических структур данных: списков и способы реализации операций с данными.
Связные списки (linked lists) – наборы элементов данных, называемых узлами, связанные при помощи связующих указателей в линейную структуру данных, причем операции вставки элементов данных и их удаления осуществляются в любом месте списка. Каждый узел содержит адреса (связующие указатели) последующего и предыдущего указателя списка (прямые и обратные цепочки). Доступ к связному списку начинается через указатель на первый элемент списка, а затем через связующие указатели каждого списка.
Стеки (stacks) – частный случай связных списков, в которых операции вставки и удаления проводятся в конце стека (в его вершине), т.е. по принципу «первый пришел, последний ушел»; применяется в компиляторах и операционных системах. Пример использования стеков и описание алгоритмов операций с элементами списка представлен в § 7.1 при программировании класса «spisok» методом объектно-ориентированного программирования.
Очереди (queues) - частный случай связных списков, в которых операция вставки проводится в конце очереди (хвосте очереди), а операция удаления проводится в начале очереди (голове очереди), т.е. по принципу «первый пришел, первый ушел».
Бинарные деревья (binary trees) – нелинейные структуры данных, обеспечивающие высокоскоростной поиск и сортировку данных.
10.2. Динамическое выделение памяти
Создание и сопровождение динамических структур данных ведет к динамическому распределению памяти, т. е. к наращиванию и сокращению области памяти в процессе выполнения программы.
Для управления динамической памятью используются:
оператор new для резервирования памяти из heap (кучи);
оператор delete для освобождения памяти.
Синтаксис оператора new (три формы):
new <тип> или new (<тип>) //резервирование памяти под
//объект типа <тип>;
new <тип>(x) //резервирование памяти и инициализация
//значением x
new <тип>[<выражение>] //резервирование под массив
//типа <тип>.
Примеры оператора new:
int* p1=new int; //резервирование памяти под объект
//типа int
int* p2=new int(5); //резервир. и инициализация значением x
char* tabn=new char[20]; //резервир. под массив типа char
t* p=new t; //резервир. под переменную типа структура t:
//struct t {char tabn[10]; float oklad;}
Результат оператора new – указатель на выделенную память, либо 0, если произошла ошибка.
Синтаксис оператора delete имеет две формы:
delete p; //освобождение памяти, p – указатель из new
delete[] p; //освобождение памяти, занятой массивом
Примеры оператора delete:
delete p1; //освобождение памяти, на которую указывает p1
delete[] tabn; //освобождение массива, на который указывает tabn
Операторы new и delete особенно эффективны при работе с объектами классов в объектно-ориентированном программировании.
Сравним структуры данных фиксированного размера (массивы) и динамические структуры данных (списки) с точки зрения их использования при программировании. Списки эффективны по сравнению с массивами в тех случаях, когда число элементов данных в структуре данных заранее не известно и может изменяться во время выполнения программы. Конечно, можно и в этих случаях использовать массивы, объявив заранее массив под максимальное число элементов, но это приведет к избыточному расходу памяти. Таким образом, связные списки экономят память.
Сравнивая операцию сортировки, можно сказать, что списки имеют преимущество, так как имеют возможность вставки нового элемента прямо в соответствующую позицию списка. Также операции вставки и удаления в массиве будут более длительными, так как все элементы при этих операциях сдвигаются.
Но массивы имеют огромное преимущество, связанное с быстрым доступом к элементам массива, так как адрес индексированного элемента массива вычисляется мгновенно по отношению к началу массива. Это объясняется распределением памяти под массив, когда элементы массива размещаются в памяти непрерывно. И в этом недостаток списков, так как узлы списков физически не хранятся в памяти по соседству друг с другом.
Контрольные вопросы
1. Дайте определение динамических структур данных.
2. Какие существуют основные виды списков?
3. Охарактеризуйте динамический класс памяти.
4. Сравните структуры данных фиксированного типа (массивы) с динамическими структурами данных (списки).
Раздел 3 Процедурное программирование
В остальных 4-ех темах мы рассмотрим вопросы технологии процедурного программирования и основные понятия объектно-ориентированного программирования: потоковый ввод-вывод данных, потоковая обработка файлов данных, способы конструирования программ и основные этапы процедурного программирования, введение в технологию объектно-ориентированного программирования.
Тема 11. Ввод/вывод данных
В C++ нет встроенных средств ввода/вывода. Альтернативой этому служит наличие библиотек ввода/вывода. Рассмотрим две основные библиотеки, имеющие средства управления экраном и клавиатурой:conio.h и iostream.h.
11.1. Видеофункции библиотеки conio.h
Файл conio.h содержит функции прямого ввода/вывода на консоли (клавиатура, экран дисплея) в текстовом режиме.
Рассмотрим функцию форматированного вывода cprintf.
Синтаксис функции:
cprintf(формат,[ аргумент1,...]);
,где формат - это символьная строка, состоящая из простых символов и спецификаций формата;
[ аргумент1,...]) – список аргументов.
Функция cprintf принимает список аргументов аргумент1, применяет к каждому из них соответствующую спецификацию формата из строки формат и выводит форматированные данные в выходной поток. Простые символы переносятся в выходной поток без изме