Билет 6. Метод барьера и различные варианты его применения.

Задача поиска – наиболее встречающаяся в программировании. Чтобы упростить поиск и избежать проверки конца области, в которой происходит поиск, придуман метод барьеров. Его идея заключается в том, что искомый элемент ставится в конец области поиска, что гарантирует наличие искомого элемента, а так же при его не нахождении выход из поиска. По тому, что искомый элемент находится в конце области поиска, можно определить, что элемент не найден.

Пример 1

Пусть мы ищем элемент в массиве из N элементов: int A[N], x, i=0; while (i<N && A[i]!=x) i++; if (A[i]==x) printf (“%d”, i);

Поиск прекращается при одном из двух условий: 1) Элемент найден. 2) Искомого элемента не существует. Здесь мы перебираем каждый элемент и увеличиваем показатель на 1. Единственный вариант упрощения такого линейного поиска – упростить условие цикла, состоящее из 2х условий.

Для этого нужно составить одно условие, из которого будут вытекать оба. В данном поиске это возможно если элемент Х будет гарантированно найден в массиве А. Это можно обеспечить, поместив Х в последний дополнительный элемент массива. Такой элемент называется барьером, т.к. он предотвращает выход поиска за границы массива. Новый код алгоритма линейного поиска с барьером будет выглядеть так: int A[N+1], x, i=0; while (A[i]!=x) i++;

Билет 7. Процедуры и функции в Си. Формальные и фактические. Входные и выходные параметры, локальные и глобальные переменные.

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

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

Подпрограмма(процедуры и функции) - это отдельная функционально независимая часть программы.

Подпрограммы решают три важные задачи:

-избавляют от необходимости многократно повторять в тексте программы аналогичные фрагменты;

-улучшают структуру программы, облегчая ее понимание;

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

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

Функция - это группа операторов у которой есть имя. Функции позволяют разбить программу на небольшие части, каждая из которых выполняет какую-то небольшую задачу. Определение функции должно располагаться в глобальной области видимости, до начала функции main. Тело функции располагается сразу под заголовком и заключено в фигурные скобки. В теле функции может содержаться сколько угодно операторов. Но обязательно должен присутствовать оператор return. Оператор return возвращает значение.

Процедура же - это функция которая ничего не возвращает, то есть тип её результата это void. вы не обязаны использовать оператор return, кроме того случая, когда нужно произвести выход из функции прежде, чем она выполнится целиком. В этом случае оператор return не имеет параметра, - ничего возвращать не нужно.

Функция отличается от процедуры двумя особенностями:

1. Она всегда вычисляет некоторое значение, возвращаемое в качестве результата функции;

2. И вызывается в выражениях.

По способу применения различают:

• фактический параметр — аргумент, используемый как значение (число, символ и т. д.);

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

Определяющим отличием формального от фактического параметра является доступ к самой переменной аргумента (обращение к памяти), в то время как фактический параметр его не имеет, так как копирует в оперативную память его значение, и пользуется именно им.

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

В заголовке подпрограммы содержится список формальных параметров с указанием их типа, которые условно можно разделить на входные и выходные.

По зоне видимости различают локальные и глобальные переменные. Первые доступны только конкретной подпрограмме, вторые — всей программе. Так вот, переменные, объявленные внутри функции, называются локальными. Локальные переменные имеют свои области видимости, этими областями являются функции, в которых объявлены переменные. Таким образом, в разных функциях можно использовать переменные с одинаковыми именами, что в свою очередь очень удобно. Разделение переменных на глобальные и локальные соответствует одному из главных правил программирования, а именно – принципу наименьших привилегий. То есть, переменные, объявленные внутри одной функции, должны быть доступны только для этой функции и ни чему другому, в конце концов, они создавались именно для этой функции. Глобальные переменные объявляются вне тела какой-либо функции, и поэтому область видимости таких переменных распространяется на всю программу. Обычно глобальные переменные объявляются перед главной функцией, но можно объявлять и после функции main(), но тогда данная переменная не будет доступна в функции main().