Программирование презентация

Содержание

4. Структурное программирование 4.10. Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect

Слайд 1Программирование


Часть 5
Функции

Слайд 24. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 34. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 44. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 54. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 64. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 74. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 84. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 94. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 104. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 114. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 124. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 134. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 144. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 154. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 164. Структурное программирование 4.10. Функции
Структурная декомпозиция программы





int main()
{
…

input_vect (a,n);
…

add_vect (a,b,c,n);
…
output_vect (c,n);
…
return 0
}

void input_vect (double v [ ], int dim)
{
…
return;
}

void add_vect (double v1 [ ], double v2 [ ],
double res [ ], int dim)
{
…
return;
}

void output_vect (double v [ ], int dim)
{
…
return;
}

Выполнение начинается с main

Возврат из main в ОС

Слайд 17


Функция – изолированный именованный блок кода, имеющий определенное назначение
Информация в функцию

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

4. Структурное программирование 4.10. Функции

int k = add_ints (2,3);

int add_ints (int a, int b)
{
return a+b;
}

аргументы

формальные параметры

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

Возвращается
значение 5

Слайд 18


Структура функций

Тип_Возврата Имя_функции (список_параметров)
{
операторы;
return выражение;


}
Область видимости параметров функции, объявленных в ее заголовке и переменных, объявленных в ее теле, ограничивается блоком тела функции.
Эти переменные, если они не объявлены с атрибутом static уничтожаются после завершения выполнения функции, а хранимые ими значения безвозвратно теряются.
Если функция не возвращает значения, в качестве типа возврата указывается void, а оператор return не содержит выражения, значение которого должно быть возвращено в вызываемую функцию.

4. Структурное программирование 4.10. Функции

Заголовок

Тело функции


Слайд 19


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

чтобы скомпилировать правильно ее вызов.
Если текст функции размещен в файле с исходным текстом после ее вызова или вообще размещен в другом файле, необходимо объявить функцию с помощью оператора, называемого прототипом функции.
Все прототипы функций обычно помещаются в начале исходного файла программы. Заголовочные файлы, включаемые для использования стандартных библиотечных функций, помимо прочего включают в себя прототипы этих функций.
Описание прототипа ничем не отличается от описания заголовка функции:
Тип_Возврата Имя_функции (список_параметров);
Описание прототипа, в отличие от заголовка, заканчивается точкой с запятой.

4. Структурное программирование 4.10. Функции

Слайд 20


4. Структурное программирование 4.10. Функции
void input_vect(double v[ ],int n);
void output_vect(double

v[ ],int n);

int main()
{
const int m=5; double x[5];

input_vect(x,m);
output_vect(x,m);

return 0;
}

void print_vector (double v[ ], int n)
{
cout << endl << "The vector is:";
for (int i=0; i<=n-1; i++)
cout < cout << endl;
return;
}

void input_vect( double v[ ], int n)
{
for (int i=0; i<=n-1; i++)
{
cout << "Enter vector[" << i << "] :";
cin >> v[i];
}
return;
}

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

Слайд 21


Способы передачи данных в вызываемую функцию

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

переменных
Через файлы на внешних запоминающих устройствах


Способы передачи данных из вызываемой функции

Через возвращаемое значение
Через формальные параметры, вызываемые по ссылке
Путем изменения значений глобальных переменных
Через файлы на внешних запоминающих устройствах

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

4. Структурное программирование 4.10. Функции

Слайд 22


Передача аргументов в функцию по значению

В С++ используются два механизма передачи

аргументов в функцию: по значению и по ссылке.

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

4. Структурное программирование 4.10. Функции

Слайд 23


int my(int i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int i)
{
int p=2;
i*=2;
return p+i;
}

k

m


АЛУ

4. Структурное программирование 4.10. Функции

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

Слайд 24


int my(int i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int i)
{
int p=2;
i*=2;
return p+i;
}


k

m

i

АЛУ

4. Структурное программирование 4.10. Функции

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

Слайд 25


int my(int i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int i)
{
int p=2;
i*=2;
return p+i;
}


k

m

i


p

АЛУ

4. Структурное программирование 4.10. Функции

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

Слайд 26


int my(int i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int i)
{
int p=2;
i*=2;
return p+i;
}


k

m

i


p

АЛУ
3*2 = 6

4. Структурное программирование 4.10. Функции

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

Слайд 27


int my(int i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int i)
{
int p=2;
i*=2;
return p+i;
}


k

m

i


p

АЛУ
3*2 = 6

4. Структурное программирование 4.10. Функции

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

Слайд 28


int my(int i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int i)
{
int p=2;
i*=2;
return p+i;
}


k

m

i


p

АЛУ
2+6 =

4. Структурное программирование 4.10. Функции

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

Слайд 29


int my(int i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int i)
{
int p=2;
i*=2;
return p+i;
}


k

m

i


p

АЛУ
2+6 = 8

4. Структурное программирование 4.10. Функции

my

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

Слайд 30


int my(int i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int i)
{
int p=2;
i*=2;
return p+i;
}

k

m


АЛУ

4. Структурное программирование 4.10. Функции

my

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

Слайд 31


Передача аргументов в функцию по ссылке

При передаче по ссылке в вызываемую

функцию передаются ссылки на переменные – аргументы.
Копии аргументов с именами формальных параметров не создаются.
Вместо этого, по ссылке обеспечивается доступ к участкам памяти, занимаемым аргументами.
Говоря другими словами, обработка аргументов ведется «на месте».
Чтобы передать значения аргументов по ссылке, в качестве формальных параметров указывают переменные –ссылки.
Все изменения формальных параметров, сделанные в функции, происходят с аргументами.
Если в качестве аргумента по ссылке передается константа, то формальный параметр-ссылка должен быть объявлен с модификатором const.

