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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Доклад

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

1. Понятие алгоритма и его свойства

Слово алгоритм происходит от algoritmi, являющегося латинской транслитерацией арабского имени математика IX века аль-Хорезми. Благодаря латинскому переводу трактата аль-Хорезми европейцы в XII веке познакомились с позиционной системой счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система счисления и правила счета в ней.

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

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

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

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

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

Алгоритм - это точная инструкция. Однако не всякая инструкция есть алгоритм. Инструкция становится алгоритмом только тогда, когда она обладает следующими свойствами.

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

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

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

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

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

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

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

2. Способы описания алгоритмов

К основным способам описания алгоритмов можно отнести следующие:

o словесный (на естественном языке); недостаток - отсутствие строгой формализации и наглядности представления вычислительного процесса.

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

o табличный - предполагает представление алгоритма в виде таблицы решений и обычно носит вспомогательный характер;

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

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

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

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

3. Основные алгоритмические конструкции

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

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

Линейные процессы имеют место, например, при вычислении арифметических выражений.

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

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

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

изменение значения этой переменной перед каждым новым повторением цикла;

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

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

4. Простые и структурированные типы данных

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

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

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

* используемый способ записи информации в ячейки памяти;

* необходимый объем памяти для ее хранения.

Объем памяти для каждого типа определяется таким образом, чтобы в него можно было поместить любое значение из допустимого диапазона значений данного типа. Например, тип «байт» может принимать значения от 0 до 255, что в двоичном коде (255 = = 11111111 ₂) соответствует ячейке памяти длиной в 8 бит (или 1 байт).

В описанных выше алгоритмах все данные хранятся в виде переменных. Например, инструкция «Ввод двух чисел а, b» означает введение пользователем значений двух переменных, а инструкция «К=К+1» означает увеличение значения переменной К на единицу.

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

Все остальные данные в программе, значения которых не изменяются на протяжении ее работы, называют константами или постоянными. Константы, как и переменные, имеют тип. Их можно указывать явно, например, в инструкции «К = К + 1» 1 есть константа, или для удобства обозначать идентификаторами: pi =3,1415926536. Только значение pi нельзя изменить, так как это константа, а не переменная.

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

Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой адресуются (различаются) порядковыми номерами (индексами). В качестве иллюстрации можно представить шкаф, содержащий множество пронумерованных ящиков (совокупность - «Ящик №1», «Ящик №2», «Ящик №3» и т.д.; «Ящик» - общее имя всех ее элементов). Доступ к содержимому конкретного ящика (элементу массива) осуществляется после выбора ящика по его номеру (индексу). Элементы массива в памяти компьютера хранятся по соседству, одиночные элементы простого типа такого расположения данных в памяти не предполагают. Массивы различаются количеством индексов, определяющих их элементы.

Одномерный массив (шкаф ящиков в один ряд) предполагает наличие у каждого элемента только одного индекса. Примерами одномерных массивов служат арифметическая и геометрическая последовательности, определяющие конечные ряды чисел. Количество элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скобках, рядом с его именем. Например, если сказано: «задан массив А(10)», это означает, что даны элементы: а_р а₂,…, a_ig. Рассмотрим алгоритмы обработки элементов одномерных массивов.

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

Размещено на Allbest.ru