ОСНОВНЫЕ ПОНЯТИЯ АЛГОРИТМИЗАЦИИ ЛЕКЦИЯ 1

1. ОПРЕДЕЛЕНИЯ Алгоритм Алгоритм - это конечная последовательность команд (предписаний) исполнителю совершить конечную последовательность действий, которая направлена на достижение определённой цели. Исполнитель - Исполнитель - человек, живое существо или автоматическое устройство, способное к восприятию и выполнению данных команд. Система команд исполнителя Система команд исполнителя - перечень команд, которые понимает и может исполнить исполнитель.

2. ПРИМЕРЫ ВЫЧИСЛИТЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ : ПРАВИЛО ВОЗВЕДЕНИЯ ЧИСЛА В СТЕПЕНЬ; ИЗВЛЕЧЕНИЕ КОРНЯ; СЛОЖЕНИЕ, УМНОЖЕНИЕ, ДЕЛЕНИЕ ДРОБЕЙ; РЕШЕНИЕ ЛИНЕЙНЫХ, КВАДРАТНЫХ И ДР. УРАВНЕНИЙ; НАХОЖДЕНИЕ S И V ФИГУР, ВЫЧИСЛЕНИЕ НОД, НОК, НЕВЫЧИСЛИТЕЛЬНЫЕ (БЫТОВЫЕ): РЕЦЕПТ ПРИГОТОВЛЕНИЯ БЛЮД; ПРАВИЛО ПОЛЬЗОВАНИЯ ЛИФТОМ, МЕЖДУГОРОДНИМ ТЕЛЕФОНОМ; ИНСТРУКЦИЯ ПО ИСПОЛЬЗОВАНИЮ ЭЛЕКТРОПРИБОРОВ.

3. СВОЙСТВА АЛГОРИТМОВ Дискретность Дискретность - алгоритм должен быть разбит на шаги (отдельные законченные действия); Определённость Определённость - у исполнителя не должно возникать двусмысленностей в понимании шагов алгоритма (исполнитель не должен принимать самостоятельные решения); Результативность (конечность)Результативность (конечность) - алгоритм должен приводить к конечному результату за конечное число шагов; Понятность Понятность - алгоритм должен быть понятен для исполнителя; Эффективность Эффективность - из возможных алгоритмов выбирается тот алгоритм, который содержит меньше шагов или времени на его выполнение требуется меньше.

4. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ Выбор средств и методов для записи алгоритма зависит прежде всего от назначения самого алгоритма, а также от того, кто будет исполнять алгоритм. Алгоритмы записываются в виде: словесных правил, блок схем, программ.

5. СЛОВЕСНЫЙ СПОСОБ ОПИСАНИЯ АЛГОРИТМОВ Это, по существу, обычный язык, но с тщательным отбором слов и фраз, не допускающих лишних слов, двусмысленностей и повторений. Дополняется язык обычными математическими обозначениями и некоторыми специальными соглашениями. Алгоритм описывается в виде последовательности шагов. На каждом шаге определяется состав выполняемых действий и направление дальнейших вычислений. При этом, если на текущем шаге не указывается какой шаг должен выполняться следующим, то осуществляется переход к следующему шагу.

Пример 1. Решение: Пример 1. Составьте алгоритм нахождения наибольшего из трех заданных чисел a, b, c. Решение: 1. Сравнить a и b. Если a>b, то в качестве максимума t принять a, иначе (a<=b) в качестве максимума принять b. 2. Сравнить t и c. Если t>c, то перейти к шагу 3. Иначе (t<=c) принять в качестве максимума с (t=c). 3. Принять t в качестве результата.

НЕДОСТАТКИ СЛОВЕСНОГО СПОСОБА ОПИСАНИЯ АЛГОРИТМОВ отсутствие наглядности, недостаточная точность.

ДОСТОИНСТВА СЛОВЕСНОГО СПОСОБА ОПИСАНИЯ АЛГОРИТМОВ С его помощью можно описать любые алгоритмы, в том числе и вычислительные.

СПЕЦИАЛЬНЫЕ СОГЛАШЕНИЯ, ИСПОЛЬЗУЕМЫЕ ДЛЯ ЗАПИСИ СЛОВЕСНЫХ АЛГОРИТМОВ. 1) все шаги нумеруют, 2) для задания значения исходных данных используют указания: ВВЕСТИ, 3) для запоминания промежуточного результата используют вспомогательные переменные, 4) для задания значений переменных используется знак присваивания (:=). Слева от него записывают ту переменную, которой присваивается значение выражения, находящегося справа от знака присваивания. Например, x:=x+1, 5) для указания начала и конца алгоритма используют указания: НАЧАЛО и КОНЕЦ.

Пример 2. Составьте алгоритм построения треугольника по трём сторонам. Решение: Алг Треугольник Начало 1. На произвольной прямой выбрать точку А. 2. Раствором циркуля, равным а, отложить отрезок АВ=а. 3. Из точки А провести окружность радиуса b. 4. Из точки В провести окружность радиуса с. 5. Точку пересечения окружностей обозначить С. 6. Соединить точку С с точками А и В. Конец