4. Структурное программирование 4.10. Функции

Слайд 32


int my(int &i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 6 8
_getch();
return 0;
}
int my(int &i)
{
int p=2;
i*=2;
return p+i;
}

k

m


АЛУ

4. Структурное программирование 4.10. Функции

Передача аргументов в функцию по ссылке

Слайд 33


int my(int &i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int &i)
{
int p=2;
i*=2;
return p+i;
}


k

m

i

АЛУ

4. Структурное программирование 4.10. Функции

Передача аргументов в функцию по ссылке

Слайд 34


int my(int &i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int &i)
{
int p=2;
i*=2;
return p+i;
}


k

m


p

АЛУ

4. Структурное программирование 4.10. Функции

i

Передача аргументов в функцию по ссылке

Слайд 35


int my(int &i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int &i)
{
int p=2;
i*=2;
return p+i;
}


k

m


p

АЛУ
3*2 = 6

4. Структурное программирование 4.10. Функции

i

Передача аргументов в функцию по ссылке

Слайд 36


int my(int &i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int &i)
{
int p=2;
i*=2;
return p+i;
}


k

m


p

АЛУ
3*2 = 6

4. Структурное программирование 4.10. Функции

i

Передача аргументов в функцию по ссылке

Слайд 37


int my(int &i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int &i)
{
int p=2;
i*=2;
return p+i;
}


k

m


p

АЛУ
2+6 =

4. Структурное программирование 4.10. Функции

i

Передача аргументов в функцию по ссылке

Слайд 38


int my(int &i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int &i)
{
int p=2;
i*=2;
return p+i;
}


k

m


p

АЛУ
2+6 = 8

4. Структурное программирование 4.10. Функции

i

Передача аргументов в функцию по ссылке

Слайд 39


int my(int &i);
int main()
{
int k=3, m=0;

m=my(k);
cout << k << " " << m; // 3 8
_getch();
return 0;
}
int my(int &i)
{
int p=2;
i*=2;
return p+i;
}

k

m


АЛУ

4. Структурное программирование 4.10. Функции

my

Передача аргументов в функцию по ссылке

Слайд 40


Передача массивов по ссылке

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

записывать перед формальным параметров знак ссылки & не следует:
int example (short a[3]);

При описании в качестве формального параметра одномерного массива, его размер указывать необязательно:
int example(short a[ ]);

При описании в качестве формального параметра многомерного массива, его размер по левому измерению указывать необязательно:
int example(short y[ ][4][3]);

4. Структурное программирование 4.10. Функции

Слайд 41


void set(short [ ][3], int);
int main()
{
short a[2][3]={0};

set(a,2);
return 0;
}
void set (short k[ ][3], int m)
{
for (short i=0; i<=m-1; i++)
for (short j = 0; j<=2; j++) k[i][j]=i+j;
return;
}

a


4. Структурное программирование 4.10. Функции

Передача массивов по ссылке

Слайд 42


void set(short [ ][3], int);
int main()
{
short a[2][3]={0};

set(a,2);
return 0;
}
void set (short k[ ][3], int m)
{
for (short i=0; i<=m-1; i++)
for (short j = 0; j<=2; j++) k[i][j]=i+j;
return;
}


4. Структурное программирование 4.10. Функции

a

k

m

Передача массивов по ссылке

Слайд 43


void set(short [ ][3], int);
int main()
{
short a[2][3]={0};

set(a,2);
return 0;
}
void set (short k[ ][3], int m)
{
for (short i=0; i<=m-1; i++)
for (short j = 0; j<=2; j++) k[i][j]=i+j;
return;
}


4. Структурное программирование 4.10. Функции

a

k

m

j

i


Передача массивов по ссылке

Слайд 44


void set(short [ ][3], int);
int main()
{
short a[2][3]={0};

set(a,2);
return 0;
}
void set (short k[ ][3], int m)
{
for (short i=0; i<=m-1; i++)
for (short j = 0; j<=2; j++) k[i][j]=i+j;
return;
}


4. Структурное программирование 4.10. Функции

a

k

m

j

i


Передача массивов по ссылке

Слайд 45


void set(short [ ][3], int);
int main()
{
short a[2][3]={0};

set(a,2);
return 0;
}
void set (short k[ ][3], int m)
{
for (short i=0; i<=m-1; i++)
for (short j = 0; j<=2; j++) k[i][j]=i+j;
return;
}


4. Структурное программирование 4.10. Функции

a

Передача массивов по ссылке

Слайд 46


Передача указателей в функции

Указатели обычно передаются по значению. Доступ к

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

4. Структурное программирование 4.10. Функции

Слайд 47


int my(int *i);
int main()
{
int k=3, m=0;

m=my(&k);
cout << k << " " << m; // 6 8
_getch();
return 0;
}
int my(int *i)
{
int p=2;
*i *= 2;
return p + *i;
}

k

m


АЛУ

4. Структурное программирование 4.10. Функции

Передача указателей в функции

Слайд 48



k
m
&i
АЛУ

4. Структурное программирование 4.10. Функции
int my(int *i);
int main()
{

int k=3, m=0;
m=my(&k);
cout << k << " " << m; // 6 8
_getch();
return 0;
}
int my(int *i)
{
int p=2;
*i *= 2;
return p + *i;
}

Передача указателей в функции

Слайд 49



k
m

p
АЛУ

4. Структурное программирование 4.10. Функции
int my(int *i);
int main()
{

int k=3, m=0;
m=my(&k);
cout << k << " " << m; // 6 8
_getch();
return 0;
}
int my(int *i)
{
int p=2;
*i *= 2;
return p + *i;
}

&i

Передача указателей в функции

Слайд 50



k
m

