Информатика (группы АВТ-х12, АВТ-х13, АВТ-х14) — Теоретические материалы

Информация и информатика

Все процессы в природе сопровождаются сигналами. Зарегистрированные сигналы образуют данные. Данные преобразуются, транспортируются и потребляются с помощью методов. При взаимодействии данных и адекватных им методов образуется информация. Информация – это динамический объект, образующийся в ходе информационного процесса. Он отражает диалектическую связь между объективными данными и субъективными методами. Свойства информации зависят как от свойств данных, так и от свойств методов.  Информация – это продукт взаимодействия данных и  адекватных им методов.

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

В структуре возможных операций с данными можно выделить следующие:

• Сбор данных – накопление информации с целью обеспечения достаточной полноты для принятия решений.
• Формализация данных – приведение данных, поступающих из разных источников, к одинаковой форме, чтобы сделать их сопоставимыми между собой, то есть повысить их уровень доступности.
• Фильтрация данных – отсеивание «лишних» данных, в которых нет необходимости для принятия решений; при этом должен уменьшаться уровень «шума», а достоверность и адекватность данных должна возрастать.
• Сортировка данных – упорядочение данных по заданному признаку с целью удобства использования; повышает доступность информации.
• Архивация данных – организация хранения данных в удобной и легкодоступной форме; служит для снижения экономических затрат по хранению данных и повышает общую надежность информационного процесса в целом.
• Защита данных – комплекс мер, направленных на предотвращение утраты, воспроизведения и модификации данных.
• Транспортировка данных – прием и передача данных между удаленными участниками информационного процесса (клиент - сервер).
• Преобразование данных – перевод данных из одной формы в другую. Преобразование данных часто связано с изменением типа носителя.

Резюме: работа с информацией может иметь огромную трудоемкость, и её надо автоматизировать.

Информатика – это техническая наука, систематизирующая приемы создания, хранения, воспроизведения, обработки и передачи данных средствами ВТ, а также принципы функционирования этих средств и методов управления ими.

Предмет информатики составляют следующие понятия:

• Аппаратное обеспечение средств ВТ.
• Программное обеспечение средств ВТ.
• Средства взаимодействия аппаратного и программного обеспечения.
• Средства взаимодействия человека с аппаратными и программными средствами.

Особое внимание в информатике уделяется вопросам взаимодействия. Для  этого есть специальное понятие – интерфейс. Методы и средства взаимодействия человека с аппаратными и программными средствами называют пользовательским интерфейсом. Соответственно, существуют аппаратные интерфейсы, программные интерфейсы и аппаратно-программные интерфейсы.

Основной задачей информатики является систематизация приемов и методов работы с аппаратными и программными средствами ВТ. Цель систематизации состоит в выделении, внедрении и развитии передовых, наиболее эффективных технологий, в автоматизации этапов работы с данными, а также в методическом обеспечении новых технологических исследований.

Информатика – это практическая наука. Её достижения должны проходить подтверждение практикой и приниматься в тех случаях, когда они соответствуют повышению эффективности.

В составе основной задачи информатики сегодня выделяют следующие направления для практических приложений:

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

На всех этапах технического обеспечения информационных процессов для информатики ключевым понятием является эффективность. Для аппаратных средств под эффективностью понимают отношение производительности оборудования к его стоимости. Для программного обеспечения под эффективностью понимают производительность лиц, работающих с ними (пользователей). В программировании под эффективностью понимают объем программного кода, создаваемого программистами в единицу времени. В информатике все жестко ориентировано на эффективность. Вопрос, как сделать ту или иную операцию, для информатики является важным, но не основным.

Основной вопрос – как сделать данную операцию эффективно?

Понятие "ПОДПРОГРАММА".
Часто случается, что программа требует многократного выполнения одного и того же действия с теми же самыми переменными или с различными переменными. Такое действие может быть также общим для ряда программ.
Например, многие программы должны сортировать данные: тип этих данных, их число, «ключи», по которым они должны быть упорядочены, могут существенно различаться, основная задача, однако, остаётся той же, и можно построить зависящий от параметров алгоритм, который будет способен обрабатывать большую часть таких случаев. Не имеет смысла создавать собственную программу для каждой сортировки. Вместо этого вызывают одним – единственным оператором ПОДПРОГРАММУ сортировки, которую снабжают в качестве ПАРАМЕТРОВ сортируемыми данными и их характеристиками и которая будет после выполнения выдавать обратно эти данные, упорядоченные должным образом.
ПОДПРОГРАММА является КОМПОНЕНТОМ программы, обладающим именем, которое позволяет этой программе (или всякой другой программе) вызвать его, чтобы заставить выполнять некоторое действие или вычислить некоторые значения. 

ПОДПРОГРАММА - это функциональная зависимость между возможными аргументами (исходными данными) и соответствующими результатами.

Аргументы и результаты подпрограммы вместе называются её ПАРАМЕТРАМИ.

ПОДПРОГРАММА как средство абстрагирования.
Чтобы оправдать написание ПОДПРОГРАММЫ совсем не обязательно, чтобы задача относилась к типу «часто повторяющихся действий или действий, общих для многих процессов», достаточно, чтобы задача образовывала логически однородную сущность. С этой точки зрения ПОДПРОГРАММА есть удобное средство абстрагирования, то есть это компонент программы, определённый функционально, посредством выполняемых над ним операций, действий, не зависящий от способа его реализации.
Использование подпрограмм позволяет на этапе проектирования общей структуры программы, то есть разбиения задачи на подзадачи, отложить на более поздний срок технические подробности реализации той или иной подзадачи.
С точки зрения структуры базовых алгоритмов, ПОДПРОГРАММА – это просто «МОДУЛЬ», который может, например, задавать действие или условие во фрагменте программы:
ПОКА условие ПОВТОРЯТЬ
| действие

Вызов ПОДПРОГРАММЫ.
О программе, которая обращается к другой для выполнения некоторого действия, говорят, что она вызывает другую программу с помощью оператора – ВЫЗОВ ПОДПРОГРАММЫ.
Различают вызывающую и вызываемую программы.
Когда выполнение вызываемой программы прекращается, говорят, что она осуществляет ВОЗВРАТ к вызывающей программе, которая продолжает свое выполнение с оператора, следующего (в цепочке) за вызовом.
Программы, которые могут вызываться другими программами, могут иметь дело не только с аргументами, известными в момент вызова, и результатами, выдаваемыми в момент возврата, но также при некоторых условиях с величинами, принадлежащими вызывающим программам; такая обработка может определенным образом преобразовывать эти величины.
Поэтому в числе параметров, кроме аргументов и результатов, выделяют те, которые называются МОДИФИЦИРУЕМЫМИ ПАРАМЕТРАМИ.
Любая программа может использовать, кроме аргументов и результатов, ещё и промежуточные переменные, необходимые на этапе вычислений.
В случае ПОДПРОГРАММЫ говорят о ЛОКАЛЬНЫХ ПЕРЕМЕННЫХ, чтобы подчеркнуть, что эти объекты недоступны за пределами подпрограммы, которая их использует.

Определение и вызов ПОДПРОГРАММЫ.
Для ПОДПРОГРАММЫ важно различать понятия её ОПРЕДЕЛЕНИЯ и её ВЫЗОВА.
Определение, или декларация, подпрограммы содержит:
- указание её имени, которое должно позволить другим программам обращаться к ней;
- указание количества параметров, которые должны быть ей конкретизированы при вызове (аргументы, результаты, - модифицируемые параметры), и типов каждого из них;
- описание действия, которое использует эти параметры.
Такое описание имеет вид программы, где аргументы представлены некоторыми именами, называемыми ФОРМАЛЬНЫМИ ПАРАМЕТРАМИ.
Синтаксически определение подпрограммы является её объявлением, и не предписывает выполнения какого-либо действия (хотя содержит операторы), а просто ставит в соответствие имя (типа «программа») некоторому объекту (элементу программы).
При таком определении подпрограммы всякая программа может содержать вызов этой подпрограммы, задаваемый её именем, за которым следует список объектов, определяемых в вызывающей программе (константы, переменные, массивы и т.д.).
Некоторые из этих объектов – аргументы, значения которых предаются вызываемой программе, другие – результаты, которым вызываемая программа присваивает значения, третьи – модифицируемые параметры.
Эти передаваемые подпрограмме объекты называются ФАКТИЧЕСКИМИ ПАРАМЕТРАМИ, каждый из которых должен соответствовать одному из формальных аргументов, фигурирующих в определении подпрограммы.
Определение подпрограммы включает в себя ЗАГОЛОВОК и ТЕЛО подпрограммы, которое образовано операторами.
Чтобы ВЫЗВАТЬ подпрограмму, достаточно написать в вызывающей программе имя этой подпрограммы вместе с заключенным в скобки списком фактических параметров.