6. ГРАФИЧЕСКИЙ СПОСОБ ОПИСАНИЯ АЛГОРИТМА (БЛОК-СХЕМЫ) Это способ представления алгоритма с помощью общепринятых графических фигур (блоков), каждая из которых описывает один или несколько шагов алгоритма. Внутри блока записывается описание команд или условий. Для указания последовательности выполнения блоков используют линии связи (линии соединения). Последовательность блоков и линий образуют блок-схему алгоритма.

ПРАВИЛА ИЗОБРАЖЕНИЯ БЛОК-СХЕМ АЛГОРИТМА 1. В блок-схеме можно использовать строго определенные типы блоков. Основные типы блоков: - начало и конец описания алгоритмов; - ввод исходных данных или вывод результатов; - блок арифметических или других действий; - блок проверки условий, от которых зависит выбор направления алгоритма.

2. Стрелки на линиях связи можно не ставить при направлении сверху вниз и слева направо; 3. Противоположные направления обязательно указывают стрелкой на линии. 4. Для удобства блоки могут помечаться метками (буквами или цифрами). 5. Внутри блока ввода/вывода пишется ВВОД или ВЫВОД и перечисляются имена данных, принадлежащих вводу/выводу. 6. Внутри блока действия для присваивания переменных значений используется знак присваивания. ПРАВИЛА ИЗОБРАЖЕНИЯ БЛОК-СХЕМ АЛГОРИТМА

Пример нахождения максимума трех чисел.

7. ОПИСАНИЕ АЛГОРИТМОВ С ПОМОЩЬЮ ПРОГРАММ Программа - алгоритм, записанный на языке программирования. Алгоритм, предназначенный для исполнения на компьютере, записывается на языке программирования ( языке, понятном ЭВМ). Наиболее популярные языки: Си Паскаль Delphi Бэйсик

Задачи Бейсик

8.1. В заданном слове (тексте) подсчитать количество: а) всех символов; б) всех слов; в) данных букв; г) слов, начинающихся с заданной буквы; д) всех цифр; е) строчных (заглавных) латинских (русских) букв Преобразовать введенное слово в последовательность кодов его букв. Решить и обратную задачу Переписать заданное слово (фразу) в обратном порядке.

10 LINE INPUT A$ 20 PRINT"Количество символов:";LEN(A$) 5 'б - количество слов 10 LINE INPUT A$ 20 FOR I=1 TO LEN(A$) 30 IF MID$(A$,I,1)=" "THEN K=K+1 40 NEXT50 PRINT"Количество слов:";K+1 5 'в

10 LINE INPUT A$ 20 B$=INPUT$(1) 30 FOR I=1 TO LEN(A$) 40 IF MID$(A$,I,1)=B$ THEN L=L+1 50 NEXT60 PRINT"Количество вхождений буквы (";B$;"):";L 5 'г

10 LINE INPUT A$ 20 B$=INPUT$(1) 30 IF LEFT$(A$,1)=B$ THEN M=1 40 FOR I=1 TO LEN(A$) 50 IF MID$(A$,I,2)=" "+B$ THEN M=M+1 60 NEXT

70 PRINT"Количество слов, начинающихся с ";B$;":";M 5 'д - е - количество цифр (строчных (заглавных) латинских (русских) букв) 10 LINE INPUT A$ 20 FOR I=1 TO LEN(A$) 30 IF ASC(MID$(A$,I,1)) 47 THEN K=K+1 31 'IF ASC(MID$(A$,I,1)) 96 THEN K=K+1

32 'IF ASC(MID$(A$,I,1)) 64 THEN K=K+1 33 'IF ASC(MID$(A$,I,1)) 191 THEN K=K+1 34 'IF ASC(MID$(A$,I,1)) 223 THEN K=K+1 40 NEXT 50 PRINT"Количество цифр:";K

51 'PRINT"Количество строчных латинских букв:";K 52 'PRINT"Количество заглавных латинских букв:";K 53 'PRINT"Количество строчных русских букв:";K 54 'PRINT"Количество заглавных русских букв:";K

'слово - в последовательность кодов 10 LINE INPUT A$ 20 FOR I=1 TO LEN(A$) 30 PRINT ASC(MID$(A$,I,1)); 40 NEXT

5 'последовательность кодов - в слово 10 INPUT"Количество букв:";N 20 FOR I=1 TO N 30 PRINT"Код буквы N ";I;:INPUT A 40 C$=C$+CHR$(A)50 NEXT60 PRINT C$

'переписывание слова в обратном порядке 10 LINE INPUT"Слово:";A$ 20 FOR I=LEN(A$) TO 1 STEP-1 30 PRINT MID$(A$,I,1); 40 NEXT

8. ДОМАШНЕЕ ЗАДАНИЕ §41, §43, конспект, Задача: –Имеются два кувшина: 8 л и 3 л. С помощью этих кувшинов налейте 4 л. воды. Опишите алгоритм решения задачи словесным способом и графическим.