Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

алгоритмизация и программирование 2 глава




Общие правила построения схемы алгоритма задачи

1. Выявить исходные данные, результаты, назначить им имена.

2. Выбрать метод (порядок) решения задачи.

3. Разбить метод решения задачи на этапы (с учетом возможностей ЭВМ).

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

5. В полученной схеме при любом варианте вычислений:

а) предусмотреть выдачу результатов или сообщений об их отсутствии;

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

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


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

- структурированные;

- неструктурированные (т.е. с нарушением структуры – с операторами безусловного перехода);

- вспомогательные (используемые в составе других алгоритмов).

Виды алгоритмов

- линейный алгоритм;

- алгоритм ветвления;

- циклический алгоритм;

- алгоритм с подпрограммами;

- смешанные (т.е. содержащие и циклы, и ветвление, и функции).

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

Базовые алгоритмические конструкции

Структу́рное программи́рование – методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70-х годах XX века Э. Дейкстрой, разработана и дополнена Н. Виртом. Основывается на теореме о структуре.

Согласно теореме о структуре (теорема Бёма – Якопини, 1966 г) логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл.

Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.

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

2. Базовая структура ветвление (алгоритм ветвления) обеспечивает в зависимости от результата проверки условия выбор одного из альтернативных путей работы алгоритма. Условие – вопрос, имеющий два варианта ответа: да или нет. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Запись ветвления выполняется в двух формах: полной и неполной.


 

Структура ветвление существует в четырех основных вариантах:

Неполная форма записи Полная форма записи
1. если-то 2. если-то-иначе
3. выбор 4. выбор-иначе

Примеры команды если


Пример: найти наименьшее из трех чисел.

1 вариант решения: 2 вариант решения:

ЦИКЛЫ
с неизвестным числом повторов
с предусловием (цикл «пока»)
с известным числом повторов (цикл «для»)
с постусловием (цикл «до»)
3. Базовая структура цикл обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла, над новыми данными.

 

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

Зацикливание - бесконечное повторение выполняемых действий.

Цикл типа «до»
Тело цикла
Условие
+
Исполнение цикла начинается с выполнения действия. Таким образом, тело цикла будет реализовано хотя бы один раз. После этого происходит проверка условия. Поэтому цикл "до" называют циклом с постусловием. Если условие выполняется, то происходит возврат к выполнению действий, иначе осуществляется выход из цикла. Для предотвращения зацикливания необходимо предусмотреть действия, приводящие к ложности условия.

Цикл типа «для» Цикл с параметром, или цикл со счетчиком, или арифметический цикл - это цикл с заранее известным числом повторов. Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.
x = x0..xn, h
тело цикла
х0 – начальное значение параметра; h – шаг; хn – последнее значение параметра.

 

Для создания циклов с параметром необходимо использовать правила:

1. Параметр цикла, его начальное и конечное значения и шаг должны быть одного типа.

2. Запрещено изменять в теле цикла начальное, текущее и конечное значения для параметра.

3. Запрещено входить в цикл, минуя блок модификации.

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

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

1.3. Теоретические основы программирования

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

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

Языки программирования – это совокупность средств и правил представления алгоритма в виде, приемлемом для компьютера.

Системы программирования – это набор средств ввода, редактирования, трансляции и выполнения программ на ЭВМ.

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

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

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

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

Например, компилятор берет программу, написанную на языке C, и преобразует ее в программу на языке ассемблера.

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

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

1.4. Правила записи в С++ арифметических выражений

Арифметические выражения

Выражение состоит из операторов и операндов. Операндами могут быть, в свою очередь, выражения или одни из его частных случаев – числа (константы) или переменные, операторы обозначают выполняемые над ними действия (+ сложение, - вычитание, * умножение, / деление (для целых операндов – целая часть от деления), % остаток от деления (только для целых), …).

Все основные операции языка С++ можно разбить на следующие группы:


- арифметические операции;

- логические операции;

- операции отношения;

- операции с битами информации;

- операции со строками;

- операции присваивания;

- операция sizeof;

- условная операция (?:).


Примеры выражений:

(a + 0.12)/6

x && ||!z

(t * sin(x)-1.05e4)/((2 * k + 2) * (2 * k + 3))

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

Порядок вычисления выражений определяется рангом (приоритетом) входящих в него операций (табл. 3). Принятый в С++ ранг операций наиболее близок к математическому, также как и принятый порядок их вычисления. Так, умножение и деление (мультипликативные операции) старше сложения и вычитания (аддитивные операции). Унарные операции + и – старше бинарных, т.е., знак операнда вычисляется в первую очередь. Операции типа присваивания младше прочих, что позволяет выполнить их только после того, как значение выражения вычислено полностью. Операции отношения младше арифметических операций, что позволяет использовать естественную запись логических выражений, например, x>0 && y>0. Здесь в первую очередь вычисляются значения отношений, которые затем являются операндами конъюнкции.

Таблица 1 – Порядок вычисления выражений

Группа Тип действий Операции или элементы
  Вычисления в круглых скобках ()
  Вычисления значений функции Функции
  Унарные операции ++, --, ~,!, унарные - и +, &, * (разадресация), …
  Операции типа умножения *, /, %
  Операции типа сложения +, –
  Операции отношения <, <=, >, >=, ==,!=

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

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

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

- Запись ведётся в строчку.

- Нельзя опускать знак умножения между сомножителями.

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

- Операции выполняются в соответствии с приоритетами: сначала вычисление функций, затем умножение и деление, потом сложение и вычитание.

- Если в одном выражении записано несколько операций одинакового приоритета, унарные операции, условная операция и операции присваивания выполняются справа налево, остальные – слева направо. Например, a = b = c означает a = (b = c), а a + b + с означает (a + b) + c.

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

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

- В языке С++ предусмотрены базовые математические операции (см. прил. 2).

Примеры записи выражений:

Математическое выражение Запись на C++
1. 1. 10 * x + 3 * sqrtf(cos(x))
2. 2. (sin(2*x) - 1) / (pow(x, 2) - 1)
3. 3. abs(x) + 2 * cos(x) / sin(x)

Лабораторная работа № 1
Запись арифметических выражений

ЦЕЛЬ РАБОТЫ: закрепление знаний по теоретическим основам алгоритмизации и программирования, приобретение навыков использования арифметических операций, функций и правил записи арифметических выражений согласно синтаксису языка C++.

Выполнение работы: записать следующие выражения по правилам языка C++.

Задание I

1. sin 5 x + 2 tg x 2 5. ;
2. 2x + 3y2 - sin3x 6. ;
3. 7. ;
4. 8.

Задание II

Выполнить согласно варианту:

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. , .

Контрольные вопросы

1. Что такое алгоритм?

2. Перечислите свойства алгоритмов.

3. Способы записи алгоритма.

4. Перечислите базовые алгоритмические конструкции. Какова блок-схема следования?

5. Какова блок-схема полной (неполной) формы команды ветвления?

6. Какова блок-схема цикла с предусловием?

7. Какова блок-схема цикла с постусловием?

8. Какова блок-схема цикла с параметром?

9. Что такое программа?

10. Что такое транслятор?

11. Что такое компилятор?

12. Что такое интерпретатор?

13. Что такое оператор и операнд?

14. В каких случаях при записи математических выражений на языке С++ используются круглые скобки?

15. Как используются стандартные математические функции в С++?


2. Программирование алгоритмов линейной структуры

2.1. Общая характеристика языка программирования С++

C++ – компилируемый статически типизированный язык программирования общего назначения.

Поддерживает такие парадигмы программирования как процедурное программирование, объектно-ориентированное программирование, обобщённое программирование, обеспечивает модульность, раздельную компиляцию, обработку исключений, абстракцию данных, объявление типов (классов) объектов, виртуальные функции. Стандартная библиотека включает, в том числе, общеупотребительные контейнеры и алгоритмы. C++ сочетает свойства как высокоуровневых, так и низкоуровневых языков. В сравнении с его предшественником – языком C, – наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования.

C++ широко используется для разработки программного обеспечения, являясь одним из самых популярных языков программирования. Область его применения включает создание операционных систем, разнообразных прикладных программ, драйверов устройств, приложений для встраиваемых систем, высокопроизводительных серверов, а также развлекательных приложений (игр). Существует множество реализаций языка C++, как бесплатных, так и коммерческих и для различных платформ. Например, на платформе x86 это GCC, Visual C++, Intel C++ Compiler, Embarcadero (Borland) C++ Builder и другие. C++ оказал огромное влияние на другие языки программирования, в первую очередь на Java и C#.

Синтаксис C++ унаследован от языка C. Одним из принципов разработки было сохранение совместимости с C. Тем не менее, C++ не является в строгом смысле надмножеством C; множество программ, которые могут одинаково успешно транслироваться как компиляторами C, так и компиляторами C++, довольно велико, но не включает все возможные программы на C [1].

2.2. Основные понятия языка

Основу любого языка программирования образуют три, его составляющие: алфавит, синтаксис и семантика.

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

Алфавит С ++ включает:

1. Прописные и строчные латинские буквы и знак подчеркивания.

2. Арабские цифры от 0 до 9.

3. Специальные знаки:
“ {}, | [ ] () + - / % *. \ `:? < = >! & # ~; ^

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

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

Синтаксис C++ устанавливает, как можно на этом языке сформировать корректный текст и писать программы. Синтаксически правильная программа компилируется без ошибок.

Из символов алфавита формируются лексемы языка:

- идентификаторы;

- ключевые (зарезервированные) слова;

- знаки операций;

- константы;

- разделители (скобки, точка, запятая, пробельные символы).

Лексема, или элементарная конструкция - минимальная единица языка, имеющая самостоятельный смысл. Границы лексем определяются другими лексемами, такими, как разделители или знаки операций.

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

Идентификаторимя программного объекта.

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

Для улучшения читаемости программы следует давать объектам осмысленные имена. Существует соглашение о правилах создания имен, называемое венгерской нотацией (поскольку предложил ее сотрудник компании Microsoft венгр по национальности), по которому каждое слово, составляющее идентификатор, начинается с прописной буквы, а вначале ставится префикс, соответствующий типу величины, например, lpfnSetFirstDialog. Другая традиция – разделять слова, составляющие имя, знаками подчеркивания: max_length, number_of_galosh [2].

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

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

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

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

Примеры правильных идентификаторов: value25, My_File, index, Operation. Примеры синтаксически неправильных идентификаторов:

1_Side (имя не должно начинаться с цифры),

Том 2 (не допускается пробел),

New-Name (не допускается дефис),

break(служебное слово),

ехр (предопределенное имя функции-экспоненты).

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

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

Знаки операций. Знак операции – это один или более символов, определяющих действие над операндами. Внутри знака операции пробелы не допускаются. Операции делятся на унарные, бинарные и тернарные по количеству участвующих в них операндов. Один и тот же знак может интерпретироваться по-разному в зависимости от контекста. Все знаки операций за исключением [ ],() и?: представляют собой отдельные лексемы.

Семантика языка – это смысловое значение слов. В программировании – начальное смысловое значение операторов, основных конструкций языка, т.п. [1].

Пример. Первый код: i=0; while(i<5){i++;}

Второй код: i=0; do{i++;}while(i<5);

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

Таким образом,

- синтаксис – формальный набор правил, определяющий способ построения любых конструкций языка;

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

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

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...