Понятие алгоритма. Свойства алгоритмов.

Понятие алгоритма. Свойства алгоритмов.

Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.

Свойства алгоритмов:
1. Дискретность (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);
2. Детерминированность (любое действие должно быть строго и недвусмысленно определено в каждом случае);
3. Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);
4. Массовость (один и тот же алгоритм можно использовать с разными исходными данными);
5. Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).

+

Этапы создания исполняемой программы (загрузочного модуля).

 

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

Исходный модул ь – текстовый файл с расширением .cpp, содержащий текст программы на языке С++. Исходный модуль получается в результате работы программы редактор.

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

Директивы – особые строки программы, начинающиеся с символа #.

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

Полный модуль обрабатывается компилятором – программой, переводящей исходный текст программы в машинные коды.

В результате получаем объектный модуль – файл с расширением .obj, содержащий машинный код программы.

Компоновщик – программа, которая на основе полученных объектных модулей и с участием библиотечных файлов создает загрузочный модуль – файл с расширением .exe, который и выполняется компьютером.

Библиотечные файлы – файлы с расширением .lib, содержащие объектные модули стандартных функций.

Итак, для получения исполняемой программы нам необходимы следующие средства:

ü Текстовый редактор;

ü Компилятор;

ü Компоновщик;

ü Библиотеки функций;

ü Отладчик;

ü Справочник.

+

3.Структура программы на С++. Директивы препроцессора include и define.

Классы памяти

int a;

void func(int a, …)

{

…

}

// внешняя переменная маскируется

int main(void)

{

int a;

func(a);

…

{

int a;

…

}

…

}

 

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

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

Область действия – часть программы, где переменная доступна по имени.

 

Класс памяти	Как объявить?	Область действия	Время жизни	Обнуление
Extern Глобальная внешняя	По умолчанию Вне функции	Вся программа	Вся программа	+
Auto Автоматическая локальная	В блоке	Блок	Блок	-
Register (рекомендованная)	В блоке	Блок	Блок	-
Static Внешняя статическая	Вне функции со словом static	Файл	Вся программа	+
Static Локальная статическая	В блоке со словом static	Блок	Вся программа	+

 

+

7.Программирование ввода-вывода в языке С++ с использованием стандартных объектов потоков cin и cout.

Стандартный ввод/вывод данных через потоки

#include<iostream>

using namespace std;

 

Используем следующие средства:

1) cin – поток ввода (объект класса istream) (этот поток по умолчанию связан с клавиатурой)

2) cout – поток вывода (объект класса ostream) (по умолчанию связан с монитором)

3) cerr – поток вывода сообщений об ошибках (объект класса ostream) (по умолчанию связан с клавиатурой)

4) операция >> - операция извлечения из потока (ввод данных)

5) операция << - операция помещения в поток (вывод данных)

6) методы ввода-вывода

7) манипуляторы

Ввод-вывод данных производится в соответствии с типом данных

Ввод данных

Синтаксис:

cin>>ИмяПеременной;

В одном операторе можно ввести несколько данных, разделяя имена переменных операцией >>

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

 

Пример 1:

int a, b; cin>>a>>b;

При выполнении:

13 163<ввод> ИЛИ 13<ввод>163<ввод>

 

Пример 2:

char simv; cin>>simv;

При выполнении:

а<ввод>

 

Ввод строки без пробелов внутри:

char str[20];

cin>>str;

При выполнении:

Привет!<ввод>

 

Ввод строки с пробелом внутри

char str[80];

cin.getline(str,80);//контроль количества вводимых символов

При выполнении:

Люблю грозу в начале мая!<ввод>

 

НО: операция >> и getline конфликтуют. Операция >> считывает данное и оставляет на входном потоке клавишу ввода. Метод getline считывает клавишу ввода – получается пустая строка (“проскакивает” ввод строки).

cin.ignore(); - игнорирует один символ с входного потока (при переходе от cin к выполнению)

 

Вывод данных

Синтаксис:

cout<<Выражение;

 

В одном операторе можно вывести несколько выражений, разделяя их операцией <<.

Беспокоиться о разделении данных на экране.

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

int a=3, b=5;

cout<<”a=”<<a<<”, b=”<<b<<endl;

При выполнении:

a=3, b=5

 

endl – манипулятор, переводящий строку на следующую.

 

+

8.Операции языка С++: арифметические операции; операция определения остатка от деления; увеличения и уменьшения на единицу.

Операции применяются для представления каких-либо действий над данными.

Операции могут быть:

1) Арифметические

2) Логические

3) Побитовые

4) Отношения и т.д.

Операнды – участники операции. В зависимости от количества операндов, операции делятся на:

1. Унарные

2. Бинарные

3. Тернарные

 

Арифметические операции:

1. Сложение

2. Вычитание

3. Умножение

4. Деление (1/3=0) (1.0/3.0=0.3333)

Операции выполняются с учетом типа: операнды должны быть одинакового типа и результат получается этого же типа. Если типы разные, то происходит автоматическое выравнивание (по высшему): char->int->long->float->double.

Определение остатка при делении a%b результат – сколько минимально надо отнять от a, чтобы a поделилось на b нацело. (17%4=1)

9.Операции языка С++: операция присваивания, арифметические операции с присваиванием.

 

Операции присваивания – изменяют значение любой переменной, слева пишется имя переменной, справа её новое значение (a=5; a=b+c; a+=2).

Арифметические операции с присваиванием: +=, -=, *=, /=.

+

10.Операции языка С++: операция sizeof, операция приведения к типу, операция определения адреса по имени переменной.

Условные выражения

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

1 (true) 0 (false)

> >= < <=!= ==

Замечание: избегать сравнения на равенства вещественных чисел или сравнивать с определенной долей точности.

(double a, b;

if (fabs(a-b)<1E-8)

cout<<”pochti ravnie”;

else

cout<<”ne ravnie”;)

 

Условные выражения, состоящие из нескольких операций отношения, соединяются логическими операциями:

а) && - логическая операция И – результат истина т.е. 1, если оба операнда истины, или ложь в противном случае;

б) || - логическая операция ИЛИ – результат операции истина или 1 если хотя бы один операнд истинен, или ложь в противном случае;

в)! – логическая операция НЕ (пишется перед операндом) если операнд – истина, то результат операции – ложь, и наоборот.

 

Анализ символьной информации.

‘0’ ‘9’ ‘A’ ‘Z’ ‘a’ ‘z’ ‘А’ ‘Я’ ‘а’ ‘п’ ‘р’ ‘я’

 

 

char sim;

1. Убедиться, что в переменной записана цифра sim>=’0’&& sim<=’9’

2. В переменной sim содержится большая латинская буква. sim>=’A’&&sim<=’Z’

Операция условия?:

(тернарная операция)

Альтернатива оператору if.

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

Синтаксис: выражение 1? выражение 2: выражение 3;

Выполняется: если выражение 1 истина, то результатом операции является выражение 2, иначе - выражение 3.

Примеры:

y=|x|

y=(x>0)?x:-x; вычисляется модуль числа.

 

max=a,b? вычислить max из двух чисел

double a, b, max;

cin>>a>>b;

max=(a>b)?a:b;

 

Задача: определить, кратно ли одно число другому.

 

int main(void)

{

int a, b;

cout<<"Vvedite bolshee chislo";

cin>>a;

cout<<"Vvedite menshee chislo";

cin>>b;

if (a%b==0)

cout<<"kratno";

else

cout<<"ne kratno";

return 0;

} +

Выражения (в том числе и условные). Порядок выполнения операций в выражении. Таблица приоритетов.

Выражение – это объединение операций и операндов. Значение выражения определяется выполнением операций по уровню старшинства (приоритету).

 

