1 Понятие алгоритма. Алгоритм icon

1 Понятие алгоритма. Алгоритм



Название1 Понятие алгоритма. Алгоритм
Дата конвертации08.11.2012
Размер60.63 Kb.
ТипРешение



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

Эта глава будет посвящена первому этапу решения задачи - разработке алго­ритма.


1.1. Понятие алгоритма.

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

1. Ввести исходные данные.

2. Преобразовать исходные данные в результаты (выходные данные).

3. Вывести результаты.

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

Разработанный алгоритм можно записать несколькими способами:

  • на естественном языке;

  • в виде блок-схемы;

  • на языке программирования.

Рассмотрим пример алгоритма на естественном языке:

1. Ввести в компьютер числовые значения переменных а, b и с.

2. Вычислить D по формуле D= b2 - 4ас.

3. Если d<0, то напечатать сообщение «Корней нет» и перейти к п. 4. Иначе вычислить корни по формулам Х1 = (-b+)/2a, Х2 = (-b-)/2a и напечатать значения Х1 и Х2.

4. Прекратить вычисления.


^ 1.2. Изображение алгоритма в виде блок-схемы

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


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

  • блок начала-конца алгоритма (рис. 1.1). Надпись внутри блока: «начало» («конец»);

  • блок ввода-вывода данных (рис. 1.2). Надпись внутри блока: ввод (вывод или печать) и список вводимых (выводимых) переменных;

  • блок решения или арифметический (рис. 1.3). Внутри блока записывается действие, вычислительная операция или группа;

  • условный блок (рис. 1.4). Условие записывается внутри блока. В результате проверки условия осуществляется выбор одного из возможных путей (вет­вей) вычислительного процесса. Если условие истинно, то следующим выполняется этап, соответствующий ветви «+»; если условие ложно, то выполняется этап, соответствующий ветви «?».



В качестве примера рассмотрим блок-схему алгоритма решения квадратно­го уравнения (рис. 1.5), описанного в предыдущем подразделе.



^ 1.2.1. Алгоритмы линейной структуры

Линейный алгоритм - это такой, в котором все операции выполняются последо­вательно одна за другой (рис.1.6).

Рассмотрим несколько примеров линейных алгоритмов.

ПРИМЕР 1.1. Зная длины трех сторон треугольника, вычислить его площадь и периметр.

Пусть а, b, с - длины сторон треугольника. Необходимо найти S - площадь треугольника, Р- периметр. Для нахождения площади можно воспользоваться

формулой Герона: S = где г - полупериметр.

Входные данные: а, b, с. Выходные данные: S, Р.



Блок-схема алгоритма представлена на рис. 1.7.

!этих блоках знак «=» означает не математическое равенство, а операцию при­сваивания. Переменной, стоящей слева от оператора, присваивается значение, указанное справа. Причем это значение может быть заранее определенным либо вычисляться при помощи математического выражения. Например, операция r = (а + b + с)/2-имеет смысл (переменной r присвоить значение r=(а + b + с)/2), . а выражение (а + b+-с)/2 = r - бессмыслица.

ПРИМЕР 1.2. Известны плотность и геометрические размеры цилиндриче­ского слитка, полученного в металлургической лаборатории. Найти объем, мас­су и площадь основания слитка.

Входные данные: R - радиус основания цилиндра, h - высота цилиндра, р -плотность материала слитка.

Выходные данные: т - масса слитка, V- объем, S - площадь основания.

Блок-схема представлена на рис. 1.8.

ПРИМЕР 1.3. Заданы длины двух катетов в прямоугольном треугольнике. Найти длину гипотенузы, площадь треугольника и величину его углов.

Входные данные: а, b- длины катетов.

Выходные-данные: с - длина гипотенузы, S - площадь треугольника, α,β-углы.

Блок-схема представлена на рис. 1.9.


^ 1.2.2. Алгоритмы разветвленной структуры

Алгоритмы разветвленной структуры применяются, когда в зависимости от не­которого условия необходимо выполнить либо одно, либо другое действие. В блок-схемах разветвленные алгоритмы изображаются так, как показано на рис. 1.10-1.11

Рассмотрим несколько примеров построения алгоритмов разветвленной структуры.

ПРИМЕР 1.4. Известны коэффициенты а, b и с квадратного уравнения. Вы­числить корни квадратного уравнения.

Входные данные: а, b, с.

Выходные данные: x1 x2.

Блок-схема представлена на рис. 1.5.

ПРИМЕР 1.5. Заданы коэффициенты a, b vt с биквадратного уравнения ax4+bx2+c+0. Найти корни уравнения. Для решения задачи необходимо заменой у = х2 привести уравнение к квадратному и решить его.

Входные данные: а, Ь, с.

Выходные данные: х1, х2, х3, х4

Блок-схема представлена на рис. 1.12.

Алгоритм сострит из следующих этапов: -

1. Вычисление дискриминанта уравнения d.

2. Если d> 0, то определяются y1, и у2; иначе корней нет.