В языке Си подпрограммы называются функциями.
ФУНКЦИЯ - это совокупность объявлений и операторов, обычно предназначенная для решения определенной задачи.
Каждая функция должна иметь имя, которое используется для ее объявления, определения и вызова.
В любой программе на Си должна быть функция с именем main () (главная функция), именно с этой функции, в каком бы месте программы она не находилась, начинается выполнение программы.
При вызове функции ей при помощи аргументов (формальных параметров) могут быть переданы некоторые значения (фактические параметры), используемые во время выполнения функции.
Функция может возвращать некоторое (одно) значение. Это возвращаемое значение и есть результат выполнения функции, который при выполнении программы подставляется в точку вызова функции, где бы этот вызов ни встретился.
Допускается также использовать функции, не имеющие аргументов, и функции, не возвращающие никаких значений. Действие таких функций может состоять, например, в изменении значений некоторых переменных, выводе на печать некоторых текстов и т.п.

Определение, объявление и вызов функции.
С использованием функций в языке Си связаны три понятия:
- определение функции (описание действий, выполняемых функцией);
- объявление функции (задание формы обращения к функции);
- вызов функции.
Определение функции задает тип возвращаемого значения, имя функции, типы и число формальных параметров, а также объявления переменных и операторы, называемые телом функции, и определяющие действие функции.
В соответствии с синтаксисом языка Си определение функции имеет следующую форму:
 [спецификатор типа] имя функции([список формальных параметров]) // ЗАГОЛОВОК функции
{
 тело функции  
}
Спецификатор типа функции задает тип возвращаемого значения и может задавать любой тип.
Если спецификатор типа не задан, то предполагается, что функция возвращает значение типа int.
Функция возвращает значение если ее выполнение заканчивается оператором return, содержащим некоторое выражение. Указанное выражение вычисляется, преобразуется, если необходимо, к типу возвращаемого значения и возвращается в точку вызова функции в качестве результата.
Если оператор return не содержит выражения или выполнение функции завершается после выполнения последнего ее оператора (без выполнения оператора return), то возвращаемое значение не определено.
Для функций, не использующих возвращаемое значение, должен быть использован тип void, указывающий на отсутствие возвращаемого значения.
В языке Си переменные можно объявлять внутри функций. Такие переменные называются локальными переменными, поскольку их имена и значения имеют смысл только внутри функций, в которых они определены.
При каждом вызове функции для размещения локальных переменных выделяется пространство. При завершении функции пространство, содержащее значения этих переменных, освобождается. Какое бы количество локальных переменных ни объявлялось в функции, Си сохраняет значение каждой из них.

Объявление функции - это заголовок функции с точкой с запятой в конце.

Список формальных параметров.
Определение функции состоит из двух частей: заголовка и тела.
Заголовок определяет имя функции, ее тип и формальные параметры, тело определяет действия над данными, выполняемые функцией.
Возвращаемое функцией значение передается в вызывающую программу оператором return (выражение). Значение “выражения” и есть результат функции.
По умолчанию тип функции целый.
Список формальных параметров - это последовательность объявлений формальных параметров, разделенная запятыми.
Формальные параметры - это переменные, используемые внутри тела функции и получающие значение при вызове функции путем копирования в них значений соответствующих фактических параметров.

Список формальных параметров может заканчиваться запятой (,) или запятой с многоточием (,...), это означает, что число аргументов функции переменно.
Однако предполагается, что функция имеет, по крайней мере, столько обязательных аргументов, сколько формальных параметров задано перед последней запятой в списке параметров. Такой функции может быть передано большее число аргументов, но над дополнительными аргументами не проводится контроль типов.
Если функция не использует параметров, то наличие круглых скобок обязательно, а вместо списка параметров рекомендуется указать слово void.
Порядок и типы формальных параметров должны быть одинаковыми в определении функции и во всех ее объявлениях.
Типы фактических параметров при вызове функции должны быть совместимы с типами соответствующих формальных параметров.
Тип формального параметра может быть любым основным типом, структурой, объединением, перечислением, указателем или массивом.
Если тип формального параметра не указан, то этому параметру присваивается тип int.
Идентификаторы формальных параметров используются в теле функции в качестве ссылок на переданные значения.

Вызов функции.
При передаче параметров в функцию, если необходимо, выполняются обычные арифметические преобразования для каждого формального параметра и каждого фактического параметра независимо.
После преобразования формальный параметр не может быть короче чем int, т.е. объявление формального параметра с типом char равносильно его объявлению с типом int.
А параметры, представляющие собой действительные числа, имеют тип double (float).
Несоответствие типов фактических аргументов и формальных параметров может быть причиной неверной интерпретации.
При вызове функции локальным переменным отводится память и производится их инициализация.
Управление передается первому оператору тела функции и начинается выполнение функции, которое продолжается до тех пор, пока не встретится оператор return или последний оператор тела функции. Управление при этом возвращается в точку, следующую за точкой вызова, а локальные переменные становятся недоступными.
При новом вызове функции для локальных переменных память распределяется вновь, и поэтому старые значения локальных переменных теряются.
Функция не обязательно возвращает какое-либо значение.
Допускается “пустой” оператор return; либо он вообще может отсутствовать.
В последнем случае нормальное завершение функции обеспечивается при достижении правой закрывающей фигурной скобки. 

Объявление (прототип) функции.
В языке С нет требования, чтобы определение функции обязательно предшествовало ее вызову.
Определения используемых функций могут следовать за определением функции main(), перед ним, или находится в другом файле.
Однако для того, чтобы компилятор мог осуществить проверку соответствия типов передаваемых фактических параметров типам формальных параметров до вызова функции нужно поместить объявление (прототип) функции.
Объявление функции имеет такой же вид, что и определение функции, с той лишь разницей, что тело функции отсутствует, и имена формальных параметров тоже могут быть опущены.
В программах на языке С широко используются, так называемые, библиотечные функции, т.е. функции предварительно разработанные и записанные в библиотеки.
Прототипы библиотечных функций находятся в специальных заголовочных файлах, поставляемых вместе с библиотеками в составе систем программирования, и включаются в программу с помощью директивы #include.
Если объявление функции не задано, то по умолчанию строится прототип функции на основе анализа первой ссылки на функцию, будь то вызов функции или определение.
Однако такой прототип не всегда согласуется с последующим определением или вызовом функции. Рекомендуется всегда задавать прототип функции. Это позволит компилятору либо выдавать диагностические сообщения, при неправильном использовании функции, либо корректным образом регулировать несоответствие аргументов устанавливаемое при выполнении программы.

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

• заголовка, создающего "интерфейс" функции к внешнему миру,
• тела функции, реализующего заложенный в  нее  алгоритм  с  использовaнием внутренних локальных данных.

"Интерфейс" функции состоит из формальных параметров (вход) и результата (выход).
Тело функции - это составной оператор, содержащий операторы, определяющие действие функции.

#include 
#include 
#include

int  Counter (long Number) // заголовок функции Counter,  Number - формальный параметр
{
// начало тела функции
int k = 1; // k - локальная переменная
while ((Number/(long) pow(10,k)) > 0) k++;
return k;
} // конец тела функции

void main() // заголовок функции main
{
long number; // оператор описания
printf("Определение количества разрядов в числе. Введите число:");
scanf("%ld", &number);
// вызов функции Counter, с фактическим параметром number
printf("Количество разрядов в числе %ld равно  %d", number, Counter (number));
getch();
}
Заголовок и тело составляют определение функции.
Тип функции определяется типом возвращаемого ею значения ( по умолчанию int – целый).
Заголовок функции с точкой запятой в конце составляют объявление функции.
int  Counter (long  );

Выполнение функции завершается оператором return, которых может быть несколько.
Функция может вернуть:

• одно значение через оператор return; 
• значения переменных через аргументы, являющихся адресами переменных.

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

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

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