p
АЛУ
3*2 = 6
4. Структурное программирование 4.10. Функции
int my(int *i);
int

main()
{
int k=3, m=0;
m=my(&k);
cout << k << " " << m; // 6 8
_getch();
return 0;
}
int my(int *i)
{
int p=2;
*i *= 2;
return p + *i;
}

&i


Передача указателей в функции

Слайд 51



k
m

p
АЛУ
3*2 = 6
4. Структурное программирование 4.10. Функции
int my(int *i);
int

main()
{
int k=3, m=0;
m=my(&k);
cout << k << " " << m; // 6 8
_getch();
return 0;
}
int my(int *i)
{
int p=2;
*i *= 2;
return p + *i;
}

&i


Передача указателей в функции

Слайд 52



k
m

p
АЛУ
2+6 =
4. Структурное программирование 4.10. Функции
int my(int *i);
int main()


{
int k=3, m=0;
m=my(&k);
cout << k << " " << m; // 6 8
_getch();
return 0;
}
int my(int *i)
{
int p=2;
*i *= 2;
return p + *i;
}

&i


Передача указателей в функции

Слайд 53



k
m

p
АЛУ
2+6 = 8
4. Структурное программирование 4.10. Функции
my
int my(int *i);
int

main()
{
int k=3, m=0;
m=my(&k);
cout << k << " " << m; // 6 8
_getch();
return 0;
}
int my(int *i)
{
int p=2;
*i *= 2;
return p + *i;
}

&i

Передача указателей в функции

Слайд 54


k
m

АЛУ

4. Структурное программирование 4.10. Функции
my
int my(int *i);
int main()
{

int k=3, m=0;
m=my(&k);
cout << k << " " << m; // 6 8
_getch();
return 0;
}
int my(int *i)
{
int p=2;
*i *= 2;
return p + *i;
}

Передача указателей в функции

Слайд 55


Передача указателей на функции

Указатель может хранить адрес функции. Это позволяет

присваивать ему адрес точки вызова функции и вызывать ее через указатель.
Указатель на функцию должен не только содержать адрес памяти, где находится функция, которую необходимо вызвать. Такой указатель должен поддерживать информацию о количестве и типах аргументов и типе возвращаемого значения.
Объявление указателей на функцию:
Тип_возврата (*Имя_указателя) (список_типов_параметров);
Скобки, в которые взято *Имя_указателя позволяет отличит описание указателя на функцию
double (*pfun)(char*, int);
от описания прототипа функции, возвращающей указатель на double:
double *pfun (char*, int);

4. Структурное программирование 4.10. Функции

Слайд 56


Передача указателей на функции: пример

double calc_fun (double (*p_f)(double), double x);
int

main()
{
double (*p_func)(double)=NULL;

p_func=sin; // можно и p_func = &sin;
cout << p_func(0) << endl;
cout << calc_fun(cos, 0) << endl; // можно и calc_fun(&cos,0)
_getch();
return 0;
}
double calc_fun (double (*p_f)(double), double x)
{
return p_f(x);
}

4. Структурное программирование 4.10. Функции

Слайд 57


Инициализация параметров

Параметры функции, передаваемые по значению, можно инициализировать в ее

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

4. Структурное программирование 4.10. Функции

Слайд 58


Инициализация параметров