3. Если y1,y2< 0 , то корней нет; ,



4. Если y1,y2 > О , то вычисляются четыре корня по формулам ±, ±и выводятся значения корней.

5. Если условия 3 и 4 не выполняются, то необходимо проверить знак y1. Если y1 0, то вычисляются два корня по формуле ±. Если же y20, то вы­числяются два корня по формуле ±Вычисленные значения корней вы­водятся.



Еще раз обратимся к алгоритмам на рис. 1.5, 1.12. Нетрудно заметить, что если а принимает значение 0, алгоритмы не работают (ведь на 0 делить нельзя). Это - недостаток алгоритмов. Его можно избежать, если проверять значение переменной а сразу после ввода. Алгоритмы такой проверки приведены ниже. В первом случае (см. рис. 1.13)» если введенное значение переменной а = 0, выполнение вычислительного процесса сразу же прекращается. Алгоритм, изображенный на рис. 1.14, позволяет при нулевом значении а повторить ввод переменной. Этот процесс будет продолжаться до тех пор, пока вне станет отличной от нуля. Подобные алгоритмы называются циклическими.





!Перед вычислением значения математического выражения последнее следует про­анализировать: при каких значениях переменных выражение имеет смысл. В ал­горитме необходимо предусмотреть предварительную проверку переменных на значения, для которых выражение не может быть определено. Если, например, требуется извлечь корень четной степени, то перед вычислением необходимо про­верить подкоренное выражение - оно не должно быть отрицательным, а в случае ' нахождения знамения дроби - проверить знаменатель - он не должен быть рав­ным 0. В блок-схеме такие проверки реализуются с помощью условного блока. Отсутствие подобных проверок в программе может привести к критическим ошибкам.

^ 1.2.3. Алгоритмы циклической структуры

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

Существует два типа алгоритмов циклической структуры:

  • цикле предусловием (рис, 1.15); .

  • цикл с постусловием (рисЛ. 16).



Рассмотрим, в чем отличие этих типов алгоритмов:

  • в цикле с предусловием условие проверяется до тела цикла, в цикле с по­стусловием - после тела цикла;

  • в цикле с постусловием тело цикла выполняется хотя бы один раз, в цик­ле с предусловием оно может не выполниться ни разу;

  • в цикле с предусловием проверяется условие продолжения цикла, в цик­ле с постусловием - условие выхода из цикла.

Оба эти цикла взаимозаменяемы, какой из них выбрать - зависит от конк­ретной задачи.

Рассмотрим основные алгоритмы циклической структуры на примерах.




Похожие:

1 Понятие алгоритма. Алгоритм icon1. Понятие алгоритма. Исполнитель алгоритма. Система команд исполнителя. Свойства алгоритма. Способы записи алгоритмов; блок-схемы
В 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой...
1 Понятие алгоритма. Алгоритм iconПонятие алгоритма. Виды алгоритмов
Составьте алгоритм решения задачи: Мастер выполнил 60% работы, и ему заплатили 24 талера. Сколько стоит вся работа?
1 Понятие алгоритма. Алгоритм iconПонятие алгоритма
Слово «алгоритм» происходит от латинского написания имени арабского математика Аль-Хорезми (Algorithmi), впервые описавший правила...
1 Понятие алгоритма. Алгоритм iconОбобщенный алгоритм, или последовательность выполнения проекта
Основной задачей выполнения проектов является усвоение алгоритма проектирования, который, в общих чертах, включает развернутые ответы...
1 Понятие алгоритма. Алгоритм iconДокументи
1. /9кл/Урок-1/instruction_on_safety_and_rule_of_the_behaviour_in_computer_class.doc
1 Понятие алгоритма. Алгоритм iconЗапись алгоритма (алгоритмический язык) Алгоритм
Стимул: Вы повар-кондитер детского кафе «Буратино». Для проведения детского утренника вам сделали заказ на кондитерское изделие «Творожные...
1 Понятие алгоритма. Алгоритм iconПравила выполнения определенных действий; ориентированный граф, указывающий порядок выполнения некоторого набора команд
Свойство алгоритма, заключающиеся в том, что каждое действие и алгоритм в целом должны иметь возможность завершения, называется
1 Понятие алгоритма. Алгоритм iconИмеется два вида структуры алгоритма
В основе автоматических устройств лежит принцип формального исполнения алгоритма. Суть его заключается в том, что исполнитель не...
1 Понятие алгоритма. Алгоритм iconПравила структурной записи алгоритма. Метод пошаговой детализации алгоритма. Краткая характеристика псевдокода. Базовые операции: содержание и правила записи в алгоритме
Назначение и правила представления этапов: постановка задачи, выбор метода решения, внешняя спецификация программы
1 Понятие алгоритма. Алгоритм iconТема : Определение и свойства алгоритма
Напишите алгоритм перевоза через реку волка, козы и капусты, если ски «Перевозчика» содержит 5 команд: взять козу, взять волка, взять...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib.podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов