Основы алгоритмизации

Алгоритм: свойства, исполнители, формы представления, блок-схемы и их типы.

Составитель:

учитель информатики и ИКТ

МБОУ «СОШ №19» Якушина И. В.

Слово «алгоритм» происходит от имени великого среднеазиатского ученого 8–9 вв. Аль-Хорезми.

Из математических работ Аль-Хорезми до нас дошли только две – алгебраическая и арифметическая. Вторая книга долгое время считалась потерянной, но в 1857 в библиотеке Кембриджского университета был найден ее перевод на латинский язык. В ней описаны четыре правила арифметических действий, практически те же, что используются и сейчас. Первые строки этой книги были переведены так: «Сказал Алгоритми. Воздадим должную хвалу Богу, нашему вождю и защитнику». Так имя Аль-Хорезми перешло в «Алгоритми», откуда и появилось слово «алгоритм».

Пример 1. Решение квадратного уравнения:

1.Найти дискриминант по формуле:

2. Найти первый корень по формуле

x1=(-b+√D)/2a

3. Найти второй корень по формуле

x2=(-b-√D)/2a

4. Записать ответ.

Пример 2. Выключение компьютера:

Определение:

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

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

Характеристики исполнителя:

• Сpеда — это «место обитания» исполнителя.
• Система команд – некоторый строго заданный список команд.

• После вызова команды исполнитель совершает соответствующее элементарное действие.

• Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.

Выберите примеры исполнителей:

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

Понятность - исполнитель алгоритма должен знать, как его выполнять.

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

Дискpетность — алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых шагов.

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

Опpеделенность — каждое пpавило алгоpитма должно быть четким и однозначным.

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

Pезультативность - алгоpитм должен пpиводить к pешению задачи за конечное число шагов.

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

Массовость – алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными.

Является ли пример алгоритмом для вас? Почему?

Вы вышли к доске, взяв мел в правую руку, вам велели написать слово «информатика» на китайском языке.

Формы представления алгоритмов:

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

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел. Алгоритм может быть следующим:

• задать два числа;
• если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
• определить большее из чисел;
• заменить большее из чисел разностью большего и меньшего из чисел;
• повторить алгоритм с шага 2.

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

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

Название символа

Процесс (действие)

Обозначение и пример заполнения

Решение (условие)

Пояснение

Модификация (счетчик)

Вычислительное действие или последовательность действий

Проверка условий

Предопределенный процесс

Начало цикла

Ввод-вывод

Пуск-останов (начало-конец)

Вычисления по подпрограмме, стандартной подпрограмме

Документ

Ввод-вывод в общем виде

Начало, конец алгоритма, вход и выход в подпрограмму

Вывод результатов на печать

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

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

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

• В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова , смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
• Примером псевдокода является школьный алгоритмический язык в русской нотации ( школьный АЯ ),

Основные служебные слова

алг (алгоритм) сим (символьный) дано для да

арг (аргумент) лит (литерный) надо от нет

рез (результат) лог (логический) если до при

нач (начало) таб (таблица) то знач выбор

кон (конец) нц (начало цикла) иначе и ввод

цел (целый) кц (конец цикла) все или вывод

вещ (вещественный) длин (длина) пока не утв

Общий вид алгоритма:

алг название алгоритма (аргументы и результаты)

дано условия применимости алгоритма

надо цель выполнения алгоритма

нач описание промежуточных величин

последовательность команд (тело

алгоритма)

кон

• Часть алгоритма от слова алг до слова нач называется заголовком ;
• часть, заключенная между словами нач и кон — телом алгоритма;
• В предложении алг после названия алгоритма в круглых скобках указываются характеристики ( арг, рез ) и тип значения (цел, вещ, сим, лит или лог) всех входных ( аргументы ) и выходных ( результаты ) переменных . При описании массивов (таблиц) используется служебное слово таб , дополненное граничными парами по каждому индексу элементов массива.

Команды школьного АЯ

• Оператор присваивания . Служит для вычисления выражений и присваивания их значений переменным. Общий вид: А := В , где знак ":=" означает команду заменить прежнее значение переменной, стоящей в левой части , на вычисленное значение выражения, стоящего в правой части .

Например, a:=(b+c)*sin(Pi/4); i:=i+1.

• Для ввода и вывода данных используют команды

ввод имена переменных

вывод имена переменных, выражения, тексты.

• Для ветвления применяют команды если и выбор , для организации циклов — команды для и пока

0 надо | S = 1*1 + 2*2 + 3*3 + ... + n*n нач цел i   ввод n; S:=0   нц для i от 1 до n     S:=S+i*i   кц   вывод "S = ", S кон " width="640"

Пример записи алгоритма на школьном АЯ