Операции от высшего приоритета	Порядок выполнения
(), {}, →	слева - направо
унарные!, ~, ++, --, &, sizeof * (тип)	справа - налево
*, /, %	слева - направо
+, -	слева - направо
<< >>	слева - направо
<, <=, >, >=.	слева - направо
==,!=	слева - направо
&	слева - направо
^	слева - направо
|	слева - направо
(лог)&&	слева - направо
||	слева - направо
?:	слева - направо
=, +=, -=, *=, /=, %	справа - налево
,	слева - направо

Операции выполняются в основном слева-направо (справа-налево выполняются только унарные и присваивания). Расставляем круглые скобки для повышения приоритета. Если операции идут в нужном нам приоритете – скобок не ставим. +

13.Виды операторов в языке С++.

Операторы служат строительными блоками программы и являются командой компьютеру.

Операторы делятся на:

а) оператор выражения,

б) пустой оператор,

в) составной оператор (блок),

г) оператор вызова функции,

д) оператор, начинающийся с ключевого слова.

 

а) Оператор выражение – если в конце, какого либо выражения поставим; получим оператор выражения.

Синтаксис: выражение; a1=a2=a3; <-=<-=<-

б) Пустой оператор – не вызывает никакого действия. Используется там, где по синтаксису необходимо написать оператор, но никакого действия не должно быть.

Синтаксис:;

в) Составной оператор – (блок) – любая последовательность операторов заключенная в {}. Блок позволяет написать несколько операторов там, где по синтаксису необходимо написать один оператор.

Синтаксис: { = }

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

· название,

· количество, тип и порядок следования аргументов (исходных данных для функции),

· тип результата функции, передаваемого через оператор return,

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

 

Синтаксис: result=name(arg1, arg2, …, argN);

где result – переменная под результат функции,

name – название функции,

arg1, arg2, …, argN – аргументы функции, разделенные запятой(исходные данные).

В качестве аргумента можно писать константу, переменную, выражение, вызов другой функции. Если аргументов нет – пишутся пустые круглые скобки. Если результата нет или он не важен – пишется просто name(arg1, arg2, …, argn).

Например:

Y=sin(x);

F=pow(2., y+a);

Simv=getchar();

 

д) if switch while do while for return +

Полная форма оператора if

if-else

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

Синтаксис: if (выражения)

один оператор или блок(1)

else // во всех остальных случаях

один оператор или блок(2)

Выполнение: если выражение истинно, то выполняется действие 1, во всех остальных действие 2.

Пример:

F(x)=

if (x>0)

func=sin(x);

else

func=cos(x);

cout<<”Функция=”<<func<<endl;

 

Множественный выбор else if

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

Синтаксис: if (выражение 1)

один оператор или блок(1)

else if (выражение 2)

один оператор или блок(2)

else if (выражение 3)

один оператор или блок(3)

…

else (во всех остальных случаях)

один оператор или блок(n)

Выполнение: если выражение 1 истинно, выполняется действие 1,

если выражение 1 ложно, а выражение 2 истинно, выполняется действие 2,

если выражения 1 и 2 ложны, а выражение 3 истинно, выполняется действие 3.

Действие n выполняется, если все вышеперечисленные выражения ложны.

Заключительная ветвь else не обязательна, но крайне желательна, т.к. она указывает, что все возможные варианты рассмотрены.

F(x)=

 

int main(void) обязательно без кавычек!

{

int x;

cin>>x;

 

if(x<5)

cout<<"sinx"<<endl;

else if(x>=5&&x<=10)

cout<<"cosx"<<endl;

else if(x>10&&x<=20)

cout<<"tgx"<<endl;

else

cout<<"kekeke"<<endl;

return 0;

}

 

+

Break continue goto

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

Операторы применяются в составе условных конструкций.

 

Оператор break

Применяется: для построения цикла с выходом из него изнутри тела цикла

while(1)

