Алгоритмизация. Подготовила: Камышная И.Н.

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

Алгоритм и его свойства Основными свойствами алгоритмов являются: 1. Универсальность (массовость) - применимость алгоритма к различным наборам исходных данных. 2. Дискретность - процесс решения задачи по алгоритму разбит на отдельные действия. 3. Однозначность - правила и порядок выполнения действий алгоритма имеют единственное толкование. 4. Конечность - каждое из действий и весь алгоритм в целом обязательно завершаются. 5. Результативность - по завершении выполнения алгоритма обязательно получается конечный результат. 6. Выполнимость - результата алгоритма достигается за конечное число шагов.

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

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

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

Способы записи алгоритмов Общепринятыми способами записи являются графическая запись с помощью блок-схем и символьная запись, с помощью какого-либо алгоритмического языка. Описание алгоритма с помощью блок схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Написание алгоритмов с помощью блок-схем регламентируется ГОСТом.

Внешний вид основных блоков

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

Алгоритм линейной структуры В алгоритмах линейной структуры действия выполняются последовательно одно за другим:

Алгоритм разветвленной структуры В алгоритмах разветвленной структуры в зависимости от выполнения или невыполнения какого-либо условия производятся различные последовательности действий. Каждая такая последовательность действий называется ветвью алгоритма. Условие Ветвь 1Ветвь 2

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

Основные элементы алгоритмического языка Имена (идентификаторы) - последовательность символов для обозначения объектов программы (переменных, массивов, функций и др.). Существуют следующие типы операций: - арифметические операции: сложение, обозначается символом +; вычитание, обозначается символом -; умножение, обозначается символом *; деление, обозначается символом / и др.; - логические операции: операции логическое и, логическое или, логическое не и др.; - операции отношения: меньше, обозначается символом ; меньше или равно, обозначается символами =; равно, обозначается символом =; не равно, обозначается символами . - операция конкатенации символьных значений друг с другом, изображается знаком "+". Данные - величины, обрабатываемые программой.

Основные элементы алгоритмического языка Константы - это данные, которые зафиксированы в тексте программы и не изменяются в процессе ее выполнения. Примеры констант: числовые: 7.5, 12; логические: true(истина), false(ложь); символьные: "А", "+"; строковые: "abcde", "информатика". Переменные – это данные, которые могут изменять свои значения в ходе выполнения программы. Они обозначаются именами. Переменные бывают целые, вещественные, логические, символьные и строковые. Массивы - последовательности однотипных элементов, число которых фиксировано и которым присвоено одно имя. Положение элемента в массиве однозначно определяется его индексами - одним в случае одномерного массива, или несколькими, если массив многомерный. Выражения – элементы языка, которые предназначаются для выполнения необходимых вычислений, состоят из констант, переменных, указателей функций, объединенных знаками операций. Выражения записываются в виде линейных последовательностей символов (без подстрочных и надстрочных символов, "многоэтажных" дробей и т. д.), что позволяет вводить их в компьютер, последовательно нажимая на соответствующие клавиши клавиатуры.

Основные элементы алгоритмического языка Различают выражения арифметические, логические и строковые. Арифметические выражения служат для определения одного числового значения. Арифметические выражения записываются по следующим правилам: 1. Нельзя опускать знак умножения между сомножителями и ставить рядом два знака операций. 2. Индексы элементов массивов записываются в скобках. 3. Операции выполняются в порядке старшинства: сначала вычисление функций, затем возведение в степень, потом умножение и деление и в последнюю очередь - сложение и вычитание. 4. Операции одного старшинства выполняются слева направо. Логические выражения описывают некоторые условия, которые могут удовлетворяться или не удовлетворяться. Таким образом, логическое выражение может принимать только два значения - "истина" или "ложь" (да или нет).

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

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

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

Основные элементы алгоритмического языка Функция - это программная единица, которая может быть употреблена в выражении. Функция прямо возвращает величину, которая используется при вычислении этого выражения, и, кроме того, может возвращать величины через параметры. Подпрограммы и функции позволяют создавать большие структурированные программы, которые можно делить на части. Это дает преимущества в следующих ситуациях: 1. Если программа большая, разделение ее на части облегчает создание, тестирование и ее сборку. 2. Если программа большая и повторная компиляция всего исходного текста занимает много времени, разделение ее на части экономит время компиляции. 3. Если процедуру надо использовать в разных случаях разным образом, можно записать ее в отдельный файл и скомпилировать отдельно.

