Функциональная декомпозиция программы

Функциональная декомпозиция программы Курс «Разработка ПО систем управления» Кафедра управления и информатики НИУ «МЭИ» Осенний семестр 2017 г. Декомпозиция Деление сложного на простые части. ▪ Физическая — разделение кода по файлам. • Упрощение редактирования, навигации, контроля версий. • Ускорение сборки: пересобирать только измененные файлы. ▪ Процедурная — выделение в коде функций. • Упрощение восприятия кода. • Повторное использование. • Защита от ошибок: в компактной функции сложнее запутаться. ▪ Модульная — выделение в программе подсистем и их интерфейсов. • Управление сложностью: не важно, как реализовано, — важно, как с этим работать обращаться. • Тестирование части программы в изоляции от других. Осень 2017 г. © кафедра УиИ НИУ «МЭИ» 2 Определение функции Тип возвращаемого значения. Имя функции. double area ( double width, Параметры и их типы. • Тип указывается каждому! double height ) тело функции { Возврат значения и выход из функции. return width * height; } double S = area ( 4, 5 ); // S == 20 area ( 3, 2 ); Осень 2017 г. © кафедра УиИ НИУ «МЭИ» // 6 (игнорируется) 3 Пример функции на C++ int find(vector where, string what) { for (int i = 0; i < where . size(); ++i) { if (where[ i ] == what) return i; Результат: значение i при выполнении return. } return -1; } Результат: –1. Осень 2017 г. © кафедра УиИ НИУ «МЭИ» 4 Оператор return • Оператор return X: • указывает, что возвращаемое значение — X; • производит выход из функции. • Если тип возвращаемого значения — void, функция ничего не возвращает (return;). • Не-void функции обязаны вернуть значение. • Иначе — не ошибка, но опасное предупреждение! Осень 2017 г. © кафедра УиИ НИУ «МЭИ» 5 Объявление и определение double get_mean ( vector xs ); int main() { vector data { 1, 2, 3, 4, 5 }; cout << "Mean is " << get_mean(data); } double get_mean ( vector xs ) { double mean = 0; for (double x : xs) { mean += x; } return mean / xs . size(); } Осень 2017 г. © кафедра УиИ НИУ «МЭИ» Объявление функции (прототип). Благодаря объявлению, компилятор уже «знает», что такая функция есть. Определение функции. 6 Рекурсия • Вызов функцией самой себя. • Для случаев, когда задача часть решения такая же задача с другими условиями путь(от Новокосино до Авиамоторной) = «Новокосино — Новогиреево» + путь(от Новогиреево до Авиамоторной) Осень 2017 г. © кафедра УиИ НИУ «МЭИ» 7 Рекурсивный вызов power ( 2, 3 ); // 23 = 𝑎 ∙ 𝑎𝑛−1 , 𝑛 > 0 𝑓 𝑎, 𝑛 = 𝑎 = ൤ = 1, 𝑛=0 8 double power ( 2, 3) { if (3 == 0) return 1; return 2 * power ( 2, 3 − 1 ); } 𝑛 𝑎 ∙ 𝑓(𝑎, 𝑛 − 1), =ቈ 1, условие окончания 4 double power ( 2, 2) { if (2 == 0) return 1; return 2 * power ( 2, 2 − 1 ); } 2 double power ( 2, 1) { if (1 == 0) return 1; return 2 * power ( 2, 1 − 1 ); } 1 Осень 2017 г. 𝑛>0 𝑛=0 double power (double a, int n) { if (n == 0) return 1; return a * power ( a, n − 1 ); } double power ( 2, 0) { if (0 == 0) return 1; return 2 * power ( 2, 0 − 1 ); } © кафедра УиИ НИУ «МЭИ» 8 Рекурсия (продолжение)  Вызов функции расходует часть ограниченной области памяти — стека. ▪ Этот расход возвращается по выходе из функции. ▪ Глубокая рекурсия сильно расходует стек. • Бесконечная рекурсия невозможна. • Ошибка: «Stack overflow» («переполнение стека»).  Прямая рекурсия Косвенная рекурсия power() При косвенной рекурсии одну из функций нужно объявить перед определением другой. Осень 2017 г. ! bool is_even ( unsigned int n ) { return n == 0 | | is_odd ( n – 1); } bool is_odd ( unsigned int n ) { return n != 0 && is_even ( n – 1); } © кафедра УиИ НИУ «МЭИ» 9 Структуры • Тип данных, хранящий несколько именованных значений разных типов. • struct Temperature { double value; пользовательский char scale; тип данных }; переменная этого типа data . scale … • Temperature data; data . value = 273.15; data . scale = 'K'; cin >> data . value >> data . scale; cout << data . value – 273.15 << 'C'; Осень 2017 г. © кафедра УиИ НИУ «МЭИ» … data . value data 10 Как вернуть два значения? vector< double > (выборка) double (среднее) get_statistics() double (оценка дисперсии) void get_statistics( vector samples, double mean, double variance) { mean = 42; // Для пробы достаточно. variance = 43; } double mean = 0, variance = 0; get_statistics(…, mean, variance); // mean == 0, variance == 0 Осень 2017 г. Аргументы — копии переданного. Изменение копии не влияет на оригинал. © кафедра УиИ НИУ «МЭИ» 11 Параметр-указатель void get_statistics( vector samples, Проверка, передана ли double* mean, double* variance) переменная или nullptr. { double mx = …; Вместо ненужной if (mean) выходной переменной. *mean = mx; if (variance) { // Расчет дисперсии. vector data { … }; } double mean; } get_statistics(data, &mean, nullptr); Видно, что mean может измениться. Осень 2017 г. © кафедра УиИ НИУ «МЭИ» 12 Что такое указатель? Все данные хранятся в памяти. Переменная — именованная область памяти. Можно считывать и записывать значения переменных. Память — массив нумерованных ячеек-байт. У переменных есть адреса. Имея адрес ячейки, можно работать с её значением. 1) Как получить адрес? 2) Как хранить адрес? Номер называется адресом. Осень 2017 г. Как? … Память: Адреса: © кафедра УиИ НИУ «МЭИ» 8 13 Указатели • Это переменные, содержащие адрес памяти. • Указатель pointer: • • pointer — адрес; *pointer — значение по адресу (разыменование). • Переменная mean (не указатель): • mean — значение; • &mean — адрес (взятие адреса). • nullptr == NULL == 0: • нулевой указатель; • значение по нему получить нельзя. Осень 2017 г. © кафедра УиИ НИУ «МЭИ» 14 Указатель как тип данных Звездочка перед переменной. ! double x = 42; double * unknown; double* pointer = &x; Указатель на double: • может хранить адрес double • и только double; • разыменование дает double. *pointer … … &x x = *pointer; Осень 2017 г. До присваивания значения указывает неизвестно куда. © кафедра УиИ НИУ «МЭИ» 15 Указатели и неизменяемость Можно создать указатель, по которому можно прочитать данные, но нельзя их изменить. — Зачем? — При передаче параметров создаются копии. • • Это может быть вычислительно сложно (например, аргумент занимает много памяти). Это может быть невозможно (например, аргумент — открытый файл). • Обычный указатель: *pointer = 0; pointer = nullptr; int * p; • Указатель на неизменяемое значение: *pointer_to_const = 0; pointer_to_const = nullptr; Осень 2017 г. © кафедра УиИ НИУ «МЭИ» const int * pc; 16 Передача параметра по константной ссылке • Ссылка — новое имя для ячейки памяти (переменной, элемента массива и т. п.) • В отличие от указателя, сама ссылка ничего не хранит (ее значение — значение того, на что она ссылается). • Для ссылок нет разыменования. • Адрес ссылки == адресу того, на что она ссылается. • По константной ссылке изменить значение нельзя. • Не единственное, но типичное использование ссылок — избежать копирования: double get_mean ( & при объявлении ссылки const vector & data) и & для взятия адреса не связаны никак! Осень 2017 г. {…} © кафедра УиИ НИУ «МЭИ» 17 Какими должны быть функции? int square(int x) { return x * x; } ✓ Одна задача; ✓ ничего лишнего; ✓ полезна широко. int square(int* x, int* count) { cout << "Enter element #" << *count << ": "; cin >> *x; Задачи: (*count)++; 1) ввод и вывод, return (*x) * (*x); • а если не нужны? } 2) подсчет; • зачем? 3) возведение в квадрат. 1) Повторно используемыми (reusable). • Решать одну задачу. • Не иметь побочных эффектов (т. н. чистые функции): • зависеть только от входных данных (не от ввода, времени и т. п.); • выдавать результат только возвращаемым и выходными значениями (см. далее). Осень 2017 г. © кафедра УиИ НИУ «МЭИ» 18 Какими должны быть функции? 2) Могут обозначать логику работы программы. «Как съесть слона? — По кусочкам!» Расчет корреляции 𝒙 и 𝒚: vector < double > input ( unsigned int how_many ) 1) ввести 𝑁, 𝑥, Ԧ 𝑦; Ԧ { return { }; } 2) вычислить 𝑚𝑥 и 𝑚𝑦 ; double get_mean ( const vector & data) 3) вычислить 𝑠𝑥 и 𝑠𝑦 ; { return 0; } 4) 𝑆 = σ𝑁−1 𝑖=0 (𝑥𝑖 − 𝑚𝑥 )(𝑦𝑖 − 𝑚𝑦 ); 5) 𝑐𝑜𝑣 𝑥, 𝑦 = 𝑆Τ𝑁−1; 6) 𝑟𝑥𝑦 = Осень 2017 г. 𝑐𝑜𝑣(𝑥,𝑦) . 𝑠𝑥 𝑠𝑦 Цикл? double get_stdev ( const vector & data, double mean) { return 0; } © кафедра УиИ НИУ «МЭИ» 19 Декомпозиция Расчет корреляции 𝒙 и 𝒚: unsigned int N; 1) cin >> N; vector < double > x = input ( N ); vector < double > y = input ( N ); 2) double m_x = get_mean ( x ); double m_y = get_mean ( y ); 3) double s_x = get_stdev ( x, m_x ); double s_y = get_stdev ( y, m_y ); 4) double sum = 0; for (unsigned int i = 0; i < N; ++i) { sum += (x [ i ] – m_x) * (y [ i ] – m_y); } 1) ввести 𝑁, 𝑥, Ԧ 𝑦; Ԧ 2) вычислить 𝑚𝑥 и 𝑚𝑦 ; 3) вычислить 𝑠𝑥 и 𝑠𝑦 ; 4) 𝑆 = σ𝑁−1 𝑖=0 (𝑥𝑖 − 𝑚𝑥 )(𝑦𝑖 − 𝑚𝑦 ); 5) 𝑐𝑜𝑣 𝑥, 𝑦 = 𝑆Τ𝑁−1; 6) 𝑟𝑥𝑦 = 𝑐𝑜𝑣(𝑥,𝑦) . 𝑠𝑥 𝑠𝑦 5) double covariance = sum / (N – 1); 6) double correlation = covariance / ( s_x * s_y ); Осень 2017 г. © кафедра УиИ НИУ «МЭИ» 20 Литература к лекции ▪ Programming Principles and Practices Using C++: • глава 4, раздел 4.5 — функции; • глава 6, раздел 6.5 — декомпозиция; • глава 8 (пункт 8.5.8 — опционально); • пункт 9.4.1 — структуры; • упражнения к главам 4 и 8. ▪ C++ Primer: • глава 2, раздел 2.3 — указатели, ссылки; • глава 6 — функции; • упражнения. Осень 2017 г. © кафедра УиИ НИУ «МЭИ» 21