{

операторы

if (условие выхода из цикла)

break;

операторы

{

 

Пример:

Определить является ли простым натуральное число N.

int main(void)

{

int n, i;

cout<< "vvedite chislo: ";

cin>>n;

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

if (n%i==0)

break;

if (i==n)

cout<<"\nprostoe"<<endl;

else

cout<<"\nneprostoe"<<endl;

return 0;

}

Оператор continue

Применяется внутри тела цикла и приводит к выполнению следующей итерации, оставшаяся часть текущей итерации пропускается.

while(выражение)

{

операторы

if(условие)

continue;

операторы

}

 

Оператор continue в цикле применяется всегда в составе условного оператора, также как и break.

 

Оператор goto

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

Синтаксис: Не входить внутрь блока, условных операторов цикла.

goto m1;

.............

m1:

.............

 

Пример:

for (…)

for (…)

{

if (условие ошибки)

goto m1;

.............

}

............

m1:

............

 

+

Вложенные циклы.

Цикл называется вложенным, если находится в теле другого цикла.

 

Задача: из двух цифр сформировать всевозможные двузначные числа и расположить в порядке возрастания (матрица)

int j, i;

i=1;

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

{

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

cout<<i*10+j<<’ ‘;

cout<<endl;

}

return 0;

Нужно расписать вложенный цикл и показать, как он работает.

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

 

Формирование пустого квадрата.

int main()

{

int n=5, m=5;

char simv = 'a';

cout<<endl;

 

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

{

if (i==1 || i==n) // 1-я и последняя строка

{

for (int j=1; j<=m; j++)

cout << simv; // сплошная из символов

}

else // все строки между первой и заключительной

{

cout << simv; // показать один символ

for (int j=1; j<=m-2; j++)

cout << ' ';

cout << simv; // показать ещё один символ

}

cout << endl; // новая строка

}

cout << endl;

return 0;

}

+

Объявление указателя.

Синтаксис: имя_типа*имя_ указателя;

Пример:

1. int *p1; // переменная p1 объявлена как указатель на целый тип данных, т.е. она может содержать адрес любой переменной целого типа.

2. void *p3; // переменная p3 является указателем на тип void т.е. может содержать адрес любого типа.

Инициализация указателей. Помещение в указатель правильного адреса.

Имеются несколько способов инициализации:

· в указатель помещаем адрес существующей переменной

double *p1, a; // * относится только к p1

p1=& a; // & - амперсант, операция определения адреса по имени переменной

· Инициализация указателя с помощью другого указателя, уже правильно инициализированного.

char a, *p1, *p2;

p1=&a;

p2=p1; // нельзя присваивать указатели разного типа

Указатель на тип void совместим с любым адресом

void *p3;

p3=(void*)p1;

p3=(double*)p2;

· В указатель помещаем адрес памяти, выделенной под данное динамически

Способы выделения памяти под данные:

· статическая память выделяется в момент компиляции и её объём должен быть заранее известен

· динамическая память выделяется в процессе выполнения операции new, её объём может быть вычислен или введён; освобождается память при выполнении delete

int *p1 = new int; - выделяется память под одну переменную целого типа

int *p2 = new int(5); - выделяется память под одну переменную целого типа и туда помещается значение 5

int *p3 = new int[7]; - выделяется память под семь переменных целого типа, лежащих в памяти подряд

 

В нужном месте программы выделенную память обязательно нужно освободить

delete p1;

delete p2;

delete[]p3;

Операции над указателем.

1. Операция доступа к содержимому по адресу (операция разадресации) * - унарная.

Пример:

int *p=new int;;

*p = 7; // операция разадресации - значение по адресу p равно 7.

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

3. От указателя на соответствующий тип можно отнять целое число n, при этом мы сместимся в памяти назад на n элементов.

4. Два адреса можно сравнить с помощью операции отношения = =,! =, <, < =, >, > =.

5. Можно найти разность между двумя указателями, и определить на каком расстоянии находится два объекта между собой. p[2]-p[4]

p-(p-4)=4

 

 

Задача.

Выделить память под 3 данных типа int, находящихся в памяти подряд, присвоить значение 1,2,3.

int *p;

p = new int[3];

*p = 1;

*(p+1) = 2;

*(p+2) = 3;

Указатель на константу:

int a=98, b=20; const int *pa;

pa=&a;// правильно

*pa=10;// ошибка

pa=&b;// правильно

 

Константный указатель:

int a=9, int b=4; int* const pa=&a;

*pa=11;

pa=&b;// ошибка

+

23.Строки в языке С++: объявление (статически), инициализация, доступ к символам строки, стандартный цикл обработки.

Строка – набор символов, завершающийся 0 символом.

Адрес строки – адрес первого символа в строке.

Со строкой работаем как с единым целым, при этом используется имя или адрес строки.

Если хотим выполнить действие над строкой, как над единым целым – ищем функцию обработки строки.

 

Статические строки

#define SIZE 80 размер строки только константное данное

или

const int SIZE=80;

char str[SIZE];

char str[SIZE]=”Hello!”; // с инициализацией

Особенность строки: объем выделенной памяти отличается от реального размера введенной строки.

Реальный размер вычисляется.

 

Как определить адрес символа строки?

Имя строки является константным адресом строки.

str+i – адрес символа с индексом i (i=0, с шагом 1)

 

Как определить значение символа строки?

*(str+i) или str[i]

 

Динамические строки

Размерность может быть константой или переменной.

#define SIZE 80

или

const int SIZE=80

или

int SIZE=80;

или

cin>>SIZE;

char *p;

p=new char[SIZE];

…

delete []p;

Особенность – без инициализации

 

Как определить адрес символа строки?

p+i – адрес элемента с индексом i

*(p+i) – значение элемента с индексом i

p[i] – значение элемента с индексом i

 

Одномерные числовые массивы

Особенность – любая обработка численного массива – цикл.

Под числовой массив выделяем памяти столько, сколько необходимо.

Статические массивы

1) Как объявить?

Размерность задается только константным данным(или целым)

#define SIZE 7

или

const int SIZE=7;

int mas[SIZE];

или

int mas1[SIZE]={1,2,3,4,5,6,7}; // с инициализацией

После выделения памяти в элементах массива находится «мусор». При объявлении массива возможна инициализация.

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

 

2) Как определить адрес и значение элемента массива?