Символы языка. буквы – латинские строчные и прописные, буквы русского алфавита допустимы только в текстовых константах и комментариях; цифры – только арабские от 0 до 9; знаки арифметических операций: сложение (+), вычитание (-), умножение (*), деление (/), возведение в степень (^ ); знаки логических операций: a OR b – «или», логическое сложение, равно «Истина», если истинно a или b a AND b– «и», логическое умножение, равно «Истина», если и a и b истинны a XOR b– «исключающее или», равно «Истина», если истинно только a или только b, NOT b логическое отрицание; знаки операций отношения: a>b (больше), a

Виды переменных Есть 3 вида переменных: 1. Целые – к этим переменным в имени добавляется значок %. ПРИМЕР: Symma% = 1, но нельзя записывать не целые значения (такие как: 0,5 или 0,002 или 1,5) 2. Символьные (литерный, строковый) – к этим переменным в имени добавляется значок $. ПРИМЕР: name$ = Артем, R$ = 2+3=4 3. Действительные – к этим переменным не надо добавлять значок. ПРИМЕР: Symma, Ao1

ПРИМЕР Обычная запись На Qbasic Sqr(x) Abs(x) sin xSin(x) cos xCos(x) tg xTan(x) Ctg x Arcsin xAsn(x) arccos xAcs(x) Arctg xAtn(x) e x Exp(x)

Линейный алгоритм Алгоритм линейной структуры – алгоритм, в котором команды выполняются последовательно друг за другом в естественном порядке и независимо от каких бы то ни было условий. Для записи линейных программ используются операторы: ввода; вывода; присваивания; конца программы.

Линейный алгоритм P$ - Добрый день; O$ - дорогая ; NN$ - Машенька!, то в результате выполнения операций сцепления переменной XX$ будет присвоено значение Добрый день, дорогая Машенька!, что и будет выведено на экран. Начало ввод Приветствие,Р$ ввод Форма обращения,О$ ввод Имя, NN$ XX$ = P$+,+O$+NN$ вывод ХХ$ Конец

Алгоритм ветвления Важным для составления программ является сравнение: чисел, условий, значений и т.д. За сравнение в Qbasic отвечает оператор - IF …. THEN … ELSE If (если) THEN (тогда) ELSE (иначе)

Алгоритм ветвления IF условие THEN действие 1 ELSE действие 2 Если выполняется условие, тогда действие 1, иначе действие 2

Алгоритм ветвления Синтаксис условного оператора. IF условие THEN оператор 1 ELSE оператор 2, где условие – логическое выражение, оператор 1 – оператор или группа операторов, которые будут работать в случае, если логическое выражение истинно, оператор 2 - оператор или группа операторов, которые будут работать в случае если логическое выражение ложно. Краткая форма оператора IF: IF условие THEN оператор здесь при невыполнении условия управление передается строке, следующей за IF; если же условие выполняется, то работают операторы, записанные после слова THEN в той же строке. IF условие GOTO nc где nc – номер строки или метка оператора, куда осуществляется переход в случае выполнения условия. Могут встречаться достаточно сложные конструкции, когда внутри одного оператора IF находится другой оператор IF, так называемый, вложенный IF, например: IF условие. THEN операторы 1 ELSE IF условие THEN операторы 2 ELSE операторы 3 Заметим, что в программе это должно быть написано в одной строке, таково требование синтаксиса. Когда по одному условию выполняется несколько операторов, чтение программы затруднено, т.к. все они записаны должны быть в одну строку и строка становится слишком длинной. В таком случае рекомендуется создавать блок IF, в котором операторы можно записывать в столбик, а не в строчку, что облегчает чтение и понимание программы. Блок- IF Синтаксис: IF условие THEN … оператор 1 …… оператор N ELSE … оператор 2 …. операторM END IF Необходимо четко различать блок и оператор IF. Если в строке после THEN записан хотя бы один оператор, то такая конструкция считается оператором IF. Следующий после нее оператор выполняется безусловно.0

