«Понятие об алгоритме. Примеры алгоритмов. Свойства алгоритмов. Типы алгоритмов, построение простых алгоритмов для решения простых задач. Группы алгоритмов»

Вид материала

Лекция

Содержание Типы алгоритмов. Группы алгоритмов Циклические алгоритмы – Условие задачи

Подобный материал:

• Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов. Способы, 96.46kb.
• Построение и анализ комбинаторных алгоритмов, 62.76kb.
• 8 Понятие об алгоритме и исполнителе алгоритмов. Свойства алгоритмов, 109.92kb.
• Основы алгоритмизации, 754.96kb.
• Метод принятия решения в выборе варианта реализации алгоритмов при разнородных условиях, 70.86kb.
• Язык описания алгоритмов начертательной геометрии adgl, 70.57kb.
• Урок: «типы алгоритмов. Линейные алгоритмы»    Тема: Типы алгоритмов. Линейные алгоритмы, 101.98kb.
• «бесконечность», 189.92kb.
• Методические рекомендации к занятиям темы 7 «Алгоритмы обработки информации», 163.76kb.
• Лекция 12: Алгоритмы на графах и деревьях, 395.7kb.

Раздел 3. Алгоритмизация.


ЛЕКЦИЯ


«Понятие об алгоритме. Примеры алгоритмов. Свойства алгоритмов. Типы алгоритмов, построение простых алгоритмов для решения простых задач. Группы алгоритмов»


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

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


Свойства алгоритмов:

1. Точность- на каждом определенном шаге алгоритма точно известно, что нада делать.
   
2. Искренность- каждый шаг алгоритма должен указывать только одно конкретное действие и исполнитель должен выполнить его целиком.
   
3. Массовость- с помощью одного и того же алгоритма можно решать однотипные задачи и делать это неоднократно.
   
4. Результативность- Исполнение алгоритма сводится к выполнению конечного числа действий и всегда это неоднократно.
   

Очень важно отметить особенность того, что исполнитель алгоритма может

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


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


Существует три основных способа описания алгоритма:

1. Словесный – все рассмотренные ранее примеры являются словесными (алгоритм перехода улицы, решение алгебраического выражения и т.д.)
   
2. Способ, использующий псевдокоды (алгоритмический язык)
   
3. Графический способ – изображается графическим в виде блок-схем. Он наиболее наглядно изображает алгоритм любой степени сложности.
   

Наиболее часто для решения на ЭФМ графический способ изображения алгоритмов в виде боксёр-. Всякая такая схема состоит из блоков, которые изображаются различными фигурами: овалом, параллелограммом, прямоугольником или ромбом.




Параллелограмм – это ввод и вывод информации




Прямоугольник – это конкретные вычисления



Ромб – операции проверки условия (условные переходы)



Овалы – обозначают «начало» и «конец» операции


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

Из каждого ромба выходят две линии. Одна соответствует выполнению условия и начинается словом «да», другая невыполнению и начинается словом «нет».


^ Группы алгоритмов


Алгоритмы делятся на три основные группы: линейные, разветвляющиеся и циклические.

1. Линейные – или алгоритмы следования, Состоят из серии команд, которые выполняются последовательно, одна за другой. (например алгоритм заварки чая)
   

Графическое изображение линейного алгоритма:




Вход








Выход

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

Графическое изображение разветвляющегося алгоритма:




Вход





Серия 1

Серия 2
Да Нет


Выход

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

3. ^ Циклические алгоритмы – Алгоритмы данного типа включают в себя циклы. Циклы – это часть алгоритма (или программы), которая выполняется многократно, каждый раз при новых значениях параметра.
   

Графическое изображение циклического алгоритма:


Серия
Вход Да Нет Выход


Примером циклического алгоритма может служить сбор ягод в саду.


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

1. Графическая запись линейного алгоритма в виде блок-схемы:
   

Условия задачи:

Составить алгоритм вычисления функции y=x² + 1 при х=51. Результат вычислений выдать на печать





Х:=51


y:=x²+1

2. Графическое изображение разветвляющегося алгоритма в виде блок-схемы:
   

^ Условие задачи:

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

Алгоритм этой задачи изображаем в виде блок-схемы:














Нет







Да

3. Графическое изображение циклического алгоритма в виде блок – схемы
   

Условие задачи:

Вычислить и напечатать значение функции:




для значений функции х = 3,5,7,9,11,13. Алгоритм это задачи должен содержать многократное обращение (пока х <= 13) к выше написанному значению функции. Каждый раз при этом значении х должно увеличиваться на 2, начиная с х=3. Такое последовательно увеличение значения аргумента на постоянную величину можно осуществлять командой х:=х+2






Х=3







Нет







Да












X:=x+2







Вопросы для самопроверки упражнения.

1. Назвать основные способы описания алгоритмов.
   
2. Какой способ описания алгоритмов для ЭВМ является наиболее распространенным.
   
3. Привести основные обозначения для графического способа описания алгоритмов.
   
4. Перечислить основные типы алгоритмов.
   
5. К какому типу алгоритмов относятся:
   

Алгоритм перехода улицы?

Алгоритм режима дня?

Алгоритм вычисления функции У= е^√хcos(2x-3) для х, меняющегося от 1 до 2 с шагом 0,1?

6. Составить блок-схему алгоритма вычисления площади треугольника по формуле:
   

S=1/2ah, где а – основание, а h – высота треугольника.

Ответы:

1. а) Словесный

в) Способ, использующий псевдокоды

г) Графический

2. Графический

3. Ромб-условие, параллелограмм- ввод/вывод, прямоугольник- выполнение одной или группы операций, овал –начало, конец или прерывание обработки данных.

4. Линейные, разветвляющие и циклические.

5. а) разветвляющийся

в) линейный

г) циклический

6.











S=1/2ah













Домашнее задание:

1. Составить графический алгоритм вычисления у по формуле: у=2х-3х³+4 при х=1,2







Х=1















Y=2x-3x³+4









x=x+1







Контрольная работа №3 (Раздел 3. «Алгоритмизация»)

1. вариант.
   

Вопрос1

а) Какое свойство алгоритма позволяет решать однотипные задачи?

б) Назвать блок, который осуществляет ввод/вывод данных?

Вопрос 2

Дана формула у=3х²-5х при х=2,4,6,8,10,12. Составить графическое изображение данного алгоритма. Результат вывести на печать.

Вопрос 3.

Составить графическое изображение алгоритма расчета длины окружности по формуле 2РR. Диаметр вывести на печать.

Ответы:

Вопрос 1

а) массовость

б) параллелограмм

Вопрос 2






х = 2









Y=3x²=5x








x=x+2












Вопрос 3









D=2PR










Вариант 2


Вопрос 1


а) какое свойство алгоритма указывает только одно конкретное действие?


б) что такое алгоритм?


Вопрос 2


Составить графический алгоритм, который вводит значение t равное температуре воздуха и если t<5, то вывести сообщение «Я надену пальто и перчатки, в противном случае вывести: «Я надену только пальто».


Вопрос 3


Составить графичекий алгоритм вычисления у по формуле у=4х³+4х-1 при х=2


Ответы:


Вопрос 1

а) дискретность

б) набор правил и действий, которые надо совершить, чтобы за конкретное число шагов решить задачу.


Вопрос 2














Да Нет



Я надену пальто и

Я надену только пальто










Вопрос 3













Y=4x³-4x-1