Глава 5 Функции

План 5.1Введение 5.2Программные модули на С 5.3Функции из математической библиотеки 5.4Функции 5.5Объявление функции 5.6Прототип функции 5.7Хедеры 5.8Вызов функции: по имени и по значению 5.9Случайные числа 5.10Пример: Игра «Шанс» 5.11Классы хранения 5.12Области видимости 5.13Рекурсия 5.14 Пример использования рекурсии: Числа Фибоначчи 5.15Рекурсии или Итерации

5.1Введение Разделяй и властвуй Разделяй и властвуй Собирай программу из маленьких кусочков или компонентов Собирай программу из маленьких кусочков или компонентов Эти кусочки называются «модуль» Эти кусочки называются «модуль» Каждый кусочек более управляемый чем оригинальная «большая» программа Каждый кусочек более управляемый чем оригинальная «большая» программа

5.2Программные модули на C Функции Функции Модули на C Модули на C Программа комбинирует написанные программистом и библиотечные функции Программа комбинирует написанные программистом и библиотечные функции Стандартная библиотека C содержит хороший набор функций Стандартная библиотека C содержит хороший набор функций Вызовы функций Вызовы функций Вызов функции Вызов функции Название функции и аргументы (данные) Название функции и аргументы (данные) Функции обеспечивают операции или манипуляции с данными Функции обеспечивают операции или манипуляции с данными Функции возвращают результат Функции возвращают результат

5.2Программные модули на C Аналог вызова функции: Аналог вызова функции: Босс просит сотрудника выполнить задачу Босс просит сотрудника выполнить задачу Сотрудник получает информацию, выполняет задачу, возвращает результат Сотрудник получает информацию, выполняет задачу, возвращает результат Скрытие лишнего: босс не вдается в детали Скрытие лишнего: босс не вдается в детали

5.3Функции из математической библиотеки Мат. функции Мат. функции Выполняют математические расчеты Выполняют математические расчеты #include #include Формат вызова функции Формат вызова функции Имя_функции( аргумент ); Имя_функции( аргумент ); Для нескольких аргументов, используется список, разделенных запятыми Для нескольких аргументов, используется список, разделенных запятыми printf( "%.2f", sqrt( ) ); printf( "%.2f", sqrt( ) ); Вызываем функцию sqrt, которая считает квадратный корень от аргумента Вызываем функцию sqrt, которая считает квадратный корень от аргумента Все результаты математических функций double Все результаты математических функций double Аргументы могут быть константами, переменными, или выражениями Аргументы могут быть константами, переменными, или выражениями

5.4Функции Функции Функции Модульность программы Модульность программы Все переменные, объявленные внутри функции являются локальными Все переменные, объявленные внутри функции являются локальными Локальная область видимости Локальная область видимости Параметры Параметры Обмен информации между функций Обмен информации между функций Локальные переменные Локальные переменные

5.4Функции Выгода от функций Выгода от функций Разделяй и властвуй Разделяй и властвуй Управляемая разработка программ Управляемая разработка программ Повторное использование Повторное использование Использование существующих функций как блоков для новой программы Использование существующих функций как блоков для новой программы Абстракция – спрятать внутреннюю «кухню» (библиотеки функций) Абстракция – спрятать внутреннюю «кухню» (библиотеки функций) Избежание повторения кода Избежание повторения кода

5.5Объявление функций Формат объявления функции Формат объявления функции Тип-возвращаемого-значения имя-функции ( список-параметров) { объявление и операторы } Имя-функции: любой корректный идентификатор Имя-функции: любой корректный идентификатор Тип-возвращаемого-значения: тип результата (по умолчанию int ) Тип-возвращаемого-значения: тип результата (по умолчанию int ) void – указывает что функция ничего не возвращает void – указывает что функция ничего не возвращает

5.5Объявление функций Формат объявления функции Формат объявления функции Тип-возвращаемого-значения имя-функции ( список-параметров) { объявление и операторы } Список-параметров: разделенный запятыми, объявляет параметры Список-параметров: разделенный запятыми, объявляет параметры Тип должен быть указан для каждого параметра, за исключением типа int Тип должен быть указан для каждого параметра, за исключением типа int

5.5Объявление функций Формат определения функции Формат определения функции тип-возвращаемого-значения имя-функции ( список-параметров) { определения и операторы } Определения и операторы: тело функции (блок) Определения и операторы: тело функции (блок) Переменные можно объявляться внутри блока (не обязательно) Переменные можно объявляться внутри блока (не обязательно) Функции не могут быть определены внутри другой функции Функции не могут быть определены внутри другой функции

5.5Объявление функций Формат определения функции Формат определения функции Возвращение управления Возвращение управления Если нечего возвращать Если нечего возвращать return; return; Или пока не достигнем правой скобки Или пока не достигнем правой скобки Если есть что вернуть Если есть что вернуть return выражение ; return выражение ;

Прототипфункции (3 параметра) Ввод данных ВызовфункцииОпределениефункцииРезультат 1/* Fig. 5.4: fig05_04.c 2 Finding the maximum of three integers */ 3#include 4 5int maximum( int, int, int ); /* function prototype */ 6 7int main() 8{8{ 9 int a, b, c; printf( "Enter three integers: " ); 12 scanf( "%d%d%d", &a, &b, &c ); 13 printf( "Maximum is: %d\n", maximum( a, b, c ) ); return 0; 16} 17 18/* Function maximum definition */ 19int maximum( int x, int y, int z ) 20{ 21 int max = x; if ( y > max ) 24 max = y; if ( z > max ) 27 max = z; return max; 30} Enter three integers: Maximum is: 85

5.6Прототипы функций Имя функции Имя функции Параметры – Что функция получает Параметры – Что функция получает Тип возвращаемого значения (по умолчанию int ) Тип возвращаемого значения (по умолчанию int ) Используется для валидации функций Используется для валидации функций Прототипы нужны только если вызов функции идет до ее определения Прототипы нужны только если вызов функции идет до ее определения Функция с прототипом Функция с прототипом int maximum( int, int, int ); Получает 3 int Получает 3 int Возвращает int Возвращает int ВНИМАНИЕ ВНИМАНИЕ Преобразование к меньшему по размеру типу может привести к ошибкам Преобразование к меньшему по размеру типу может привести к ошибкам

5.7Заголовочные файлы Заголовочные файлы Заголовочные файлы Содержит прототипы функций для библиотечных функций Содержит прототипы функций для библиотечных функций,, и т.д.,, и т.д. Загружается через директиву препроцессора Загружается через директиву препроцессора #include #include Персональные «хедеры» Персональные «хедеры» Создать файл с функциями Создать файл с функциями Сохранить как filename.h Сохранить как filename.h Загрузить как #include "filename.h" Загрузить как #include "filename.h" Использовать функции Использовать функции

5.8Вызов функций: параметры по значению и по ссылке Передача по значению Передача по значению Копии аргументов передаются функции Копии аргументов передаются функции Изменения внутри не меняет оригинал Изменения внутри не меняет оригинал Используется когда не нужно менять значение Используется когда не нужно менять значение Чтобы избежать нежелательных изменений Чтобы избежать нежелательных изменений Передача по ссылке Передача по ссылке Передает оригинальный аргумент Передает оригинальный аргумент Изменения внутри меняет оригинал Изменения внутри меняет оригинал Используется только с доверенными «trusted» функциями Используется только с доверенными «trusted» функциями Сосредоточимся на функциях «по значению» Сосредоточимся на функциях «по значению»

5.9Генерация случайных чисел Функция rand Функция rand Загрузим Загрузим Возвращает «случайное» число между 0 и RAND_MAX (по крайней мере ) Возвращает «случайное» число между 0 и RAND_MAX (по крайней мере ) i = rand(); Псевдорандомизация Псевдорандомизация Устанавливает последовательность «случайных» чисел Устанавливает последовательность «случайных» чисел Одна и та же последовательность для каждого вызова функции Одна и та же последовательность для каждого вызова функции

5.9Генерация случайных чисел Масштабирование Масштабирование Для получения числа между 1 и n Для получения числа между 1 и n 1 + ( rand() % n ) rand() % n возвращает число между 0 и n - 1 rand() % n возвращает число между 0 и n - 1 Добавим 1 чтобы сделать диапазон от 1 до n Добавим 1 чтобы сделать диапазон от 1 до n 1 + ( rand() % 6) Число от 1 до 6 Число от 1 до 6

5.9Генерация случайных чисел Функция srand Функция srand Получает целое и переходит на позицию в псевдопоследовательности Получает целое и переходит на позицию в псевдопоследовательности srand( seed ); srand( time( NULL ) ); //нужно загрузить srand( time( NULL ) ); //нужно загрузить time( NULL ) time( NULL ) Возвращает время когда программа была скомпилирована в секундах Возвращает время когда программа была скомпилирована в секундах Улучшает «случайность» Улучшает «случайность»

1. Инициализация 2. Ввод значения 2.1 Используем srand 2.2 Цикл 3. Генерируем и печатаем результат 1/* Fig. 5.9: fig05_09.c 2 Randomizing die-rolling program */ 3#include 4#include 5 6int main() 7{7{ 8 int i; 9 unsigned seed; printf( "Enter seed: " ); 12 scanf( "%u", &seed ); 13 srand( seed ); for ( i = 1; i

Результат Enter seed: Enter seed: Enter seed:

5.10 Пример: Игра «Шанс» Симулятор «кости» Симулятор «кости» Правила Правила Бросаем две кости Бросаем две кости 7 или 11 на первой, игрок выиграл 7 или 11 на первой, игрок выиграл 2, 3, или 12 на первой, игрок проиграл 2, 3, или 12 на первой, игрок проиграл 4, 5, 6, 8, 9, 10 – очки начисляются игроку 4, 5, 6, 8, 9, 10 – очки начисляются игроку Игрок набирает очки пока не выпадет 7 Игрок набирает очки пока не выпадет 7

1. rollDice прототип 1.1 Инициализация 1.2 вызов srand 2. Определим switch для наших условий 2.1 Цикл 1/* Fig. 5.10: fig05_10.c 2 Craps */ 3#include 4#include 5#include 6 7int rollDice( void ); 8 9int main() 10{ 11 int gameStatus, sum, myPoint; srand( time( NULL ) ); 14 sum = rollDice(); /* first roll of the dice */ switch ( sum ) { 17 case 7: case 11: /* win on first roll */ 18 gameStatus = 1; 19 break; 20 case 2: case 3: case 12: /* lose on first roll */ 21 gameStatus = 2; 22 break; 23 default: /* remember point */ 24 gameStatus = 0; 25 myPoint = sum; 26 printf( "Point is %d\n", myPoint ); 27 break; 28 } while ( gameStatus == 0 ) { /* keep rolling */ 31 sum = rollDice(); 32

2.2 Печатаем результат 2.3 Тело функции Результат 33 if ( sum == myPoint ) /* win by making point */ 34 gameStatus = 1; 35 else 36 if ( sum == 7 ) /* lose by rolling 7 */ 37 gameStatus = 2; 38 } if ( gameStatus == 1 ) 41 printf( "Player wins\n" ); 42 else 43 printf( "Player loses\n" ); return 0; 46} 47 48int rollDice( void ) 49{ 50 int die1, die2, workSum; die1 = 1 + ( rand() % 6 ); 53 die2 = 1 + ( rand() % 6 ); 54 workSum = die1 + die2; 55 printf( "Player rolled %d + %d = %d\n", die1, die2, workSum ); 56 return workSum; 57} Player rolled = 11 Player wins

Результат Player rolled = 12 Player loses Player rolled = 10 Point is 10 Player rolled = 6 Player rolled = 11 Player rolled = 6 Player rolled = 10 Player wins Player rolled = 4 Point is 4 Player rolled = 5 Player rolled = 9 Player rolled = 10 Player rolled = 9 Player rolled = 3 Player rolled = 7 Player loses

5.11 Классы хранения Спецификатор класса хранения Спецификатор класса хранения Длительность хранения – как долго объект существует в памяти Длительность хранения – как долго объект существует в памяти Область – где объект может быть доступен в программе Область – где объект может быть доступен в программе Связность – указывает файлы в которых известен идентификатор (Глава 14) Связность – указывает файлы в которых известен идентификатор (Глава 14)

5.11 Классы хранения Автоматическое сохранения Автоматическое сохранения Объект создается и уничтожается в рамках своего блока Объект создается и уничтожается в рамках своего блока auto : по умолчанию для локальных переменных auto : по умолчанию для локальных переменных auto double x, y; register : пытается разместить переменную в высокоскоростных регистрах register : пытается разместить переменную в высокоскоростных регистрах Можно использовать только для авто переменных Можно использовать только для авто переменных register int counter = 1;

