Билет №1 Основные этапы решения задач на ЭВМ

Этапы создания программного обеспечения

В процессе разработки программ с использованием структурного подхода можно выделять следующие этапы: 1.постановка задачи – определение требований к программному продукту; 2. анализ – осуществление формальной постановки задачи и определение методов ее решения;3. проектирование – разработка структуры программного продукта, выбор структур для хранения данных, построение и оценка алгоритмов подпрограмм и определение особенностей взаимодействия программы с вычислительной средой (другими программами, операционной системой и техническими средствами); 4. реализация – составление программы на выбранном языке программирования, ее тестирование и отладка. 5.модификация – выпуск новых версий программного продукта.

Постановка задачи

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

конкретную комплектацию и параметры технических средств, версию используемой операционной системы и, возможно, версии и параметры другого установленного программного обеспечения, с которым предстоит взаимодействовать будущему программному продукту. В результате согласования между заказчиком и исполнителем всех перечисленных вопросов составляют техническое задание в соответствии с ГОСТ 19.201-78, которое служит основанием для дальнейшей работы.

Анализ, формальная постановка и выбор метода решения

На данном этапе по результатам анализа условия задачи – выбирают математические абстракции, строят модель задачи и определяют метод преобразования исходных данных в результат (метод решения задачи).

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

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

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

Проектирование

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

Логическое проектирование. Логическое проектирование при структурном подходе предполагает детальную проработку последовательности действий будущей Программы. Его начинают с определения структуры будущего программного продукта: отдельная программа или программная система, состоящая из нескольких взаимосвязанных программ. Затем переходят к разработке алгоритмов программ. Алгоритмом называют формально описанную последовательность действий, которые необходимо выполнить для получения требуемого результата.

Реализация

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

понятный процессору – в машинные коды. Этот процесс для языка С состоит из нескольких этапов

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

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

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

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

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

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

тестов обе стратегии.

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

Билет №2 Критерий качества программы. Диалоговые программы. Дружественность.

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

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

Критериями качества ПП являются:

·          Функциональность

·          Соответствие назначению

·          Точность

·          Способность взаимодействовать со средой

·          Соответствие нормам

·          Безопасность (защита от взлома данных и других преступных посягательств)

·          Надежность

·          Зрелость ("обкатанность")

·          Отказоустойчивость

·          Способность восстанавливаться после сбоев

·          Пригодность к использованию

·          Понимаемость

·          Изучаемость

·          Удобство и простота в работе

·          Эффективность

·          Быстродействие и время отклика

·          Потребление ресурсов

·          Сопровождаемость

·          Анализируемость (диагностика причин ошибок и сопоставление с исходным кодом)

·          Пригодность к изменениям

·          Стабильность

·          Тестируемость

·          Переносимость

·          Адаптируемость

·          Легкость инсталляции

·          Мобильность

·          Соответствие нормам по переносимости и инсталляции

·          Заменяемость (способность заменить аналоги?)

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

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

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

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

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

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

Билет№3 Жизненный цикл программы

Жизненный цикл и этапы разработки программного обеспечения.

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

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

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

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

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

·          Проектирование общей структуры – определение основных компонентов и их взаимосвязей;

·          Декомпозицию компонентов и построение структурных иерархий в соответствии с рекомендациями блочно – иерархического подхода;

·          Проектирование компонентов.

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

Реализация. Реализация представляет собой процесс поэтапного написания кодов программы на выбранном языке программирования (кодирование), их тестирование и отладку.

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

·          Необходимость исправления ошибок, выявленных в процессе эксплуатации предыдущих версий;

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

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

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

Билет № 4  Классификация языков программирования.

1. Машинно – ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и т.д.). Машинно-ориентированные языки по степени автоматического программирования подразделяются на классы.  

1.1. Машинный язык. Отдельный компьютер имеет свой определенный Машинный язык (далее МЯ), ему предписывают выполнение указываемых операций над определяемыми ими операндами, поэтому МЯ является командным. Однако, некоторые семейства ЭВМ (например, ЕС ЭВМ, IBM/370/ и др.) имеют единый МЯ для ЭВМ разной мощности. В команде любого из них сообщается информация о местонахождении операндов и типе выполняемой операции.

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