Алгоритм ветвления Для нарушения линейного порядка выполнения программы используются операторы передачи управления: оператор безусловного перехода GOTO. условный оператор IF … THEN …ELSE. Синтаксис оператора GOTO. GOTO номер строки или GOTO метка. Меткой является идентификатор, заканчивающийся символом : стоящий перед оператором. Управление передается строке с соответствующим номером или оператору, перед которым стоит метка. Пример: M1: a=a*10 … GOTO M1 Пример: 10 a=a*15 … 100 GOTO 10 STOP – оператор логического конца программы. Им можно воспользоваться в том случае, когда программа должна быть завершена досрочно.

Алгоритм ветвления Если у Вас два условия, то их записывают так: IF A = N AND N = C THEN … этот способ используется, если два условия должны выполняться одновременно. (AND – и). IF A = N OR N = C OR A = C THEN … а этот способ, если хотя бы одно условие должно выполниться. (OR – или).

Пример Проверка правильности ввода пароля, например, «36w54». Описание алгоритма: вводится пароль Р$; проверяется равенство введенного пароля заданному значению; если пароль введен верно, то выводится сообщение «Здравствуйте» и начинается выполнение программы, защищенной паролем;Началоввод Пароль?,Р$P$=39W54Вывод Пароль неверен!Вывод Здравствуйте!Программа Конец если пароль введен неверно, то выводится сообщение Пароль неверен!, а защищенная паролем программа выполняться не будет.

Пример алгоритма Начало ввод Пароль?,Р$ P$=39W5 4 Вывод Пароль неверен! Вывод Здравствуйте ! Программа Конец

Пример алгоритма INPUT Пароль!,P$ If P$=39w54 THEN Print Пароль неверен! Программа выполняться не будет!: STOP END IF PRINT Здравствуйте» > END

Цикл Цикл – это многократное повторение одних и тех же операций. Виды циклов: циклы с заданным числом повторений (шагов); циклы с неизвестным числом повторений (шагов). К последним относятся итерационные циклы, характеризующиеся последовательным приближением к искомому значению с заданной точностью.

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

Основные понятия Тело цикла – это операторы, которые многократно повторяются в процессе выполнения цикла. Параметр цикла – это величина, которая меняет свое значение при каждом входе в цикл.

Цикл с параметром FOR k = k1 TO k2 STEP s ……………….. NEXT k Иначе говоря: ДЛЯ k = k1 ДО k2 ШАГ s …………….. СЛЕДУЮЩЕЕ ЗНАЧЕНИЕ k k – параметр цикла. k1 – начальное значение параметра. k2 – конечное значение параметра. s – величина, которая показывает на сколько изменится параметр цикла при каждом входе в цикл.

Цикл с параметром В начале параметру циклу k присваивается значение k1 и один раз выполняется тело цикла. Вслед за этим оператор NEXT увеличивает значение параметра на величину s. И проверяет, не превысило ли новое значение параметра, конечного k2, если нет, то снова выполняется тело цикла, но уже для нового значения параметра. А если новое значение превысило k2, то происходит выход из цикла, и управление передается оператору, который стоит после NEXT. счетный цикл FOR x=xo TO xk [STEP h] Тело цикла NEXT [x] тело цикла к следующему за циклом оператору x=x 0,x k,h

Циклический алгоритм Между FOR…… и NEXT могут стоять любые операторы, они будут являться телом цикла. ПРИМЕР: FOR w = 1 TO 50 STEP 2 IF ….. THEN…..ELSE NEXT w FOR w = 1 TO 50 STEP 2 symma = w + 1 NEXT w FOR w = 1 TO 50 STEP 2 INPUT.. IF …. THEN… PRINT … NEXT w INPUT … FOR w = 1 TO 50 STEP 2 IF ….. THEN…..ELSE NEXT w PRINT …

Пример Вычислить множество значений функции y=x 2 +b для всех значений x от -10 до 10 с шагом 2, при b=5 CLS B=5 FOR X=10 TO 10 STEP 2 Y= x 2 +b PRINT Y NEXT X END

Цикл до и Цикл пока Цикл до Есть два способа записи: I) 1 S IF NOT (p) THEN 1 выход из цикла II) DO (тело цикла) LOOP WHILE (условие) Тело цикла выполняется до истинности условия P. да нет тело цикла к следующему за циклом оператору условие

Цикл «пока» WHILE условие (тело цикла) WEND ( пока выполняется условие, выполнять тело цикла ) да нет к следующему за циклом оператору тело цикла условие