Результат функции - это временная переменная, которая возвращается функцией и может быть использована как операнд в контексте (окружении) выражения, где был произведен ее вызов.
Поскольку все переменные в Си имеют  типы,  тип  результата также должен быть определен.
Это делается в заголовке функции тем же способом, что и для обычных переменных. 
Используется тот же самый синтаксис, в котором  имя  функции  выступает в роли переменной-результата.
Значение переменной - результатa устанавливается в операторе return, который производит это действие наряду  с завершением выполнения функции и выходом из нее.
Между ключевым словом return и ограничивающим  символом  ";"  может стоять любое  выражение,  значение  которого  и  становится результатом функции.
Если вспомнить еще  и  о  преобразованиях  типов,  то  при   таком   "присваивании"   результата таковое должно производиться -  от  типа,  соответствующего выражению, к типу результата функции.
Имеется специальный пустой тип результата -  void,  который обозначает, что функция не возвращает  никакого  результата и, соответственно, не может быть вызвана внутри  выражения.
Оператор return в такой функции также не содержит  никакого выражения:
void    Nothing()  { return; }

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

После открывающейся скобки в блоке могут стоять определения переменных. Это локальные переменные  блока  (в  данном  случае тела функции). Они обладают следующими свойствами:

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

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

#include 
#include 
#include 
long Convert (int Number, int base) // два формальных  параметра Number, base
{
 long result = 0L; // локальные переменные result, t
 int  t = 0;
 while(Number > 0)
 {  result = result  + (Number % base) *(long) pow (10, t);
     Number = Number / base;
     t++;
 }
return result; // возврат управления и передача значения в точку вызова
}
void main()
{
int number, k;
printf("Перевод числа из десятичной системы в двоичную и восьмеричную.\n");
printf("Введите число:");
scanf("%d", &number);
// вызов функции, в котором первый фактический параметр есть переменная number, а второй - костанта целого типа 2
printf("\n Число в двоичной системе         = %ld", Convert (number,2));
printf("\n Число в восьмеричной системе = %ld", Convert (number,8));
getch();
}

Существуют три способа передачи параметров в функцию:

• по значению (классический способ);
• по ссылке;
• по указателю.

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

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

#include <stdio.h>
int Sum1 (int a, int b) {return (a + b); }

int Sum2 (int a, int b) { a = a + b; return a; }

void main()
{
int x = 5, y = 10, z = -7 ;
printf("Сумма чисел.\n");
printf(" %d + %d = %d \n", x, y, Sum1(x, y));
printf(" %d + %d = %d \n", x, z, Sum1(x, z));
printf(" %d + %d = %d \n", (x + y), z,  Sum2( x + y, z));
printf(" %d + %d = %d \n", (x * x), y, Sum2( x * x, y));
getch();
}

Результат:
Сумма чисел.
5 + 10 = 15
5  - 7   = -2
15 - 7  =  8
25 + 10 = 35
Значение переменной х не меняется после вызова функции.

Формальные параметры функции полностью локализованы в ней и недоступны для любых других функций.
Аргументы передаются функции по значению, т.е. вызываемая функция получает копии значений фактических параметров.
Определим функцию, которая определяет количество разрядов в десятичной записи числа.
#include
#include
int  Counter (long Number)
{
int k = 1;         // k - локальная переменная
while ((Number/(long) pow(10,k)) > 0) k++;
return k;
}
void main()
{
long number; // оператор описания
printf("Определение количества разрядов в числе. Введите число:");
scanf("%ld", &number);
printf("Количество разрядов в числе %ld равно  %d", number, Counter (number));
getch();
}
Описание формального параметра функции происходит в заголовке функции (long Number).
Оператор int k = 1;  в теле функции объявляет k как переменную целого типа и присваивает ей начальное значение, равное единице.
Здесь используется возможность инициализации переменных в операторах описания типа.
Инициализация int k = 1; в точности эквивалента последовательности операторов int k; k = 1;
Фактический и формальный параметры функции в точности соответствуют друг другу.
Выражение Counter (number) предписывает вызов функции.
Когда программа main() достигает этой точки, управление от main() передается функции Counter ().
Одновременно значение фактического аргумента  number копируется в формальный параметр Number.
Операторы, содержащиеся в теле функции power фактически оперируют данными, полученными от main().
Когда достигается оператор return, осуществляется переход в ту точку программы main(), из которой мы пришли в Counter ().
Значение, вычисляемое функцией Counter (), передается в головную программу с помощью опреатора return k.

В скобках в общем случае может быть любое выражение.

long Convert (int Number, int base)
{
 long result = 0L;
 int  t = 0;
 while(Number > 0)
 {  result = result  + (Number % base) *(long) pow (10, t);
     Number /= base;
     t++;
 }
return result;
}

void main()
{
int number, k;
printf("Перевод числа из десятичной системы в двоичную и восьмеричную.\n");
printf("Введите число:");
scanf("%d", &number);
printf("\n Число в двоичной системе         = %ld", Convert (number,2));
printf("\n Число в восьмеричной системе = %ld", Convert (number,8));
getch();
}

При передаче параметра по ссылке функция работает непосредственно с переменной, а не с её значением.

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

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

Параметру ссылочного типа должна быть присвоена ссылка на переменную того же типа.

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

Если необходимо "защитить" параметр от модификации, то следует описать его как const.
#include <stdio.h>
int Sum2 (int &a, int &b) { a = a + b; return a; }

int main()
{
int x = 5, y = 10, z = -7 ;
printf("Сумма чисел.\n");
printf("x = %d  y = %d ", x, y);
printf(" Sum =  % d    \n", Sum2(x,y));
printf("x = %d  z = %d ", x, z);
printf(" Sum = % d     \n", Sum2(x,z));
printf("z = %d  y = %d ", z, y);
printf(" Sum = % d    \n", Sum2(z,y));
printf("x = %d y = %d z = %d", x, y, z);
}

При передаче параметров через  указатели обеспечивается доступ к самим участкам памяти, отведенным для переменных, но дополнительно приходится использовать операцию разыменования указателя (*) для изменения значения переменных и унарную операцию взятия адреса (&) в списке фактических параметров.

#include <stdio.h>
int Sum2 (int *a, int *b) { *a = *a + *b; return *a; }

int main()
{
int x = 5, y = 10, z = -7 ;
printf("Сумма чисел. \n");
printf("x = %d  y = %d ", x, y);
printf(" Sum =  % d    \n", Sum2(&x, &y));
printf("y = %d  z = %d ", y, z);
printf(" Sum = % d     \n", Sum2(&y, &z));
printf("z = %d  y = %d ", z, y);
printf(" Sum = % d    \n", Sum2(&z, &y));
printf("x = %d y = %d z = %d", x, y, z);
}

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

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

• имя функции;
• тип результата;
• список формальных параметров (переменные и типы).

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

Вся перечисленная информация о функции находится в ее заголовке. Достаточно  этот  заголовок привести отдельно,  и  проблема  корректного вызова  решается.

Такой заголовок называется  ОБЪЯВЛЕНИЕМ  ФУНКЦИИ  или в рассматриваемом нами варианте синтаксиса ПРОТОТИПОМ.
Объявление функции - заголовок функции, необходимый транслятору для формирования корректного вызова функции, если она по каким-либо причинам ему недоступна.

Перечислим причины  такого  "незнания"  транслятора.

1. Трансляторы обычно используют  довольно  простые алгоритмы просмотра текста программы, "не заглядывая"  вперед. Поэтому обычно на данный момент трансляции  содержание текста программы за текущим  транслируемым  оператором  ему неизвестно.
2. Функция  может  быть  в  библиотеке.
3. Функция  может  быть в  другом текстовом  файле,  содержащем  часть программы.

Во всех этих случаях необходимо использовать объявления.

Единственный  случай,  когда  этого  делать  не надо - когда  определение  функции  присутствует  ранее  по тексту программы как в трёх ранее приведенных примерах.

Объявление функции практически дублирует заголовок, отличаясь в некоторых деталях:

• объявление заканчивается символом ";" ;
• если функция находится вне текущего файла, то объявление предваряется служебным словом extern;
• имена переменных в списке формальных параметров объявления могут отсутствовать;
• если функция не имеет формальных параметров, то в объявлении присутствует формальный параметр типа void.

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

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

Вариант 1.
#include <math.h>
#include <stdio.h>
// логическая функция, возвращает значение 1, если число является простым, и ноль - в противном случае.
int Is_Simple (int Number)
{
if (Number = = 2) return 1; //  первое простое число = 2
if ((Number < 2) || (Number % 2) = = 0)  return 0; // если число чётное, то оно не может быть простым
for (int i = 3; i <= (long) sqrt (Number); i += 2) // проверяем, если у числа делители
if ((Number % i ) = = 0) return 0;
return 1;
}