1.3.Автокоды. Есть также языки, включающие в себя все возможности ЯСК, посредством расширенного введения макрокоманд - они называются Автокоды. Макрокоманды переводятся в машинные команды двумя путями – расстановкой и генерированием. В постановочной системе содержатся “остовы” - серии команд, реализующих требуемую функцию, обозначенную макрокомандой. Макрокоманды обеспечивают передачу фактических параметров, которые в процессе трансляции вставляются в “остов” программы, превращая её в реальную машинную программу. В системе с генерацией имеются специальные программы, анализирующие макрокоманду, которые определяют, какую функцию необходимо выполнить и формируют необходимую последовательность команд, реализующих данную функцию. Обе указанных системы используют трансляторы с ЯСК и набор макрокоманд, которые также являются операторами автокода.  Развитые автокоды получили название Ассемблеры. Сервисные программы и пр., как правило, составлены на языках типа Ассемблер.

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

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

3. Проблемно – ориентированные языки. С расширением областей применения вычислительной техники возникла необходимость формализовать представление постановки и решение новых классов задач. Необходимо было создать такие языки программирования, которые, используя в данной области обозначения и терминологию, позволили бы описывать требуемые алгоритмы решения для поставленных задач, ими стали проблемно – ориентированные языки. Эти языки, ориентированные на решение определенных проблем, должны обеспечить программиста средствами, позволяющими коротко и четко формулировать задачу и получать результаты в требуемой форме. Проблемных языков очень много, например: Фортран, Алгол – языки, созданные для решения математических задач; Simula, Слэнг - для моделирования; Лисп, Снобол – для работы со списочными структурами.

4. Универсальные языки были созданы для широкого круга задач: коммерческих, научных, моделирования и т.д. Первый универсальный язык был разработан фирмой IBM, ставший в последовательности языков Пл/1. Второй по мощности универсальный язык называется Алгол-68. Программы в Пл/1 компилируются с помощью автоматических процедур. Язык использует многие свойства Фортрана, Алгола, Кобола. Однако он допускает не только динамическое, но и управляемое и статистическое распределения памяти.

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

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

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

6. Непроцедурные языки. Непроцедурные языки составляют группу языков, описывающих организацию данных, обрабатываемых по фиксированным алгоритмам (табличные языки и генераторы отчетов), и языков связи с операционными системами.

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

Билет №5 Способы записи алгоритма

Алгоритмом называется система формальных правил, четко и однозначно определяющая процесс выполнения заданной работы в виде конечной последовательности действий или операций. Алгоритм, реализующий вычислительные операции, называется вычислительным алгоритмом. Любой алгоритм должен обладать следующими основными свойствами:1.детерминированностью - однозначностью получаемого результата при одних и тех же исходных данных;2.результативностью - обязательным получением некоторого искомого результата либо сигнала о том, что/данный алгоритм неприменим для решения поставленной задачи;3.массовостью - возможностью получения искомого результата при различных исходных данных для некоторого класса задач;4.дискретностью - возможностью разбиения алгоритма на отдельные элементарные действия, выполнение которых человеком или машиной не вызывает сомнения.

На практике различные формы представления алгоритмов:1. содержательная (текстуальная) форма;2.графическая форма (схемы алгоритмов);3.представление алгоритмов на языках программирования ЭВМ.

Рассмотрим перечисленные формы представления алгоритмов на примере решения следующей задачи. Пусть заданы три числа А₁, А₂, А₃. Требуется определить максимальное по абсолютному значению число А_max из заданного набора.

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

1.определить абсолютные значения чисел А₁, А₂, А_{3; ;} 2.сравнить абсолютные значения чисел А₁, А₂, 3.если абсолютное значение числа А₁ больше или равно абсолютному значению числа А₂ то числу А_max присвоить абсолютное значение числа А_2;

4.если абсолютное значение числа А₁ меньше абсолютного значения числа А₂, то числу А_max присвоить абсолютное значение числа А₂; 5.сравнить абсолютные значения чисел А₃ и А_max;

6.если абсолютное значение числа А₃ больше значения числа А_max, то числу А_max присвоить абсолютное значение числа А_3;

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

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

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

                                  Рис. 1. Условные графические обозначения в схемах алгоритмов

Схема алгоритма определения максимального по абсолютному значению числа А_max   из набора трех заданных чисел А₁, А₂, А₃ приведена на рис. 2.

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

Рис. 2. Схема алгоритма определения максимального по абсолютному значению числа из набора трех чисел 

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

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

Билет № 6: Программа как реализация алгоритма на ЯВУ.

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

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

При выполнении программ явно выделяются три объекта:

1.последовательность команд или процедура, которая определяет
программу;

2. процессор, который выполняет процедуру;

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

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

Можно выделить следующие свойства программы:

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

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

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

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

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

Структура программы на С++

Пример программы:

//Hello.cpp – имя файла с программой

#include <iostream.h>

void main ()

{cout << “\n Hello, Word!\n”;}

Результат выполнения программы: Hello, Word!

В первой строке программы – однострочный комментарий начинающийся парой символов //, заканчивающийся неизображаемым символом конца строки. Между этими символами можно написать произвольный текст. Во второй строке помещена команда (директива) препроцессора обеспечивающая включение в программу средств связи со стандартными потоками ввода и вывода данных, указанные средства находятся в файле iostream.h. третья строка является заголовком функции с именем main. Любая программа на языке С++ должна включать только одну функцию с этим именем. Именно с нее начинается выполнение программы. Перед именем main помещено служебное слово void – спецификатор типа, указывающий, что функция main в данной проге не возвращает ни какого значения. Круглые скобки после main требуются в соответствии с синтаксисом любой функции. В них помещаются список параметров, в нашем случае параметров нет. Тело любой функции – заключенная в фигурные скобки последовательность операторов. Каждое описание, определение или оператор заканчивается символом точка с запятой. В теле функции main явных описаний и определений нет есть только один оператор. cout << “\n Hello, Word!\n”; Имя cout в соответствии с информацией, содержащейся в файле iostream.h, является именем объекта, который обеспечивает вывод информации на экран дисплея. Информация для вывода передается объекту cout с помощью операции << («поместить в»). То что нужно вывести, помещается справа от знака операции<<. В данном случае строка - \n Hello, Word!\n

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

Билет№ 7. Стандартные типы данных

Основные {стандартные) типы данных часто называют арифметическими, поскольку их можно использовать в арифметических операциях. Для описания основных типов определены следующие ключевые слова: 1.• int (целый);• char (символьный);• wcha_t (расширенный символьный);• bool (логический);• float (вещественный);• double (вещественный с двойной точностью).

Первые четыре типа называют целочисленными {целыми), последние два — типами с плавающей точкой. Код, который формирует компилятор для обработки целых величин, отличается от кода для величин с плавающей точкой. Существует четыре спецификатора типа, уточняющих внутреннее представление и диапазон значений стандартных типов: • short (короткий);• long (длинный);• signed (знаковый);• unsigned (беззнаковый).

Целый тип (int) Размер типа int не определяется стандартом, а зависит от компьютера и компилятора. Для 16-разрядного процессора под величины этого типа отводится 2 байта,  для 32-разрядного — 4 байта. Спецификатор short перед именем типа указывает компилятору, что под число требуется отвести 2 байта независимо от разрядности процессора. Спецификатор long означает, что целая величина будет занимать 4 байта. Таким образом, на

16-разрядном компьютере эквиваленты int и short int, а на 32-разрядном — int и long int.

Внутреннее представление величины целого типа — целое число в двоичном коде. При использовании спецификатора signed старший бит числа интерпретируется как знаковый (0— положительное число, 1-отрицательное). Спецификатор unsigned позволяет представлять только положительные числа, поскольку старший разряд рассматривается как часть кода числа. Таким образом, диапазон значений типа 1nt зависит от спецификаторов. По умолчанию все целочисленные типы считаются знаковыми, то есть спецификатор signed можно опускать.

Символьный тип (char) Под величину символьного типа отводится количество байт, достаточное для размещения любого символа из набора символов для данного компьютера, что и обусловило название типа. Как правило, это 1 байт. Тип char, как и другие целые типы, может быть со знаком или без знака. В величинах со знаком можно хранить значения в диапазоне от -128 до 127. При использовании спецификатора unsigned значения могут находиться в пределах от 0 до 255. Этого достаточно для хранения любого символа из 256-символьного набора ASCII. Величины типа char применяются также для хранения целых чисел, не превышающих границы указанных диапазонов.

Расширенный символьный тип (wchar_t) Тип wchar_t предназначен для работы с набором символов, для кодировки которых недостаточно 1 байта, например, Unicode. Размер этого типа зависит от реализации; как правило, он соответствует типу short. Строковые константы типа wchar_t записываются с префиксом L, например, L"Gates".

Логический тип (bool) Величины логического типа могут принимать только значения true и false, являющиеся зарезервированными словами. Внутренняя форма представления значения