5.11 Классы хранения Статическое хранение Статическое хранение Переменные существуют в течении всего времени исполнения программы Переменные существуют в течении всего времени исполнения программы По умолчанию равны 0 По умолчанию равны 0 static : локальные переменные, определенные в функциях. static : локальные переменные, определенные в функциях. Сохраняет значение до конца выполнения функции Сохраняет значение до конца выполнения функции Известны только в их собственной функции Известны только в их собственной функции extern : по умолчанию для глобальных переменных и функций extern : по умолчанию для глобальных переменных и функций Известны в любой функции Известны в любой функции

5.12 Области видимости Область файла Область файла Идентификаторы, определенные вне функции видны всем функциям Идентификаторы, определенные вне функции видны всем функциям Используется для глобальных переменных, определения функций, прототипов функций Используется для глобальных переменных, определения функций, прототипов функций Область функции Область функции Может быть получена только внутри тела функции Может быть получена только внутри тела функции Используется только для меток ( start:, case:, и т.д.) Используется только для меток ( start:, case:, и т.д.)

5.12 Области видимости Область блока Область блока Идентификатор объявляется внутри блока Идентификатор объявляется внутри блока Область видимости начинается с объявления и заканчивается правой скобкой Область видимости начинается с объявления и заканчивается правой скобкой Используется для переменных, параметров функции (локальных переменных функции) Используется для переменных, параметров функции (локальных переменных функции) Внешние блоки «спрятаны» от «внутренних» блоков если есть переменная с одинаковым именем Внешние блоки «спрятаны» от «внутренних» блоков если есть переменная с одинаковым именем Область прототипа функции Область прототипа функции Используется для идентификаторов в списке параметров Используется для идентификаторов в списке параметров

1. Прототипы функций 1.1 Инициализация 1.2 Инициализация локальных переменных 1.3 Инициализация локальных переменных в блоке 2. Вызов функций 3. Вывод результатов 1/* Fig. 5.12: fig05_12.c 2 A scoping example */ 3#include 4 5void a( void ); /* function prototype */ 6void b( void ); /* function prototype */ 7void c( void ); /* function prototype */ 8 9int x = 1; /* global variable */ 10 11int main() 12{ 13 int x = 5; /* local variable to main */ printf("local x in outer scope of main is %d\n", x ); { /* start new scope */ 18 int x = 7; printf( "local x in inner scope of main is %d\n", x ); 21 } /* end new scope */ printf( "local x in outer scope of main is %d\n", x ); a(); /* a has automatic local x */ 26 b(); /* b has static local x */ 27 c(); /* c uses global x */ 28 a(); /* a reinitializes automatic local x */ 29 b(); /* static local x retains its previous value */ 30 c(); /* global x also retains its value */

3.1 Определение функций printf( "local x in main is %d\n", x ); 33 return 0; 34} 35 36void a( void ) 37{ 38 int x = 25; /* initialized each time a is called */ printf( "\nlocal x in a is %d after entering a\n", x ); 41 ++x; 42 printf( "local x in a is %d before exiting a\n", x ); 43} 44 45void b( void ) 46{ 47 static int x = 50; /* static initialization only */ 48 /* first time b is called */ 49 printf( "\nlocal static x is %d on entering b\n", x ); 50 ++x; 51 printf( "local static x is %d on exiting b\n", x ); 52} 53 54void c( void ) 55{ 56 printf( "\nglobal x is %d on entering c\n", x ); 57 x *= 10; 58 printf( "global x is %d on exiting c\n", x ); 59}

Результат local x in outer scope of main is 5 local x in inner scope of main is 7 local x in outer scope of main is 5 local x in a is 25 after entering a local x in a is 26 before exiting a local static x is 50 on entering b local static x is 51 on exiting b global x is 1 on entering c global x is 10 on exiting c local x in a is 25 after entering a local x in a is 26 before exiting a local static x is 51 on entering b local static x is 52 on exiting b global x is 10 on entering c global x is 100 on exiting c local x in main is 5

5.13 Рекурсия Функции, которые вызывают сами себя Функции, которые вызывают сами себя Может решить только базовую задачу Может решить только базовую задачу Делят проблему на две Делят проблему на две Что они могут делать - делают Что они могут делать - делают Что не могут Что не могут Функция вызывает копию себя для решения проблемы, которую она решить не может Функция вызывает копию себя для решения проблемы, которую она решить не может В конце концов проблема решается В конце концов проблема решается