int main()
{
int k;
printf ("Enter number:");
scanf ("%d", &k);
if (Is_Simple(k)) puts("\n Simple"); // анализируем результат вызова функции
else    puts("\nNo Simple");
}

Вариант 2.
#include <math.h>
#include <stdio.h>
// определяем новый тип данных (истина, ложь)
enum logical { true, false };
// функция может вернуть либо true, либо false
logical Is_Simple (int Number)
{
if (Number == 2) return true;
if ((Number < 2) || (Number % 2)==0)  return false;
for(int i = 3; i <= (long) sqrt (Number); i += 2)
if ((Number % i ) == 0) return false;
return true;
}
int main()
{
int k;
printf ("Enter number:");
scanf ("%d", &k);
if (Is_Simple(k) = = true) puts ("\n Simple"); // анализируем результат вызова функции
else    puts("\nNo Simple");
}

Одномерный массив целых чисел как параметр функции.

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

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

Пример 1. Определить сумму элементов массива, начиная с i-го, количество элементов, заносимых в сумму, равно n.

#include <stdio.h>
int Summa (int mas[ ], int n)    // Размерность передается отдельным параметром.
{                                         
for (int i = 0, sum = 0; i < n; i++)  sum + = mas[i];
return sum;
}
int main()
{
int     arr [ ] = {1, 6, 4, 7, 3, 56, 43, 7, 55, 33};
int total, s1, s2, k = sizeof(arr) / sizeof (arr[0]);     //  вычисляем размер массива
total = Summa (arr, k);                      // сумма всех элементов с 1-го до последнего.
s1 = Summa (arr, 5);                                       // сумма первых пяти элементов.
s2 = Summa (&arr [3], 2);               // сумма двух элементов, начиная с четвертого.
printf(" total = %d s1 = %d s2 = %d ", total, s1, s2);
}

Одномерный массив целых чисел как модифицируемый параметр функции.

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

Пример 2. Заменить значения всех отрицательных элементов массива на значение 0,подсчитать количество замен.

#include <stdio.h>
// Замена отрицательных чисел на ноль.
int Pozitiv (int mas[ ], int n)
{                                         
for (int i = 0, coun = 0; i < n; i++)
if (mas[i]<0) { mas[i] = 0; coun++; }
return coun;
}
// вывод массива
void Output(int Array[ ], int size, char *s)
{
printf ("\n %s \n ", s);
for (int  i = 0; i < size; i ++)  printf ("%d ", Array [i]);
printf ("\n");
}
int main()
{
int arr[ ] = { -1, 6,-4, 7, -3, 56, 43,-7, 55, 33};
int total, s1, s2, k = sizeof(arr) / sizeof (arr[0]);   //  вычисляем размер массива

Output (arr, k, "First array :");                     // Вывод первоначального массива
total = Pozitiv (arr, k);            // Вызов функции замены значений (<0) на ноль
Output (arr, k, "Array - rezult:");                       // Вывод массива после замены
printf(" Total changings = %d ", total);
}

Результаты работы:
First array :
-1  6  -4  7  -3  56  43  -7  55  33
Array - rezult:
0  6  0  7  0  56  43  0  55  33
Total changings = 4

Одномерный массив целых чисел как модифицируемый параметр функции.

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

Пример 3. Удалить из массива все нули.

#include <stdio.h>
// вывод массива
void Output(int Array[ ], int size, char *s)
{
printf ("\n %s \n ", s);
for (int  i = 0; i < size; i ++)  printf ("%d ", Array [i]);
printf ("\n");
}
// Удаление нулевых элементов.
void Delete_Zeros (int Array[], int &size)
{
int i = 0, j;
while (i < size)
   if (Array[i] == 0)
      {
 for (j = i; j < size - 1; j ++) Array [j] = Array [j + 1];
  size --;
      }
   else i++;
}

int main()
{
int arr[ ] = { -1, 0, -4, 0, 0, 56, 43,-7, 0, 33};
int total, s1, s2, k = sizeof(arr) / sizeof (arr[0]);
Output (arr, k, "First array :");
Delete_Zeros (arr, k);
Output (arr, k, "Array - rezult:");
}

Результаты работы:
First array :
-1  0  -4  0  0  56  43  -7  0  33
Array - rezult:
-1  -4  56  43  -7  33

Одномерный массив целых чисел как модифицируемый параметр функции  ("Указатель на указатель").
Пример 4.
Рассмотрим случай, когда исходные данные содержатся в двух массивах. Значения из них копируются в массив-результат.

Вариант 1. Аналогичен тому, что рассмотрен в следующем примере. Размер нового массива равен сумме размеров двух массивов. Указатель на вновь созданный массив возвращается из функции.

Вариант 2. Массив-результат как параметр функции.

#include <stdio.h>
#define N 20
int*  Input (int &size)
{
int *arr;
while(1)
{
 printf ("Enter size (2 - %d): ", N);
 scanf ("%d", &size);
 if ((size >1) && (size <= N)) break;
 else printf("NO!\n");
}
arr = new int[size]; // выделяем память под массив
for (int i = 0; i < size; i ++) arr[i] = i+1;
return arr;
}
// вывод массива
void Output(int Array[ ], int size, char *s)
{
printf ("\n %s \n ", s);
for (int  i = 0; i < size; i ++)  printf ("%d ", Array [i]);
printf ("\n");
}

void Union (int A[ ], int al, int B[ ], int bl, int **C)
// С - это "указатель на указатель", т.е. передаем адрес участка памяти, в котором будет хранится адрес начала нового массива
{
int i = 0,  j;
*C = new int [al+bl]; // выделяем память под массив
// копируем значения из первого и второго массива в третий
for (j = 0; j < al; j ++, i++) (*C) [i] = A [ j ];
for (j = 0; j < bl; j ++, i++) (*C) [i] = B [ j ];
}

int main()
{
int arr[] = { -1, 0,-4, 0, 0, 56, 43,-7, 0, 33 };
int total, l, k = sizeof(arr) / sizeof (arr[0]);
int *ptr = Input (l);
int *rez;
// выводим "объединенный" массив
Union (arr, k, ptr, l, &rez);
Output (rez, l + k, "Union array :");
}

Результаты работы:
Enter size (2 - 20): 3
Union array :
-1  0  -4  0  0  56  43  -7  0  33  1  2  3

Одномерный массив целых чисел как возвращаемое функцией значение.

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

Пример 5.
Создать массив заданного размера и инициализировать его.
#include <stdio.h>
#define N 20
int*  Input (int &size) // формальный параметр - размер массива
{
int *arr;
while(1)
{
 printf ("Enter size (2 - %d): ", N);
 scanf ("%d", &size);
 if ((size >1) && (size <= N)) break;
 else printf("NO!\n");
}
// выделяем память под массив и адрес начала выделенного участка сохраняем в переменной arr
arr = new int [size];
// задаем значения
for (int i = 0; i < size; i ++) Array [i] = i + 1;
return arr;
}
// вывод массива
void Output(int Array[ ], int size, char *s)
{
printf ("\n %s \n ", s);
for (int  i = 0; i < size; i ++)  printf ("%d ", Array [i]);
printf ("\n");
}

int main()
{
int k;
int *ptr = Input (k); // функция возвращает указатель на массив
Output (ptr, k, "New array :");
}

Результаты работы:
Enter size (2 - 20): 10
New array :
1 2 3 4 5 6 7 8 9 10

Строка (символьный массив) как параметр функции.

Если в качестве параметра в функцию передаётся строка, то нет необходимости передавать размер такого массива, так как присутствует индикатор конца строки ('\0').

Просмотр строки string можно осуществлять двумя способами:
- определить длину строки, используя функцию  len = strlen (string);
Функция возвращает "чистую" длину строки (без '\0').
- организовать цикл for (int i = 0; string [i] != '\0' i++) ... "просмотра" строки.

Пример 6. Удалить из строки заданный символ. Вернуть количество удаленных символов.
#define N 60
#include

int Delete_Simbol (char s[ ], char c)
{
int i = 0, j, k = 0;
while (s[i] != '\0')
     if (s[i] = = c)
 { for (j = i; s[j] != '\0' j++) s[j] = s[j+1];
    k++;
 }
     else i++;
return k;
}

void main()
{
int k;
char s[N], ch;
puts ("Delete_Simbol.\nEnter string:"); gets (s);
puts ("Enter simbol:"); ch = getchar();

puts ("Result string:");
k = Delete_Simbol(s, ch);
puts (s);
printf ("total changings = %d",k);
}