false — О (нуль). Любое другое значение интерпретируется как true. При преобразовании к целому типу true имеет значение 1.

Типы с плавающей точкой (float, double и long double) Стандарт C++ определяет три типа данных для хранения вещественных значений: float, double и long double. Типы данных с плавающей точкой хранятся в памяти компьютера иначе, чем целочисленные.

Внутреннее представление вещественного числа состоит из двух частей — мантиссы и порядка. В IBM PC-совместимых компьютерах величины типа float занимают 4 байта, из которых один двоичный разряд отводится под знак мантиссы, 8 разрядов под порядок и 23 под мантиссу. Мантисса — это число, большее 1.0, но меньшее 2.0. Поскольку старшая цифра мантиссы всегда равна 1, она не хранится. Для величин типа double, занимающих 8 байт, под порядок и мантиссу отводится И и 52 разряда соответственно. Длина мантиссы определяет точность числа, а длина порядка — его диапазон. Как можно видеть из табл. 1.4, при одинаковом количестве байт, отводимом под величины типа float и long int, диапазоны их

допустимых значений сильно различаются из-за внутренней формы представления. Спецификатор long перед именем типа double указывает, что под величину отводится 10 байт. Константы с плавающей точкой имеют по умолчанию тип double. Для вещественных типов в таблице приведены абсолютные величины минимальных и максимальных значений.

Билет №9 Процедуры и функции.

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

Любая программа на C++ состоит из функций, одна из которых должна иметь имя main (с нее начинается выполнение программы). Функция начинает выполняться в момент вызова. Любая функция должна быть объявлена и определена. Как и для других величин, объявлений может быть несколько, а определение только одно. Объявление функции должно находиться в тексте раньше ее вызова для того, чтобы компилятор мог осуществить проверку правильности вызова. Объявление функции (прототип, заголовок, сигнатура) задает ее имя, тип возвращаемого значения и список передаваемых параметров. Определение функции содержит, кроме объявления, тело функции, представляющее собой последовательность операторов и описаний в фигурных скобках:

[ класс ] тип имя ( [ список_параметров ])[throw ( исключения )]

{ тело функции }

Рассмотрим составные части определения.

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

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

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

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

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

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

#include <iostream.h>

int sum(int a. int b); // объявление функции     int main(){      int a = 2, b = 3, c, d;    с = sum(a, b); // вызов функции

cin » d;    cout « sum(c, d); // вызов функции    return 0;}