алг Сумма квадратов ( арг цел n, рез цел S)

дано | n 0

надо | S = 1*1 + 2*2 + 3*3 + ... + n*n

нач цел i  

ввод n; S:=0  

нц для i от 1 до n     S:=S+i*i  

кц  

вывод "S = ", S

кон

• Подробнее о школьном АЯ поговорим на следующем уроке. А теперь вернемся к алгоритмам.

Способы записи алгоритмов:

• словесный
• графический
• программный

Определение:

Блок-схема

Основные типы блоков:

• блок начала (конца)
• блок ввода (вывода)
• блок действия
• блок условия

Название символа

Процесс (действие)

Обозначение и пример заполнения

Решение (условие)

Пояснение

Модификация (счетчик)

Вычислительное действие или последовательность действий

Проверка условий

Предопределенный процесс

Начало цикла

Ввод-вывод

Пуск-останов (начало-конец)

Вычисления по подпрограмме, стандартной подпрограмме

Документ

Ввод-вывод в общем виде

Начало, конец алгоритма, вход и выход в подпрограмму

Вывод результатов на печать

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

Запись линейного алгоритма в виде блок-схемы:

начало

действие 1

…

действие n

конец

Разветвляющийся алгоритм –

это алгоритм,

в котором та

или иная

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

в зависимости

от истинности условия.

Ветвление

Полное

Неполное

если

то

если

то

иначе

Запись полного ветвления в виде блок-схемы:

нет

да

условие

серия команд 2

серия команд 1

Запись неполного ветвления в виде блок-схемы:

да

нет

условие

серия команд 1

Определение:

Условие – это в ысказывание, которое может быть либо истинным, либо ложным.

Условия

простые

сложные

4; x * y=3+8 ) . " width="640"

Простое условие

Включает в себя одно предложение; два числа, две переменных или два арифметических выражения, которые сравниваются между собой

Например: Идет дождь;

5 4;

x * y=3+8 ) .

0) AND (89); (x=10) OR (x=0). " width="640"

Сложное условие

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

И ( AND ) , ИЛИ (OR) .

Например: ( 10 0) AND (89);

(x=10) OR (x=0).

Задание:

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

Принадлежит ли точка x отрезку [ a, b ]?

Задания:

• Лежит ли x вне отрезка [ a, b ];
• Принадлежит ли x отрезку [ a, b ] или отрезку [ c, d ];
• Является ли k трехзначным числом;
• Какое из чисел a, b, c является меньшим;
• Есть ли среди чисел a, b, c взаимно противоположные;
• Равны ли треугольники со сторонами a1, b1, c1 и a2, b2, c2 ;
• Является ли четырехугольник с попарно параллельными сторонами a, b, c и d ромбом.

b); ((x=a) and (xor ((x=c) and (x(k 99) and (k (c and (b a); (a=-b) or (a=-c) or (b=-c); (a1= a2 ) and ( b1 = b2 ) and ( c1 =c 2 ); (a=b) and (c=d) and (b=c). " width="640"

Ответы:

• (x and (x b);
• ((x=a) and (xor ((x=c) and (x
• (k 99) and (k
• (c and (b a);
• (a=-b) or (a=-c) or (b=-c);
• (a1= a2 ) and ( b1 = b2 ) and ( c1 =c 2 );
• (a=b) and (c=d) and (b=c).

Определение:

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

Полный выбор

при условие 1: действия 1  

при условие 2: действия 2

. . . . . . . . . . . .  

при условие N: действия N

иначе действия N+1

Неполный выбор

при условие 1: действия 1

при условие 2: действия 2

. . . . . . . . . . . .  

при условие N: действия N

Запись полного выбора в виде блок-схемы:

да

серия команд 1

условие 1

нет

…

да

серия команд n

условие n

нет

серия команд n +1

Запись неполного выбора в виде блок-схемы:

да

серия команд 1

условие 1

нет

да

серия команд 2

условие 2

нет

…

да

серия команд n

условие n

нет

Определение:

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

Цикл с предусловием

пока истинно условие, предписывает выполнять тело цикла.

Словесный способ записи:

пока условие

тело цикла

Запись цикла с предусловием в виде блок-схемы:

нет

условие

да

тело цикла

Цикл с постусловием

предписывает выполнять тело цикла до тех пор, пока не выполнится условие выхода из цикла.

Словесный способ записи

тело цикла

до условие

Запись цикла с постусловием в виде блок-схемы:

тело цикла

нет

да

условие

Цикл со счетчиком

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

Словесный способ записи

для i от i1 до i2  

тело цикла

Запись цикла со счетчиком в виде блок-схемы:

нет

счетчик

да

тело цикла

• Благодарю за внимание!