void repchar (char с = ‘_', int n =

20);
int main ()
{
repchar (); // ___________________
repchar (‘&'); // &&&&&&&&&&&&&&&&
repchar ('=', 10); / // =========
_getch();
return 0;
}
void repchar (char с, int n)
{
for (int i=1; i<=n; i++) cout << с;
cout << endl;
}

4. Структурное программирование 4.10. Функции

Слайд 59


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

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

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

4. Структурное программирование 4.10. Функции

Слайд 60


Перегрузка функций
void repchar ();
void repchar (char с);
void repchar (int n);
void repchar

(char c, int n);
int main ()
{
repchar (); // ______________
repchar (5); // _____
repchar ('=', 3); // ===
repchar ('+'); // ++++++++++++++
_getch();
return 0;
}

4. Структурное программирование 4.10. Функции

void repchar ()
{
for (int i=1; i<=20; i++) cout << ’_’
cout << endl;
}
void repchar (char c)
{
for (int i=1; i<=20; i++) cout << c;
cout << endl;
}
void repchar (int n)
{
for (int i=1; i<=n; i++) cout << ’_';
cout << endl;
}
void repchar (char c, int n)
{
for (int i=1; i<=n; i++) cout << c;
cout << endl;
}

Слайд 61


Возвращаемые значения

В случае, если функция возвращает значение, его тип должен быть

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

4. Структурное программирование 4.10. Функции

Слайд 62


Структуры как возвращаемые значения

В С в качестве возвращаемых значений могут фигурировать

структуры.

struct myst
{
short i;
short j;
};

myst init ();
int main()
{
myst r;
r=init();
return 0;
}

4. Структурное программирование 4.10. Функции

myst init()
{
myst w;
w.i=1; w.j=2;
return w;
}

Слайд 63


Массивы и структуры как возвращаемые значения

Массив не может быть непосредственно возвращаемым

значением. Зато вполне можно вот так:

struct myst
{
short k [10];
};
myst init (int n);

int main()
{
myst r;
r=init(10);
return 0;
}

4. Структурное программирование 4.10. Функции

myst init(int n)
{
myst w;
for (int i=0; i<=n-1; i++) w.k[i]=i;
return w;
}

Слайд 64


Возврат ссылок: функция в левой части оператора присваивания

Функция может возвращать ссылку

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

4. Структурное программирование 4.10. Функции

Слайд 65


char &repl (int i, char c[ ]);
int main()
{

char str[]="Hehlo";
repl(2,str)=‘l';
cout << str; // Hello

_getch();
return 0;
}

char &repl(int i, char c[])
{
return c[i];
}

Str


4. Структурное программирование 4.10. Функции

Возврат ссылок

Слайд 66


char &repl (int i, char c[ ]);
int main()
{

char str[]="Hehlo";
repl(2,str)=‘l';
cout << str; // Hello

_getch();
return 0;
}

char &repl(int i, char c[])
{
return c[i];
}

Str


4. Структурное программирование 4.10. Функции

i


c

Возврат ссылок

Слайд 67


char &repl (int i, char c[]);
int main()
{
char

str[]="Hehlo";
repl(2,str)=‘l';
cout << str; // Hello

_getch();
return 0;
}

char &repl(int i, char c[])
{
return c[i];
}

Str


4. Структурное программирование 4.10. Функции

i


c

c[2]

Возврат ссылок

Слайд 68


char &repl (int i, char c[]);
int main()
{
char

str[]="Hehlo";
repl(2,str)=‘l';
cout << str; // Hello

_getch();
return 0;
}

char &repl(int i, char c[])
{
return c[i];
}

Str


4. Структурное программирование 4.10. Функции

i


c

c[2]

repl

Возврат ссылок

Слайд 69


char &repl (int i, char c[]);
int main()
{
char

str[]="Hehlo";
repl(2,str)=‘l';
cout << str; // Hello

_getch();
return 0;
}

char &repl(int i, char c[])
{
return c[i];
}

Str


4. Структурное программирование 4.10. Функции

repl

Возврат ссылок

Слайд 70


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

Внимание: рассмотренный выше пример находится на грани фола. Возвращаемая

ссылка остается действительной (ссылается на существующий после вызова функции объект ) только потому, что массив с – формальный параметр и ссылается на то же место в памяти, что и продолжающий существование массив str.
Гораздо спокойнее возвращать ссылки на глобальные или статические переменные.
Все сказанное относится и к возврату указателей.
Пример некорректной функции:

char &repl(int i)
{
char c=“Hello”;
return c[i];
}

4. Структурное программирование 4.10. Функции

Слайд 71


Области видимости и классы памяти переменных

Область видимости определяет, из каких частей

программы возможен доступ к переменной
Класс памяти определяет время, в течение которого перменная существует в памяти компьютера
В С++ существуют 3 типа области видимости переменных:
локальная область видимости
область видимости файла
область видимости класса (будет рассмотрена позднее)
Переменные, имеющие локальную область видимости доступны только внутри того блока, в котором они определены (блоком обычно считается код, заключенный в фигурные скобки)
Переменные, имеющие область видимости файла, доступны из любого места файла, в котором они определены

4. Структурное программирование 4.10. Функции

Слайд 72


Области видимости и классы памяти переменных

В С++ существует 3 класса памяти:


auto (автоматический)
static (статический)
динамический (будет рассмотрен позднее)

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

4. Структурное программирование 4.10. Функции

Слайд 73


Локальные автоматические переменные

int main()
{
int k=1; int i=10;

cout << k << endl;
for (int j=1; j<=3; j++)
{
int k=2; //2 2 2
cout << k << endl;
{
cout << i << endl; // 10
int k; if (j==1) k=3; // Это неправильно!
cout << k << endl; k++; //3 4 5 Но! В режиме отладки - ошибка // выполнения: неинициализированная переменная
}
cout << k << endl; // 2 2 2
}
cout << k << endl; // 1
return 0;
}

4. Структурное программирование 4.10. Функции

Слайд 74


Локальные статические переменные

int main()
{
static int k=1;


for (int j=1; j<=3; j++)
{
static int k=2; //2 2 2
cout << k << endl;
{
static int k=3; // Корректно !
cout << k << endl; k++; //3 4 5
}
cout << k << endl; // 2 2 2
}
cout << k << endl; // 1
return 0;
}

4. Структурное программирование 4.10. Функции

Слайд 75


Области видимости и классы памяти переменных

Глобальные переменные объявляются вне всех блоков

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

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

4. Структурное программирование 4.10. Функции

Слайд 76


Просто пример: внутреннее представление переменных

int internal_form (void *p, int n_bytes, char

str [72])
// Explores memory area from p within n_bytes (n_bytes <=8)
// The result is string str[72]:
// each bit is represented with '0' or '1‘ like bits in the memory
// bytes are separated with space
// Returns 0 if OK, -1 when n_bytes >8
{
unsigned char k=0, m=0;
if (n_bytes > 8) return -1;

unsigned char *pc = reinterpret_cast (p);
for (int i=0; i<=70; i++)str[i]=' '; str[71]='\0';


4. Структурное программирование 4.10. Функции

Слайд 77


Просто пример: внутреннее представление переменных


for (int i=0; i<=n_bytes-1; i++, pc++) // cycle on bytes
{
k=*pc;
for (int j=0; j<=7; j++, k>>=1) // bits in the byte
{
m = k;
k >>= 1; k <<= 1;
str [i*8+7-j+i] = m==k ? '0‘ : '1';
}
}
return 0;
}

4. Структурное программирование 4.10. Функции

Слайд 78


Просто пример: внутреннее представление переменных

int internal_form (void *p, int n_bytes, char

str [72]);
int main() // Example: how to get an internal form of a variable
{
typedef short my_type; //type to be explored

my_type c=-2; // variable to be explored
char str [72] = {0}; // this string will represent memory
void *p = &c;
if (!internal_form (p, sizeof (my_type), str)) cout << str << endl;
else cout << "Error while internal_form executed" << endl;
_getch();
return 0;
}

4. Структурное программирование 4.10. Функции

Слайд 79



Преобразовать указатель void* p в указатель char* pc

[n_bytes>8]
return-1
[n_bytes

в str[71] символ конца строки

Номер анализируемого байта i=0



сохраняем анализируемый байт в char k= *pc



m=k; k>>=1; k<<=1


[i > n_bytes-1]

[i<=n_bytes-1]

Номер анализируемого бита j=0

str [i*8+7-j+i] = ‘0’

str [i*8+7-j+i] = ‘1’

j++; k>>=1 (отбрасываем обработанный бит)

i++; pc++ (сдвигаемся на 1 байт)

[j <= 7]

[j > 7]

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


[m == k]

[m != k]

Слайд 80


Еще один пример: решение нелинейного уравнения x=f(x) методом простых итераций

Постановка задачи


Методом последовательных приближений найти решение уравнения x=f(x) с заданной точностью r.

Математическая модель .
Выберем начальное приближение x0
Положим x1=f(x0);
x2=f(x1);
…
xn=f(xn-1)
Погрешность d = |xn-1-f(xn-1)| = |xn-1-xn|
Условие сходимости: |f'(x)|<1

4. Структурное программирование 4.10. Функции

Слайд 81


Еще один пример: решение нелинейного уравнения x=f(x) методом простых итераций


Данные.
Заданная точность

float r
Текущая погрешность float d
Текущее значение xn-1 float x
Текущее значение f(xn-1) float y
Алгоритм.
Задать x=x0, r
Если r < 1e-6, положить r = 1e-6
3. Инициализировать d=2*r
4. Пока d>r выполнять
4.1. Вычислить y = cos(x)
4.2. Положить d = |x-y|
4.3. Положить x = y
5. Вывести значение x

4. Структурное программирование 4.10. Функции

Полученный ранее алгоритм на псевдокоде

Слайд 82


Еще один пример: решение нелинейного уравнения x=f(x) методом простых итераций

Параметры:
Заданная точность

double r
Начальное приближение double x
Указатель на функцию double (*p_func)(double);
Максимальное число итераций integer max_i
Достигнутая точность double &d
Возвращаемое значение:
Решение double x
Внутренние переменные:
Текущее значение xn-1 double x
Текущее значение f(xn-1) double y
Алгоритм.
1. Если r < 1e-12, положить r = 1e-12
3. Инициализировать d=2*r, y=0
4. Пока d>r и число итераций не больше максимального и y<1e100 выполнять
4.1. Вычислить y = cos(x)
4.2. Положить d = |x-y|
4.3. Положить x = y
5. Вывести значение x

4. Структурное программирование 4.10. Функции

Проект функции на псевдокоде

Слайд 83


Еще один пример: решение нелинейного уравнения x=f(x) методом простых итераций

double solveqn

(double r, double x, double (*p_func)(double), int max_i, double&d)
// Solves equation f(x)=0
// r - required precision (<=1e-12), x - initial approximation
// p_func - pointer to the f(x), max_i - max number of iterations
// d - attained accuracy
{
double y=0;
if (r < 1e-12) r=1e-12; d=2*r;

for (int i=1; (i<=max_i) && (d > r) && abs(y)< 1e100; i++)
{
d = abs(x-(y=p_func(x)));
x = y;
}
return y;
}

4. Структурное программирование 4.10. Функции


Слайд 84


Еще один пример: решение нелинейного уравнения x=f(x) методом простых итераций

double solveqn

(double r, double x, double (*p_func)(double), int max_i, double&d);
double myfun(double x);
int main() // Example: how to solve an equation f(x)=0
{
double d = 0;
cout << setprecision(12) << solveqn (1e-5,1.0, cos, 10000, d)
<< " d = " << setprecision(12) << d << endl; // 0.739 d= 7.043e-006
cout << setprecision(12) << solveqn (1e-5,10.0, myfun, 10000, d)
<< " d = " << setprecision(12) << d << endl; //1e+128 d= 1e+128 divergence!!!
_getch();
return 0;
}
double myfun(double x)
{
return x*x;
}

4. Структурное программирование 4.10. Функции


Слайд 85


4. Структурное программирование 4.11. Рекурсия
Рекурсивным называется объект, который частично определяется

через самого себя.

0!=1
для любых n>0 n! = n*(n-1)!

int fact (int i);
int main()
{
cout << fact(4) << endl; // 24
return 0;
}
int fact (int i) // recursive function
{
return i == 0 ? 1: i * fact(i-1);
}

Слайд 86


4. Структурное программирование 4.11. Рекурсия
Нерекурсивное определение факториала

n!=1*2*3*…*n

int

fact (int i);
int main()
{
cout << fact(4) << endl; // 24
_getch();
return 0;
}
int fact (int i) // non-recursive function
{
int f=1;
for (int j=1; j<=i; j++) f*=j;
return f;
}

Слайд 87
Содержание и мощность рекурсивного определения, а также его главное назначение, состоит

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

Аналогично, с помощью конечного рекурсивного алгоритма можно определить бесконечное вычисление, причем алгоритм не будет содержать повторений фрагментов текста.

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














4. Структурное программирование 4.11. Рекурсия

Слайд 88
В общем случае любая рекурсивная процедура Rec включает в себя некоторое

множество операторов S и один или несколько операторов рекурсивного вызова Р.

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

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
















4. Структурное программирование 4.11. Рекурсия

Слайд 89
Максимальное число рекурсивных вызовов процедуры без возвратов, которое происходит во время

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

Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.
















4. Структурное программирование 4.11. Рекурсия

Слайд 90
Структура рекурсивной процедуры может принимать три разных формы:

Форма с выполнением действий

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

void Rec()
{
… S … ;
if (условие) Rec ();
return;
}

















4. Структурное программирование 4.11. Рекурсия

Слайд 91
Вычисление факториала на рекурсивном спуске:

unsigned int fact_dn (int m, unsigned int

worker=1);
int main ()
{
cout << fact_dn (5) << endl;
_getch();
return 0;
}
int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}












4. Структурное программирование 4.11. Рекурсия

Слайд 92











4. Структурное программирование 4.11. Рекурсия
Трассировка вызовов

1) cout