int sum(int а. int b){ // определение функции        return (а + b);}

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

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

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

Возвращаемое значение. Механизм возврата из функции в вызвавшую ее функцию реализуется оператором return [ выражение ] ; Функция может содержать несколько операторов return

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

Билет№8 Представление базовых алгоритмических структур:

линейной, ветвления и цикла

Следование, ветвление и цикл называют базовыми конструкциями структурного программирования

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

Пример программы по алгоритму следования

# include <iostream.h>

void main ()

{ int a,b,c;   cout<<”Введите а:”;  cin>>a;

cout<<”\nВведите b:”;  cin>>b;  c=a+b;

cout<<”\nРезультат выражения a + b =”<<c;

return 0;}

Второй базовой структурой является Ветвление. Эта структура обеспечивает в зависимости от результата проверки условия (истина или ложь) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма продолжается независимо от того, какой путь будет выбран. Основные операторы ветвления – условный оператор if, оператор switch.

Условный оператор if используется для разветвления процесса вычислений на два направления. Формат оператора: i f ( выражение ) оператор_1; [else оператор_2;]

Сначала вычисляется выражение. Если оно имеет значение true, выполняется первый оператор, иначе — второй. После этого управление передается на оператор, следующий за условным.

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

Примеры:

i f (а<0) b = 1; - пример ветвления с отсутствием одной ветви ветвления

i f (a<b && (a>d || a==0)) b++; else {b *- a: a = 0;} пример с проверкой нескольких условий

i f (b>a) max = b: else max = a; стандартный вид

Оператор switch (переключатель) предназначен для разветвления процесса вычислений на несколько направлений. Формат оператора:

switch ( выражение ){

case константное_выражение_1:     [список_операторов_1]

case константное_выражение_2:     [список_операторов_2]

…case константное_выражение_n: [список_операторов_п]

[default: операторы ] }

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

Выход из переключателя обычно выполняется с помощью операторов break или return.

Пример (программа реализует простейший калькулятор на 4 действия):

#include <iostream.h>

int main(){

int a, b, res; char op;

cout « "\nВведите 1й операнд: ";    cin » a; cout « "\nВведите знак операции: "; cin » op;

cout « "\nВведите 2й операнд: ";    cin » b; bool f = true;

switch (op) {case '+': res = a + b; break; case '-':  res = a – b; break; case '*':  res = a * b; break; case ‘/’:  res = a / b; break;

default: cout <<"\пНеизвестная операция”; f=false;}

If (f) cout<<"\nРезультат: "<<res; eturn 0;}

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

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

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

C++ есть три разных оператора цикла —while, do while и for.

Цикл с предусловием (while)

Цикл с предусловием имеет вид: while ( выражение ) оператор

Выполнение оператора начинается с вычисления выражения. Если оно истинно (не равно false), выполняется оператор цикла. Если при первой проверке выражение равно false, цикл не выполнится ни разу. Тип выражения должен быть арифметическим или приводимым к нему. Выражение вычисляется перед каждой итерацией цикла.

Пример (программа находит все делители целого положительного числа):

#inclucle <iostream.h>

int main(){

int num;  cout « "\nВведите число : "; cin » num;

int half = num / 2: // половина числа    int div = 2: // кандидат на делитель

while (div <= half){ if (!(num % div))  cout « div « " \ n ";  div++;  }return 0;}

Цикл с постусловием (do while)

Имеет вид: do оператор while выражение;

Сначала выполняется простой или составной оператор, составляющий тело цикла, а затем вычисляется выражение. Если оно истинно (не равно false), тело цикла выполняется еще раз. Цикл завершается, когда выражение станет равным false или в теле цикла будет выполнен какой-либо оператор передачи управления. Тип выражения должен быть арифметическим или приводимым к нему.

Пример (программа осуществляет проверку ввода):

#include <iostream.h>

int main (){

char answer;

do{ cout « "\пКупи слоника! "; cin » answer; }

while (answer != 'y');

return 0;}

Цикл с параметром (for)

Имеет следующий формат: for (инициализация; выражение; модификации) оператор;

Инициализация используется для объявления и присвоения начальных значений величинам, используемым в цикле. Выражение определяет условие выполнения цикла: если его результат, приведенный к типу bool, равен true, цикл выполняется. Цикл с параметром реализован как цикл с предусловием. Модификации выполняются после каждой итерации цикла и служат обычно для изменения параметров цикла.

Пример (оператор, вычисляющий сумму чисел от 1 до 100):    for (int i = 1, s = 0; i<=100; i++) s += 1;

Пример (программа находит все делители целого положительного числа):

#include <iostream.h>

int main(){

int num. half, div;  cout « "\пВведите число : "; cin » num;

for (half = num / 2, div = 2; div <= half; div++)

if (!(num % div))cout « div «"\n":

return 0;}

Билет №10 Рекурсивные функции

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

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

long fact (int n)

{ if ( n<1 ) return 1;

else return n*fact(n-1);  }

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

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

void f2();
void f1(){

 …

 if (…);
f2();
     …}

void f2(){
    …
     f1();
     …}

Билет №11 Структуры, файлы, списки

Файлы.Под файлом обычно подразумевается именованная информация на внешнем носителе, например, на жестком или гибком магнитном диске. Логически файл можно представить как конечное количество последовательных байтов, поэтому такие устройства, как дисплей, клавиатуру и принтер также можно рассматривать как частные случаи файлов. По способу доступа файлы можно разделить на последовательные, чтение и запись в которых производятся с начала байт за байтом, и файлы с произвольным доступом, допускающие чтение и запись в указанную позицию. Стандартная библиотека содержит три класса для работы с файлами: ifstream — класс входных файловых потоков;ofstream— класс выходных файловых потоков;fstream — класс двунаправленных файловых потоков.

Эти классы являются производными от классов istream, ostream и iostream соответственно, поэтому они наследуют перегруженные операции « и » , флаги форматирования, манипуляторы, методы, состояние потоков и т. д.

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

Каждый класс файловых потоков содержит конструкторы, с помощью которых можно создавать объекты этих классов различными способами.• Конструкторы без параметров создают объект соответствующего класса, не связывая его с файлом: ifstream();ofstream();fstream();•Конструкторы с параметрами создают объект соответствующего класса, открывают файл с указаным именем и связывают файл с объектом:

ifstream(const char *nаmе, int mode = ios::in);

ofstream(const char *name, int mode = ios::out | ios::trunc);

fstream(const char *name, int mode = ios::in | ios::out);

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

enum open_mode{in=0x01,// Открыть для чтения;out=0x02,// Открыть для записи;ate=0x04,// Установить указатель на конец файла;app=0x08,// Открыть для добавления в конец;trunc=0x10// Если файл существует, удалить;nocreate=0x20,//Если файл не существует, выдать ошибку;noreplace=0x40,/// Если файл существует, выдать ошибку;binary=0x80// Открыть в двоичном режиме};

Открыть файл в программе можно с использованием либо конструкторов, либо метода open, имеющего такие же параметры, как и в соответствующем конструкторе, например:

ifstream inpf ("input.txt", , ios::in|ios::nocreate); //Использование конструктора

if(!inpf){ cout « "Невозможно открыть файл для чтения"; return 1;}

ofstream f;

f.open("output.txt"); // Использование метода open

if (!f){ cout « "Невозможно открыть файл для записи";return 1; }

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

#include <fstream.h>

int main(){

char text[81]. buf[81]:

cout « "Введите имя файла:"; cin » text;

ifstream f(text, ios::in | ios::nocreate);

if (!f){ cout « "Ошибка открытия файла"; return 1;}

while (!f.eof()){ f.getline(buf. 81); cout « buf « endl;} 

return 0;}

Для закрытия потока определен метод close(), но поскольку он неявно выполняется деструктором, явный вызов необходим только тогда, когда требуется закрыть поток раньше конца его области видимости.

Структуры (struct) - В отличие от массива, все элементы которого однотипны, структура может содержать элементы разных типов. В языке C++ структура является видом класса и обладает всеми его свойствами, но во многих случаях достаточно использовать структуры так, как они определены в языке С:

struct [ имя_типа ] {

тип_1 элемент_1;

тип_2 элемент_2;

тип_n элемент_n;

} [ список_описателей ];

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

/ / Определение массива структур и указателя на структуру:

struct { char fio[30];int date, code;double salary;} staff[100]. *ps;

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

struct Worker{ // описание нового типа Worker

 char f1o[30]; int date, code;double salary;}; // описание заканчивается точкой с запятой

/ / определение массива типа Worker и указателя на тип Worker: Worker staff[100]. *ps;

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

Для инициализации структуры значения ее элементов перечисляют в фигурных скобках в порядке их описания:

struct{char fio[30];int date, code;double salary;}worker = {"Хаб-а", 31, 215, 3400.55};

Пример инициализации массивов структур:

struct complex{ float real, im;} compl [2][3] = { {{1,1},{1,1},{1,1}}, // строка 1. TO есть массив compl[0]

{{2,2},{2,2},{2,2}}}; // строка 2. то есть массив compl[1]

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

Доступ к полям структуры выполняется с помощью операций выбора “.” (точка) при обращении к полю через имя структуры и -> при обращении через указатель, например:

Worker worker, staff[100], *ps; … worker.fio = "Хаб-а";   staff[8].code = 215;  ps->salary = 0.12;

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

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

Доступ к элементам для списков ограничивается следующими методами:

reference front();   const_reference front() const;    reference back();   const_reference back() const;

Для занесения в начало и конец списка определены методы, аналогичные соответствующим методам очереди:

void push_front(const Т& value); void pop_front(); void push_back(const T& value); void pop_back();

Кроме того, действуют все остальные методы для изменения объектов list, аналогичные векторам и очередям:

iterator insert(iterator position, const Т& value);  void insert(iterator position, size_type n, const T& value);

template <class InputIter>

void insert(iterator position, InputIter first, InputIter last); iterator erase(iterator position);

iterator erase(iterator first , iterator last);  void swap();  void clear();

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

void splice(iterator position, list<T>& x); void splice(iterator position, list<T>& x, iterator i );

void splice(iterator position, list<T>& x, iterator first , iterator last);

Для удаления элемента по его значению применяется функция remove:

void remove(const Т& value);

Если элементов со значением value в списке несколько, все они будут удалены.

Для упорядочивания элементов списка используется метод sort:

void sort();  template <class Compare> void sort(Compare comp):

Для слияния списков служит метод merge:

void merge(list<T>& x);  template <class Compare> void merge(list<T>& x, Compare comp);

Метод reverse служит для изменения порядка следования элементов списка на обратный (время работы пропорционально количеству элементов):

void reverse();