Структурное программирование. Описание. Достоинства и недостатки. Подходы.

Сутью структурного программирования является возможность разбиения программы на составляющие элементы. Идеи структурного программирования появились в начале 70-годов в компании IBM, в их разработке участвовали известные ученые Э. Дейкстра, Х. Милс, Э. Кнут, С. Хоор. Распространены две методики (стратегии) разработки программ, относящиеся к структурному программированию: программирование "сверху вниз" и программирование "снизу вверх".

Достоинства структурного программирования:

1) повышается надежность программ (благодаря хорошему структурированию при проектировании, программа легко поддается тестированию и не создает проблем при отладке);

2) повышается эффективность программ (структурирование программы позволяет легко находить и корректировать ошибки, а отдельные подпрограммы можно переделывать (модифицировать) независимо от других);

3) уменьшается время и стоимость программной разработки;

4) улучшается читабельность программ.

Главный недостаток структурного подхода заключается в следующем: процессы и данные существуют отдельно друг от друга (как в модели деятельности организации, так и в модели программной системы), причем проектирование ведется от процессов к данным. Таким образом, помимо функциональной декомпозиции, существует также структура данных, находящаяся на втором плане.

Теорема о структурном программировании:

Любую схему алгоритма можно представить в виде композиции вложенных блоков begin и end, условных операторов if, then, else, циклов с предусловием (while) и может быть дополнительных логических переменных (флагов).
Эта теорема была сформулирована итальянскими математиками К. Бомом и Дж. Якопини в 1966 году и говорит нам о том, как можно избежать использования оператора перехода goto.

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

Разветвляющие программы. Циклы и другие управляющие средства. Примеры.

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

1. Выполнение последовательности операторов.

2. Использование проверки истинности условия для выбора между различными возможными способами действия.

3. Выполнение определенной последовательности операторов до тех пор, пока некоторое условие истинно.

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

Цикл с предусловием — цикл, который выполняется пока истинно некоторое условие, указанное перед его началом. Это условие проверяется до выполнения тела цикла, поэтому тело может быть не выполнено ни разу (если условие с самого начала ложно). В большинстве процедурных языков программирования реализуется операторомwhile, отсюда его второе название — while-цикл. На языке Pascal цикл с предусловием имеет следующий вид:

На языке Си:

while(<условие>){ <тело цикла>}

Цикл с постусловием— цикл, в котором условие проверяется после выполнения тела цикла. Отсюда следует, что тело всегда выполняется хотя бы один раз. В языке Паскаль этот цикл реализует оператор repeat..until; в Си — do…while.
На языке Си:

do{ <тело цикла>}while(<условие продолжения цикла>)

Цикл со счётчиком — цикл, в котором некоторая переменная изменяет своё значение от заданного начального значения до конечного значения с некоторым шагом, и для каждого значения этой переменной тело цикла выполняется один раз. В большинстве процедурных языков программирования реализуется оператором for, в котором указывается счётчик (так называемая «переменная цикла»), требуемое количество проходов (или граничное значение счётчика) и, возможно, шаг, с которым изменяется счётчик.

for (int i=0; i<20; i++) {действие}

if, if-else и switch

Оператор break используется для выхода из оператора while, do, for, switch, непосредственно его содержащего.

Оператор continue служит для пропуска оставшейся части выполняемой итерации цикла, непосредственно его содержащего

Статическая память. Указатели. Примеры.

Указатель содержит адрес переменной (объекта), что дает возможность "косвенного" доступа к этой переменной (объекту) через указатель.

Когда за знаком & следует имя переменной, результатом операции является адрес указанной переменной.

Когда за знаком * следует указатель на переменную, результатом операции является величина, помещенная в ячейку с указанным адресом.

int x = 1, y = 2;

int *ptr; // объявили указатель на целую переменную

ptr = &x; // взяли адрес переменной х = 2

y = *ptr; // переменная у стала равной 1

*ptr = 0; // переменная х стала равной 0

Пример:

age = 105;

ptr =&age;/*указатель на age*/

val= *ptr;

Результатом выполнения этого фрагмента является присваивание значения 105 переменной val.

6 Динамическая память. Основные функции. Примеры

Динамическая память – это оперативная память компьютера, предоставляемая программе при ее работе.