<< endl

(1) m=4, worker=1; fact_dn=?

int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}

Слайд 93











4. Структурное программирование 4.11. Рекурсия
(1) m=3, worker=4;

fact_dn=?

Трассировка вызовов

1) cout << fact_dn (4) << endl

int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}

Слайд 94











4. Структурное программирование 4.11. Рекурсия
(1) m=4, worker=4;

fact_dn=?

Трассировка вызовов

cout << fact_dn (4) << endl

if (4 !=1) return fact_dn (3, 4);

(2) m=3, worker=4; fact_dn=?

int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}


Слайд 95











4. Структурное программирование 4.11. Рекурсия
(1) m=4, worker=4;

fact_dn=?

Трассировка вызовов

cout << fact_dn (4) << endl

if (4 !=1) return fact_dn (3, 4);

(2) m=3, worker=12; fact_dn=?

int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}


Слайд 96











4. Структурное программирование 4.11. Рекурсия
(1) m=4, worker=4;

fact_dn=?

Трассировка вызовов

cout << fact_dn (4) << endl

if (4 !=1) return fact_dn (3, 4);

if (3 != 1) return fact_dn (2, 12);

(2) m=3, worker=12; fact_dn=?

(3) m=2, worker=12; fact_dn=?

int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}



Слайд 97