Имя массива – константный адрес первого элемента массива.

mas+i – адрес элемента с индексом i

*(mas+i) или mas[i]– значение элемента с индексом i

 

Динамические массивы

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

const int SIZE=7; // или #define SIZE 7

int *p=new int[SIZE];

 

Указатель инициализируется адресом первого байта

 

p+i – адрес элемента с индексом i

*(p+i) или p[i] – значение элемента с индексом i

Перебор элементов for (i=0;i<n;i++)

 

//Обращение к элементам массива по имени осуществляется по индексу, значение которого начинается с нуля.

mas[0]=1

mas[1]=2;

mas[2]=3;

 

 

ð for(i=0;i<SIZE;i++)

{

алгоритм обработки i-го элемента; cin>>* (a+i) или cin>>a[i];

}

+

25.Двумерные числовые массивы в языке С++: объявление (статически), инициализация, доступ к элементам массива, стандартные циклы обработки.

Многомерные массивы

на примере матриц

#define RAZ1 2

#define RAZ2 4

…

#define RAZN 7 // объявление многомерного массива

 

int MAS[RAZ1][RAZ2]…RAZ[N];

 

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

// Двумерный массив располагается построчно.

a [0] [0], a [0] [1], a [0] [2]

a [1][0], a [1] [1], a [1] [2]

 

Матрицы

Матрицы имеют два набора.

Элементы матрицы лежат в памяти по одному, друг за другом, построчно.

Статические матрицы

Как объявить матрицу?

Размер – константное данное

#define STR 3

#define STLB 4

или

const int STR=3, STLB=4;

int A[STR][STLB];

