Слайд 2
План
Лекция 8
План
Пара заданий для самопроверки
Функции
Подпрограмма как алгоритмическая структура
Функции
в языке Си
Передача параметров
Возврат значений
Примеры функций
Функции: что еще?
Игнорирование возвращаемого
значения
Тип функции по умолчанию
Неопределенное значение функции
Тип и аргументы функции main()
Функции с переменным числом параметров
Функции и структура программы
Программа из одного файла
Программа из многих файлов
Области видимости переменных
Слайд 3
Пара заданий
для самопроверки
Задание «Поразрядные операции»
Задание «Оператор выбора»
Слайд 4
Пара заданий для самопроверки
Задание «Поразрядные операции»
Что выведет программа?
void
main()
{
unsigned char p=0xFF, q=0360, r;
r
= p & ~q;
printf("%d", r);
}
p=11111111
q=11110000
~q=00001111
p=11111111
p&~q=00001111
Вывод: 15
Слайд 5
Пара заданий для самопроверки
Экзаменационная работа. Задание 1.
Для выражения
укажите порядок вычисления, промежуточные результаты вычисления подвыражений и их
тип. Укажите также значения и тип окончательного результата вычисления выражения, стоящего справа от оператора присваивания, и значение с его типом, сохраняемое в переменной, стоящей слева от оператора присваивания.
2, unsigned int
2, unsigned int
1, unsigned long int
3, unsigned long int
3, int
3
3
unsigned long int
int
Слайд 6
Функции
Подпрограмма как алгоритмическая структура
Функции в языке Си
Передача параметров
Возврат
значений
Примеры функций
Слайд 7
Функции
Алгоритмические структуры
Базовые алгоритмические структуры
Следование
Повторение
Ветвление
Слайд 8
Функции
Алгоритмические структуры
Алгоритмические структуры вкладываются друг в друга
Слайд 9
Функции
Подпрограммы
Часто при построении алгоритмов приходится использовать алгоритмы, составленные
ранее
Алгоритмы, целиком используемые в составе других алгоритмов, называются вспомогательными
(или подчиненными)
В алгоритмических языках вспомогательные алгоритмы оформляются в виде подпрограмм (процедур, функций)
Слайд 12
Функции
Подпрограммы
1. Повторять 3 раза
2. Нажать на
кнопку звонка
Позвонить в звонок
Заголовок подпрограммы
Тело
подпрограммы
Вызов
подпрограммы
Слайд 13
Функции
3. Шаг 3
4. Шаг 4
5. Шаг 5
1. Функция
1
2. Функция 2
Подпрограммы
Вызов подпрограммы приводит к выполнению ее тела
Программа
1.
Шаг 1
2. Шаг 2
Функция 1
Функция 2
Слайд 14
Функции
Подпрограммы
Использование подпрограмм
сокращает описание алгоритма (выполнение одинаковых действий
в разных местах программы)
структурирует описание алгоритма (разбивка программы (или
другой подпрограммы) на подзадачи для лучшего восприятия)
позволяет реализовать на практике принципы структурного программирования при построении больших программ
Слайд 15
Функции
Подпрограммы в Си
В Си подпрограммы реализуются в виде
функций
Выполнение программы начинается с вызова функции main(), которая вызывает
другие функции
#include
void main() {
int i, j, n, m;
printf(“n=”); scanf(“%d”,&n);
printf(“m=”); scanf(“%d”,&m);
for(i=1; i<=n; i++) {
for(j=1; j<=m; j++)
printf(“*”);
printf(“\n”);
}
}
Заголовок функции main()
Тело функции main()
Вызов функции scanf()
Вызов функции printf()
Слайд 16
Функции
Функции в Си
Как описать собственную (нестандартную) функцию?
#include
void
starbar() {
…
}
void main() {
…
starbar();
…
}
Описание функции должно располагаться ранее вызова этой функции
Вызов функции
#include
void starbar();
void main() {
…
starbar();
…
}
void starbar() {
…
}
Объявление функции – до использования
Вызов функции
Описание
функции -- где угодно (может быть и в другом файле)
Вариант 1
Вариант 2
Слайд 17
Функции
Функции в Си
Как описать собственную (нестандартную) функцию?
#include
void
starbar() {
int count;
for (count=1; count
printf(“*”);
printf(“\n”);
}
void main() {
…
starbar();
…
}
Функция, выводящая на экран строку из звездочек
Слайд 18
Функции
Функции в Си
Как описать собственную (нестандартную) функцию?
#include
void
starbar() {
int count;
for (count=1; count
printf(“*”);
printf(“\n”);
}
void main() {
starbar();
printf(“Привет!”);
starbar();
}
Вызов функции
Вызов функции
Слайд 19
Функции
Функции в Си
После выполнения программы:
***********************************************************************
Привет!
***********************************************************************
Слайд 20
Функции
Функции в Си
Как описать функцию с параметрами?
#include
void
starbar() {
…
}
void spaces(int n) {
int count;
for (count=1; count <=n; count++)
printf(“ ”);
printf(“\n”);
}
void main() {
starbar();
spaces(27); printf(“Привет!”);
starbar();
}
Функция с параметром
Вызов функции с параметром
Формальный параметр
Фактический параметр – константа
Слайд 21
Функции
Функции в Си
После выполнения программы:
***********************************************************************
Привет!
***********************************************************************
Слайд 22
Функции
Функции в Си
Как описать функцию с параметрами?
#include
void
starbar() { …
}
void spaces(int n) {
int count;
for (count=1; count <=n; count++)
printf(“ ”);
printf(“\n”);
}
void main() {
int space_num=27;
starbar();
spaces(space_num); printf(“Привет!”);
starbar();
}
Вызов функции с параметром
Фактический параметр – переменная
Формальный параметр
Слайд 23
Функции
Функции в Си
Как описать функцию с параметрами?
#include
void
starbar() { …
}
void spaces(int n) {
int count;
for (count=1; count <=n; count++)
printf(“ ”);
printf(“\n”);
}
void main() {
starbar();
spaces((60-7)/2); printf(“Привет!”);
starbar();
}
Вызов функции с параметром
Фактический параметр – выражение
Формальный параметр
Слайд 24
Функции
Функции в Си
Как описать функцию с несколькими параметрами?
#include
void starbar(int n, int m) {
int i, j;
for (i=1; i <=n; i++) {
for (j=1; j <=m; j++)
printf(“*”);
printf(“\n”);
}
}
void main() {
starbar(4,15);
}
Вызов функции с параметрами
Фактические параметры
Формальные параметры: перечисляются с указанием типа через запятую
Слайд 25
Функции
Функции в Си
После выполнения программы:
***************
***************
***************
***************
Слайд 26
Функции
Параметры функций
в заголовке функции перечисляются формальные параметры, они
обозначаются именами, поскольку могут меняться
при вызове функции в скобках
указывают фактические параметры (константы или выражения) в том же порядке
void tr( int x, int y, int c )
tr ( 200, 100, COLOR(255,0,0));
x
y
c
Функции в Си
Слайд 27
Функции
Параметры функций
для каждого формального параметра в заголовке функции
указывают его тип
внутри функции параметры используются так же, как
и прочие переменные
в функции можно объявлять дополнительные локальные переменные, остальные функции не имеют к ним доступа
void A ( int x, float y, char z ) { ... }
void A ( int x, float y, char z )
{
int a2, bbc = 345;
...
}
локальные переменные
int a2, bbc = 345;
Функции в Си
Слайд 28
Функции
Функции в Си
Функция как «черный ящик»
#include
void starbar()
{
int count;
…
}
void spaces(int n) {
int count;
…
}
void main() {
starbar();
spaces(27); printf(“Привет!”);
starbar();
}
Вход
y = f(x1,x2)
Выход
Вход
Выход – последовательность пробелов
Механизм скрыт от головной и прочих функций
Функция: внутренний механизм скрыт
Слайд 29
Функции
Функции в Си
Возвращаемое значение функции
#include
void starbar(int n,
int m) {
int i, j;
for (i=1; i
<=n; i++) {
for (j=1; j <=m; j++)
printf(“*”);
printf(“\n”);
}
}
void main() {
starbar(4,15);
}
void указывает на отсутствие возвращаемого значения
Слайд 30
Функции
Функции в Си
Возвращаемое значение функции
#include
double max(double a,
double b) {
if (a > b)
return a;
else
return b;
}
void main() {
double x=10.5, y=20;
printf(“max(%lf, %lf) = %lf\n”,
x, y, max(x,y));
}
При наличии возвращаемого значения нужно указать его тип
Выходная величина возвращается оператором return
После выполнения return функция прекращает свою работу
Слайд 31
Функции
Функции в Си
Возвращаемое значение функции
#include
void WritePositive(int a)
{
if (a < 0)
return;
printf(“%d”, a);
}
void main() {
int n= −10, p=100;
WritePositive(n);
WritePositive(p);
}
Функция без возвращаемого значения
Оператор return используется без аргумента
Выполнение return прекращает работу функции
Слайд 32
Функции
Функции в Си
После выполнения программы:
100
Слайд 33
Функции
Функции: резюме
Шаблон описания функции
(
есть>) {
}
В
определении можно опускать имена параметров (только типы)
До вызова функции – ее описание или определение
Если нет возвращаемого значения, <тип-результата> = void
Возврат результата и прекращение функции:
return <результат>; или
return;
Параметры передаются по значению
фактические параметры могут быть константами и выражениями
формальные параметры – локальные переменные
Шаблон определения функции
<тип-результата> <имя-функции> (<список параметров, если есть>);
Слайд 34
Функции
Как поменять местами?
2
3
1
Задача: поменять местами содержимое двух чашек.
Задача:
поменять местами содержимое двух ячеек памяти.
4
6
?
4
6
4
x
y
c
c = x;
x =
y;
y = c;
x = y;
y = x;
3
2
1
Слайд 35
Функции
Параметры, передаваемые по указателю
Задача: составить процедуру, которая меняет
местами значения двух переменных.
Особенности: надо, чтобы изменения, сделанные в
процедуре, стали известны вызывающей программе.
main()
{
int x = 1, y = 2;
swap ( x, y );
printf ( "x = %d, y = %d", x, y );
}
void swap ( int a, int b )
{
int c;
c = a; a = b; b = c;
}
эта процедура работает с копиями параметров
x = 1, y = 2
Слайд 36
Функции
Параметры, передаваемые по указателю
Применение:
таким образом функция может
возвращать несколько значений
Вызов:
swap ( 2, 3 );
// числа
swap ( x+z, y+2 ); // выражения
swap ( &x, &y ); // адреса переменных
void swap ( int * a, int * b )
{
int c;
c = *a; *a = *b; *b = c;
}
*
передаются не значения,
а адреса переменных
*
Слайд 37
Функции
Функции: пример 1
Задача: составить функцию, которая вычисляет наибольшее
из двух значений, и привести пример ее использования
Функция:
формальные параметры
int
Max ( int a, int b )
{
if ( a > b ) return a ;
else return b ;
}
return - вернуть результат функции
тип результата
Слайд 38
Функции
Функции: пример 2
Задача: составить функцию, которая определяет, верно
ли, что заданное число – простое.
Особенности:
ответ – логическое значение:
«да» (1) или «нет» (0)
результат функции можно использовать как логическую величину в условиях (if, while)
Алгоритм: считаем число делителей в интервале от 2 до N-1, если оно не равно нулю – число составное.
count = 0;
for (i = 2; i < N; i ++)
if ( N % i == 0) count ++;
if ( count == 0 )
// число N простое}
else // число N составное
Слайд 39
Функции
Функция: пример 2
int Prime ( int N )
{
int count = 0, i;
for (i =
2; i*i <= N; i++)
if (N % i == 0) count ++;
return (count == 0);
}
if (count == 0) return 1;
else return 0;
Слайд 40
Функции
Функции: пример 2
#include
main()
{
int N;
printf (
"Введите целое число\n" );
scanf ( "%d", &N );
if ( Prime( N ) )
printf ("%d - простое число", N);
else printf ("%d - составное число", N);
}
int Prime ( int N )
{
...
}
функция
Prime( N )
Слайд 41
Функции: что еще?
Игнорирование возвращаемого значения
Тип функции по умолчанию
Неопределенное
значение функции
Тип и аргументы функции main()
Функции с переменным числом
параметров
Слайд 42
Функции: что еще?
Функции: что еще?
При вызове функции можно
игнорировать возвращаемое значение, вызывая ее как процедуру
#include
int calc_and_print
(int a, int b) {
int c = a + b;
printf(“%d+%d=%d”, a, b, c);
return c;
}
void main() {
int z;
z=calc_and_print(4,15);
calc_and_print(z,33);
}
Вызов с сохранением значения
Вызов, игнорирующий
возвращаемое значение
Слайд 43
Функции: что еще?
Функции: что еще?
Если при описании функции
не указан тип возвращаемого значения, то подразумевается int
#include
calc_and_print
(int a, int b) {
int c = a + b;
printf(“%d+%d=%d”, a, b, c);
return c;
}
void main() {
int z;
z = calc_and_print(4,15) % 7;
}
int calc_and_print (int, int)
Слайд 44
Функции: что еще?
Функции: что еще?
Если при описании функции
не использован return для возврата значения, то значение функции
не определено
#include
int calc_and_print (int a, int b) {
int c = a + b;
printf(“%d+%d=%d”, a, b, c);
}
void main() {
int z;
z = calc_and_print(4,15);
printf(“%d”, z);
}
Нет return
В результате будет получен «мусор»
Слайд 45
Функции: что еще?
Функции: что еще?
Функция main() может иметь
тип int или void
Возвращаемое значение в main() – код
завершения процесса в ОС
0 – нет ошибок
>0 – код ошибки
#include
void main() {
int z=0xCAFE;
printf(“%d”, z);
}
#include
int main() {
int z=0xCAFE;
scanf(“%d”,&z);
if(z) {
printf(“%d”, z);
return 0;
}
else
return 255;
}
Код ошибки – 255
Слайд 46
Функции: что еще?
Функции: что еще?
Функция main() может иметь
параметры
int argc количество параметров командной строки
char *argv[] массив строк –
значений параметров
#include
void main(int argc, char *argv[]) {
for(int i=0; i}
c:\> my_prog.exe a.txt 10
0: C:\TEMP\my_prog.exe
1: a.txt
2: 10
argv[0] – всегда полный путь к исполняемому файлу
Слайд 47
Функции: что еще?
Функции: что еще?
Функции могут иметь переменное
количество параметров
#include
int sred_znach(int x,...) {
int
i=0, j=0, sum=0;
va_list uk_arg;
va_start(uk_arg,x); /*установка указателя uk_arg на */
/* первый необязательный параметр*/
if (x!=-1) sum=x; /*проверка на пустоту списка */
else return (0);
j++;
while ( (i=va_arg(uk_arg,int))!=-1) /* выборка очередного */
{ /* параметра и проверка*/
sum+=i; /* на конец списка */
j++;
}
va_end(uk_arg); /* закрытие списка параметров*/
return (sum/j);
}
int main() {
int n;
n=sred_znach(2,3,4,-1); /* вызов с четырьмя параметрами*/
printf("n=%d",n);
n=sred_znach(5,6,7,8,9,-1); /* вызов с шестью параметрами */
printf("n=%d",n); return (0);
}
Слайд 48
Функции и
структура программы
Программа из одного файла
Программа из
многих файлов
Области видимости переменных
Слайд 49
Функции и структура программы
Функции и структура программы
Функции в
одном файле
Слайд 50
Функции и структура программы
Функции и структура программы
Программа из
нескольких файлов
int mul(int a, int b) {
return a+b;
}
second.c
Слайд 51
Функции и структура программы
Области видимости переменных
Переменные доступны только
в той области видимости,
где они описаны (за исключением
описанных как static)
vars.c
Глобальная
область
видимости
Переменная локальна, область
видимости – тело функции
Переменная локальна, область
видимости – блок
Переменная yourVariable доступна внутри функции main()
Переменная hisVariable доступна только внутри блока { … }
Слайд 52
Рекурсивные функции
Рекурсия: в математике и программировании
Общий вид рекурсии
Задача
о ханойских башнях
Цена рекурсии
Слайд 53
Организация курса
Рекурсия в математике
Рекурсия – метод определения множества
объектов через себя, с использованием ранее заданных частных определений.
Факториал
n! = n×(n – 1)! при n>0 и n! = 1 при n=0
Числа Фибоначчи: F1 = F2 = 1, Fn = Fn– 1+Fn– 2, при n>2
Слайд 54
Рекурсивные функции
Рекурсия в программировании
Рекурсия – вызов функции из
нее самой напрямую или через другие функции
#include
long fact(long
n) {
if( n == 0 ) return 1;
else return n*fact(n-1);
}
void main() {
long N=5;
printf(“%d! = %d\n”, N, fact(N));
}
Функция вычисления факториала
В теле функции вызывается она сама
Слайд 55
Рекурсивные функции
Общий вид рекурсии
Если (простейший случай) тогда
Решить напрямую
Иначе
Делать рекурсивный вызов до появления простейшего
случая
Слайд 56
Рекурсивные функции
Задача о ханойских башнях
В одном буддийском монастыре
монахи уже тысячу лет занимаются перекладыванием колец. Они располагают
тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.
Слайд 57
Рекурсивные функции
Задача о ханойских башнях
Рекурсивное решение
Итак, нам необходимо
перенести n дисков со стержня (a) на стержень (c).
Если есть функция перенесения n –1 диска, тогда задача легко разрешима.
Вначале перенесем n –1 диск со стержня (a) на стержень (b)
Применяя рекурсивный вызов той же функции, затем перенесем n-ый диск со стержня (a) на стержень (c)
И, наконец, перенесем n –1 диск со стержня (b) на стержень (c).
Конец света
Слайд 58
Рекурсивные функции
Задача о ханойских башнях
Рекурсивное решение
void Step(int n,
char a, char b, char c)
// n
- количество колец;
// a, b, c - башни;
{
// т. к. на каждом шаге количество колец
// будет уменьшаться на один,
// это условие будет условием выхода из рекурсии
if (n <= 0) return;
Step(n-1, a, c, b);
printf("диск %d с %c на %c \n", n, a, b);
Step(n-1, c, b, a);
}
Слайд 59
Организация курса
Цена рекурсии
Использование рекурсии может сократить размер исходного
кода программы и сделать код более элегантным и понятным.
Однако рекурсия имеет и свои недостатки…
Слайд 60
Организация курса
Цена рекурсии
Пример – вычисление чисел Фибоначчи
long F(
int n )
{
if( n
return n;
else
return F( n - 1 ) + F( n - 2 );
}
F(3) вычисляется трижды!
Слайд 61
Организация курса
Цена рекурсии
При рекурсивном вызове функции запоминается ее
состояние, чтобы после окончания рекурсивного вызова можно было продолжить
ее вычисление
Состояние функции – совокупность значений всех локальных переменных функции
Значения локальных переменных запоминаются в стэке (специальной области памяти)
Стэк имеет ограниченный размер и не позволяет глубокие рекурсии
Слайд 62
Организация курса
Рекурсия
Рекурсия всегда(!) может быть заменена итеративным алгоритмом
При
использовании итеративного алгоритма, как правило, необходимо самостоятельно имитировать работу
стэка