4. Структурное программирование 4.11. Рекурсия
(1) m=4, worker=4;

fact_dn=?

Трассировка вызовов

cout << fact_dn (4) << endl

if (4 !=1) return fact_dn (3, 4);

if (3 != 1) return fact_dn (2, 12);

(2) m=3, worker=12; fact_dn=?

(3) m=2, worker=24; fact_dn=?

int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}



Слайд 98











4. Структурное программирование 4.11. Рекурсия
(1) m=4, worker=4;

fact_dn=?

(2) m=3, worker=12; fact_dn=?

(3) m=2, worker=24; fact_dn=?

(4) m=1, worker=24; fact_dn=?

int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}




Трассировка вызовов

cout << fact_dn (4) << endl

if (4 !=1) return fact_dn (3, 4);

if (3 != 1) return fact_dn (2, 12);

if (2 ! = 1) return fact_dn (1, 24);

Слайд 99











4. Структурное программирование 4.11. Рекурсия
(1) m=4, worker=4;

fact_dn=?

(2) m=3, worker=12; fact_dn=?

(3) m=2, worker=24; fact_dn=?

(4) m=1, worker=24; fact_dn=?

int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}




Трассировка вызовов

cout << fact_dn (4) << endl

if (4 !=1) return fact_dn (3, 4);

if (3 != 1) return fact_dn (2, 12);

if (2 ! = 1) return fact_dn (1, 24);

Слайд 100











4. Структурное программирование 4.11. Рекурсия
int fact_dn (int m, int worker)
{


worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}

(1) m=4, worker=4; fact_dn=?

(2) m=3, worker=12; fact_dn=?

(3) m=2, worker=24; fact_dn=?

(4) m=1, worker=24; fact_dn=24




Трассировка вызовов

cout << fact_dn (4) << endl

if (4 !=1) return fact_dn (3, 4);

if (3 != 1) return fact_dn (2, 12);

if (2 ! = 1) return fact_dn (1, 24);

if (1 !=1)…else return worker




Слайд 101











4. Структурное программирование 4.11. Рекурсия
int fact_dn (int m, int worker)
{


worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}

(1) m=4, worker=4; fact_dn=?

(2) m=3, worker=12; fact_dn=?

(3) m=2, worker=24; fact_dn=24




Трассировка вызовов

cout << fact_dn (4) << endl

if (4 !=1) return fact_dn (3, 4);

if (3 != 1) return fact_dn (2, 12);

if (2 ! = 1) return fact_dn (1, 24);




Слайд 102Трассировка вызовов

cout

(3, 4);

if (3 != 1) return fact_dn (2, 12);

















4. Структурное программирование 4.11. Рекурсия

int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}

(1) m=4, worker=4; fact_dn=?

(2) m=3, worker=12; fact_dn=24



Слайд 103Трассировка вызовов

cout

(3, 4);


















4. Структурное программирование 4.11. Рекурсия

int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}

(1) m=4, worker=4; fact_dn=24


Слайд 104
Вычисление факториала на рекурсивном спуске:

int fact_dn (int m, int worker=1);
int main

()
{
cout << fact_dn (5) << endl;
_getch();
return 0;
}
int fact_dn (int m, int worker)
{
worker *= m;
if (m!= 1) return fact_dn (m-1, worker);
else return worker;
}












4. Структурное программирование 4.11. Рекурсия


Можно записать короче


Оптимизируем типы аргументов

Слайд 105
Вычисление факториала на рекурсивном спуске:

unsigned long fact_dn (unsigned int m, unsigned

long worker=1);
int main ()
{
cout << fact_dn (5) << endl;
_getch();
return 0;
}

unsigned long fact_dn (unsigned int m, unsigned long worker)
{
return m==1 ? worker : fact_dn (m-1, worker*m);
}













4. Структурное программирование 4.11. Рекурсия

Слайд 106
Структура рекурсивной процедуры может принимать три разных формы:

Форма с выполнением действий

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

void Rec()
{
if условие Rec ();
… S … ;
return;
}

















4. Структурное программирование 4.11. Рекурсия

Слайд 107
Вычисление факториала на рекурсивном возврате:















int fact_up (int m);
int main ()
{

cout << fact_up(6) << endl;
_getch();
return 0;
}