int B[STR][STLB]={ ,5,6,7,8,9,10,11,12}; // с инициализацией, где 1,2,3,4 – первая строка, 5,6,7,8 – вторая строка, 9,10,11,12 – третья строка.

int C[STR][STLB]={{1,2,3},{5,6,7,8},{9,10,11,12};

 

2) Адрес элемента матрицы

A[i] – адрес i-ой строки, т.е. адрес 1-го элемента в i-ой строке

0<=i<STR

A[i]+j – адрес элемента матрицы

0<=i<STR 0<=j<STLB

3) Значение элемента матрицы

*(A[i]+j) или A[i][j]

 

Динамические матрицы

Работаем как с одномерным массивом.

Как объявить матрицу?

Размер – константное данное или переменная

int STR, STLB;

cin>>STR>>STLB;

int *p;

p=new int[STR*STLB]

…

delete []p;

 

2) Адрес элемента массива

p+i*STLB – количество в полных строках

p+i*STLB+j – смещение по неполной строке

 

3) Значение элемента массива

*(p+i*STLB+j) или p[i*STLB+j]

 

Циклы перебора матрицы

Пусть есть матрица A, STR=3 и STLB=4

a₀₀ a₀₁ a₀₂ a₀₃

a₁₀ a₁₁ a₁₂ a₁₃

a₂₀ a₂₁ a₂₂ a₂₃

 

Механизм вывода функции

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

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

При выполнении оператора return управление передается назад – в место вызова. Передаваемый результат подставится вместо вызова и присвоится указанной переменной.

Выводы

 

Для написания собственной функции необходимо:

· определить функцию(написать заголовок и тело)

· объявить функцию(написать прототип)

· в нужном месте программы организовать вызов функции.

 

Основные принципы построения функции:

1) Каждая функция решает одну подзадачу.

2) Исходные данные всегда передаются через параметры. (за незначительным исключением)

3) Результат всегда передается из функции с помощью оператора return или другими средствами.

+

Передача данных по адресу.

 

 

 

 

Пусть из функции необходимо передать результат целого типа

Необходимо:

· Объявить в функции main переменную целого типа под результат.

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

· В имени функции и в прототипе объявить параметр указатель на целый тип.

· Внутри функции вычислить результат и записать его значение по указанному в параметре адресу.

… func(…, int *result) // параметр является указателем, *result=&result

{

…

*result=результату;// возвратили результат функции через параметр

…

}

 

int main(void)

{

int result; //переменная целого типа под результат.

…

… func(…, &result); // передали в функцию адрес переменной res

cout<<result<<endl;

…

}

 

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

void Swap(int *p1, int *p2)

{

int a;

a=*p1;

*p1=*p2;

*p2=a;

return;

}

 

int main(void)

{

int A, B;

cin>>A>>B;

Swap(&A, &B);

cout<<A<<" "<<B<<endl;

return 0;

}

+

Выделение памяти под массив-результат функции пользователя в функции main(). Написать схематично программу с функцией пользователя, в которой на основе исходного одномерного числового массива формируется массив-результат.

 

void func(int *p, int *p1, int n)

{

int i, j;

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

*(p1+i)=*(p+i)*2;

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

cout<<p1[j]<<' ';

return;

}

 

int main(void)

{

const int SIZE=10;

int mas1[SIZE]={1,2,3,4,5,6,7,8,9,10};

int mas2[SIZE];

func(mas1,mas2,SIZE);

return 0;

}

+

37.Передача многомерных массивов в функцию (на примере двумерных). Написать схематично программу с функцией, использующей целый двумерный числовой массив в качестве исходного данного.

Любая матрица определяется адресом 1-го элемента, количеством строк и столбцов.

Для передачи матрицы в функцию, необходимо объявить эти 3 параметра:

1) int *p; // для передачи адреса

2) int *n; // количество строк

3) int *m; // количество столбцов

 

void InMas(const int *p,int *pr, int n, int m)

{

int i,j;

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

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

pr[i*m+j]=p[i*m+j]*2;

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

{

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

cout<<setw(4)<<pr[i*m+j]<<' ';

cout<<endl;

}

return;

}

 

 

