В. Ю. Наумов Введение в информатику
 Скачать 2.05 Mb.
|
|
FALSE, исполнение тела завершается и управление передается структуре, следующей далее по стрелке. 13 Очень часто в предикатных узлах для проверки логической переменной ее сравнивают с одной из двух возможных логических констант (TRUE или FALSE), что не является алгоритмической ошибкой. Однако не стоит забывать, что сама по себе логическая переменная уже равна TRUE или FALSE, а потому нет необходимости в избыточной проверке. Описанную ситуацию можно отнести к стилистическим ошибкам, которые могут быть свойственны новичкам в программировании. L Тело цикла Рис. 2.9. Цикл с предусловием 49 ПРИМЕР Разработаем алгоритм (блок-схему) вычисления факториала некоторого натурального числа N . ! F N N Напомним, что ! 1 2 ... ( 1) N N N Можно заметить, что для вычисления факториала справедлива рекуррентная формула 1 F K F K K Вообще, понятие рекуррентности и рекурсии в программировании играют большую роль. Следует напомнить, что рекуррентной называется последовательность, для которой текущий ее член определяется через предыдущий. Соответственно функция называется рекурсивной, если она может вызывать сама себя. Всегда в рекуррентном соотношении должна существовать точка входа. Для факториала таковой является определение 0! 1 Для вычисления факториала будем использовать рекуррентное выражение F F I . В этой формуле вместо I последовательно подставляются натуральные числа от 1 до N. При первом ее использовании F возьмем равным 1 (точка входа), так как число I, умноженное на 1, останется равным I, т. е. после первого шага переменная F станет 1 F I Дальнейшее умножение на 2, 3 (и т. д. до N) даст факториал числа ( ) ! F N N Рассмотрим, как работает данный алгоритм (рис. 2.10). Пусть при вводе N будет введено значение N=4, тогда перед входом в цикл переменные будут иметь следующие значения: N=4; I=1; F=1. 50 При входе в цикл анализируется логическое выражение «I≤N». Для текущих значений I=1 и N=4 оно даст результат TRUE, т. е. будет выполняться тело цикла. В нем на первом шаге новое значение F получается путем умножения его старого значения на I (именно так нужно читать формулу * F F I ), т. е. 1*1 1 F . Вторая формула увеличивает I на 1, т. е. 1 1 2 I В результате выполнения первого прохода тела цикла переменные примут следующие значения: N=4; I=2; F=1. Следуя далее по стрелке, возвращаемся к предикатному блоку с логическим выражением и анализируем его для новых значений переменных. Результат опять TRUE. После выполнения второго прохода переменные примут такие значения: N=4; I=3; F=2. Логическое выражение снова даст результат TRUE. В третьем проходе получим: N=4; I=4; F=6. Логическое выражение равно TRUE. В четвертом проходе N=4; I=5; F=24. И только после этого прохода логическое выражение становится равным FALSE, т. е. выполнение цикла завершается и происходит переход на шаг вывода значения F. Результат I ≤ N F = F * I Ввод N Начало F = 1 I = 1 I = I + 1 Вывод F Конец Рис. 2.10. Алгоритм расчета факториала (цикл с предусловием) 51 F=24 легко проверить в уме: (4) 4! 1 2 3 4 24 F , следовательно, алгоритм верен. Следующий вид цикла носит название «цикл с постусловием», или цикл «до» (цикл выполняется до проверки логического выражения, до получения в качестве результата логического выражения L значения FALSE). В C++ этот цикл записывается «do … while». На блок-схеме изображается так, как показано на рис. 2.11. Важное замечание. Можно подобрать такие начальные значения операндов логического выражения, что тело цикла с предусловием ни разу не будет выполнено, но невозможно подобрать подобные значения для цикла с постусловием (его тело выполняется всегда хотя бы один раз). Это замечание может быть доказано, если проанализировать блок-схемы рассмотренных циклов. Тело цикла I = 1, I L Тело цикла + - Рис. 2.11. Цикл с постусловием 52 У цикла с предусловием существует стрелка обхода тела, а у цикла с постусловием такого обхода нет (через цикл можно пройти лишь только сквозь его тело). На рис. 2.13 представлена блок-схема алгоритма вычисления факториала числа N с помощью цикла с постусловием. Ввод N Начало F = 1 I = 1 Вывод F Конец F = F * I I = I + 1 I>N + - Рис. 2.13. Алгоритм расчета факториала (цикл с постусловием) Ввод N Начало F = 1 Вывод F Конец F = F * I I = 1, I (цикл с параметром) 53 Третий цикл – цикл с параметром, или, как его еще называют «цикл For». В упрощенном виде этот цикл работает следующим образом. Параметру I присваивается его начальное значение K; далее выполняется тело цикла, в котором этот параметр может быть использован; затем к текущему значению параметра I прибавляется шаг M и вновь выполняется тело цикла. Так продолжается до тех пор, пока условие I≤N истинно (рис. 2.12). Вообще, цикл For является модификацией цикла с предусловием. Просто настолько часто возникают задачи, в которых параметр цикла меняет свое значение с постоянным шагом на некотором диапазоне, что в языки программирования внедрили этот специальный цикл. Более того, именно его наиболее часто используют в большинстве программ. Задача вычисления факториала с помощью этого цикла выглядит гораздо проще (рис. 2.14). Как уже отмечалось ранее, блок-схемы представляют собой одну из форм записи последовательности действий. Поскольку решено использовать ограниченный набор базовых блоков, то, естественно, с их помощью можно изобразить не всякий алгоритм. Кроме того, базовых алгоритмических конструкций в рамках структурного программирования всего три. Каждая из этих конструкций имеет ровно один вход и ровно один выход. Потому, для сохранения наглядности, всегда изображают выход из конструкции строго под ее входом, на одной оси (рис. 2.15). Следующее правило уже озвучивалось ранее и предназначено для различения конструкций развилок и конструкций циклов. Обе они изображаются при помощи блока предиката. Но в циклах принято вход в его тело (или выход из него) обозначать стрелкой, выходящей из крайней нижней точки ромба вниз, а в разветвляющихся алгоритмических конструкциях плечи рисуются горизонтально. Причем для развилок 54 положительную ветвь можно рисовать как влево, так и вправо, а для циклов языка С++ положительное направление всегда направляют вниз. Особенность структурного программирования – наличие внутри каждой элементарной конструкции блока действия. Так вот, вместо этого блока может быть любая другая базовая конструкция; внутри этой базовой конструкции может опять стоять любая базовая конструкция и т. д. В итоге иерархия вложенных структур может быть весьма большой. Вследствие этого, блок-схема не помещается на одном листе и ее наглядность страдает. Для корректного дробления алгоритмов часть вложенных действий заменяют одним блоком (прямоугольником, внутри которого пишут описание производимого действия) с нумерацией потока входа и потока выхода. Далее, в удобном месте пишут название этого блока и шаги, которые он заменяет. Пример пошаговой детализации приведен на рис. 2.16. Еще одним признаком корректности изображения блок-схемы является факт непересечения поточных линий. Если при составлении блок-схемы линии пересекаются, то нужно попытаться представить ее так, чтобы эти пересечения ушли. Если этого сделать нельзя, то блок-схема составлена неправильно (вне рамок структурного программирования). вход выход вход выход вход выход + - Рис. 2.15. Симметрия в обозначении базовых алгоритмических конструкций 55 На блок-схеме не должно быть блоков (кроме терминаторов), в которые есть вход и нет выхода, так называемых «висячих» блоков. Вход в алгоритмическую структуру происходит сверху, а выход – снизу. То есть всегда строго сверху вниз, а не с боков и уж, тем более, не с низу наверх. Использование базовых алгоритмических конструкций показано на рис. 2.16; на нем можно различить все их типы, а также входы и выходы. вход выход вход выход вход1 вход2 выход1 выход2 вход1 выход1 вход2 выход2 + - Рис. 2.16. Вложенные алгоритмические конструкции 56 3. ОСНОВНЫЕ СВЕДЕНИЯ О ЯЗЫКЕ С++ 3.1. Алфавит языка. Идентификаторы Как и разговорный язык, язык программирования обладает своим алфавитом. Из символов алфавита выстраиваются слова, а из них, в свою очередь, – предложения. В С++ из алфавита формируются зарезервированные слова, идентификаторы (имена процедур, функций, переменных, констант и т. д.), выражения (алгебраические, логические и т. д.), значения констант и переменных, описание типов и т. п. Алфавит языка состоит из следующих наборов символов: – по 26 прописных A .. Z и 26 строчных a..z букв латиницы, знака подчеркивания _; – арабские цифры 0 .. 9; – знаки арифметических операций: + – * / ; – знаки операций отношения: > < = ; – скобки: ( ) [ ] { } ; – разделители: . , : ; ; – апостроф: ‘ ; – специальные символы: @, #, $, ^, &. В языке С++ прописные и строчные буквы латиницы различаются, поэтому нужно быть очень внимательным при использовании переменных в оразных регистрах. Первоночально рекомендуется использовать при написании программ только строчные буквы, это позволит избежать массы ошибок. Кроме этого, здесь не отмечены иные символы таблицы ASCII, которые могут быть использованы в комментариях, в строковых или символьных константах. Это, прежде всего, символы кириллицы. Язык С++ обладает целым рядом служебных (зарезервированных) слов, которые нельзя использовать в качестве пользовательских 57 (придуманных пользователем) имен типов, переменных и других идентификаторов: asm auto bool break case catch char class const const_cast continue default delete do double dynamic_cast else enum explicit export extern false float for friend goto if inline int long mutable namespace new operator private protected public register reinterpret_cast return short signed sizeof static static_cast struct switch template this throw typedef true try typeid typename union voidunion using virtual void Идентификаторы – имена переменных констант, процедур, функций и т. д. Идентификаторы могут состоять только из букв латиницы, цифр и символа «_». Чтобы текст программы был более понятным, рекомендуется придерживаться общепринятых соглашений об именах объектов: – имя переменной обычно пишется строчными буквами, например index; – идентификатор должен нести какой-либо смысл, поясняя назначение объекта в программе, например: first_index; – если имя состоит из нескольких слов, как, например, first_index, то принято либо разделять слова символом подчеркивания (first_index), либо писать каждое следующее слово с большой буквы (FirstIndex). 58 ПРИМЕР Правильные: A; B; Next; ffFRt; _EE; IvanovIvan; d2w; x3; Ivanov_Ivan; Неправильные: 1x {начинается с цифры}; Ivanov Ivan {пробел в имени}; Sob@ka {использование спецсимвола}; while {зарезервированное слово}; Q2-R {использование запрещенного символа}. 3.2. Структура программы на языке C++ В С++ действие называется выражением, а выражение, заканчивающееся точкой с запятой, - инструкцией. Инструкция - это атомарная часть С++ программы, которой можно поставить в соответствие предложение естественного языка. Программа на языке C++ имеет следующую структуру: # <директивы препроцессора> <описание функций> int main() { <тело программы> return 0; } Заголовочные файлы включаются в текст программы с помощью директивы препроцессора #include. Директивы препроцессора начинаются со знака "диез" (#), который должен быть самым первым символом строки. Программа, которая обрабатывает эти директивы, называется 59 препроцессором (в современных компиляторах препроцессор обычно является частью самого компилятора). Директива #include включает в программу содержимое указанного файла. Имя файла может быть указано двумя способами: #include #include "my_file.h" Если имя файла заключено в угловые скобки (<>), считается, что нам нужен некий стандартный заголовочный файл, и компилятор ищет этот файл в предопределенных местах. (Способ определения этих мест сильно различается для разных платформ и реализаций.) Двойные кавычки означают, что заголовочный файл - пользовательский, и его поиск начинается с того каталога, где находится исходный текст программы. Имя файла с текстом программы, или исходного файла, как правило, состоит из двух частей: собственно имени (например, bookstore) и расширения, записываемого после точки. Расширение, в соответствии с принятыми соглашениями, служит для определения назначения файла. Файл bookstore.h является заголовочным файлом для Си или С++ программы. (Необходимо отметить, что стандартные заголовочные файлы С++ являются исключением из правила: у них нет расширения.) Заголовочные файлы С++ программ могут иметь разные расширения в разных реализациях (и это одна из причин того, что стандартные заголовочные файлы С++ не имеют расширения). Расширения, используемые в конкретной реализации компилятора С++, указаны в поставляемой вместе с ним документации. Далее идет описание функций, про них подробнее будет расказано дальше, main() также является функцией, но функция main() является основной и должна быть единственной с таким именем во всей программе. Исполнение программы начинается с выполнения первой инструкции функции main(), затем одна за другой исполняются все 60 дальнейшие инструкции, и, выполнив последнюю инструкцию функции main() , программа заканчивает работу. Последней выполняется инструкция return 0; Инструкция return обеспечивает механизм завершения работы функции. Если оператор return сопровождается некоторым значением (в данном примере 0), это значение становится возвращаемым значением функции. В нашем примере возвращаемое значение 0 говорит об успешном выполнении функции main(). (Стандарт С++ предусматривает, что функция main() возвращает 0 по умолчанию, если оператор return не использован явно.) Можно выделить условный вид блоков программ, который называется комментариями. Комментарии играют очень большую роль при написании программы, поскольку помогают справиться с ее возрастающей сложностью. По прошествии некоторого времени, при повторном обращении к исходному коду для внесения в него исправлений или модификации, возникает ситуация забывания подробностей. Если комментарии расставлены грамотно, то вспомнить подробности работы алгоритма не составит труда. Кроме того, комментарии помогают разбираться в ваших алгоритмах тому, кто с ними будет работать в дальнейшем. Сами по себе разделы комментариев пропускаются компилятором и на работу алгоритма никакого влияния не оказывают. В языке С++ блок комментариев выделяется сочетанием символов «/*» – начало комментария и «*/» – конец комментария. Наиболее же часто используют так называемые однострочные комментарии. Начало такого комментария обозначается комбинацией «//», а конец – переходом на новую строчку. 61 3.3. Типы данных в С++ С++ является языком со строгим контролем типов, что означает четкое определение размера места занимаемого переменной в памяти, правила работы с этой переменной и порядок преобразования ее значения к другому типу. Данные отображают в программе окружающий мир. Цель программы состоит в обработке данных. Данные различных типов хранятся и обрабатываются по-разному. Тип данных определяет: – внутреннее представление данных в памяти компьютера; – множество значений, которые могут принимать величины этого типа; – операции и функции, которые можно применять к данным этого типа. В зависимости от требований задания программист выбирает тип для объектов программы. Типы С++ можно разделить на простые и составные. К простым типам относят типы, которые характеризуются одним значением. В С++ определено 6 простых типов данных: (табл. 3.1). Существует 4 спецификатора типа, уточняющих внутреннее представление и диапазон стандартных типов: short (короткий), long (длинный), signed (знаковый), unsigned (беззнаковый). 62 Таблица 3.1 Основные типы языка C++ Категория Тип Описание Целые числа char целочисленный тип, обычно содержащий члены кодировки ASCII. bool целочисленный тип, который может иметь одно из двух значений: true или false. int целочисленный тип Числа с плавающей запятой float тип с плавающей запятой наименьшего размера double тип с плавающей запятой, повышенной точности Расширенные символы __wchar_t Переменная __wchar_t обозначает тип расширенных символов или многобайтовых символов. Основные типы в С++ делятся на три категории: целочисленные, с плавающей запятой и void. Целочисленные типы позволяют обрабатывать целые числа.Типы с плавающей запятой позволяют задавать значения, которые могут иметь дробные части. Типом void описывается пустой набор значений. Задание переменных типа void невозможно. Этот тип служит в основном для объявления функций, не возвращающих значения, или универсальных указателей на нетипизированные или произвольно типизированные данные. |