Результаты работы:
Delete_Simbol.
Enter string: wethbefuindfudfdffdunfddun
Enter simbol:
f
Result string: wethbeuindudddunddun
total changings = 6

Строка (символьный массив) как модифицируемый параметр функции.

Пример 7.
Передадим в функцию строку str, из которой необходимо снять копию подстроки ( параметр substr для возврата) заданного размера len , начиная с определенной позиции i.

#include
#include
#define N 60
int Copy_SubStr (char *str, char *substr, int i, int len)
{
int length = strlen(str);                // определяем длину строки
if ((i < 0) || (i >= length)) return 0;  // если позиция начала подстроки находится вне строки
                        // копируем кусочек строки: или заданного размера, или до конца строки
strncpy (substr, &str[i], len);
substr [len] = '\0'
return 1;
}

void main()
{
int k, l;
char s[N], ss[N], ch;
puts ("Copy substring.\nEnter string:");
gets (s);
puts ("Enter position and length:");
scanf ("%d %d", &k, &l);
puts ("Result:");
if (Copy_SubStr (s, ss, k, l)) puts(ss);
else puts ("No substring!");
}

Результаты работы:
Copy substring.
Enter string: To be or not to be.
Enter position and length:
6 6
Result: or not
-------------------------------
Copy substring.
Enter string: To be or not to be.
Enter position and length:
25 6
Result: No substring!

Строка (символьный массив) как возвращаемое функцией значение.
Пример 8.
#include
#include
#define N 60
char* Union_Str (char *str1, char *str2)
{
int length = strlen (str1) + strlen (str2) + 1;    // определяем длину строки-результата
char *res = new char[length];                      // выделяем память под строку-результат
strcpy (res, str1);                               // копируем в результат первую строку
strcat (res, str2);                               // добавляем в результат вторую строку
return res;                                       // возвращаем указатель на строку-результат
}

void main()
{
int k, l;
char s[N], ss[N], ch;
puts("Union strings.\nEnter string1:");
gets(s);
puts("Enter string2:");
gets(ss);
puts("Result:");
puts(Union_Str (s, ss));
}

Результаты работы:
Union strings.
Enter string1: First string +
Enter string2: second STRING!
Result: First string + second STRING!

Объекты и их атрибуты.

Переменная – это частный случай объекта как именованной области памяти. Имя переменной используется для доступа к объекту. Имя переменной есть частный случай понятия «лево допустимое выражение»  или L - value (left value expression), которое в общем случае определяет ссылку на некоторый объект.  L – value: имена скалярных арифметических и символьных переменных; имена элементов, принадлежащих массивам; имена указателей; ссылки на объекты; уточненные имена компонентов структурированных данных; выражения, обеспечивающие косвенный выбор компонентов структурированных данных; лево допустимые выражения, заключенные в круглые скобки; выражения с операцией разыменования *.

 Тип объекта (переменной) определяет:

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

Кроме того, для объектов определяются (явно или по умолчанию):

• класс памяти (задает размещение объекта);
• область (сфера) действия, связанного с объектом идентификатора;
• видимость объекта;
• продолжительность существования объектов и их имён.

Определение переменной вызывает выделение памяти для переменной.

Класс памяти

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

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

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

Сферой действия идентификатора

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

Пространство имен – это сфера действия, в пределах которой идентификатор должен быть уникальным.

Видимостью идентификатора

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

Продолжительность существования,

связанная с классом памяти, определяет период, в течение которого объявленным идентификаторам соответствуют в памяти реальные объекты. Существуют различия между объектами периода компиляции и периода выполнения. Например, переменным, в отличие от typedef и типов, во время выполнения выделяется память. Есть три вида продолжительности: статическая, локальная и динамическая.

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

Объекты с локальной продолжительностью жизни, иначе называемые автоматическими переменными, ведут более случайное существование. Они создаются в стеке (или в регистре) при входе в окружающий их блок или функцию. При выходе из такого блока или функции они уничтожаются. Объекты с локальной продолжительностью должны быть инициализированы явно; в противном случае их исходное содержимое непредсказуемо. Не для всех объектов с локальной областью действия определена  локальная продолжительность жизни. Для локальных переменных может быть определена статическая продолжительность жизни спецификатором класса памяти static.

Объекты с динамической продолжительностью жизни создаются и разрушаются конкретными вызовами функций при выполнении программы. Им распределяется память из специального резерва памяти, называемого динамически распределенной памятью, при помощи стандартных библиотечных функций, например malloc, или операции С ++  new. Освобождение памяти выполняется функцией free() или операцией delete.

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

В число объектов, которые могут быть объявлены, входят:

• переменные,
• функции,
• типы,
• имена структур, объединений и  перечислений данных,
• элементы структур,
• элементы объединений,
• массивы прочих типов,
• перечисляемые константы,
• макросы препроцессора.

Спецификатор класса памяти

(спецификатор типа) обязательно должен присутствовать в объявлении. Спецификатор класса памяти может быть одним из ключевых слов: auto, register, extern, static, typedef.

Спецификатор класса памяти auto используется только в объявлениях переменных с локальной сферой действия. Он подразумевает локальную (автоматически определяемую) продолжительность существования.

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

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

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

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

Сложные объявления объектов

ДИНАМИЧЕСКИЕ ПЕРЕМЕННЫЕ

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

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

Оперативное управление памятью в соответствии с требованиями, предъявляемыми данными, называется динамическим распределением памяти.

Основные свойства динамических переменных

1. Динамические переменные создаются и уничтожаются работающей программой путем выполнения специальных операций или вызова функций.
2. Количество и размерность динамических переменных может меняться в процессе работы программы и зависит от количества вызовов соответствующих функций создания переменных и передаваемых при вызове параметров.
3. Динамическая переменная не имеет имени, доступ к ней возможен только через указатель.
4. При выполнении функции создания динамической переменной выделяется свободная память необходимого размера и возвращается указатель на неё.
5. При уничтожении динамической переменной соответствующей функции необходимо передать указатель на неё.

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

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

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

void *calloc (size_t  nitems, size_t size);  // Блок выделенной памяти обнуляется.

void *malloc (size_t size);                     // Выделяет оперативную память.

void *realloc (void  *block, size_t size);  // Перераспределяет память.

char *strdup (const char *s);  // Копирует строку по новому адресу в памяти.

void   free (void  *block);       // Освобождает память, выделенную под блок.

Массивы указателей

В соответствии с принципом контекстного определения переменной вида int *pnt; возможны следующие интерпретации  в памяти:

• это указатель на отдельную переменную типа int;
• это указатель на область памяти, отведенную под вектор, матрицу и т.д.

По аналогии мы можем определять массивы указателей int *pnt[10]; , где pnt может быть массивом указателей,  как на отдельные переменные целого типа, так и на массивы переменных целого типа.

Рассмотрим определение переменной вида – указатель на указатель на переменную типа  float (двойная ссылка):

float **ptr;

При таком определении получаются четыре варианта структур данных.

1. Указатель на переменную, которая является указателем на переменную типа float.
2. Указатель на переменную, которая есть указатель на массив переменных типа float.
3. Указатель на массив, содержащий указатели на одиночные переменные типа float.
4. Указатель на массив, содержащий указатели на массивы переменных типа float.

Массивы указателей допускают различные способы формирования, которые отличаются как способом создания самих элементов, так и способом установления связей.

1. Структуры данных формируются при трансляции, переменные определяются статически, массив указателей инициализируется.
2. Переменные определяются статически, массив указателей инициализируется программно.
3. Переменные создаются динамически, массив указателей определяется статически.
4. Все переменные создаются динамически.

Массив указателей позволяет объединить в общую структуру данных множество переменных одного типа. В этом его сходство с обычным массивом.

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

При использовании массива указателей последовательность элементов определяется последовательностью указателей в массиве.

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

Преимущества проявляются, когда сами элементы являются достаточно большими.

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

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

В определении указателя должен быть тот же тип, что возвращаемое функцией значение и та же сигнатура (типы, количество и последовательность параметров).
Определение указателя на функцию:
тип_функции (*  имя_указателя) (спецификация параметров);
int (*Pointer1)(char); определение указателя на функцию с параметром типа char, возвращающую значение типа int
char* (*Pointer2)(char*, int ); определение указателя на функцию с параметрами типа указатель на char и типа int, возвращающую значение типа указатель на char.

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

void f1 (void)
{
puts(“Работает функция f1”);
}
void f2 (void)
{
puts(“Работает функция f2”);
}
int main()
{ 
 void (*Pnt_f) (void);
 Pnt_f = f1;  
 (*Pnt_f)();
 Pnt_f = f2;  
 Pnt_f();
}
Вызов функции имеет вид:
(*имя_указателя)(список_фактических параметров);