5.13 Рекурсия Пример: факториалы Пример: факториалы 5! = 5 * 4 * 3 * 2 * 1 5! = 5 * 4 * 3 * 2 * 1 Помните что Помните что 5! = 5 * 4! 5! = 5 * 4! 4! = 4 * 3!... 4! = 4 * 3!... Можно считать факториалы рекурсивно Можно считать факториалы рекурсивно Посчитаем ( 1! = 0! = 1 ), далее Посчитаем ( 1! = 0! = 1 ), далее 2! = 2 * 1! = 2 * 1 = 2; 2! = 2 * 1! = 2 * 1 = 2; 3! = 3 * 2! = 3 * 2 = 6; 3! = 3 * 2! = 3 * 2 = 6; … И т.д. И т.д.

5.14 Пример использования рекурсии: Числа Фибоначчи… Числа Фибоначчи: 0, 1, 1, 2, 3, 5, 8... Числа Фибоначчи: 0, 1, 1, 2, 3, 5, 8... Следующее равно сумме двух предыдущих Следующее равно сумме двух предыдущих Можно считать рекурсивно: Можно считать рекурсивно: fib( n ) = fib( n - 1 ) + fib( n – 2 ) fib( n ) = fib( n - 1 ) + fib( n – 2 ) Код для функции: Код для функции: long fibonacci( long n ) { if (n == 0 || n == 1) // типовой случай return n; return n;else return fibonacci( n - 1) + fibonacci( n – 2 ); return fibonacci( n - 1) + fibonacci( n – 2 );}

5.14 Пример использования рекурсии: Числа Фибоначчи… f( 3 ) f( 1 ) f( 2 ) f( 1 )f( 0 )return 1 return 0 return + +

1. Прототип функции 1.1 Инициализация переменных 2. Ввод целого 2.1 Вызов функции fibonacci 2.2 Печать результата 3. Определим рекурсию fibonacci Результат 1/* Fig. 5.15: fig05_15.c 2 Recursive fibonacci function */ 3#include 4 5long fibonacci( long ); 6 7int main() 8{8{ 9 long result, number; printf( "Enter an integer: " ); 12 scanf( "%ld", &number ); 13 result = fibonacci( number ); 14 printf( "Fibonacci( %ld ) = %ld\n", number, result ); 15 return 0; 16} 17 18/* Recursive definition of function fibonacci */ 19long fibonacci( long n ) 20{ 21 if ( n == 0 || n == 1 ) 22 return n; 23 else 24 return fibonacci( n - 1 ) + fibonacci( n - 2 ); 25} Enter an integer: 0 Fibonacci(0) = 0 Enter an integer: 1 Fibonacci(1) = 1

Результат Enter an integer: 2 Fibonacci(2) = 1 Enter an integer: 3 Fibonacci(3) = 2 Enter an integer: 4 Fibonacci(4) = 3 Enter an integer: 5 Fibonacci(5) = 5 Enter an integer: 6 Fibonacci(6) = 8 Enter an integer: 10 Fibonacci(10) = 55 Enter an integer: 20 Fibonacci(20) = 6765 Enter an integer: 30 Fibonacci(30) = Enter an integer: 35 Fibonacci(35) =

5.15 Задание Написать программу, подсчитывающую факториал/число Фибонначи, с печатью промежуточных значений Написать программу, подсчитывающую факториал/число Фибонначи, с печатью промежуточных значений Входные данные: Входные данные: Целое число от 0 до int_max Целое число от 0 до int_max Тип операции: 0 – Число Фибоначчи, 1- Факториал Тип операции: 0 – Число Фибоначчи, 1- Факториал Выходные данные: Выходные данные: Шаг 1: Считаем 0! = 1 Шаг 1: Считаем 0! = 1 Шаг 2: Считаем 1! = 1 Шаг 2: Считаем 1! = 1 … Сделать вариант с итерацией и с рекурсией Сделать вариант с итерацией и с рекурсией Сравнить скорость расчета :) Сравнить скорость расчета :)

5.15 Рекурсия и итерации Повторение Повторение Итерации: явный цикл Итерации: явный цикл Рекурсия: неоднократные вызовы функции Рекурсия: неоднократные вызовы функции Завершение Завершение Итерации: условие цикла не выполнено Итерации: условие цикла не выполнено Рекурсия: условие распознано Рекурсия: условие распознано Обе могут привести к бесконечным повторам Обе могут привести к бесконечным повторам Выбор между производительностью (итерации) и хорошей формой (рекурсии) Выбор между производительностью (итерации) и хорошей формой (рекурсии)