int main(void)

{

const int STR=3, STLB=4;

int mas[STR][STLB]={1,2,3,4,5,6,7,8,9,10,11,12};

int masr[STR][STLB];

InMas(mas[0],masr[0],STR,STLB);

 

return 0;

}

 

+

Рекурсивная функция

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

Рекурсия – мощный инструмент разработки программ, когда большие объемы действий могут быть записаны кратко.

Рекурсию можно рассматривать как еще одну управляющую структуру – управление из точки рекурсивного вызова передается на начало функции.

Ключевым фактором обеспечения рекурсии является использование стека. Стек – особое устройство оперативной памяти по принципу: последним пришел – первым вышел.

 

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

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

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

 

Числа Фибоначчи

, n>2

 

a=0, b=1, c=a+b, a=b, b=c

 

int Fib(int n)

{

if(n==0)

return 0;

else if(n==1)

return 1;

else

return Fib(n-2)+Fib(n-1);

}

 

int main(void)

{

int n;

cin>>n;

cout<<Fib(n)<<endl;

return 0;

}

Задача: вычислить факториал числа N

N!=N*(N-1)

 

int rek(int n) рабочая

{

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

return n;

else

return rek(n-1)*n;

 

}

int main(void)

{

int N=5;

cout<<rek(N)<<endl;

return 0;

}

+

Перегрузка функций.

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

 

Использование нескольких функций с одним и тем же именем, но с разными списками параметров(по типу или количеству) называется перегрузкой.. Тип функции не участвует в перегрузке.

 

Компилятор определяет, какая функция вызвана по набору аргументов.

 

Вызов функции должен быть однозначным.

Неоднозначность может возникнуть при:

1. Преобразовании типа

2. Использовании параметров ссылок

3. Использовании параметров по умолчанию

 

1.

float f(float a);

double f(double a);

 

int main (void)

{

int a =...;

float b =...;

double c =...;

f (b);

f (c);

f (a); // неоднозначность. возникнет ошибка компиляции

f ((double)a); // таким образом можно устранить неоднозначность

return 0;

}

 

2.

 

void f1(int a);

void f1(int&a);

 

int main (void)

{

int a =...;

f1(a); // неоднозначность

return 0;

}

 

3.

 

void f2 (int a);

int f2 (int a, int b=3);

 

int main (void)

{

int a =...;

f2(a); // неоднозначность

return 0;

}

Шаблоны функций.

Многие алгоритмы не зависят от типов используемых данных.

 

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

 

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

 

Шаблон необходим для формирования текста функции.

 

Формат функции шаблона

template <class Type>

имя функции

{

// тело функции

}

 

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

Параметризованных типов может быть несколько.

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

Пример демонстрирует замену параметризованного типа по умолчанию.

Ставим цель: функция работает для массива любого типа. Тип массива параметризуем или обобщаем –Type.

Тип массива Type

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

Если да, то их тип тоже Type

Если нет, можно задавать стандартный тип или создать другую параметризацию

template<class Type>

Type MaxMas(Type *p, int n)

{

int i;

Type max=p[0];

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

if (max<p[i])

max=p[i];

return max;

}

 

int main(void)

{

const int N=7;

int M1[N]={3,-2,7,5,9,2,4};

double M2[N]={3.25,1.7,-5.6,7.3,7.3,-4.4,-1.9};

int max1;

double max2;

max1=MaxMas(M1,N);

max2=MaxMas(M2,N);

cout<<max1<<endl;

cout<<max2<<endl;

return 0;

}

Механизм шаблона

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

В тексте функции слово Type везде заменяется на int, получается один экземпляр функции.

Опираясь на второй вызов, Type заменяется на double – получился второй экземпляр функции.

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

// Процесс создания экземпляра функции называется инстанцирование.

 

Пример 2: явное задание типа.

Если параметризована локальная переменная, то её тип не в