Запись вызова без круглых скобок будет воспринята как синтаксическая ошибка.
имя_указателя (список_фактических параметров);

Имя указателя есть адрес функции, операция разыменования обеспечивает обращение по адресу к этой функции.
При определении указатель на функцию может быть инициализирован
#include <stdio.h>
int Add (int a, int b) { return a + b;}
int Subt(int a, int b) { return a - b;}
int Mult(int a, int b) { return a * b;}
int Div  (int a, int b) { return a / b;}
int Formula ()
{
int f, x, y, (*Operat)(int, int);
char c, op;
c = getchar();
if(( c >= '0') && (c <= '9')) return ( c - '0');
{
x = Formula (); op = getchar();  y = Formula ();
  switch (op)
 {
  case '+‘ : Operat = Add; break;
  case '-‘ : Operat = Subt; break;
  case '*‘ : Operat = Mult; break;
  case '/‘ : Operat = Div; break;
 }
getchar();
return Operat (x,y);
}
}

Массивы указателей на функции

Указатели на функции могут быть объединены в массивы:
int (*PntArray)(char)[N];// описание массива с именем PntArray из N указателей на функции, каждая из которых имеет параметр типа char и возвращает значение типа int.
Обращение к элементам массива будет следующим:
int value1, value2 = (*PntArray[1])(‘b’);
value1 = PntArray[0](‘a’);

Массивы указателей на функции удобно использовать при разработке программ, использующих МЕНЮ.
Действия, предлагаемые на выбор, оформляются в виде функций, адреса которых помещаются в массив указателей на функции. По номеру пункта меню как по индексу из массива выбирается соответствующий адрес функции. Обращение к функции по адресу обеспечивает выполнение требуемых действий.

Пример. Работа с базой данных по автомобилям

typedef void (*MENU)(CAR*, int &);
int main()
{
int i, k, num;
char c, *ss[] = {" 1-Input "," 2-Save base "," 3-Open base ",
     " 4-Print base", " 5-Sort base "," 6-Search", " 7-EXIT"};
MENU Action[] = {Save_in_File, Load_from_File,Print_base, Sort_base, Bin_search};// массив указателей на функции
CAR *base;
k = sizeof (ss) / sizeof(ss[0]);
for (;;)
  {
 for (i = 0; i < k; i++) puts (ss[i]);
 c = getch(); 
 if (c == '7') exit (1);
 if (c == '1') base = Enter_Data (base, num);
  else Action [(c -'0'-2)](base, num); // вызов функций
 }
}

Структурный объект («Запись»)

При использовании массива подразумевается, что:

           1.      Число его элементов ограничено.

           2.      Все элементы принадлежат к одному и тому же типу и имеют один и то же размер.

           3.      Доступ к элементам организуется в соответствии с их положением в массиве.

Реальные множества данных редко бывают однотипными. Порядок использования данных может оказаться несущественным или может определяться значениями данных.

Дополнительные методы агрегирования данных – структуры.

Структура – элемент данных, содержащий набор полей неоднородного типа. Каждое поле имеет имя, обеспечивающее прямой доступ к данным в поле.

Основные операции со структурами:

Тип элемента структуры может быть любым: массив, структура, указатель на объект того же или ранее описанного структурного типа, указатель на функцию и т.д.

Объявление структуры вводит новый производный тип, структурный тип. Объявление структуры задает имя структурной переменной и последовательность переменных величин, называемых элементами структуры, которые могут иметь различные типы.

struct [имя_типа_структуры]

{

  список объявлений

  элементов

}

[описатель [, описатель]…];

struct имя_типа_структуры описатель[, описатель]…;

Имя_типа_структуры – идентификатор, который именует тип структуры, определяемый списком объявлений элементов.

Элементы структуры могут быть как базовых, так и производных типов.

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

С именем структурного типа не связан никакой конкретный объект, с его помощью нельзя сформировать уточненные имена элементов.

struct Point

{

char name[N];

float x, y;

} xx, yy, coord[M], *pnt;

…

struct Point city_1, city_2, towns[M], *pt;

Для обращения к объектам, входящим в качестве элементов в конкретную структуру, используются уточненные имена:

имя_объекта_структурного_типа . имя_элемента_структуры.

yy . x = 0.756;              yy . y = - 0.234;

gets (coord[0] . name);

scanf (”%f %f”, &coord[i] . x, &coord[i] . y);

При определении структур возможна их инициализация:

Struct address

{

char country[N], city[N], index [L];

int home, f;

} sibiryak = {”Россия”, «Новосибирск”, ”630092”, 30, 26};

Указатель на структуру может входить в определение того же структурного типа.

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

Элементом структуры может быть структура, тип которой уже определен.

Элементами структуры могут быть массивы, и массивы могут содержать в качестве элементов структуры.

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

Для структур могут быть определены ссылки:

struct Point &refx = xx;

Функция может в качестве параметров получать и возвращать как результат: структуру, указатель на структуру и ссылку на структуру.

Сходство и отличия  массива и структуры:

 Оба являются структурами со «случайным доступом» к элементам.

Структура более универсальна, так как содержит элементы разных типов.

Массив предоставляет большие возможности, так как селекторы его компонентов могут быть выражениями, а селекторы компонентов структуры – это фиксированные идентификаторы, задаваемые в описании типа.

Размер структуры определяется операцией sizeof (имя_типа).

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

• Логическая организация данных: проектный уровень

• Представление данных: уровень языка реализации

• Физическая организация данных: машинный уровень

Логическая организация данных отражает взгляд пользователя на данные.

В её основе лежат требования пользователя и  внутренне присущие данным связи.

Только на логическом уровне могут применяться формальные методы описания динамически изменяющихся структур.

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

Если на этапе проектирования системы удачно выбрана логическая организация данных, изменения системных требований, не приводящие к модификации логической структуры данных, не повлекут за собой реорганизации на более низких уровнях представления данных.

Никакая дополнительная информация о членах семьи не изменит общую логическую структуру семьи:

семья = отец, мать, ребенок,…
отец = имя, возраст, профессия
мать = имя, возраст, девичья фамилия, профессия
ребенок = имя, возраст, пол

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

Описание данных на языке программирования относится к уровню представления данных.

Отношения между данными задаются в виде, характерном для конкретного языка. На этом уровне оперируют массивами и указателями.

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

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

При внешнем представлении главным является определение возможных путей доступа.

Внутренне представление – это представление в виде внутренних областей хранения данных, то есть структура данных может быть во внешнем представлении стеком, а во внутреннем – массивом или связанным списком.

Например, данные о покупателе включают номер счета, имя, адрес, даты предыдущих расходов, платежи и счета.

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

Внутреннее представление может состоять из таблиц, полей признаков и указателей.

Уровень физической организации связан с  системным программным обеспечением.

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

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

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

Алгоритмы содержат определение пошагового процесса обработки данных с описанием преобразований данных и функций управления.

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

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

Типы алгоритмов.

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

Если задача может быть решена прямым способом, говорят, что она имеет детерминированный метод решения.

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

Для построения детерминированных алгоритмов недопустимо применение методов проб и ошибок.

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

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

Третий, основной тип алгоритмов, предназначен не для поиска ответа на поставленную задачу, а для моделирования сложных систем с использованием ЭВМ.

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

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

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

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

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

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

Недетерминированный характер свойственен играм и головоломкам.

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

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

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

Методы, используемые для сокращения числа вариантов при переборе или позволяющие выбирать наиболее правдоподобные варианты, называются эвристическими.

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

Способы реализации алгоритмов.

Целью любой программы является преобразование входных данных в выходные.

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

Если организация входного потока отличается от организации выходного, логичнее использовать две независимые сопрограммы: одну для получения выходных данных, другую – для их организации.

Если порядок следования данных несущественен, можно использовать параллельную обработку.

Все виды обработки могут быть разделены на следующие классы:

• последовательная обработка, использующая повторения;

• структурное распараллеливание с помощью сопрограмм;

• произвольная обработка с применением параллельных вычислений.

Итерация и рекурсия.

Существуют две основные формы повторений: итерация и рекурсия.

Итерация в основном используется для тех видов обработки, которые лучше всего определяются выражением типа «выполнить для всех Х», а рекурсия – для получения результирующих данных,  которые легче всего описать рекурсивно, то есть задать выражением вида «выполнить то же, что и в последний раз».

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

