Учебное электронное издание Алгоритмизация и программирование

Раздел «Алгоритмизация и программирование» ГОУ СПО ЯО Угличский механико-технологичский техникум Основные понятия Алгоритм – это понятное и точное указание исполнителю совершить последовательность действий, направленных на решение поставленной задачи.Исполнителем может быть человек и техническое устройство.Примерами алгоритмов могут быть аптечные и поваренные рецепты, инструкции по эксплуатации бытовой техники, математические алгоритмы умножения, деления и др. Свойства алгоритма Дискретность – разделение информационного процесса в алгоритме на отдельные команды (шаги).Понятность – алгоритм должен составляться в расчете на конкретного исполнителя с учетом его возможностей.Определенность – команды должны быть предельно четкими и однозначными.Конечность – любой алгоритм должен завершиться за конечное число шагов.Корректность - любой алгоритм создан для решения определенной задачи. Решение будет правильным для любых допустимых исходных данных.Массовость – алгоритм может применяться для многократного решения при различных наборов исходных данных Способы описания алгоритмов Словесный – на алгоритмическом языке, на языке программирования;Input x, yP=x*yS=x+y Print S, P, Графический – с помощью блок – схем. начало конец x, y S, P, P=x*y S=x+y Стандартные обозначения, принятые в блок схемах Наименование блочных символов Обозначение Определение функции или действия Процесс (действие) Выполнение операции или группы операций, в результате которых изменяется значение, форма представления или расположения данных Решение (ветвление по условию) Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий. Ввод- вывод Преобразование данных в форму, пригодную для обработки (ввода) или регистрации результатов обработки (вывод) Линии потока Указание последовательности связей между символами. Стандартные обозначения, принятые в блок схемах Наименование блочных символов Обозначение Определение функции или действия Пуск - останов Начало, конец, прерывание процесса обработки данных или выполнение программы. Соединитель Указание связей между прерванными линиями потока для символов, представленных на одном листе. Межстраничный соединитель Указание связи между разъединенными частями схем алгоритмов и программ, расположенных на разных листах. Линейные алгоритмы Линейный алгоритм Алгоритм, в котором все этапы решения задачи выполняются строго последовательно, без пропусков и повторений называется линейным.Линейный алгоритм решения имеют простейшие задачи. Действие 1 Действие 2 Действие 3 Пример 1. Вычислить площадь круга при заданном значении радиуса R. Дано: Математическая модельR S = 3,14*R2 S-? Блок – схемаПрограмма на языке Бейсик начало конец R S S=3,14*R2 Даны два действительных числа x,y. Вычислить их сумму, разность, произведение и частное. Дано: Математическая модель x, yS=x+y R= x-y P=x*y C=x/y S, R, P, C Блок – схема Программа на языке Бейсик начало конец x, y S, R, P, C P=x*y C=x/y S=x+y R= x-y Задачи Составить алгоритм вычисления площади треугольника со сторонами a,b,c (a,b,c –вещественные числа).Вычислить периметр и площадь прямоугольного треугольника по заданным длинам двух катетов.Даны два действительных числа x,y. Вычислить их сумму, разность, произведение и частное.Три сопротивления R1, R2, R 3 соединены параллельно. Найти сопротивление соединения Rобщ. Даны два действительных числа x,y. Вычислить их сумму, разность, произведение и частное. Дано: Математическая модель x, yS=x+y R= x-y P=x*y C=x/y S, R, P, C Блок – схема Программа на языке программирования начало конец x, y S, R, P, C P=x*y C=x/y S=x+y R= x-y Язык программирования QBasic Оператор INPUT (ввод) позволяет присвоить значение переменным с клавиатуры во время выполнения программы.Формат записи оператораINPUT«комментарий»;список переменныхПример записи оператораINPUT«ввести значение х1,х2,х3»;х1,х2,х3 Язык программирования QBasic Оператор PRINT (вывод) позволяет вывести информацию в зонном (,) и уплотненном формате(;).Формат записи оператораPRINT список выраженийПример записи оператора PRINT 20,А,В;2 Язык программирования QBasic Оператор REM является строкой комментария.Формат записи оператораREM комментарийПример записи оператораREM вычисление суммы 3 чисел Язык программирования QBasic Оператор END (конец) завершает выполнение программы, закрывает все файлы, не выходя из системы QBasicФормат записи оператораEND Математические функции и выражения ABS(x) Определить абсолютное значение аргумента SQR(x) Извлечь квадратный корень из аргумента. EXP(x) Возвести число е в степени х LOG(x) Определить натуральный логарифм числа TAN(x) Вычислить тангенс аргумента SIN(x) Вычислить синус аргумента ATN(x) Вычислить арктангенс аргумента * умножение / \ Деление (целочисленное деление) ^ Возведение в степень Пример 1. Написать программу вычисления площади круга при заданном значении радиуса R. Дано: Математическая модельR S = 3,14*R2 S-? Блок – схемаНа языке Бейсик начало конец R S S=3,14*R2 REM вычисление площади кругаINPUT«ввести значение радиуса R»;RS=3,14*R^2PRINT SEND Задача 3. Даны два действительных числа x,y. Вычислить их сумму, разность, произведение и частное. Дано: Математическая модель x, yS=x+y R= x-y P=x*y C=x/y S, R, P, C Блок – схема Программа на языке программирования начало конец x, y S, R, P, C P=x*y C=x/y S=x+y R= x-y REM вычисление суммы, разности, произведения частного Х,Y INPUT «ввести значение x, y»; x, yP=x*y C=x/yS=x+y R= x-yPRINT S, R, P, CEND Задачи для самостоятельной работы 1. Дана длина ребра куба. Найти площадь грани, площадь полной поверхности и объем этого куба.2. Найти произведение цифр заданного четырехзначного числа.3. Вычислить корни квадратного уравнения a*x^2+b*x+c=0, заданного коэффициентами a, b, c. Предполагается а≠0 и D>0.4. Полторы кошки за полтора часа съедают полторы мышки. Сколько мышек съедят Х кошек заY часов. Задачи для самостоятельной работы Обработка символьной информации Работа с символьными данными Выделение определенной части символьного выражения – функции LEFT$, MID$, RIGHT$.Замена части символьного выражения – оператор MID$.Обработка числовой информации в тексте –функцииVAL и STR$.Определение количественных характеристик символьных строк – функции LEN и INSTR.И др. Функции LEN(X$) – вычисляет длину строки символов X$;INSTR(I,X$,Y$) – отыскивает место первого появления строки символов Y$ в строке X$ и выдает номер позиции, на которой она была найдена. I- номер позиции, с которой должен начаться поиск. Если I отсутствует, то поиск начинается с первой позиции Выделение определенной части символьного выражения Имеются три функции, которые позволяют выделить определенную часть символьного выражения: правую RIGHT$, левую- LEFT$, среднюю MID$. Формат записи функции LEFT$:LEFT$(x$,n), где x$-исходное символьное выражение; n – количество символов, выделяемых из символьного выражения, начиная с крайнего левого символа текстовой строки. Формат записи функции MID$, MID$ (x$, n, m), x$- исходное символьное выражение, n- определяет начальную позицию символьного выражения, начиная с которой будет выделена подстрока, m – длина подстроки.Например.x$=«Колесо»PRINT MID$ (x$, 2, 3) Формат записи функции RIGHT$ RIGHT$(x$, n ) ,где x$-исходное символьное выражение; n – количество символов, выделяемых из символьного выражения, начиная с крайнего правого символа текстовой строки. Задания 1. Используя функции LEFT$, MID$, RIGHT$, составить свою фамилию из 4 слов.Например. «Иванова» из слов «диван», «коза», «ворона», «лак».A$= «диван» B$= «коза»C$= «ворона»D$= «лак»PRINT MID$(A$,2,4);MID$(B$,2,1);LEFT$(C$,1); MID$(D$,2,1) Задание 2. Зашифровать фразу «завтра не учимся», используя 8 слов. Обработка графической информации Работа с графической информацией Графические программные средства позволяют создавать на экране дисплея сложные изображения с различной глубиной свечения точек, а также выводить одновременно с графической текстовую информацию. Операторы и функции, используемые при работе с графикой. № Оператор или функция Назначение 1. CIRCLE Построить эллипс, окружность. 2. COLOR Выбрать цвет 3. DRAW Изобразить сложную фигуру, объект. 4. LINE Начертить линию, отрезок. 5. PAINT Окрасить фигуру, объект. 6. PSET Изобразить точку 7. PRESET Убрать свечение точки. 8. SCREEN Установить режим работы экрана. Оператор SCREEN Устанавливает режим и параметры работы дисплея.Формат записи SCREEN{1 2} [,[цветное изображение][,[активная страница][, отображаемая страница]]]{ }- указывается параметр выбора[ ] - параметр не обязательный Оператор SCREEN SCREEN 1,0 – цветное изображениеSCREEN 1,1 – средняя разрешающая способность, ширина текстовой строки 40 колонокSCREEN 2 -средняя разрешающая способность, ширина текстовой строки 80 колонокSCREEN 0,0,0 – переход от графического режима к текстовому. Оператор COLOR Позволяет выбрать фон и палитру цветов для переднего плана.Формат записи оператораCOLOR[фон] [, палитра цветов переднего плана] Для цветного изображения фон выбирается из таблицы Цвета, используемые при цветном графическом режиме Номер цвета Передний план 0 Черный 1 Синий 2 Зеленый 3 Голубой 4 Красный 5 Пурпурный 6 Коричневый 7 Белый Оператор LINE Позволяет начертить отрезок, линию или прямоугольник.Формат записиLINE[(x1,y1)] - (x2,y2) [,[цвет][,[B[F]], где (x1,y1), (x2,y2) – координаты точек начала и конца отрезка;B[F] – рисуется прямоугольник (закрашенный).Если (x1,y1) отсутствует, то в качестве начальной точки используется координата точки, которая последней участвовала в обработке. Оператор CIRCLE Позволяет получить на экране дисплея эллипс, круг.Формат записи CIRCLE (x1,y1),R[,[цвет][,[начало] [,[конец][,сжатие]]]]Где (x1,y1) – координаты центра эллипса, R – любое числовое выражение, значение которого задает большую полуось эллипса Задание 1 Построить прямоугольник с помощью 4 линий.SCREEN 2KEY OFF: CLSочистка экранаLINE (200,50) - (400,50)LINE – (400,100)LINE – (200,100)LINE – (200,50) (200,50) (200,100) (400,100) (400,50) Задание 2 Построить три прямоугольника, вложенных друг в друга. (79, 24) (159, 49) (239, 74) (319, 99) (399, 124) (559, 159) Задание 3 (0,0) Задание 4 Получение четырех эллипсов.REMSCREEN 1KEY OFF: CLSCIRCLE (100,100), 100CIRCLE (100,100), 100, 1, , , 3/10CIRCLE (100,100), 100, 2, , , 4/10CIRCLE (100,100), 100, 3, , , 5/10END Задание 5 Построение двух взаимно перпендикулярных эллипсов.SCREEN 1KEY OFF: CLSCIRCLE (320,100), 50, , , , 2CIRCLE (320,100), 100, , , , 5/30END Задание 6 Варианты построения дуг эллипсовSCREEN 2KEY OFF: CLSPI=3.14CIRCLE (160,50), 50, , PI, PI/2CIRCLE (160,50), 40, , PI/2 ,PICIRCLE (320,50), 50, ,-PI/2,- PI CIRCLE (480,50), 40, , -PI, PI/2CIRCLE (160,150), 50, , PI/2, PI/4CIRCLE (160,150), 40, , PI/2 , -PI/4CIRCLE (320,150), 50, , 0, PI/4CIRCLE (480,150), 50, , PI/4 , -3/4*PICIRCLE (480,150), 40, , -PI/4, -3/4*PIEND Задание 7 70 270 Задание 8 Задание 9 Нелинейные структурные элементы программ В нелинейных частях программы используются операторы переходов, по которым управление передается в нужное место программы. По назначению операторы переходов делятся на две группы:операторы для организаций ветвлений, которые позволяют выбрать одно из двух возможных направлений продолжения программы;Операторы для организации циклов, позволяющих обращаться к группам операторов и выполнять несколько раз. Операторы переходов Организация ветвлений Организация циклов Безусловные переходы Условные переходы простых сложных GOSUB GOTO RETURN IF – GOTOIF – THEN – ELSE FOR – TO - NEXT Разветвляющиеся алгоритмы Ветвлением называется такая алгоритмическая структура, в которой выбирается один из возможных путей выполнения алгоритма с непременным выходом на общее продолжение.Каждый такой путь называется ветвью алгоритма. Существует две формы ветвления: полная, неполная. Условие Серия команд 1 Серия команд 2 Да Нет Условие Серия команд 1 Да Нет На алгоритмическом языке структура ветвление записывается в форме:Если выполняется условие то выполняется серия команд 1 иначе выполняется серия команд 2Если выполняется условие то выполняется серия команд 1 Условия могут быть простыми и сложными.Простое условие – это выражение, составленное из двух переменных, арифметических выражений или двух текстовых величин, связанных одним из знаков сравнения (< > = <= >= < >) Сложное условие – это последовательность простых условий, объединенных между собой знаками логических операций (AND, OR, NOT). Например, 70 то X1= (-B+SQR(D))/(2*A) и X2= (-B-SQR(D))/(2*A) иначе «решений нет» Задание 1Найти корни квадратного уравнения a*x^2+b*x+c=0 Задание 2 Ввести значение переменной Х, если число больше 10 , то вывести на экран «достаточно» иначе «мало». Задание 3 Найти модуль числа Х.Дано:Математическая модель:ХЕсли Х<0, Х1=(-1)*Х иначе Х1=ХНайти:Х1 начало Х Х<0 Х1=(-1)*Х Х1=Х Х1 конец Да Нет Input «ввести значение х»;ХIF X<0 THEN X1=(-1)*X ELSE X1=XPrint X1 Циклические алгоритмы Циклы Циклом называется программа (или часть программы), многократно выполняемая при заданном условии.Цикл охватывает последовательность операторов, заключенную между оператором перехода и оператором, который позволяет возвратиться на начало цикла. Циклы на языке Бейсик Общая структура арифметического цикла Оператор FOR - TO Последовательность операторов оператор NEXT Выход Вход Операторы FOR – TO (для – к ) и NEXT (следующий) предназначены для многократного выполнения операторов, заключенных в этом блоке. FOR переменная цикла = начальное значение цикла ТО конечное значение цикла STEP значение шага цикла,Начальное и конечное значения цикла и шага могут быть записаны с помощью арифметических выражений. Значение шага может быть записаны как с положительным, так и с отрицательным знаком. Если STEP равен 1, то операнд может отсутствовать.NEXT всегда заканчивает блок.В операторе перечисляются переменные цикла, которые были указаны в операторе FOR – ТО. Задание 1. Задана последовательность чисел от 1 до 10. Найти сумму квадратов этих чисел. Составить алгоритм и программу. Дано[1; 10],Step 1Найти: S Математическая модель:S = 0,I =1Если, то S = S+I^2 данная последовательность повторяется до тех пор пока значение I не достигнет 10 начало конец S=0 I=1 I>10 НапечататьS Да Нет S=S+I^2 I=I+1 1 шаг: I=1, S=12 шаг: I=2, S=53 шаг: I=3, S=144 шаг: I=4, S=305 шаг: I=5, S=556 шаг: I=6, S=917 шаг: I=7, S=1408 шаг: I=8, S=2049 шаг: I=9, S=28510 шаг: I=10, S=38511 шаг: I=11 вывод S=385 Задание 2 Найти произведение членов последовательности 12,14,16,18,20,22.Составить блок схему Задание 1. Составить программу, подсчитывающую количество букв «А» в тексте. REM Сколько букв А в тексте INPUT «Введите текст»; S$L=LEN(S$)K=0FOR I=1 TO LX$=MID$(S$,I,1)IF X$=«А» THEN K=K+1NEXT IPRINT «в тексте», К , «букв А» Используемая литература Угринович Н.Д. Информатика и информационные технологии. Учебник для 10-11 классов. – М.: Бином, 2007.Угринович Н.Д. Босова Л.Л., Михайлова Н.И. Практикум по информатике и информационным технологиям. Учебное пособие для общеобразовательных учреждений. – М.: БИНОМ Лаборатория знаний, 2006.Угринович Н.Д. Преподавание курса «Информатика и ИКТ» в основной старшей школе (7-11 кл.).- М.: БИНОМ Лаборатория знаний, 2006.