В. Ю. Наумов Введение в информатику
 Скачать 2.05 Mb.
|
|
ПРИМЕР Посчитать количество нулей в нижнем треугольнике матрицы. Способ с анализом условия на индексы (рис. 5.21): int k = 0; for (int i=0; i Способ с изменением границ циклов (рис. 5.22): int k = 0; for (int i=0; i j=0; j k ++ Рис. 5.21. Обработка нижнего треугольника с изменением границ циклов 166 if (A[i][j]==0) k++; Далее рассмотрим более сложную задачу на двумерные массивы. ПРИМЕР Заменить все нулевые элементы квадратной матрицы значением максимума среди элементов над побочной диагональю. вход: 4 2 8 9 3 0 0 1 6 7 8 0 5 3 2 0 A выход: 4 2 8 9 3 6 6 1 6 7 8 6 5 3 2 6 A Начало Ввод матрицы A Конец Поиск максимума Max над поб. диагональю A Вывод матрицы A после преобразования Вывод матрицы A до преобразования Замена нулей в матрице A на Max 1 2 3 4 5 6 i=0; i i=0; i Шаг 1-2 Ввод матрицы A Шаги 2-3 и 5-6 Вывод матрицы A а) б) в) Ввод n Рис. 5.22. Общая блок-схема с пошаговой детализацией отдельных действий 167 i=0; i j=0; j Max=A[i][j] Вывод Max Шаг 3-4 Поиск Max Рис. 5.23. Поиск максимума над побочной диагональю i=0; i A[i][j] = Max Шаг 4-5 Замена нулей Рис. 5.24. Замена нулей найденным максимумом 168 #include { // шаг 1-2: ввод матрицы int n,a[10][10]; cout<<”\nInput count of rows and columns”; cin< } //шаг 2-3: вывод матрицы до преобразования for (int i=0; i //шаг 3-4: поиск максимума int max=a[0][0]; for (int i=0; i //шаг 4-5: замена for (int i=0; i Стоит отметить, что помимо квадратных матриц достаточно часто используют другие, более экзотические их виды. Это, например, треугольные (т. е. такие матрицы, у которых число элементов в строке/столбце зависит от того, в каком столбце/строке оно содержится). Есть еще разреженные матрицы, т. е. такие, у которых не все ячейки заполнены элементами и т. д. 169 Среди прочего может быть интересен алгоритм для решения такой задачи (хотя он и не относится к квадратным матрицам): ПРИМЕР Удалить из матрицы строку и столбец, содержащие максимум всей матрицы. Вот что требуется сделать: вход : 1 2 3 4 5 6 7 8 9 2, , 10 11 12 13 14 4; 15 16 17 18 19 30 Imax = Jmax = выход: 1 2 3 5 10 11 12 14 15 16 17 19 Блок-схема алгоритма без программной реализации показана на рис. 5.26. Здесь не приводится стандартный поиск максимума. Считается, что координаты максимума Imax и Jmax были найдены ранее. i=0; i 1 j=0; j 1 Рис. 5.25. Удаление строки и столбца из матрицы 170 5.5. Матрицы и динамическая память Как говорилось ранее, матрица – это массив, элементами которого служат массивы. Например, массив с описанием int a[4][5] – это массив из 4 указателей типа int*, которые содержат адреса одномерных массивов из 5 целых элементов (см. рис. 5.27). 0 Элементы типа *int 1 2 int ** a→ 3 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 *(a+0) – адрес строки массива с номером 0 Рис. 5.267. Представление матрицы с помощью указателей Инициализация многомерных массивов выполняется аналогично одномерным массивам. ПРИМЕР //проинициализированы все элементы массива int a[3][4] = {{11,22,33,44},{55,66,77,88},{99,110,120,130}}; //проинициализированы первые элементы каждой строки int b[3][4] = {{1},{2},{3}}; //проинициализированы все элементы массива int c[3][2]={1,2,3,4,5,6}; Доступ к элементам многомерных массивов возможен не только с помощью индексированных переменных, но и с помощью указателей: a[1][1] – доступ с помощью индексированных переменных, *(*(a+1)+1) – доступ к этому же элементу с помощью указателей. 171 При работе с матрицами с использованием динамической памяти есть несколько вариантов их описания. 1) Описание указателя на массив из 4 элементов типа int int (*la)[4]; выделение динамической памяти на четыре массива по два элемента lа=new[2][4]; 2) Еще один способ выделения памяти под двумерный массив int**matr=(int**)new int[5][10]; 2) С использованием цикла. Описываем указатель на матрицу. int **matr; выделяем память под массив указателей int* их n элементов matr=new int*[4]; выделяем память под строки массива for(int i=0;i<4;i++) matr[i]=new int[6]; Освобождение выделенной динамической памяти происходит подобным образом. Сначала в цикле очищается память, выделенная для строк, затем освобождается сам указатель на матрицу. for(int i=0;i 172 6. ФУНКЦИИ 6.1. Иерархия. Черный ящик. Функция Сознание человека устроено таким образом, что восприятие окружающей действительности происходит по принципам подобия. Это значит, например, что научившись некоторым базовым операциям, мы впоследствии опираемся на полученный опыт, пытаясь применить его к новой ситуации. Человек воспринимает мир иерархически. Отчасти это связано с особенностью способности мыслить методами формальной логики используя язык, с помощью которого человек общается с другими людьми. Законы иерархии предполагают наличие в воспринимаемом объекте различных уровней с четкими законами подчинения. Именно по законам иерархии наиболее часто строятся схемы управления людскими коллективами, т. е. такие схемы, которые предполагают наличие начальника сверху, нескольких начальников чуть ниже, подчиняющихся главному. У каждого из них, соответственно, есть свои подчиненные и т. д. (рис. 6.1). Одна из самых жестких систем такого типа – это система военной субординации. Важным свойством систем, подобных изображенной на рис. 6.1, является самоподобие. Самоподобие позволяет для задания экземпляра системы описать лишь порядок взаимодействия между родительским и подчиненным модулем, а далее эти свойства распространить на все урони иерархии. Программирование, как известно, тоже является средством управления. Только здесь в качестве подчиненных выступают не люди, а информация. Иерархия при программировании строится по схеме, аналогичной рис. 6.1. Следует обратить внимание на отсутствие связей между блоками на одном иерархическом уровне. 173 Еще одним важным понятием на пути к определению подпрограмм является понятие черного ящика. Кибернетический черный ящик – такое средство обработки информации, которое скрывает структуру своего внутреннего устройства от окружающих его объектов, не являющихся непосредственно подчиненными ему. Все, что известно про черный ящик управляющему модулю – это как правильно подать входную и забрать обработанную информацию. Если рассматривать схему на рис. 6.1, то главный модуль ничего не будет знать об устройстве своих подчиненных модулей A, B и C (и уж, естественно, про A1, A2, A3, B1, B2, C1, C2). Более того, он даже не будет знать об их существовании. Далее, например, модуль A будет находиться в неведении относительно устройства A1, A2, A3, он будет знать только о факте их существования. Про соседние B, B1, B2 и C, C1, C2 ему ничего не будет известно. При таких существенных ограничениях, накладываемых на модули, возникает резонный вопрос о методах их взаимодействия между собой. Главный модуль Модуль A Модуль B Модуль C Модуль A1 Модуль A2 Модуль A3 Модуль B1 Модуль B2 Модуль C1 Модуль C2 Первый уровень Второй уровень Третий уровень Рис. 6.1. Иерархическая организация Черный ящик X 1 X 2 X N-1 X N Y 1 Y 2 Y M вход выход Рис. 6.2. Черный ящик 174 Для взаимодействия пары модулей, находящихся на соседних уровнях иерархии, существует так называемый интерфейс. Интерфейс – набор правил, позволяющих организовать взаимодействие между парой систем. Нужно иметь в виду, что правила взаимодействия между системами могут быть не только алгоритмическими, но выраженными в иной материальной или нематериальной форме. Чаще всего это некоторая условная конструкция и протокол ее работы 17 Достаточно распространенной практикой является выделение в информационных потоках интерфейса входных данных и данных на выходе. Иногда черный ящик называют системой типа «вход-выход»; в этом случае его изображение может быть таким, как на рис. 6.2. Множество X называют входом черного ящика, а множество Y – его выходом. Две системы называют согласованными по интерфейсу, если выходы первой можно совместить со входами второй. При программировании можно столкнуться с ситуацией, когда одни и те же действия необходимо производить несколько раз над однотипными объектами. Например, ввести две матрицы и найти в них максимальный элемент. Для того, чтобы не писать один и тот же алгоритм несколько раз, используют функции. Функция – это снабженный заголовком внутренний программный блок, расположенный в разделе описаний внешнего программного блока или программы. Назначение функций – изменение внешней по отношению к ним программной обстановки. Функция описывается один раз и может быть затем неоднократно вызвана в разделе операторов программы или другой подпрограммы. 17 Простыми примерами такой конструкции могут быть интерфейсы USB в компьютере, интерфейсы силовой сети зданий (вилка и розетка + протокол (синусоидальное напряжение 50 Гц со среднеквадратичным значением 220 В)) и т.д. 175 Вызов функции (т. е. ее реальное использование) приводит к выполнению входящих в нее операторов. После их выполнения работа программы продолжается с оператора, который следует непосредственно за вызовом функции, в вызывающем блоке. При вызове функция может получать исходные данные от вызывающего блока и, при необходимости, возвращать ему результат работы. В С++ функции бывают двух видов: возращающие void и не void. Разница между ними достаточно условна 18 . Суть этой разницы сводится к различию методов работы с ними. Использование функций позволяет вывести процесс программирования на качественно иной уровень. Так как функции, по сути, являются независимыми блоками, то их разработку можно вести последовательно, шаг за шагом. Более того, различные участки кода, объединенные в общие библиотеки, можно поручать разным программистам. Это позволяет более четко выделить сферы ответственности и разбить процесс программирования по времени и степени сложности. Кроме того, выделив в функции многократно повторяющиеся действия, можно получить существенное сокращение программного текста, чем достигается более высокая наглядность и меньшая загруженность памяти ЭВМ. 18 Например, в Pascal функции, возвращающие void называются процедурами, но принцип работы у них одинаковый. Рис. 6.3. Графическое обозначение блока вызова функции 176 Функции, являясь алгоритмами, написанными пользователем языка программирования С++ и имеющими уникальное имя на своем уровне иерархии в программе, на блок-схемах изображаются блоком предопределенного процесса, имеющего вид рис. 6.3. 6.2. Функции в языке С++ Использование функций вносит иерархическую зависимость в алгоритм решения задачи, т. е. одна часть программы подчиняется другой; также соблюдается принцип вложенности, то есть любой блок может содержать внутренние блоки. Также, как и переменные функции должны быть описаны до их использования. Обычно функции описываются перед функцией main(), а затем в ней используются. Для того, чтобы описать функцию нужно указать тип возвращаемого значения, имя функции, список аргументов и их типы. <тип> <имя> (<список формальных параметров>) { <тело функции> } имя – идентификатор пользователя, используемый затем для ее вызова; список формальных параметров – набор параметров, состоящий для функции, как правило, только из входных переменных. Для каждого формального параметра указывается его тип и способ передачи. Результат работы функции возвращается в вызывающий модуль через ее имя. Тип результата указывается в заголовке. Чтобы вернуть результат, необходимо чтобы в разделе операторов (теле) функции присутствовал оператор return. 177 Пример описания функции может быть таким: float Summa(int a, float b, int c) { … } Тело функции, реализующее ее алгоритм, называется определением функции. Если в программе описывается большое количество функций это может затруднить ее чтение, поэтому в таких программах применяют упреждающее описание или выноят определение функций в заголовочные файлы. При упреждающем описании указывается тип возвращаемого значения, имя функции и типы аргументов, после чего ставится точка с запятой (при определении функции ее описание точкой с запятой не закрывается), а определяется функция за функцией main(). Как отмечалось выше, в языке С++ можно условно выделить два вида функций: функции возращающие void и не void. Функция возвращающая не void – реализует некоторый алгоритм, результатом которого является формирование некоторого единственного значения. Обращение к функции происходит через ее имя. Функция всегда возвращает, как минимум, один параметр, причем возвращение параметра происходит через операцию return. Такие функции очень похожи на математические и обычно используются для вычисления чего-либо. Необходимо помнить, что любой вариант завершения алгоритма функции должен заканчиваться возвращением значения. После обработки оператора return происходит выход из функции и последующие операторы не обрабатываются. Стандартные функции языка С++ библиотеки math.h представляют собой некоторый алгоритм, реализующий последовательность действий с максимальной оптимальностью. Так, например, арифметико-логическое устройство микропроцессора не может напрямую реализовать вычисление функции sin, потому, на первом этапе sin раскладывается в ряд, что позволяет, используя только базовые арифметические операторы (+, –, *, / ), вычислять сложные 178 тригонометрические функции. Естественно, что не нужно заботиться о программировании этих рядов, поскольку, в виду частоты использования, их уже описали авторы базовых библиотек C++. Потому работа с этими функциями достаточно проста. Однако, если бы в базовый набор не был встроен sin, то, вспомнив, что разложение синуса в ряд имеет вид: ! 9 ! 7 ! 5 ! 3 ) sin( 9 7 5 3 x x x x x x можно было бы написать функцию: float sin1(float x) { float S=x; int f=1, i=2; float xx=x; while (i<20) { f=f*i*(i+1); xx=xx*x*x; if (i % 4 == 0) S=S+xx/f; //добавл. в сумму неч. члена с плюсом else S=S-xx/f; //добавл. в сумму неч. члена с минусом i=i+2; } return S; } Здесь для простоты понимания принципа работы функции мы ограничились двадцатой степенью переменной. Кроме того, здесь учтено, что период повтора знака у членов равен четырем (четные члены в сумму не включаются, однако используются для вычисления нечетных). Далее рассмотрим порядок обращения к функциям, или, как принято говорить, «вызов». Совершенно естественной выглядит запись обращения: y=sin(x); z=exp(y); в то время как такая запись бессмысленна: sin(x) = y; (! не верно!) exp(y) = z; (! не верно!) 179 Синтаксис C++ не допускает подобных общений. Всегда имя функции ставится справа от операции присваивания. Что касается вызова функции, то стоит сказать, что он не является отдельным оператором и может быть использован: – только в выражениях, правой части оператора присваивания; – в составе булевского выражения; – в списке вывода операции cout<<; – в списке фактических параметров любой функции, если только способ их передачи позволяет это 19 ПРИМЕР float x=1.2, y=2.3, a=1, b=2, c=3,d=4; float S=Summa(a,x,b) + Summa(c,y,d); или так: if (Summa(a,x,b) > Summa(c,y,d)) { cout<<”\n The first sum is greater then the second sum”; } Описание функции поиска положительных элементов в двумерном массиве может быть таким: int summa(int x[10][15], int n, int m) { int s=0; for (int i=0; i } Блок-схема алгоритма этой функции показана на рис. 6.4. Необходимо отметить, что обычно функции применяются для выполнения каких-либо математических вычислений, в результате которых получается одно число. Если в результате работы функции 19 Подробнее о способах передачи будет рассказано ниже. |