В действительности итерация и рекурсия взаимозаменяемы.

Рекурсивные процедуры могут быть переписаны в итерационном виде в языках, где рекурсия невозможна (например, ФОРТРАН) и наоборот (язык ЛИСП).

Параллельная обработка.

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

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

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

Сопрограммы.

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

В многопроцессорных системах сопрограммы могут выполняться параллельно.

Это характерно для задачи типа «поставщик-потребитель», которая является классическим примером взаимодействия сопрограмм.  Один процесс Р поставляет некоторый продукт, другой С этот продукт использует. Р может выпустить столько единиц продукта, сколько может разместиться в общей области хранения. Если же область хранения полна, то Р должен ждать С. С может использовать единицы продукта только в том случае, если они есть в области хранения. Если же она пуста, то С должен ждать Р. Процесс начинается с того, что Р производит первую единицу продукта, а заканчивается, когда или С получил достаточное для него количество продукта, или у Р кончился материал, нужный для производства продукта, или, наконец, когда Р извещает С о прекращении работы.

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

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

Метод «разделяй и властвуй»

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

Пример 1. Матричные операции сложения и вычитания выполняются таким же способом, как эти операции определены для отдельных элементов.

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

Пример 3. Численное интегрирование.

Пример 4. Большинство способ сортировки данных строится по этому принципу (сортировка слиянием, сортировка Шелла).

Метод последовательных приближений (метод подъема)

Когда известно приближенное решение и есть способы для его уточнения, можно использовать данный подход. Начиная с исходного приближения f₀,  производится последовательное уточнение решения f₁, затем уточнения решений f₂,  f₃ и т.д. Этот  ряд представляет собой последовательность приближенных решений, которые или сходятся к действительному решению, или приближаются к нему настолько, насколько это нужно для практического использования. Каждый член последовательности может зависеть или только от предшествующего ему члена, или от всех более ранних приближений.

Пример 1. Метод Ньютона-Рафсона для нахождения корней уравнения вида x^k – n = 0. Вычисление  заканчивается при том значении индекса k, когда значения s_k-1 и s_k приблизительно равны между собой.

Пример 2. Численное интегрирование. Определенный интеграл представляет собой площадь между кривой, изображающей функцию, и осью абсцисс. Для вычисления интеграла отрезок, на котором он определен, делится на равные части, и на каждой из  этих частей вычисляется приближение с помощью значения f (x_k) Δx , где x_k – некоторое значение x в пределах k – ой части, а Δx – размер каждой из частей отрезка. Затем производится дальнейшее разбиение частей на более мелкие отрезки и вычисляется следующее приближение. Когда два приближения достаточно близки друг к другу, то решение найдено. В этом примере использовались два различных способа построения алгоритма: аддитивный метод применялся для нахождения последовательных приближений к значению интеграла.

Пример 3. Имеется 25  монет. Все они одного веса, за исключением одной монеты с дефектом, которая весит меньше остальных. Разработайте алгоритм, определяющий фальшивую монету за три взвешивания. Каково максимальное число монет, для которых можно определить монету с дефектом не больше, чем за три взвешивания на весах с чашками?

Метод наискорейшего спуска

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

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

Пример 1. Задача коммивояжера.

Пример 2. Применение рассматриваемого метода в математике можно продемонстрировать на примере использования последовательных приближений, которые сами по себе не являются аппроксимацией требуемой величины. Таким примером служит ряд чисел Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21, 34, …, каждое из которых является суммой двух предыдущих. k – ое число последовательности отыскивается с помощью вычисления всех предшествующих чисел, ни одно из которых не является его приближением. Ряд, образуемый этими числами, не сходится, а расходится.

Пример 3. То же можно сказать о последовательностях для получения биноминальных коэффициентов.

Метод обратного прохода (отрабатывания назад)

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

Пример 1. Имеется два резервуара емкостью 3 и 5 литров. Требуется с помощью этих емкостей отмерить 4 литра жидкости.

Пример 2. Определить, сколько прыжков потребуется лягушке, чтобы выбраться из ямы глубиной 1 метр, если за один прыжок она поднимается на 30 см, а между прыжками сползает вниз на 20 см.

Метод поиска с возвратом (программирование с отходом назад)

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

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

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

Пример 2. Вычисление арифметического выражения типа: 2 + 3 * ( 4 + 5 ) - 6. Указанное выражение может быть представлено в виде синтаксического дерева. Вычисление выполняется с помощью поиска по синтаксическому дереву в глубину, для чего используется рекурсивная функция.

Пример 3. Комбинационный замок, состоящий из N переключателей, каждый из которых может быть в положении «вкл» или «выкл». Замок открывается только при одном наборе переключателей, из которых не менее N/2 находятся в положении «вкл». Для того чтобы определить комбинацию переключателей, при которой замок откроется, необходимо перебрать 2N вариантов.

Промоделируем каждую возможную комбинацию вектором из N нулей и единиц. На i–ом месте будет единица, если i–ый переключатель находится в положение «вкл», и 0 в противном случае. Множество всех возможных N- векторов хорошо моделируется с помощью двоичного дерева. Каждая вершина   k-го уровня этого дерева будет соответствовать определенному набору первых k компонент N-вектора. Две ветви, идущие вниз из вершины этого уровня, соответствуют двум возможным значениям (k+1)-й компоненты в N-векторе. У дерева будет N уровней. Рисунок на примере N = 4 поясняет сам алгоритм поиска комбинаций (см Приложение 1).

Условие, заключающееся в том, что число переключателей в положении «вкл» должно быть не меньше N/2, позволяет нам не образовывать части дерева, которые не могут привести в правильной комбинации. Например, вершина 00. Так как правая ветвь (к 000) не может привести к допустимой комбинации, нет нужды её формировать. Если какие-то вершины, следующие за рассматриваемой вершиной, не удовлетворяют ограничению задачи, то эти вершины не надо рассматривать. В данном случае вершины, выделенные жирным курсивом, не нужно исследовать и даже формировать.

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

Метод выделения подцелей (метод частных целей)

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

Можем ли мы решить часть задачи?  Можно ли, игнорируя некоторые условия, решить оставшуюся часть задачи?

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

Есть ли что-то, относящееся к задаче, что мы недостаточно хорошо поняли? Если попытаемся глубже вникнуть в некоторые особенности задачи, сможем ли мы что-то узнать, что поможет нам подойти к решению?

Встречались ли мы с похожей задачей, решение которой известно? Можно ли видоизменить её решение для решения нашей задачи? Возможно ли, что эта задача эквивалентна известной нерешенной задаче?

Ранее приведенные методы могут иллюстрировать метод выделения подцелей.

Использование подхода «разделяй и властвуй» может служить примером применения метода выделения подцелей, если, например, процесс решения имеет следующий вид.

Подцели: разделить задачу на части; решить каждую часть.

Цель: объединить все частичные решения вместе, чтобы получить решение всей задачи.

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

Подцели: найти приближенное решение; уточнить его.

Вторая из этих подцелей повторяется до тех пор, пока не будет получено достаточно точное приближение.

В методе наискорейшего спуска используется единственная  подцель – продвинуться на один шаг дальше, и эта подцель повторяется, пока не будет достигнута такая позиция, из которой дальнейшее продвижение невозможно.

В методе поиска с возвратом задача решается не путем разбиения её на части, а с помощью её модификации.

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

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

Проблемы оптимизации процесса сортировки различаются в обоих случаях:

• во внутренней сортировке стремятся сократить число сравнений и других внутренних операций,

• во внешней сортировке тоже кроме числа сравнений решающим фактором является количество операций по вводу и выводу данных.

Ограничимся внутренней сортировкой и данными, представляемыми в виде массивов.

Обычно функция упорядочения не вычисляется по какому-либо специальному правилу, а содержится в каждом элементе в виде явной компоненты (поля). Её значение называется ключом элемента.

Инверсия в массиве а – это пара индексов i и j, такая, что i < j ,  а  key _i > key _j.

Массив называется отсортированным, если он не содержит ни одной инверсии.

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

Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять на одном и том же месте.

Классификацию алгоритмов  сортировки массивов проводят в соответствии с их эффективностью, то есть экономией времени или быстродействием.

Удобная мера эффективности получается при подсчёте числа С – необходимых сравнений ключей и М – пересылок элементов. Эти числа определяются некоторыми функциями от числа n сортируемых элементов. Простые методы сортировки требуют порядка n² сравнений ключей, хорошие – n*log n сравнений. Все методы простой сортировки можно разбить на три основных класса в зависимости от лежащего в их основе приема: сортировка включениями, сортировка выбором и сортировка обменом.