Задача Изменить программу проверки правильности ввода пароля, предоставив три попытки ввода пароля. Если пароль вводится трижды неправильно, то выполнение программы прекращается. Рассмотрим решение задачи тремя способами. 1-ый способ – организация цикла с помощью операторов If… и Goto. Программа P$=#$W56 K=0 55 Input Пароль, X$ K=K+1 If K>3 Then Print Нет доступа!: Stop If P$X$ Then Print Пароль неверен. Попытка, К: Goto 55 Print Программа выполняется! > End

Задача 2-ой способ – организация цикла с помощью оператора While … Wend Описание алгоритма: Программная реализация алгоритма P$=#$W56 K=0 While K End

Задача 3-ий способ – организация цикла с помощью оператора For Описание алгоритма: Алгоритм отличается от предыдущего использованием оператора For K=1 To 3, который сам умеет считать циклы, поэтому счетчик К=К+1 не требуется. Программная реализация алгоритма. P$=#$W56 For K=1 To 3 Input Введите пароль, X$ If P$=X$ Goto 44 Print Пароль неверен. Попытка К Next Print Нет доступа! Stop 44 Print Программа выполняется! > End

Текстовые функции Слово – это любая последовательность символов некоторого алфавита. Алфавит - любая последовательность цифр, букв любого алфавита, а так же любые знаки препинания. Длина слова – это число символов в слове. Пустое слово – это слово, которое не содержит символов. Длина пустого слова = 0. Переменные слов всегда обозначаются значком - $ Основные операции над словами: Выделение части слова. Соединение слова (значок +) Слова можно сравнивать.

Операторы, которые производят операции над словами LEN(x$) – вычисляет длину заданного слова x$. x$ = Петров-Волков l = LEN$(x$) l = 13 Значит так, в данном примере Петров – Волков – это слово. И его длина 13, но если поставить пробелы перед и после -, то длина станет 15, так как оператор LEN считает и пробелы и ведь они то же входят в слово.

Операторы, которые производят операции над словами LEFT$(x$, r) – вырезаетиз переменной x$, r символов слева. CLS x$ = Петров-Волков a$ = LEFT$ (x$, 4) PRINT a$ END При выполнении этой программы компьютер отсчитает слева 4 символа и «вырежет» их. И слово a$ будет Петр.

Операторы, которые производят операции над словами RIGHT$(x$, r) – «вырезает» справа r символов. CLS x$ = Петров-Волков x$ = RIGHT$(x$, 6) PRINT a$ END После выполнения программы a$ будет Волков.

Операторы, которые производят операции над словами MID$(x$, p, r) – «вырезает» из переменной x$, r символов с позиции p CLS x$ = Петров-Волков v$ = MID$(x$, 4, 3) PRINT v$ END При выполнении этой программы компьютер будет действовать так, он отсчитает 4 символа и это будет позиция (p), затем он «вырежет» 3 символа, включая позицию. v$ будет равно ров.

Операторы, которые производят операции над словами VAI(x$) – преобразует символьную переменную x$ в десятичное число. CLS x$ = y = VAI(x$) PRINT y END

Операторы, которые производят операции над словами Обратный оператор, который преобразует число в символьную строку с учетом знака (Если число > 0, то вместо знака ставится пробел) – STR$(y) CLS y = 556 x$ = STR$ (y) PRINT x$ END

Операторы, которые производят операции над словами Оператор COLOR. ПРИМЕР: CLS COLOR 7 PRINT Серый COLOR 13: PRINT Сиреневый END Цвет задается числом после оператора. Вот основной список цветов: 0 - Сажа 1 – Темно - синий 2 – Тёмно – зеленый 3 – Тёмно - голубой 4 – Темно - красный 5 – Темно - пурпурный 6 - Цитрус 7 - Серый 8 - Тёмно - серый 9 – Светло - синий 10 - Светло - зеленый 11 – Светло - голубой 12 - Светло - красный 13 - Сиреневый 14 - Жёлтый 15 – Ярко – белый Некоторые сочетания цветов в операторе COLOR: 14, 8 - желтый на темно-сером фоне; 1, 7 - синий на светло-сером фоне; 5, 14 - фиолетовый на желтом фоне; 4, 11 - красный на голубом фоне; 5, 10 - фиолетовый на светло- зеленом фоне; 15, 5 - белый на фиолетовом фоне; 14, 1 - желтый на синем фоне; 15, 1 - белый на синем фоне; 8, 11 - темно-серый на голубом фоне; 1, 15 - синий на белом фоне. Пример: COLOR 1, 15