unsigned long fact_up (unsigned int m)
{
if (m > 1) return m * fact_up (m - 1);
else return 1;
}

4. Структурное программирование 4.11. Рекурсия

Слайд 108











4. Структурное программирование 4.11. Рекурсия
Трассировка вызовов

cout

endl




(1) m=4, fact_dn=?

unsigned long fact_up (unsigned int m)
{
if (m > 1) return m * fact_up (m - 1);
else return 1;
}

Слайд 109











4. Структурное программирование 4.11. Рекурсия
Трассировка вызовов

cout

endl

if (4 > 1) return m * fact_up (3);






(1) m=4, fact_up=?

unsigned long fact_up (unsigned int m)
{
if (m > 1) return m * fact_up (m - 1);
else return 1;
}

(2) m=3, fact_up=?


Слайд 110











4. Структурное программирование 4.11. Рекурсия
Трассировка вызовов

cout

endl

if (4 > 1) return m * fact_up (3);

if (3 > 1) return m * fact_up (2);






(1) m=4, fact_up=?

unsigned long fact_up (unsigned int m)
{
if (m > 1) return m * fact_up (m - 1);
else return 1;
}

(2) m=3, fact_up=?

(3) m=2, fact_up=?



Слайд 111











4. Структурное программирование 4.11. Рекурсия
Трассировка вызовов

cout

endl

if (4 > 1) return m * fact_up (3);

if (3 > 1) return m * fact_up (2);

if (2 > 1) return m * fact_up (1);





(1) m=4, fact_up=?

unsigned long fact_up (unsigned int m)
{
if (m > 1) return m * fact_up (m - 1);
else return 1;
}

(2) m=3, fact_up=?

(3) m=2, fact_up=?

(4) m=1, fact_up=?




Слайд 112











4. Структурное программирование 4.11. Рекурсия
Трассировка вызовов

cout

endl

if (4 > 1) return m * fact_up (3);

if (3 > 1) return m * fact_up (2);

if (2 > 1) return m * fact_up (1);





(1) m=4, fact_up=?

unsigned long fact_up (unsigned int m)
{
if (m > 1) return m * fact_up (m - 1);
else return 1;
}

(2) m=3, fact_up=?

(3) m=2, fact_up=?

(4) m=1, fact_up=1





Слайд 113











4. Структурное программирование 4.11. Рекурсия
Трассировка вызовов

cout

endl

if (4 > 1) return m * fact_up (3);

if (3 > 1) return m * fact_up (2);






(1) m=4, fact_up=?

unsigned long fact_up (unsigned int m)
{
if (m > 1) return m * fact_up (m - 1);
else return 1;
}

(2) m=3, fact_up=?

(3) m=2, fact_up=2*1




Слайд 114











4. Структурное программирование 4.11. Рекурсия
Трассировка вызовов

cout

endl

if (4 > 1) return m * fact_up (3);







(1) m=4, fact_up=?

unsigned long fact_up (unsigned int m)
{
if (m > 1) return m * fact_up (m - 1);
else return 1;
}

(2) m=3, fact_up=3*2



Слайд 115











4. Структурное программирование 4.11. Рекурсия
Трассировка вызовов

cout

endl






(1) m=4, fact_up=4*6

unsigned long fact_up (unsigned int m)
{
if (m > 1) return m * fact_up (m - 1);
else return 1;
}


Слайд 116
Вычисление факториала на рекурсивном возврате:















int fact_up (int m);
int main ()
{

cout << fact_up(6) << endl;
_getch();
return 0;
}

unsigned long fact_up (unsigned int m)
{
if (m > 1) return m * fact_up (m - 1);
else return 1;
}


Можно записать короче

4. Структурное программирование 4.11. Рекурсия

Слайд 117
Вычисление факториала на рекурсивном возврате:















int fact_up (int m);
int main ()
{

cout << fact_up(6) << endl;
_getch();
return 0;
}

unsigned long fact_up (unsigned int m)
{
return m == 1 ? 1: i * fact_up(m-1);
}

4. Структурное программирование 4.11. Рекурсия

Слайд 118
Структура рекурсивной процедуры может принимать три разных формы:

Форма с выполнением действий

как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

void Rec ()
{
… S1 …;
if (условие) Rec();
… S2 … ;
return;
};















void Rec ()
{
if (условие)
{
… S1 …;
Rec;
… S2 … ;
}
return;
}

4. Структурное программирование 4.11. Рекурсия

Слайд 119
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

Слайд 120
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

_

Слайд 121
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

_

1) c= ?

Слайд 122
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=

H

_

‘H’

Слайд 123
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=‘H’

H

2) c=

‘E’

E

_

Слайд 124
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=‘H’

HEL

2) c=‘E’

3) c=‘L’

_

Слайд 125
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=‘H’

HELL

2) c=‘E’

3) c=‘L’

4) c=‘L’

_

Слайд 126
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=‘H’

HELLO

2) c=‘E’

3) c=‘L’

4) c=‘L’

5) c=‘O’

_

Слайд 127
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=‘H’

HELLO

2) c=‘E’

3) c=‘L’

4) c=‘L’

5) c=‘O’

6) c=13

_

Слайд 128
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=‘H’

HELLO

2) c=‘E’

3) c=‘L’

4) c=‘L’

5) c=‘O’

6) c=13

_

Слайд 129
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=‘H’

OELLO

2) c=‘E’

3) c=‘L’

4) c=‘L’

5) c=‘O’

_

Слайд 130
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=‘H’

OLLLO

2) c=‘E’

3) c=‘L’

4) c=‘L’

_

Слайд 131
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=‘H’

OLLLO

2) c=‘E’

3) c=‘L’

_

Слайд 132
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=‘H’

OLLEO

2) c=‘E’

_

Слайд 133
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

1) c=‘H’

OLLEH

_

Слайд 134
Инвертирование строки

void reverse();
int main()
{
reverse();
cout

endl;
_getch();
return 0;
}
void reverse()
{
char c=_getche();
if (c != 13) reverse();
cout << c;
return;
}

 















4. Структурное программирование 4.11. Рекурсия

OLLEH

_

Слайд 135
Подадим на вход строку ‘HELLO’:















4. Структурное программирование 4.11. Рекурсия

Слайд 136


4. Структурное программирование 4.11. Рекурсия
Быстрая сортировка
9
4
12
1
7
6
8
4
2
10
2
4
4
1
6
7
8
12
9
10
Qsort(1,5)
Qsort(6,10)
Qsort(1,10)
2
4
4
1
6
7
8
12
9
10
2
1
4
4
6
7
8
10
9
12
j=2, i=4
j=9, i=10=R
Qsort(1,2)
Qsort(4,5)
Qsort(6,9)
Вызов не выполняется
2
1
4
6
7
8
10
9
1
2
4
6
7
8
10
9
Qsort(8,9)
10
9
9
10
B=7
B=4
B=12
j=1=L,

i=2=R

j=3

Вызов не выполня-ется

Слайд 137
Быстрая сортировка

Сортируем массив, содержащий информацию о деталях:

struct detail
{
int id;
float weight;
};


Спецификация

функции быстрой сортировки:

void qsort (detail s [ ], int l, int r);















4. Структурное программирование 4.11. Рекурсия

Слайд 138
struct detail
{
int id;
float weight;
};
void qsort

(detail s [ ], int l, int r);
int main()
{
const int n=9;
detail st [n+1];
srand( static_cast (time(NULL)));
for (int i=0; i<=n; i++) st[i].id = rand()%33;
for (int i=0; i<=n; i++) cout << setw (4) << st[i].id;
cout << endl;
qsort (st, 0, 9);
for (int i=0; i<=n; i++) cout << setw (4) << st[i].id;
_getch(); return 0;
}















4. Структурное программирование 4.11. Рекурсия

Слайд 139

void qsort (detail s[ ], int l, int r)
{

int b=0, i=0, j=0;
detail tmp;
b = s[(l+r)/2].id; i = l; j = r;
while (i <= j)
{
while (s[ i ].id < b) i++;
while (s[ j ].id > b) j--;
if (i <= j)
{
tmp = s[ i ]; s[ i ] = s[ j ]; s[ j ] = tmp;
i++; j--;
}
}
if (l < j) qsort ( s, l, j );
if (i < r) qsort ( s, i, r ); return;
}
 















4. Структурное программирование 4.11. Рекурсия

Слайд 140
struct Member
{
int id;
Name ownname;

Date birth;
char address [80];
Date enter;
char position [30];
bool tradeunion;
};


















4. Структурное программирование 4.12. Шаблоны функций

struct detail
{
int id;
float weight;
};

Быстрая сортировка: шаблоны функций


template
void qsort (T s [ ], int l, int r);  

struct Date
{
unsigned short year;
unsigned short month;
unsigned short day;
};

struct Name
{
char surname [80];
char firstname [40];
char patronymic [60];
};

Слайд 141
Быстрая сортировка: шаблоны функций

int main()
{
const int n=12;
detail st[n+1];

srand( static_cast

int> (time(NULL)));
for (int i=0; i<=n; i++) st[i].key = rand()%33;
for (int i=0; i<=n; i++) cout << setw (4) << st[i].key;
cout << endl;
qsort (st,0,9);
for (int i=0; i<=n; i++) cout << setw (4) << st[i].key;
cout << endl;
_getch();
return 0;
}















4. Структурное программирование 4.12. Шаблоны функций

Слайд 142
template void qsort (T s [ ], int l,

int r)
{
int b=0, i=0, j=0, k=0;
T tmp;
b = s[(l+r)/2].key; i = l; j = r;
while (i <= j)
{
while (s[ i ].key < b) i++;
while (s[ j ].key > b) j--;
if (i <= j)
{
tmp = s[ i ]; s[ i ] = s[ j ]; s[ j ] = tmp;
i++; j--;
}
}
if (l < j) qsort ( s, l, j );
if (i < r) qsort ( s, i, r );
return;
}















4. Структурное программирование 4.12. Шаблоны функций

Слайд 143


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

Заголовку тела функции также должна предшествовать конструкция template.
Шаблонная функция может

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

template
void myswap (T *a, T *b)
{
T tmp=*a;
*a=*b;
*b=tmp;
}





4. Структурное программирование 4.12. Шаблоны функций

Слайд 144


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

Еще один простой пример шаблона – функция, осуществляющая перестановку элементов

произвольного типа:

template
void myswap (T *a, T *b)
{
T tmp=*a;
*a=*b;
*b=tmp;
}
int main()
{
int short x=15, y=2;
double a=0, b=12.4;
myswap (&x,&y); myswap (&a,&b); return 0;
}





4. Структурное программирование 4.12. Шаблоны функций

Слайд 145


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

То же самое лучше можно сделать с помощью ссылок, а

не указателей:
template
void myswap (T &a, T &b)
{
T tmp= a;
a=b;
b=tmp;
}
int main()
{
int short x=15, y=2;
double a=0, b=12.4;
myswap (x,y); myswap (a,b); return 0;
}





4. Структурное программирование 4.12. Шаблоны функций

Похожие презентации

Преобразования типов 286
Корпоративный портал, электронный документооборот и управление задачами и проектами 312
Окружающий мир. Викторина для учащихся 3-4 классов. 311
Шаблон презентации 271
QuarkXPress 380
Online сервис MyDPD 276

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

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

Для правообладателей

Яндекс.Метрика