Основу системы динамического распределения памяти в Си составляют библиотечные функции calloc(), malloc(), realloc() и free().

Рассмотрим прототипы этих функций.

1. Функцияcalloc()

calloc() – предназначена для выделения памяти под заданное количество объектов, каждый из которых имеет размер size байт, всего n ´ size байт. Возвращает указатель на первый байт выделенной область памяти.

void *calloc(size_t num, size_t size);

Функция malloc()

malloc() – предназначена для выделения непрерывной области памяти заданного размера, например, void * malloc(size_t size),

где size_t – тип результата операции sizeof, определяемый в различных объектах-заголовках

Функция realloc()

realloc() – предназначена для изменения размера динамически выделенной области, адресуемой указателем ptr, при этом размер области может как увеличиваться, так и уменьшаться:

void* realloc(void* ptr, size_t size);

где ptr – указатель на первоначальную область памяти, size – новый размер области памяти.

4. Функция free()

free() – предназначена для освобождения памяти, выделенной функциями malloc(),calloc(),realloc(). После выполнения функции освобожденная память может быть выделена вновь под другие данные:

void free(void* ptr);

где prt – указатель на область памяти, созданной только функциями динамического управления памятью malloc(),calloc(),realloc().

7 Функции. Основные определения. Примеры

Функция — это самостоятельная единица программы, спроектированная для реализации конкретной задачи.

Рекурсия — действие при котором функция вызывает сама себя.

Если некоторая задача выполняется только в одной программе, лучше оформить ее решение в виде функции

#include <stdio.h>

int hello_world();

int main() {

hello_world();

return(0);

}

void hello_world(){

printf("Hello, World!\n");

}

Классы памяти переменных.

Класс памяти переменной — понятие в некоторых языках программирования. Он определяет область видимости переменной, а также как долго переменная находится в памяти.

Каждая переменная имеет тип и принадлежит к некоторому классу памяти. Время жизни и область действия идентификатора определяются ассоциированным с ним классом памяти. Существуют четыре разновидности классов памяти:

• auto - автоматический - локальные идентификаторы, память для которых выделяется при входе в блок, т.е. составной оператор, и освобождается при выходе из блока. Слово auto является сокращением слова automatic.

• static - статический - локальные идентификаторы, существующие в процессе всех выполнений блока. В отличие от идентификаторов типа auto, для идентификаторов типа static память выделяется только один раз - в начале выполнения программы, и они существуют, пока программа выполняется.

• extern - внешний - идентификаторы, называемые внешними, external, используются для связи между функциями, в том числе независимо скомпилированными функциями, которые могут находиться в различных файлах. Память, ассоциированная с этими идентификаторами, является постоянной, однако ее содержимое может меняться. Эти идентификаторы описываются вне функции.

• register - регистровый - идентификаторы, подобные идентификаторам типа auto. Их значения, если это возможно, должны помещаться в регистрах машины для обеспечения быстрого доступа к данным.

Класс памяти можно не указывать, тогда действуют следующие умолчания:

· переменные, описанные внутри функции или блока, считаются локальными (auto)

· переменные, описанные вне всех функций, считаются внешними.

· функции считаются внешними.

Рекурсия. Классификация. Примеры.

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция Структурное программирование. Описание. Достоинства и недостатки. Подходы. - student2.ru вызывает функцию , а функция — функцию . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

Различают прямую и косвенную рекурсию. Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции. Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций. Все функции, входящие в цепочку, тоже считаются рекурсивными.

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

Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти.

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

int fact (int n) {

if (n == 0)

return 1;

else

return n * fact (n - 1);

}

Эта исходная функция fact() не имеет хвостовой рекурсии т. к. выполняется перемножение после рекурсивного вызова (умножение на n ). Для исключения рекурсии сначала приведем fact () к виду с хвостовой рекурсией, например

int fact (int n) {

return fact_w (1,n);

}

Вспомогательная функция fact_w () будет содержать хвостовую рекурсию. Ее программный код:

int fact_w (int r, int n) {

if (n == 0)

return r;

else

return fact(r*n,n-1);

}

В функции fact_w() хвостовая рекурсия присутствует в силу рекурсивного обращения только к самой функции в операторе return.

10. Символьные строки. Способы задания строк. Принципы обработки.