Сортировка простыми включениями.

Элементы условно разделяют на готовую последовательность а₁, … , а _i–1 и входную последовательность а _i, … , а _n. На каждом шаге, начиная с i = 2 и увеличивая i на единицу, берут i – ый элемент входной последовательности и передают в готовую последовательность, помещая его на подходящее место. Алгоритмы сортировки простыми включениями (метод «погружения» и метод «включения») выглядят следующим образом:

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

Анализ сортировки простыми включениями. Число С _i сравнений ключей при i-ом просеивании составляет самое большее i-1, самое меньшее 1 и, если предположить, что все перестановки n ключей равновероятны, в среднем равно i/2. Число М _i пересылок (присваиваний) равно С_i+2. Поэтому общее число сравнений пересылок следующее

C _min = n – 1                     M _min = 2 (n - 1)

C _ср. = ¼ (n² + n – 2 )       M _ср.  = ¼ (n² + 9n - 10)

C _max = ½ (n² + n) – 1       M _max = ½ (n² + 3n - 4)

Наименьшие числа появляются, если элементы с самого начала упорядочены, а наихудший случай – если элементы расположены в обратном порядке.  В этом смысле сортировка включениями демонстрирует вполне естественное поведение. Данный алгоритм описывает устойчивую сортировку: он оставляет неизменным порядок элементов с одинаковыми ключами. Однако, включение элемента с последующим сдвигом всего ряда элементов на одну позицию неэкономно. Лучших результатов можно ожидать от метода, при котором пересылка элементов выполняется только для отдельных элементов и на большие расстояния. Речь идет о сортировке выбором.

Сортировка простым выбором.

Метод основан на следующем  правиле: выбирается элемент с наименьшим ключом, он меняется местами с первым элементом; затем эти операции повторяются с оставшимися n – 1 элементами, затем с n – 2 элементами, пока не останется только один элемент – наибольший. Алгоритм сортировки можно представить следующим образом:

void Sort_Select (int m[], int n)

{

int i, j, c, k ;

for ( i = 0; i < n - 1; i ++)

 {

  k = i; 

  for( j = i + 1; j < n;  j ++) 

      if ( m [j] < m [k] ) k = j;

  c = m [k]; m [k] = m [i]; m [i] = c;

  }

}

Анализ сортировки простым выбором.

Число сравнений ключей C = ½ (n² - n)  не зависит от начального порядка ключей.

Минимальное число пересылок равно M _min = 3 (n - 1) в случае изначально упорядоченных ключей и принимает

наибольшее значение M _max = trunc (n²/4) + 3 (n - 1), если вначале ключи расположены в обратном порядке.

M _ср. = n (ln n + 0.57).

Сортировка простым обменом.

Алгоритм сортировки простым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут рассортированы все элементы. Проходя по массиву, каждый раз просеивается наименьший элемент оставшегося множества, двигаясь к левому концу массива (или наибольший - к правому концу). Этот метод широко известен как  сортировка методом пузырька.

Этот алгоритм легко оптимизировать, запоминая на каждом проходе -  был ли обмен. Если нет, то это означает, что алгоритм может закончить работу. Процесс улучшения можно продолжить, если запоминать место (индекс) последнего обмена, а также менять направление следующего один за другим проходов. Такой алгоритм называют Шейкер - сортировкой.

Анализ сортировки методом пузырька и Шейкер-сортировки.

Число сравнений в алгоритме простого обмена равно C = ½ (n² - n), а

минимальное, среднее и максимальное количества пересылок элементов равны: 

M _min = 0, M _ср.  = ¾  (n² - n), M _max  = 3/2 (n² - n).

Анализ улучшенных методов,в частности, метода Шейкер-сортировки довольно сложен. Наименьшее число сравнений равно C _min = n – 1. Обмен двух элементов - намного более "дорогостоящая" операция, чем сравнение ключей, поэтому все усовершенствования дают небольшой эффект.

Вывод: сортировка обменом и её усовершенствования хуже, чем сортировка включениями и выбором.

Поиск данных.

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

Поиск может быть двух типов: последовательным и быстрым (бинарным, двоичным).

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

В реализации последовательного поиска в массиве общее время поиска на больших наборах элементов можно значительно уменьшить, используя процедуру поиска, основанную на подходе "разделяй и властвуй". Для этого набор элементов необходимо разделить на две части, определить, к какой из двух частей принадлежит ключ поиска и перейти к этой части, которую снова разделить на две и так далее. Исходная последовательность элементов должна быть упорядочена. Такой подход называется бинарным поиском.

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

/* Функция определяет, является ли переданное слово ключевым. */

int Is_Key_Word (char *s)

{

char *Key_words[]={"break","case","char","do","double","else","float","for","if","int","long","main","return","sizeof","struct","switch","void","while"};

int i, l = 0, k, r = sizeof(Key_words) / sizeof(char*);

do

{

 i = (l + r) / 2;

 if ((k = strcmp(s,Key_words[i])) == 0) return 1; // слово найдено

 if (k > 0) l = i + 1; // ищем в "правой половине" массива

    else r = i - 1;      // ищем в "левой половине" массива

} while (l <= r);

return 0; // нет такого ключа

}

Источник - Д.Ван Тассел, Стиль, разработка, эффективность, отладка и испытание программ: Пер. с англ. – М. Мир, 1985 г.

1. Помните: программы читаются людьми.

2. Делайте комментариев больше, чем это кажется необходимым.

3. Используйте вводные комментарии.

4. Делайте оглавление в больших программах.

5. Комментарии должны содержать дополнительную информацию, а не перефразировать программу.

6. Располагайте комментарии таким образом, чтобы это не делало программу менее наглядной.

7. Неправильные комментарии хуже, чем их отсутствие.

8. Делайте пробелы для улучшения читаемости программы.

9. Используйте имена с подходящей мнемоникой.

10.  При наименовании файлов используйте определенный префикс или суффикс.

11. Одного оператора в строке достаточно.

12. Упорядочивайте списки по алфавиту.

13. Скобки обходятся дешевле, чем ошибки.

14. Для выявления структуры программы используйте отступы.

15. Для выявления структуры данных используйте отступы.

16. Стремитесь к простоте.

17. Добивайтесь точности при определении задачи.

18. Выбирайте алгоритм решения задачи самым тщательным образом.

19. Выбирайте представление данных, соответствующее задаче.

20. Используйте в качестве параметров переменные, а не константы.

21. Создавайте универсальные программы.

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

23. Устанавливайте цели проекта заблаговременно и точно.

24. Разрабатывайте тестовые данные заранее.

25. Прежде чем начать программировать, разработайте проект.

26. Исключайте ошибки с самого начала.

27. Короткие модули предпочтительнее длинных.

28. Исключите использование оператора go to.

29. Прежде чем программировать, запишите программу в псевдокодах.

30. Планируйте возможные изменения в программе.

31. Начинайте документирование на стадии разработки программы.

32. Не бойтесь начинать программирование сначала.

33. Если программа неправильная, не имеет значения, какова её эффективность.

34. Определяйте требования к эффективности программы на стадии проектирования.

35. Удобочитаемость программы обычно более важна, чем эффективность.

36. Инициализируйте переменные во время компиляции.

37. Избегайте смешанных типов данных.

38. Оптимизируйте сначала внутренние циклы.

39. Используйте для индексации наиболее предпочтительный тип данных.

40. Группируйте записи в эффективные блоки ввода-вывода.

41. При отладке программы используйте интерпретатор.

42. Первым делом проверяйте программу за столом.

43. Выполняйте эхо-проверку вводимых данных.

44. Вводите средства отладки как можно раньше.

45. Контролируйте правдоподобность вводимых данных.

46. Используйте все доступные средства отладки.

47. Делайте программу правильной с самого начала.

48. Обходитесь минимальным количеством контрольных примеров.

49. Учитывая, что исчерпывающее тестирование невозможно, испытывайте программу разумно.

50. Начинайте тестирование как можно раньше.

51. Прежде всего, проводите ручную проверку.

52. Старайтесь проверять правильность принципов построения системы на её простом варианте.

53. Старайтесь применять тестирование по методу сверху вниз.

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

55. Испытывайте программу в нормальных, экстремальных и исключительных условиях.

56. Подготавливайте тестовые данные для проверки каждой ветви алгоритма.

57. Повторяйте тестирование после каждого случая внесения изменений в программу