Любая программа является реализацией некоторого алгоритма. Понятие алгоритма является одними из фундаментальных понятий информатики, появившимся задолго до появления ЭВМ. В древнем мире алгоритмом называлось правило выполнения арифметических действий. До 50-х годов 20 века под алгоритмом понималась совокупность математических операций, выполняемых в определенном порядке.
Дадим интуитивное понятие алгоритма. Алгоритм — понятное и точное сформулированное на определенном языке предписание исполнителю совершить определенную последовательность действий для достижения указанной цели или решения поставленной задачи. Алгоритм формируется в расчете на конкретного исполнителя (человека или ЭВМ). Каждый алгоритм имеет некоторое множество входных и выходных величин. Причем размерность входного множества может быть равна нулю.
Свойства алгоритма:
— Массовость. Для алгоритма можно брать различные наборы входных данных, то есть в общем случае можно применять один и тот же алгоритм для решения целого класса задач. Хотя существуют алгоритмы, применяемые только к единственному набору входных данных (без входа).
Урок 29. Прерывания в операционной системе
— Дискретность — алгоритм может быть представлен в качестве последовательности шагов, поэтому его исполнение расчленяется на выполнение этих отдельных шагов.
— Конечность — выполнение алгоритма заканчивается после выполнения конечного числа шагов.
— Определенность — алгоритм рассчитан на чисто механическое исполнение, то есть действия, которые необходимо произвести должны быть строго и недвусмысленно определены в каждом возможном случае. Это означает, что один алгоритм будут выполнять разные исполнители, то они прейдут к одному результату.
— Эффективность- алгоритм должен быть выполнен не просто за конечное, а за разумное конечное время.
Существуют более формальные описания алгоритма, предложенные Постом, Тьюрингом, Марковым. На практике они друг другу эквивалентны друг другу и этому интуитивному понятию.
Способы описания алгоритма
1. Словесно- формульный – алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий;
2. Структурный или блок-схемный. При блок-схемном описании алгоритм изображается геометрическими фигурами (блоками), связанными линиями со стрелками (отражающими последовательность действий). В блоках записывается описания действий.
Процесс, что есть выполнение операции или группы операций, в результате которых меняется значение, форма представления или расположение данных обозначается на блок-схеме алгоритма прямоугольником. Ввод — вывод данных, то есть преобразование данных в форму пригодную для обработки или отображения результатов обработки изображается параллелограммом. Решение, то есть выбор направления алгоритма в зависимости от некоторых переменных условий изображается ромбом. Пункт-останов, то есть начало конец, прерывание процесса обработки обозначаются овалом.
С помощью языка программирования.
Урок №5 по NC Studio. Восстановление выполнения программы после сбоя
Управляющие структуры и основные конструкции языков программирования
Размещенная в памяти компьютера программа в момент выполнения занимает определенную область памяти. В каждый момент времени состояние программы характеризуется двумя типами сведений:
— состоянием некоторых ячеек памяти, понимаемых нами как переменные;
— активной точкой программы, то есть той командой программы, которая выполняется данный момент.
Следовательно, можно выделить и два основных класса действий, которые может выполнять вычислительная система:
— действия, выделяющие область памяти под переменные программы (описания).
— действия, меняющие точку выполнения программы (операторы, инструкции, конструкции).
Различные совокупности действий второго класса также называют управляющими структурами.
В теории программирования доказано, что программу для решения задачи любой сложности можно составить их трех структур, называемых следованием (цепочкой), ветвлением и циклом. Этот результат установлен Бойном и Якопини в 1966 г. путем доказательства того, что любую программу можно преобразовать в эквивалентную, состоящую только из этих структур и их комбинаций. Каждая из этих управляющих структур реализована в языке программирования набором соответствующих конструкций.
Структура следования (естественная фундаментальная структура) реализует линейный вычислительный процесс, то есть процесс, в котором действия выполняются последовательно, в порядке их записи. Каждое действие является самостоятельным, независимым от каких-либо условий. В языках программирования цепочки реализуются так называемым составной конструкцией следующим образом.
На блок-схеме блоки, отображающие эти операции, располагаются в линейной последовательности.
Каждый оператор будет выполняться только тогда, когда закончит выполняться предыдущий. Оператор; — называют оператором следования. Составные операторы заключены в инструктивные скобки. В языке С++ инструктивные скобки записываются как < >. В Паскале –begin end. Составные операторы также называют блоком кода, инструктивным блоком, блоком.
Тело любой функции в С++ является блоком.
Пример структуры следования (цепочки)
Структура ветвления реализует ветвящийся вычислительный процесс, то есть процесс, для реализации которого предусмотрено несколько направлений (ветвей). Ветвление в программе – это выбор одной из нескольких последовательностей операторов при выполнении программы. Выбор направления зависит от заранее определенного признака, который может относиться к исходным данным, к промежуточным данным или конечным результатам. Хотя на схеме алгоритма должны быть показаны все возможные направления вычислений в зависимости от выполнения определенного условия (или условий), при однократном прохождении программы процесс реализуется только по одной ветви, а остальные исключаются. Любая ветвь, по которой осуществляется вычисления, должна приводить к завершению вычислительного процесса.
В языках программирования структура ветвления реализуется условными и селективными констркуциями. Условные конструкции в общем случае имеют форму
если выражение то действие1 иначе действие2;
и следующей смысл: если выражение верно то выполняется действие1, иначе выполняется действие2.
Кроме того, используется и усеченная форма условной конструкции
если выражение то действие1;
На блок-схеме ветвление и усеченное ветвление изображаются следующим образом:
В С++ синтаксис условной конструкции
if (выражение) опрератор1; else оператор2;
if (выражение) опрератор1;
Выражение должно быть скалярным и иметь арифметический тип или тип указателя. В операторе if оператор1 выполняется в том случае, если выражение ненулевое, иначе выполняется оператор2 или не выполняются никакие действия, если оператор2 не задан, то есть отсутствует else. В частности, если a целое, то if (a) эквивалентно if (a!= 0).
Оператор1 и оператор2 могут представлять собой один оператор или блок операторов, но не могут быть описаниями.
В соответствии неписаными правилами хорошего стиля программирования в условных инструкциях логическое выражение необходимо составлять таким образом, чтобы чаще всего оно было истинным.
Часто используются в условиях логические операции , ||. Операции и || не будут вычислять второй аргумент, если это не нужно. Например, if (p r) … вначале проверяет, является ли p не нулем, и только, если это так, то проверяет r.
Еслинекоторое действие выполняется при выполнении двух условий желательно записывать их в виде одного выражения.
Селективные инструкции используются для реализации мультиветвления и в общем случае имеют вид:
имеет значение2 то действие2
имеет значениеn то действиеn
На блок-схеме мультиветление изображается следующим образом:
В С++ существует конструкция мультиветвления (переключатель). Синтаксис переключателя:
case константное_выражение2: оператор2;
case константное_выражение n: оператор n;
Если не предусмотрены переходы и выходы из переключателя, то в нем последовательно выполняются все операторы, начиная с той метки, на которую передано управление. Для выхода из переключателя обычно используют оператор break.
Источник: poisk-ru.ru
Основы алгоритмизации процессов обработки информации
Одним из базовых понятий информатики и ВТ является понятие алгоритма как некоторого правила преобразования информации. Он указывает, какие операции по обработке данных и, в какой последовательности необходимо выполнить, чтобы получить решение задачи. Алгоритм – точное распоряжение, которое определяет вычислительный процесс, который ведет от переменных исходных данных к искомому результату. 10
Рассмотрим понятие алгоритма на примере вычисления суммы элементов вектора a = ( a 1 , a 2 , . a n ) , то есть
| S = ∑ n | a i | (1.1) |
| i = 1 |
Для определения суммы применим алгоритм ее накопления, используя рекуррентное соотношение
| где S i | S i : = S i − 1 + a i ; S 0 = 0 ; i : = 1, 2, . n , | (1.2) |
| – текущее значение суммы; | ||
| S i − 1 – предыдущее ее значение; | ||
| S 0 | – начальное значение суммы; | |
| a i | – значение текущего элемента вектора. | |
Сначала значение суммы равняется нулю, потом последовательно к ней прибавляются значения первого, второго и следующих элементов вектора. Алгоритм вычисления суммы запишется в виде такой последовательности указаний: 1. Присвоить S значение 0 и перейти к п. 2. 2. Присвоить i значение 1 и перейти к п. 3. 3. Вычислить новое значение суммы, прибавив a i к ее предыдущему значению, то есть S : = S + a i и перейти к п. 4. 4. Увеличить значение i на 1 , то есть i : = i + 1 , и перейти к п. 5. 5. Сравнить значение i и n : если i ≤ n , то перейти к п. 3, иначе – к п. 6. 6. Вывести результат S , то есть сумму элементов вектора а . Алгоритм имеет следующие основные свойства: детерминированность (определенность) – однозначность результата вычислительного процесса при заданных начальных данных; дискретность – расчлененность вычислительного процесса на отдельные элементарные шаги, возможность выполнения которых не вызывает сомнения; массовость – обеспечение решения любой задачи из класса однотипных; результативность – обеспечение получения результата за конечное число шагов.
Схемы алгоритмов
Для задачи алгоритмов используют такие способы, как словесное описание последовательности вычислений, аналитический (в виде формул), графический (в виде схем и диаграмм), псевдокод, запись алгоритмическим языком. Примером словесного описания алгоритма есть приведенное выше вычисление суммы элементов вектора. Запись алгоритма алгоритмическим языком требует точного соблюдения правил этого языка, поскольку он должен быть понятным не только человеку, а и компьютеру. Такой способ представления алгоритма будет изучаться во время изучения языка программирования Visual Basic. Псевдокод занимает промежуточное место между словесным описанием алгоритма и его записью алгоритмическим языком. В этом способе употребля- 11
ются конструкции, близкие к алгоритмическому языку, но не требуется полного соблюдения всех его правил, поскольку он предназначен для восприятия человеком. Большое распространение получил графический способ задачи алгоритма в виде схем.
Схема алгоритма – графическое изображение его структуры, в котором каждый этап процесса переработки данных представляется в виде различных геометрических фигур (символов). Эти фигуры соединяются между собою линиями потока, которые для каждого этапа указывают возможных преемников. Внутри фигуры дается описание соответствующего этапа, если он не является слишком громоздким.
В противном случае такое описание приводится в приложении к схеме, а вместо него в соответствующей фигуре записывается номер или какое-нибудь обозначение этого этапа. Возле фигуры могут быть некоторые замечания, например такие, которые показывают, в каком случае выбор преемника будет делаться соответственно линии потока.
Символам присваивают порядковые номера, которые проставляются в разрыве линии контура в левой части верхней стороны изображения символа. Линии потока проводят параллельно линиям внешней рамки схемы. Направление линии потока сверху вниз и слева направо принимают как основной и, если они не имеют изломов, стрелками их можно не обозначать.
В других случаях их направление обязательно обозначают стрелкой. Линию потока, как правило, подводят к середине символа. Расстояние между параллельными линиями потока может быть не меньше 3 мм, между другими символами – не меньше 5 мм.
Линию потока можно обрывать, используя на месте обрыва соединители, если схема выполнена на двух и больше листах, или если символы, которые соединяются, расположены на значительном расстоянии один от другого. Запись внутри символа или рядом с ним нужно выполнять машинописью с одним интервалом или чертежным шрифтом.
Преимуществом схем заключается в том, что с их помощью можно наглядно изобразить структуру алгоритма в целом, отобразив его логическую суть (показать разветвление путей решения задачи в зависимости от выполнения некоторого условия, отобразить многоразовое повторение отдельных этапов вычислительного процесса). В особенности это важно для задач экономического характера и задач управления.
Они содержат большое количество операций сравнения, логических, арифметических и других операций, и потому сразу тяжело установить их последовательность в процессе решения задачи. Графическое изображение алгоритма в виде схем облегчает создание программы для решения задачи на компьютере. В табл. 1.1 приведены символы, которые чаще всего используются в схемах алгоритмов. Размер а может выбираться из ряда 10, 15, 20 мм. Допускается увеличивать размер а на число кратное 5. Размер b = 1.5 a . 12
Таблица 1.1 Символы, наиболее часто используемые в схемах алгоритмов
№ Наименование п.п. символа 1. Процесс 2. Решение 3. Ввод-вывод данных 4. Соединитель (узел) 5. Началоокончание (пуск-конец) 6. Комментарий 7. Линия потока
Графическое изображение a b a b
| 0,25·а | a |
b 0,5·a 0,5·a b
| ……. | a |
Функция символа Выполнение операции или группы операций, благодаря которым изменяются значения, форма представления или расположение данных Выбор направления выполнения алгоритма или программы в зависимости от условий Преобразование данных в форму, пригодную для обработки (ввода) или отображения полученных результатов (вывод) Обозначение связи между прерванными линиями потока, которые связывают символы Начало, конец, прерывание процесса обработки данных или выполнения программы Связь между элементом схемы и пояснением Обозначение последовательности связей между символами
В качестве иллюстрации можно рассмотреть блок-схему алгоритма вычисления суммы элементов вектора (рис. 1.2), словесный алгоритм которого приведен выше. 13
НАЧАЛО ВВОД a, n СУММА ЭЛЕМЕНТОВ S:=0 i:=1 S:=S+a i ДА i:=i+1 i
Источник: studfile.net
Обозначение блоков в соответствии с ГОСТами
Целью любого научного исследования является определение значений таких параметров исследуемого объекта, которые удовлетворяют определенному критерию с заданной достоверностью. Такие исследования называются экспериментом.
Под экспериментомпонимают целенаправленно организованный опыт, состоящий из воспроизведения и наблюдения исследуемого явления с необходимой точностью.
На практике экспериментирование с реальными объектами, как правило, обходится либо очень дорого, либо вообще не представляется возможным из-за нежелательных последствий эксперимента. Поэтому обычно в таких случаях для проведения научных экспериментов реальные объекты заменяются соответствующими им более простыми объектами, свойства которых подобны свойствам исследуемых реальных объектов в определенной части.
Объект, с целью изучения которого проводятся исследования, называется оригиналом,а объект, исследуемый вместо оригинала для изучения определенных свойств, называется моделью.
Моделированиеесть метод (или процесс) изучения свойств объектов-оригиналов посредством исследования соответствующих свойств их моделей.
Алгоритмизациялежит в основе процесса построения любой модели и потому является неотъемлемой частью научного исследования.
Вопрос 4.Этапы подготовки задачи
Источник: 5rik.ru