Сборник практических работ по УД ОП.08 Теория алгоритмов специальности 09.02.03 Программирование в компьютерных системах
МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ СТУДЕНТОВ
Ульяновский авиационный колледж
ПРОФЕССИОНАЛЬНЫЙ ЦИКЛ
ОП.08 ТЕОРИЯ АЛГОРИТМОВ
Практические работы
для специальности ФГОС СПО
09.02.03 Программирование в компьютерных системах
Базовая подготовка
Ульяновск
2016
ОДОБРЕНО
на заседании ЦМК
Программирование и ИТ________________
Протокол № ___
от «____»____________20_____г.
Председатель ЦМК
_________________/_______________/
Подпись Ф.И.О.
УТВЕРЖДАЮ
Зам. директора по УПР
_________________/______________/
Подпись Ф.И.О.
«____»__________ 20 __ г.
РАЗРАБОТЧИК: А.А. Шарифуллина – преподаватель ОГБОУ СПО УАВИАК
Методические указания для студентов по выполнению практических и работ содержат цели, формируемые образовательные результаты, краткие теоретические сведения, методические указания к заданиям, контрольные вопросы для проверки по учебной дисциплине «Теория алгоритмов»
Данные методические указания составлены в соответствии с ФГОС СПО по специальности 09.02.03 Программирование в компьютерных системах (базовый уровень)
СОДЕРЖАНИЕ
стр
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
ПРАКТИЧЕСКИЕ РАБОТЫ
ПР 1
Составление и запись на языке блок-схем линейных алгоритмов.
ПР 2
Составление и запись на языке блок-схем алгоритмов содержащих ветвления.
ПР 3
Составление и запись на языке блок-схем алгоритмов содержащих циклы с предусловием.
ПР 4
Составление и запись на языке блок-схем алгоритмов содержащих циклы с постусловием.
ПР 5
Составление и запись на языке блок-схем алгоритмов содержащих циклы с параметром.
ПР 6
Составление алгоритмов декомпозиционным методом.
ПР 7
Составление алгоритмов сборочным методом.
ПР 8
Оценка сложности алгоритмов методом Кирхгофа.
ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Данные методические рекомендации предназначены для студентов по выполнению практических и лабораторных работ по УД ОП.08 Теория алгоритмов
обучающихся на специальности СПО 09.02.03 Программирование в компьютерных системах (базовый уровень)
На УД ОП.08 Теория алгоритмов
формируются следующие образовательные результаты:
УМЕНИЯ
У1
разрабатывать алгоритмы для конкретных задач
У2
определять сложность работы алгоритмов
ЗНАНИЯ
З1
основные модели алгоритмов
З2
методы построения алгоритмов
З3
методы вычисления сложности алгоритмов
ПРОФЕССИОНАЛЬНЫЕ КОМПЕТЕНЦИИ
ПК1.1
Выполнять разработку спецификаций отдельных компонент
ПК1.2
Осуществлять разработку кода программного продукта на основе готовых спецификаций на уровне модуля
ОБЩИЕ КОМПЕТЕНЦИИ
ОК1
Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
ОК2
Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
ОК3
Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.
ОК4
Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития.
ОК5
Использовать информационно-коммуникационные технологии в профессиональной деятельности.
ОК6
Работать в коллективе и в команде, эффективно общаться с коллегами, руководством, потребителями.
ОК7
Брать на себя ответственность за работу членов команды (подчиненных), за результат выполнения заданий.
ОК8
Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.
ОК9
Ориентироваться в условиях частой смены технологий в профессиональной деятельности.
Для данной УД ОП.08 Теория алгоритмов, где формируются следующие образовательные результаты:
№
практ.
Лабор.
Наименование
практического занятия
Формируемые образовательные
результаты ( У, З, ОК, ПК)
ПР 1
Составление и запись на языке блок-схем линейных алгоритмов.
У1, З1, З2, ПК1.1, ОК2, ОК3, ОК4
ПР 2
Составление и запись на языке блок-схем алгоритмов содержащих ветвления.
У1, З1, З2, ПК1.1, ОК2, ОК3, ОК4
ПР 3
Составление и запись на языке блок-схем алгоритмов содержащих циклы с предусловием.
У1, З1, З2, ПК1.1, ОК2, ОК3, ОК4
ПР 4
Составление и запись на языке блок-схем алгоритмов содержащих циклы с постусловием.
У1, З1, З2, ПК1.1, ОК2, ОК3, ОК4
ПР 5
Составление и запись на языке блок-схем алгоритмов содержащих циклы с параметром.
У1, З1, З2, ПК1.1, ОК2, ОК3, ОК4
ПР 6
Составление алгоритмов декомпозиционным методом.
У1, З1, З2, ПК1.1, ПК1.2, ОК2, ОК3, ОК4
ПР 7
Составление алгоритмов сборочным методом.
У1, З1, З2, ПК1.1, ПК1.2
ПР 8
Оценка сложности алгоритмов методом Кирхгофа.
У2, З3, ПК1.1, ОК2, ОК3, ОК4
ОТЧЕТ по каждой практической или лабораторной работе составляется на отдельных листах формата А4 по следующему образцу:
5
Отчет по практической работе
ЦЕЛЬ:
ЗАДАНИЯ ( номер, условие каждого задания выполненное в виде постановки задачи, математическая модель задачи, алгоритм решения задачи, данные для тестирования задачи.)
1 – Фамилия разработчика
2 – Фамилия проверяющего
3 – Код-обозначение документа (практической или лабораторной работы)
4 – Тема практической (или лабораторной) работы
5 – Учебное заведение, группа
6 – Литер – у (учебный документ)
7 - № листа данного документа
8 – Количество листов в данном документе
1 2 3 4 5 6 7
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Фамилия
Подпись
Дата
70
Лит.
Лист
Листов
Разработ.
у
Проверил
50
Оформление практической работы
ПР – практическая работа
Код специальности 09.02.03 – Программирование в компьютерных системах
0000-00 – индекс дисциплины по учебному плану:
ОП.08 – Теория алгоритмов
№ группы 14 (для 14пк-1), 15 (для 15пк-1), 16(для 16пк-1) и т.д.
№ варианта – номер студента по списку в журнале
№ практической – порядковый номер практической работы
00 год – 16 (для 2016), 17 (для 2017) и т.д.
ПР. 09.02.03 ОП.08. 00. 00. 00. 00.
код индекс № № № год
специальности дисциплины, группы работы варианта
ПР-09.02.03-ОП.08-14-00-01-16
Фамилия
Подпись
Дата
Название работы
Лит.
Лист
Листов
Разработ.
Студент
у
1
1
Проверил
Преподаватель
УАвиаК
гр. 14пк-1
ПРАКТИЧЕСКАЯ РАБОТА №1
Составление и запись на языке блок-схем линейных алгоритмов
ЦЕЛЬ РАБОТЫ
формирование навыков составления, записи на языке блок-схем и тестирования линейных алгоритмов.
ОБЕСПЕЧЕННОСТЬ ЗАНЯТИЯ
Чертежные принадлежности и ГОСТ 19.701-90. (ИСО 5807-85). ЕСПД. «Схемы алгоритмов, программ, данных и систем»
ЛИТЕРАТУРА
Теория алгоритмов: учеб. пособие для студ. сред. проф. учеб. заведений / В.И. Игошин. - М.: Издательский центр «Академия», 2013. - 320 с.
Алгоритмы. Построение и анализ. / Т.Х. Кормен, Ч.И. Лейзерон, Р.Л. Ривест. – М.: Вильямс, 2013. – 1328 с.
Алгоритмы. Руководство по разработке / Стивен С. Скиена. – СПб.: БХВ – Петербург, 2011. – 720 с.
СОДЕРЖАНИЕ ЗАДАНИЙ
Составление алгоритма определения значения заданной функции при заданном значении аргумента.
Составление алгоритма определения принадлежности точки, заданной ее координатами, фигуре на плоскости, заданной графически.
Составление алгоритма решения математической задачи.
ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫПОЛНЕНИЯ ЗАДАНИЙ
Задания выполняются в любом порядке
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Алгоритм - это определенным образом организованная последовательность действий, за конечное число шагов приводящая к решению задачи.
Линейным называется алгоритм действия в котором выполняются строго одно за другим без повторов или возвратов к ранее выполненному. Основными действиями линейных алгоритмов являются присваивания и ввод-вывод данных.
ЗАДАНИЯ И ИНСТРУКЦИИ ПО ВЫПОЛНЕНИЮ
Задание 1
Выполните постановку задачи. Составьте алгоритм решения задачи. Запишите этот алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
Задача:
Вычислите значение функции y(x), при заданном значении х.
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·ion.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Задание 2
Запишите выражение, зависящее от координат точки, и принимающее значение ИСТИНА, если точка принадлежит заштрихованной области, и ЛОЖЬ, если не принадлежит. Составьте алгоритм, определяющий принадлежность точки заштрихованной области. Запишите составленный алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
Координаты исследуемой точки: (0,5;0,5)
Область задана на рисунке 1.
Рисунок 1 Рисунок 2 Рисунок 3
Координаты исследуемой точки: (1,5;0,5)
Область задана на рисунке 2.
Координаты исследуемой точки: (0,2;0,9)
Область задана на рисунке 3.
Координаты исследуемой точки: (0,75;-0,3)
Область задана на рисунке 4.
Координаты исследуемой точки: (0,2;0,45)
Область задана на рисунке 5.
Рисунок 4 Рисунок 5 Рисунок 6 Рисунок 7
Координаты исследуемой точки: (0,5;-2,5)
Область задана на рисунке 6.
Координаты исследуемой точки: (0,2;0,7)
Область задана на рисунке 7.
Координаты исследуемой точки: (1,0;1,5)
Область задана на рисунке 8.
Рисунок 8 Рисунок 9 Рисунок 10 Рисунок 11
Координаты исследуемой точки: (-0,5;0,9)
Область задана на рисунке 9.
Координаты исследуемой точки: (1,5;0,0)
Область задана на рисунке 10.
Координаты исследуемой точки: (0,5;1,2)
Область задана на рисунке 11.
Координаты исследуемой точки: (-1,5;0,75)
Область задана на рисунке 12.
Рисунок 12 Рисунок 13 Рисунок 14 Рисунок 15
Координаты исследуемой точки: (0,5;1,5)
Область задана на рисунке 13.
Координаты исследуемой точки: (3,5;-0,5)
Область задана на рисунке 14.
Координаты исследуемой точки: (-0,3;1,7)
Область задана на рисунке 15.
Координаты исследуемой точки: (-0,5;1,3)
Область задана на рисунке 16.
Рисунок 16 Рисунок 17 Рисунок 18
Координаты исследуемой точки: (1,3;-1,2)
Область задана на рисунке 17.
Координаты исследуемой точки: (-1,7;1,3)
Область задана на рисунке 18.
Координаты исследуемой точки: (-0,7;0,9)
Область задана на рисунке 19.
Координаты исследуемой точки: (-0,8;0,7)
Область задана на рисунке 20.
Координаты исследуемой точки: (1,3;-1,6)
Область задана на рисунке 21.
13 EMBED PBrush 1415 13 EMBED PBrush 1415 13 EMBED PBrush 1415
Рисунок 19 Рисунок 20 Рисунок 21 Рисунок 22
Координаты исследуемой точки: (-0,3;-0,8)
Область задана на рисунке 22.
Координаты исследуемой точки: (-0,6;-0,2)
Область задана на рисунке 23.
13 EMBED PBrush 1415 13 EMBED PBrush 1415 13 EMBED PBrush 1415 13 EMBED PBrush 1415
Рисунок 23 Рисунок 24 Рисунок 25 Рисунок 26
Координаты исследуемой точки: (-0,6;-0,2)
Область задана на рисунке 24.
Координаты исследуемой точки: (2,3;-3,5)
Область задана на рисунке 25.
Координаты исследуемой точки: (-1,3;-1,5)
Область задана на рисунке 26.
Координаты исследуемой точки: (0,9;-0,4)
Область задана на рисунке 27.
13 EMBED PBrush 1415 13 EMBED PBrush 1415 13 EMBED PBrush 1415 13 EMBED PBrush 1415
Рисунок 27 Рисунок 28 Рисунок 29 Рисунок 30
Координаты исследуемой точки: (2,3;1,5)
Область задана на рисунке 28.
Координаты исследуемой точки: (-0,7;-0,5)
Область задана на рисунке 29.
Координаты исследуемой точки: (2,3;-3,5)
Область задана на рисунке 30.
Задание 3
Составьте алгоритм решения математической задачи. Запишите этот алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
Вычислить периметр и площадь прямоугольного треугольника по заданным длинам двух катетов a и b .
Заданы координаты трех вершин треугольника. Найти его периметр и площадь.
Вычислить длину окружности и площадь круга одного и того же заданного радиуса R .
Вычислить расстояние между двумя точками с данными координатами.
Даны два действительных числа x и y . Вычислить их сумму, разность, произведение и частное.
Дана длина ребра куба. Найти площадь грани, площадь полной поверхности и объем этого куба.
Дана сторона равностороннего треугольника. Найти площадь этого треугольника, его высоты, радиусы вписанной и описанной окружностей.
Известна длина окружности. Найти площадь круга, ограниченного этой окружностью.
Найти площадь кольца, внутренний радиус которого равен r , а внешний – заданному числу R. R >r .
Треугольник задан величинами своих углов и радиусом описанной окружности. Найти стороны треугольника.
Найти площадь равнобедренной трапеции с основаниями a и b и углом
· при большем основании a.
Заданы координаты вектора, вычислить его длину.
Заданы прямая ax+by+c=0 и точка (x1;y1). Вычислить расстояние от точки до прямой.
Найти площадь треугольника, две стороны которого равны a и b , а угол между этими сторонами q.
В прямоугольном треугольнике с катетами a и b вычислить длину высоты проведенной к гипотенузе.
Найти сумму членов арифметической прогрессии, если известны ее первый член, знаменатель и число членов прогрессии.
Найти все углы треугольника со сторонами a, b , c. Предусмотреть в программе перевод радианной меры угла в градусы.
Три сопротивления 1 R , 2 R , 3 R соединены параллельно. Найдите сопротивление соединения.
Текущее показание электронных часов: m часов, n минут, k секунд. Какое время будут показывать часы через p ч q мин r c ?
Составить программу вычисления объема цилиндра и конуса, которые имеют одинаковую высоту H и одинаковый радиус основания R .
Даны длины трех отрезков a, b и с. Может ли существовать треугольник со сторонами равными длинам этих отрезков?
Дана величина A , выражающая объем информации в байтах. Перевести A в более крупные единицы измерения информации.
Составить программу для вычисления пути, пройденного лодкой, если ее скорость в стоячей воде v км/ч, скорость течения реки w км/ч, время движения по озеру 1 t ч, а против течения реки – 2 t ч.
Двоичное число записано 5 знаками. Определите запись этого числа в десятичной системе счисления.
МЕТОДИКА АНАЛИЗА РЕЗУЛЬТАТОВ, ОБРАЗЕЦ ОТЧЕТА
Задание 1
Вариант 0
Составьте алгоритм вычисления значения функции Y(x)=x2-7x+6, при заданном значении х=0,23. Запишите этот алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
Запись алгоритма решения на языке блок-схем
Построение таблицы тестирования
Вводимое значение аргумента х
Ожидаемое значение функции Y(x)
1
0
Задание 2
Запишите выражение, зависящее от координат точки, и принимающее значение ИСТИНА, если точка принадлежит заштрихованной области, и ЛОЖЬ, если не принадлежит. Составьте алгоритм, определяющий принадлежность точки заштрихованной области. Запишите составленный алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
Вариант 0
Задана область:
Определить попадает ли в эту область точка с координатами (1,87; 1,45), а также любая точка с координатами заданными пользователем.
Построение математической модели задачи
Заданная на рисунке область является объединением двух областей: треугольной части и части круга. Составим уравнение каждой части.
треугольная область является пересечением трех полуплоскостей. Первая задается неравенством y>=0, вторая неравенством x<=0. Для составления неравенства определяющего третью полуплоскость составим уравнение прямой проходящей через две точки. Из рисунка видно, что прямая проходит через точки с координатами (-3; 0) и (0; 2). Подставим эти координаты в общее уравнение прямой: 13 QUOTE 1415 получим равенство 13 QUOTE 1415. Преобразовав его получим уравнение прямой в виде 2x-3y+6=0. Определим знак неравенства задающего полуплоскость. Для этого подставим координаты точки, заведомо лежащей в искомой полуплоскости в уравнение прямой, пусть это точка (0; 0). В левой части неравенства получим 2*0-3*0+6, а справа 0, т.е. 6>0. Следовательно третью полуплоскость задает неравенство: 2x-3y+6>=0. Т.к. треугольник образован пересечением трех полуплоскостей, то объединим их неравенства логической операцией «И». Получим запись:
(x<=0) И (y>=0) И (2x-3y+6>=0)
Вторая часть задается пересечением круга и двух полуплоскостей. Полуплоскости заданы неравенствами: x>=0 и y>=0. Для определения неравенства задающего круг воспользуемся уравнением окружности вида: (x-a)2+(y-b)2=r2, где (a; b)- координаты центра окружности, а r-ее радиус. Подставив данные рисунка получим: x2+y2=4. Т.к. нас интересует только внутренняя часть круга, то зададим следующее неравенство: x2+y2<=4. Т.к. вторая часть области являет пересечением полуплоскостей, то запишем их неравенства объединив логической конструкцией «И».
(x>=0) И (y>=0) И (x*x+y*y<=4)
Область заданная рисунком содержит в себе как первую так и вторую части, т.е. является их объединением, поэтому включим определенные нами неравенства в общую запись с помощью конструкции «ИЛИ»:
(x<=0) И (y>=0) И (2x-3y+6>=0) ИЛИ (x>=0) И (y>=0) И (x*x+y*y<=4)
Запись алгоритма решения задачи на языке блок-схем
Построение таблицы тестирования
Как расположена точка
Координата X
Координата Y
Ожидаемый результат
Попала в левую (треугольник) часть области
-1
1
ИСТИНА
Попала в правую (часть круга) часть области
1
1
ИСТИНА
Не попала в область на рисунке
2
2
ЛОЖЬ
Задание 3
Составьте алгоритм решения математической задачи. Запишите этот алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием
Вариант 0
Определите величину третьего угла (с) треугольника, если заданы величины двух его углов а и в.
Построение математической модели задачи
Входными данными являются величины известных углов треугольника – а, в
Значение третьего угла треугольника определяется по формуле с=180-а-в
Результатом решения задачи будет величина угла с.
Запись алгоритма решения задачи на языке блок-схем
Построение таблицы тестирования
Величина угла а
Величина угла в
Ожидаемая величина угла с
30
45
105
КОНТРОЛЬНЫЕ ВОПРОСЫ
Определение алгоритма.
Определение линейного алгоритма
Свойства алгоритма.
Правила исполнения алгоритма.
Алгоритмические языки.
Правила записи линейных алгоритмов на языке блок – схем.
ПРАКТИЧЕСКАЯ РАБОТА №2
Составление и запись на языке блок-схем алгоритмов, содержащих ветвления
ЦЕЛЬ РАБОТЫ
формирование навыков составления, записи на языке блок-схем и тестирования алгоритмов, содержащих ветвления.
ОБЕСПЕЧЕННОСТЬ ЗАНЯТИЯ
Чертежные принадлежности и ГОСТ 19.701-90. (ИСО 5807-85). ЕСПД. «Схемы алгоритмов, программ, данных и систем»
ЛИТЕРАТУРА
Теория алгоритмов: учеб. пособие для студ. сред. проф. учеб. заведений / В.И. Игошин. - М.: Издательский центр «Академия», 2013. - 320 с.
Алгоритмы. Построение и анализ. / Т.Х. Кормен, Ч.И. Лейзерон, Р.Л. Ривест. – М.: Вильямс, 2013. – 1328 с.
Алгоритмы. Руководство по разработке / Стивен С. Скиена. – СПб.: БХВ – Петербург, 2011. – 720 с.
СОДЕРЖАНИЕ ЗАДАНИЙ
Составление алгоритма определения значения заданной функции для произвольных значений аргументов.
Составление алгоритма определяющего ответ на вопрос задачи, для любых входных значений переменных.
ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫПОЛНЕНИЯ ЗАДАНИЙ
Задания выполняются в любом порядке
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Определение 1: Ситуация, в которой в зависимости от истинности условия исполняется та или иная группа действий, называется ветвлением.
Определение 2: Условие - предложение, истинность которого можно установить, т.е. сказать истинно оно или ложно.
Ситуация ветвление реализована в алгоритмических языках в виде управляющей конструкции ветвление.
Договоримся условно обозначить условие буквой Q, действия, исполняемые в случае когда условие истинно буквой P, а действия, исполняемые в случае когда условие ложно буквой T.
Тогда на естественном алгоритмическом языке ветвление будет иметь запись:
Если Q то P иначе T
К.В.
Условное обозначение К.В. (Конец ветвления) является обязательным в записи, т.к. действия этой конструкции необходимо выделить в общем алгоритме решения задачи.
Выполненная запись называется полной формой ветвления. Конструкция ветвления может быть так же записана в неполной форме:
Если Q то P
К.В.
В записи ветвления в неполной форме может отсутствовать только группа действий T (исполняемая в том случае, когда условие ложно).
Форма ветвления полная или неполная не зависит от выбора способа записи конструкции ветвление. Так при записи этой конструкции на языке блок – схем полная форма будет иметь вид, показанный на рисунке 1, а неполная форма вид, показанный на рисунке 2.
13 SHAPE \* MERGEFORMAT 1415
Рис. 13 SEQ Рис. \* ARABIC 14115 Блок – схема ветвления в полной форме. Рис. 13 SEQ Рис. \* ARABIC 14215 Блок – схема ветвления в неполной форме.
В рассмотренных выше ситуациях ветвления были таковы, что содержали в группах P и T лишь по одному действию. При увеличении количества действий форма записи конструкций ветвления не изменяется, а лишь увеличивается количество блоков.
Выше было указано, на тот факт, что ситуация ветвления невозможна при отсутствии условия. Причем все рассматриваемые нами примеры содержали простые условия, т.е. состоящие из одного предложения. В некоторых задачах условия могут быть составными.
Определение 3: Составным условием называется выражение, содержащее простые условия, объединенные логическими конструкциями. В языках программирования для создания составных условий используются логические конструкции И, ИЛИ, НЕ.
Для определения истинности составного условия используются специальные таблицы – таблицы истинности.
А
НЕ (А)
И
Л
Л
И
Договоримся условно обозначить простые условия буквами А и В. Каждое из них может принять значение «истина» – обозначим его И, или «ложь» – обозначим его Л. Тогда таблицы истинности будут иметь вид
А
В
(А) И (В)
И
И
И
Л
И
Л
И
Л
Л
Л
Л
Л
А
В
(А) ИЛИ (В)
И
И
И
Л
И
И
И
Л
И
Л
Л
Л
ЗАДАНИЯ И ИНСТРУКЦИИ ПО ВЫПОЛНЕНИЮ.
Задание 1
Составьте алгоритм вычисления значения функции при любых значениях аргументов. Запишите этот алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equa
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Задание 2
Составьте алгоритм, определяющий ответ на вопрос задачи, для любых входных значений переменных. Запишите составленный алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
Можно ли квадрат со стороной А описать окружностью радиусом R.
Дан треугольник с углами А, В, С. Может ли данный треугольник быть равносторонним.
Может ли тело, массой М, иметь ускорение А, если на него действует сила F.
Можно ли окружность радиусом R вписать в квадрат со стороной А.
Даны углы А, В, С. Может ли существовать треугольник с данными углами.
Является ли многоугольник со сторонами A, B, C, D квадратом.
Дан треугольник с сторонами X, Y, Z. Является ли он равнобедренным.
Дан треугольник с углами А, В, С. Может ли он быть прямоугольным.
Дан треугольник с сторонами А, В, С. Является ли он равносторонним.
Дан треугольник с сторонами А, В, С. Может ли он быть прямоугольным.
Сколько решений имеет квадратное уравнение ах2+вх+с=0.
Дан многоугольник со сторонами А, В, С, D. Может ли он быть ромбом.
Дан треугольник с углами А, В, С. Может ли он быть равнобедренным.
Определить, находиться ли точка М(а, в) внутри верхней части единичного круга с центром в начале координат.
Определить, имеется ли среди трех чисел а, в и с хотя бы одна пара равных между собой чисел.
Определить, имеется ли среди трех чисел а, в и с хотя бы одна пара взаимно противоположных чисел.
Числа а и в выражают длины катетов одного прямоугольного треугольника, а с и d – другого. Определить, являются ли эти треугольники подобными.
Даны два числа а и в. Определить, является ли одно из них квадратом другого.
Можно ли квадрат со стороной А описать окружностью радиусом R.
Дан треугольник с углами А, В, С. Может ли данный треугольник быть равносторонним.
Может ли тело, массой М, иметь ускорение А, если на него действует сила F.
Можно ли окружность радиусом R вписать в квадрат со стороной А.
Даны углы А, В, С. Может ли существовать треугольник с данными углами.
Является ли многоугольник со сторонами A, B, C, D квадратом.
Дан треугольник с сторонами X, Y, Z. Является ли он равнобедренным.
Дан треугольник с углами А, В, С. Может ли он быть прямоугольным.
Дан треугольник с сторонами А, В, С. Является ли он равносторонним.
Дан треугольник с сторонами А, В, С. Может ли он быть прямоугольным.
Сколько решений имеет линейное уравнение ах = в.
Определить, находиться ли точка М(а, в) внутри нижней части единичного круга с центром в начале координат.
МЕТОДИКА АНАЛИЗА РЕЗУЛЬТАТОВ, ОБРАЗЕЦ ОТЧЕТА
Задание 1
Составьте алгоритм вычисления значения функции при любых значениях аргументов. Запишите этот алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
13 EMBED Equation.3 1415
Вариант 0
Построение математической модели задачи
При x>5 значение функции y определяется по формуле 13 EMBED Equation.3 1415. Вычисление арифметического квадратного корня возможно только в том случае, когда подкоренное значение не отрицательно. Найдем математическое решение неравенства x-813 EMBED Equation.3 14150;13 EMBED Equation.3 1415x13 EMBED Equation.3 14158.
Решая два неравенства в системе, определяем, что в случае, когда x>5 решение возможно только при x13 EMBED Equation.3 14158.
При x<-5 значение функции y определяется по формуле 13 EMBED Equation.3 1415. Приведенная формула содержит дробь, в знаменателе которой содержится переменная, следовательно, вычисления возможны только в том случае, когда знаменатель дроби отличен от 0. Найдем математическое решение уравнения 7+x=0;13 EMBED Equation.3 1415x=-7.
Следовательно, получая значение x меньшее -5 необходимо проверить, не равно ли оно -7, т.к. в этом случае решения у задачи нет.
При -513 EMBED Equation.3 14155 функция y вычисляется по формуле 13 EMBED Equation.3 1415. Так же как и в предыдущем случае в вычислениях используется дробь, следовательно, ее знаменатель не должен быть равным нулю. Найдем математическое решение уравнения x-3=0;13 EMBED Equation.3 1415x=3.
Следовательно, получая значение x на отрезке [-5;5] необходимо проверить, не равно ли оно 3, т.к. в этом случае решения у задачи нет.
Запись алгоритма решения на языке блок-схем
13 SHAPE \* MERGEFORMAT 1415
Построение таблицы тестирования
1 способ.
x
x>5
y
Да
Нет
x13 EMBED Equation.3 14158
x<-5
Да
Нет
Да
Нет
x13 EMBED Equation.3 14157
x13 EMBED Equation.3 14153
Да
Нет
Да
Нет
2 способ.
x
x>5
x13 EMBED Equation.3 14158
x<-5
x13 EMBED Equation.3 1415-7
x13 EMBED Equation.3 14153
y
Д
Н
Д
Н
Д
Н
Д
Н
Д
Н
Проведите тестирование, последовательно заполняя таблицу. На каждый маршрут достаточно привести один тестовый пример.
x
x>5
x13 EMBED Equation.3 14158
x<-5
x13 EMBED Equation.3 1415-7
x13 EMBED Equation.3 14153
y
Д
Н
Д
Н
Д
Н
Д
Н
Д
Н
9
+
+
1
7
+
+
Нет реш
-6
+
+
+
6
-7
+
+
+
Нет реш
4
+
+
+
1
3
+
+
+
Нет реш
Задание 2
Особенность второго задания в необходимости создать сложное условие. В случае правильного построения условия, в решении задачи используются ветвления в полной форме с одним действием.
КОНТРОЛЬНЫЕ ВОПРОСЫ
Определение алгоритма.
Свойства алгоритма.
Правила исполнения алгоритма.
Алгоритмические языки.
Правила записи алгоритмов на языке блок – схем.
Алгоритмическая конструкция ветвление – определение.
Алгоритмическая конструкция ветвление – виды.
Запись ветвлений разных видов на языке блок – схем.
ПРАКТИЧЕСКАЯ РАБОТА №3
Составление и запись на языке блок-схем алгоритмов содержащих циклы с предусловием
ЦЕЛЬ РАБОТЫ
формирование навыков составления, записи на языке блок-схем и тестирования алгоритмов, содержащих циклы с предусловием.
ОБЕСПЕЧЕННОСТЬ ЗАНЯТИЯ
Чертежные принадлежности и ГОСТ 19.701-90. (ИСО 5807-85). ЕСПД. «Схемы алгоритмов, программ, данных и систем»
ЛИТЕРАТУРА
Теория алгоритмов: учеб. пособие для студ. сред. проф. учеб. заведений / В.И. Игошин. - М.: Издательский центр «Академия», 2013. - 320 с.
Алгоритмы. Построение и анализ. / Т.Х. Кормен, Ч.И. Лейзерон, Р.Л. Ривест. – М.: Вильямс, 2013. – 1328 с.
Алгоритмы. Руководство по разработке / Стивен С. Скиена. – СПб.: БХВ – Петербург, 2011. – 720 с.
СОДЕРЖАНИЕ ЗАДАНИЙ
Составление алгоритма нахождения суммы ряда с заданной точностью и определения количества элементов ряда вошедших в найденную сумму.
Составление алгоритма нахождения суммы десяти первых элементов ряда.
ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫПОЛНЕНИЯ ЗАДАНИЙ
Задания выполняются в любом порядке
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Определение 1: Ситуация, в которой в зависимости от истинности условия организуется многократное исполнение группы действий, называется циклом.
Определение 2: Условие - предложение, истинность которого можно установить, т.е. сказать истинно оно или ложно.
Ситуация цикл реализована в алгоритмических языках в виде управляющей конструкции цикл.
Конструкция цикл может быть отнесена к одной из следующих групп:
цикл
с известным числом повторов с неизвестным числом повторов
цикл N раз для каждого N с предусловием с постусловием
Договоримся условно обозначить условие буквой Q, действия, исполняемые в теле цикла буквой P.
Тогда на естественном алгоритмическом языке цикл с предусловием будет иметь запись:
Если Q то P
К.Ц.
Условное обозначение К.Ц. (Конец цикла) является обязательным в записи, т.к. действия этой конструкции необходимо выделить в общем алгоритме решения задачи.
Запись цикла с предусловием на языке блок – схем будет иметь вид, показанный на рисунке 1.
Рис. 13 SEQ Рис. \* ARABIC 14115 Блок – схема цикла с предусловием.
При увеличении количества действий форма цикла не изменяется, а лишь увеличивается количество блоков.
Определение 3: Зацикливание - ситуация бесконечного исполнения действий в цикле.
ЗАДАНИЯ И ИНСТРУКЦИИ ПО ВЫПОЛНЕНИЮ
Задание 1
Составьте алгоритм для нахождения суммы ряда с точностью 10-3 и определения количества элементов ряда вошедших в найденную сумму. Запишите этот алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
1 13 EMBED Equation.3 1415 2 13 EMBED Equation.3 1415 3 13 EMBED Equation.3 1415
4 13 EMBED Equation.3 1415 5 13 EMBED Equation.3 1415 6 13 EMBED Equation.3 1415
7 13 EMBED Equation.3 1415 8 13 EMBED Equation.3 1415 9 13 EMBED Equation.3 1415
10 13 EMBED Equation.3 1415 1113 EMBED Equation.3 1415 12 13 EMBED Equation.3 1415
13 13 EMBED Equation.3 1415 14 13 EMBED Equation.3 1415 15 13 EMBED Equation.3 1415
16 13 EMBED Equation.3 1415 17 13 EMBED Equation.3 1415 18 13 EMBED Equation.3 1415
19 13 EMBED Equation.3 1415 20 13 EMBED Equation.3 1415 21 13 EMBED Equation.3 1415
22 13 EMBED Equation.3 1415 23 13 EMBED Equation.3 1415 24 13 EMBED Equation.3 1415
25 13 EMBED Equation.3 1415 26 13 EMBED Equation.3 1415 27 13 EMBED Equation.3 1415
28 13 EMBED Equation.3 1415 29 13 EMBED Equation.3 1415 30 13 EMBED Equation.3 1415
Задание 2
Составьте алгоритм для нахождения суммы десяти первых элементов ряда. Запишите составленный алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
1 13 EMBED Equation.3 1415 2 13 EMBED Equation.3 1415 3 13 EMBED Equation.3 1415
4 13 EMBED Equation.3 1415 5 13 EMBED Equation.3 1415 6 13 EMBED Equation.3 1415
7 13 EMBED Equation.3 1415 8 13 EMBED Equation.3 1415 9 13 EMBED Equation.3 1415
10 13 EMBED Equation.3 1415 11 13 EMBED Equation.3 1415 12. 13 EMBED Equation.3 1415
13 13 EMBED Equation.3 1415 14 13 EMBED Equation.3 1415 15 13 EMBED Equation.3 1415
16 13 EMBED Equation.3 1415 17 13 EMBED Equation.3 1415 18 13 EMBED Equation.3 1415
19 13 EMBED Equation.3 1415 20 13 EMBED Equation.3 1415 21 13 EMBED Equation.3 1415
22 13 EMBED Equation.3 1415 23 13 EMBED Equation.3 1415 24 13 EMBED Equation.3 1415
25 13 EMBED Equation.3 1415 26 13 EMBED Equation.3 1415 27 13 EMBED Equation.3 1415
28 13 EMBED Equation.3 1415 29 13 EMBED Equation.3 1415 30 13 EMBED Equation.3 1415
МЕТОДИКА АНАЛИЗА РЕЗУЛЬТАТОВ, ОБРАЗЕЦ ОТЧЕТА
Задание 1
Составьте алгоритм для нахождения суммы ряда с точностью 10-3 и определения количества элементов ряда вошедших в найденную сумму. Запишите этот алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
Вариант 0
an=13 QUOTE 1415
Построение математической модели задачи
n-номер элемента ряда, первое значение n=1
ап – элемент ряда, каждый элемент, зная его номер можно определить по формуле, задающей ряд, например: а1=13 QUOTE 1415=1, а2=13 QUOTE 1415=0,5 и т.д.
s – сумма элементов ряда, т.е. s=a1+a2+a3+
s1, s2 – две «соседние суммы» элементов ряда, т.е. если s1= a1+a2+a3, то s2= a1+a2+a3+а4
|s1-s2| - точность вычислений, по условию задачи она должна стать меньше 10-3.
Запись алгоритма решения на языке блок-схем
Построение таблицы тестирования
n
a
S1
S2
|s1-s2|>=10-3
f
1
1
1
2
0.5
1
1.5
+
3
1/6=
1.5
1.5+1/6=
+
6
Задание 2
Решается аналогично заданию 1
КОНТРОЛЬНЫЕ ВОПРОСЫ
Определение алгоритма.
Свойства алгоритма.
Правила исполнения алгоритма.
Алгоритмические языки.
Правила записи алгоритмов на языке блок – схем.
Алгоритмическая конструкция цикл с предусловием.
Запись циклов с предусловием на языке блок – схем.
Зацикливание.
ПРАКТИЧЕСКАЯ РАБОТА №4
Составление и запись на языке блок-схем алгоритмов содержащих циклы с постусловием
ЦЕЛЬ РАБОТЫ
формирование навыков составления, записи на языке блок-схем и тестирования алгоритмов, содержащих циклы с постусловием.
ОБЕСПЕЧЕННОСТЬ ЗАНЯТИЯ
Чертежные принадлежности и ГОСТ 19.701-90. (ИСО 5807-85). ЕСПД. «Схемы алгоритмов, программ, данных и систем»
ЛИТЕРАТУРА
Теория алгоритмов: учеб. пособие для студ. сред. проф. учеб. заведений / В.И. Игошин. - М.: Издательский центр «Академия», 2013. - 320 с.
Алгоритмы. Построение и анализ. / Т.Х. Кормен, Ч.И. Лейзерон, Р.Л. Ривест. – М.: Вильямс, 2013. – 1328 с.
Алгоритмы. Руководство по разработке / Стивен С. Скиена. – СПб.: БХВ – Петербург, 2011. – 720 с.
СОДЕРЖАНИЕ ЗАДАНИЙ
Составление алгоритма нахождения суммы ряда с заданной точностью и определения количества элементов ряда вошедших в найденную сумму.
Составление алгоритма определяющего ответ на вопрос задачи, для любых входных значений переменных.
ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫПОЛНЕНИЯ ЗАДАНИЙ
Задания выполняются в любом порядке
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Определение 1: Ситуация, в которой в зависимости от истинности условия организуется многократное исполнение группы действий, называется циклом.
Определение 2: Условие - предложение, истинность которого можно установить, т.е. сказать истинно оно или ложно.
Ситуация цикл реализована в алгоритмических языках в виде управляющей конструкции цикл.
Конструкция цикл может быть отнесена к одной из следующих групп:
цикл
с известным числом повторов с неизвестным числом повторов
цикл N раз для каждого N с предусловием с постусловием
Договоримся условно обозначить условие буквой Q, действия, исполняемые в теле цикла буквой P.
Тогда на естественном алгоритмическом языке цикл с постусловием будет иметь запись:
Н.Ц.
P
Если Q, то К.Ц. , иначе вернуться к Р
Запись цикла с постусловием на языке блок – схем будет иметь вид, показанный на рисунке 1.
Рис. 13 SEQ Рис. \* ARABIC 14115 Блок – схема цикла с постусловием.
При увеличении количества действий форма цикла не изменяется, а лишь увеличивается количество блоков.
Определение 3: Зацикливание - ситуация бесконечного исполнения действий в цикле.
ЗАДАНИЯ И ИНСТРУКЦИИ ПО ВЫПОЛНЕНИЮ
Задание 1
Составьте алгоритм для решения задачи «Введена последовательность целых чисел. Признаком конца ввода является введение числа 0. Вычислите сумму элементов этой последовательности, найдите минимальный элемент в этой последовательности и количество элементов последовательности, удовлетворяющих правилу вашего варианта».
Запишите этот алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
Варианты:
Число начинается с цифры 2.
В числе чередуются четные и нечетные цифры.
Количество цифр 2 в числе равно 1.
Число состоит из нечетного числа цифр.
Сумма цифр числа делиться на пять.
Количество цифр 3 в числе не менее 2.
Суммы четных и нечетных цифр числа равны.
В числе имеется хотя бы одна цифра шесть.
Произведение первой и последней цифр числа меньше 10.
Первая и последняя цифры числа четные.
Число состоит из четного количества цифр.
В числе более двух нулей.
Первая и последняя цифры в числе равны.
Четных цифр в числе большее, чем нечетных.
Число состоит только из нечетных цифр.
Количество цифр 1 в числе равно 2.
Сумма четных цифр числа меньше суммы нечетных цифр числа.
В числе нет ни одной цифры 4.
Число симметрично.
Первая цифра числа делиться на последнюю без остатка.
Число состоит только из цифр 3 и 4.
Число не содержит цифр 5 и 8.
Последняя цифра делиться на первую без остатка.
Первая и последняя цифры четные.
Хотя бы две цифры в числе нечетные.
Количество нечетных цифр числа больше количества четных.
Число заканчивается на 3.
Число начинается с цифры 9.
Все цифры числа упорядочены по возрастанию.
Число простое.
Задание 2
Составьте алгоритм для нахождения суммы десяти первых элементов ряда. Запишите составленный алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
1 13 EMBED Equation.3 1415 2 13 EMBED Equation.3 1415 3 13 EMBED Equation.3 1415
4 13 EMBED Equation.3 1415 5 13 EMBED Equation.3 1415 6 13 EMBED Equation.3 1415
7 13 EMBED Equation.3 1415 8 13 EMBED Equation.3 1415 9 13 EMBED Equation.3 1415
10 13 EMBED Equation.3 1415 11 13 EMBED Equation.3 1415 12. 13 EMBED Equation.3 1415
13 13 EMBED Equation.3 1415 14 13 EMBED Equation.3 1415 15 13 EMBED Equation.3 1415
16 13 EMBED Equation.3 1415 17 13 EMBED Equation.3 1415 18 13 EMBED Equation.3 1415
19 13 EMBED Equation.3 1415 20 13 EMBED Equation.3 1415 21 13 EMBED Equation.3 1415
22 13 EMBED Equation.3 1415 23 13 EMBED Equation.3 1415 24 13 EMBED Equation.3 1415
25 13 EMBED Equation.3 1415 26 13 EMBED Equation.3 1415 27 13 EMBED Equation.3 1415
28 13 EMBED Equation.3 1415 29 13 EMBED Equation.3 1415 30 13 EMBED Equation.3 1415
МЕТОДИКА АНАЛИЗА РЕЗУЛЬТАТОВ, ОБРАЗЕЦ ОТЧЕТА
Задание 1
Составьте алгоритм для решения задачи «Из каких цифр состоит введенное число?». Запишите этот алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
Вариант 0
Из каких цифр состоит введенное число?
Построение математической модели задачи
а – введенное целое число, очередной элемент последовательности.
В математике для натурального числа возможно использовать запись а=13 QUOTE 1415 , в которой an, an-1, , a1, a0 – цифры числа.
Эту запись продолжают равенством а= a0*100+а1*101++ап-1*10п-1+ап*10п.
Следовательно, каждую цифру числа возможно определить как остаток от деления на 10.
Запись алгоритма решения на языке блок-схем
Построение таблицы тестирования
Введено
Ожидается
236
6 3 2
Задание 2
КОНТРОЛЬНЫЕ ВОПРОСЫ
Определение алгоритма.
Свойства алгоритма.
Правила исполнения алгоритма.
Алгоритмические языки.
Правила записи алгоритмов на языке блок – схем.
Алгоритмическая конструкция цикл с постусловием.
Запись циклов с постусловием на языке блок – схем.
Зацикливание.
ПРАКТИЧЕСКАЯ РАБОТА №5
Составление и запись на языке блок-схем алгоритмов содержащих циклы с параметром
ЦЕЛЬ РАБОТЫ
формирование навыков составления, записи на языке блок-схем и тестирования алгоритмов, содержащих циклы с параметром.
ОБЕСПЕЧЕННОСТЬ ЗАНЯТИЯ
Чертежные принадлежности и ГОСТ 19.701-90. (ИСО 5807-85). ЕСПД. «Схемы алгоритмов, программ, данных и систем»
ЛИТЕРАТУРА
Теория алгоритмов: учеб. пособие для студ. сред. проф. учеб. заведений / В.И. Игошин. - М.: Издательский центр «Академия», 2013. - 320 с.
Алгоритмы. Построение и анализ. / Т.Х. Кормен, Ч.И. Лейзерон, Р.Л. Ривест. – М.: Вильямс, 2013. – 1328 с.
Алгоритмы. Руководство по разработке / Стивен С. Скиена. – СПб.: БХВ – Петербург, 2011. – 720 с.
СОДЕРЖАНИЕ ЗАДАНИЙ
Составление алгоритма работы с элементами матрицы.
Составление алгоритма определяющего ответ на вопрос задачи, для любых входных значений переменных.
ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫПОЛНЕНИЯ ЗАДАНИЙ
Задания выполняются в любом порядке
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Определение 1: Ситуация, в которой в зависимости от истинности условия организуется многократное исполнение группы действий, называется циклом.
Определение 2: Условие - предложение, истинность которого можно установить, т.е. сказать истинно оно или ложно.
Ситуация цикл реализована в алгоритмических языках в виде управляющей конструкции цикл.
Конструкция цикл может быть отнесена к одной из следующих групп:
цикл
с известным числом повторов с неизвестным числом повторов
цикл N раз для каждого N с предусловием с постусловием
Договоримся действия, исполняемые в теле цикла буквой P.
Тогда на естественном алгоритмическом языке цикл с параметром будет иметь запись:
Для i=i0 до i=in с шагом h
P
К.Ц.
Запись цикла с параметром на языке блок – схем будет иметь вид, показанный на рисунке 1.
Рис. 13 SEQ Рис. \* ARABIC 14115 Блок – схема цикла с параметром.
При увеличении количества действий форма цикла не изменяется, а лишь увеличивается количество блоков.
Определение 3: Зацикливание - ситуация бесконечного исполнения действий в цикле.
ЗАДАНИЯ И ИНСТРУКЦИИ ПО ВЫПОЛНЕНИЮ
Задание 1
Составьте алгоритм для решения задачи. Запишите этот алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
Дано число k (0 < k < 11) и матрица размера 4 x 10. Найти сумму и произведение элементов k - го столбца данной матрицы.
Дана матрица размера 5 x 9. Найти суммы элементов всех ее четных строк и столбцов.
Дана матрица размера 5 x 10. Найти минимальное и максимальное значение в каждой строке.
Дана матрица размера 5 x 10. В каждой строке найти количество элементов, больших среднего арифметического всех элементов этой строки.
Дана матрица размера 5 x 10. Преобразовать матрицу, поменяв местами минимальный и максимальный элемент в каждой строке.
Дана матрица размера 5 x 10. Найти минимальное значение среди сумм элементов всех ее строк и столбцов и номер строки столбца с этим минимальным значением.
Дана матрица размера 5 x 10. Найти минимальный и максимальный среди максимальных и минимальных элементов каждой строки и столбца.
Дана целочисленная матрица размера 5 x 10. Вывести номер ее первой и последней строки, содержащей равное количество положительных и отрицательных элементов (нулевые элементы не учитываются). Если таких строк нет, то вывести 0.
Дана матрица размера 5 x 10. Вывести номер ее первой и последней строки, содержащего только положительные элементы. Если таких строк нет, то вывести 0.
Дана целочисленная матрица размера M x N. Различные строки (столбцы) матрицы назовем похожими, если совпадают множества чисел, встречающихся в этих строках (столбцах). Найти количество строк, похожих на первую строку.
Дана целочисленная матрица размера M x N. Найти количество ее строк и столбцов, все элементы которых различны.
Дана целочисленная матрица размера M x N. Вывести номер ее первой строки, содержащей максимальное количество одинаковых элементов.
Дана квадратная матрица порядка M. Найти сумму элементов ее главной и побочной диагонали.
Дана квадратная матрица порядка M. Найти суммы элементов ее диагоналей, параллельных главной и побочной (начиная с одноэлементной диагонали A [1, M] и A [1, 1] ).
Дана квадратная матрица порядка M. Вывести минимальные из элементов каждой ее диагонали, параллельной главной (начиная с одноэлементной диагонали A [1, M]).
Дана квадратная матрица порядка M. Заменить нулями элементы матрицы, лежащие ниже главной и выше побочной диагонали.
Дана квадратная матрица порядка M. Заменить нулями элементы, лежащие одновременно выше главной диагонали (включая эту диагональ) и выше побочной диагонали (также включая эту диагональ).
Дана квадратная матрица порядка M. Зеркально отразить ее элементы относительно [горизонтальной оси симметрии] матрицы.
Дана квадратная матрица порядка M. Повернуть ее на 90 градусов в положительном направлении.
Дана матрица размера 5 x 10. Вывести количество строк, элементы которых монотонно возрастают.
Дана матрица размера 5 x 10. Найти минимальный среди элементов тех строк , которые упорядочены либо по возрастанию, либо по убыванию. Если такие строки отсутствуют, то вывести 0.
Даны два числа k1 и k2 и матрица размера 4 x 10. Поменять местами строки матрицы с номерами k1 и k2.
Дана матрица размера 5 x 10. Поменять местами строки, содержащие минимальный и максимальный элементы матрицы.
Дана матрица размера 5 x 10. Поменять местами столбец с номером 1 и первый из столбцов, содержащих только положительные элементы.
Дано число k и матрица размера 4 x 10. Удалить строку матрицы с номером k.
Дана матрица размера 5 x 10. Удалить столбец, содержащий минимальный элемент матрицы.
Дана матрица размера 5 x 10. Удалить первый столбец, содержащие только положительные элементы.
Дано число k и матрица размера 4 x 9. Перед строкой матрицы с номером k вставить строку из нулей.
Дана матрица размера 4 x 9. Продублировать строку матрицы, содержащий ее минимальный элемент.
Дана матрица размера 5 x 9. Перед последним столбцом, содержащим только положительные элементы, добавить столбец, состоящий из единиц.
Задание 2
Составьте алгоритм для нахождения суммы десяти первых элементов ряда. Запишите составленный алгоритм на языке блок-схем. Подтвердите правильность составленного алгоритма тестированием.
1 13 EMBED Equation.3 1415 2 13 EMBED Equation.3 1415 3 13 EMBED Equation.3 1415
4 13 EMBED Equation.3 1415 5 13 EMBED Equation.3 1415 6 13 EMBED Equation.3 1415
7 13 EMBED Equation.3 1415 8 13 EMBED Equation.3 1415 9 13 EMBED Equation.3 1415
10 13 EMBED Equation.3 1415 11 13 EMBED Equation.3 1415 12. 13 EMBED Equation.3 1415
13 13 EMBED Equation.3 1415 14 13 EMBED Equation.3 1415 15 13 EMBED Equation.3 1415
16 13 EMBED Equation.3 1415 17 13 EMBED Equation.3 1415 18 13 EMBED Equation.3 1415
19 13 EMBED Equation.3 1415 20 13 EMBED Equation.3 1415 21 13 EMBED Equation.3 1415
22 13 EMBED Equation.3 1415 23 13 EMBED Equation.3 1415 24 13 EMBED Equation.3 1415
25 13 EMBED Equation.3 1415 26 13 EMBED Equation.3 1415 27 13 EMBED Equation.3 1415
28 13 EMBED Equation.3 1415 29 13 EMBED Equation.3 1415 30 13 EMBED Equation.3 1415
МЕТОДИКА АНАЛИЗА РЕЗУЛЬТАТОВ, ОБРАЗЕЦ ОТЧЕТА
Задание 1
Задача ввода элементов матрицы размера M*N с клавиатуры
КОНТРОЛЬНЫЕ ВОПРОСЫ
Определение алгоритма.
Свойства алгоритма.
Правила исполнения алгоритма.
Алгоритмические языки.
Правила записи алгоритмов на языке блок – схем.
Алгоритмическая конструкция цикл с параметром.
Запись циклов с параметром на языке блок – схем.
Зацикливание.
ПРАКТИЧЕСКАЯ РАБОТА №6
Составление алгоритмов декомпозиционным методом
ЦЕЛЬ РАБОТЫ
формирование навыков разработки алгоритмов декомпозиционным методом.
ОБЕСПЕЧЕННОСТЬ ЗАНЯТИЯ
Чертежные принадлежности и ГОСТ 19.701-90. (ИСО 5807-85). ЕСПД. «Схемы алгоритмов, программ, данных и систем»
ЛИТЕРАТУРА
Теория алгоритмов: учеб. пособие для студ. сред. проф. учеб. заведений / В.И. Игошин. - М.: Издательский центр «Академия», 2013. - 320 с.
Алгоритмы. Построение и анализ. / Т.Х. Кормен, Ч.И. Лейзерон, Р.Л. Ривест. – М.: Вильямс, 2013. – 1328 с.
Алгоритмы. Руководство по разработке / Стивен С. Скиена. – СПб.: БХВ – Петербург, 2011. – 720 с.
СОДЕРЖАНИЕ ЗАДАНИЙ
Составление алгоритма декомпозиционным методом.
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Описание метода прямоугольников.
Пусть требуется вычислить значение определенного интеграла f(x)dx с заданной точностью. Найти значение определенного интеграла, т.е. найти площадь криволинейной трапеции.
Для вычисления первого приближения интеграла разделим отрезок [а, Ь] на n равных частей (n=4),определим значения f(Xi), где Xi=a+h*i-h/2; h=(b-a)/n Вычислим площадь Si каждого из полученных прямоугольников:
Si=h*f(xi)
Сумма S1 площадей этих прямоугольников является приближенным значением интеграла:
S1=13 EMBED Equation.3 1415=h*13 EMBED Equation.3 1415
Однако одно приближение не позволяет оценить точность, с которой вычислено значение интеграла, необходимо найти второе приближение. Для этого увеличим количество разбиений n в два раза, т.е. n:=2n. Аналогично S1 найдем S2=h13 EMBED Equation.3 1415
Требуется вычислить значение интеграла с точностью е, поэтому проверим условие |sl-s2|< e , Если условие выполняется, то s2 принимается за искомое значение интеграла; если не выполняется, то последнее поученное значение s2 считается предыдущим, т.е. sl:=s2
После этого удвоим число точек деления отрезка и вычислим новое значение s2. Процесс удвоения n и вычисления s2 будем продолжать до тех пор, пока модуль разности sl и s2 не станет меньше е.
ЗАДАНИЯ И ИНСТРУКЦИИ ПО ВЫПОЛНЕНИЮ
Задание 1
Составьте алгоритм решения задачи используя декомпозиционный метод. «Задана функция F(x). Требуется найти определенный интеграл от функции с точностью 10-4 в заданных пределах. Для решения задачи использовать численный метод вычисления определенного интеграла – «метод прямоугольников». Запишите составленный алгоритм на языке блок-схем.
Варианты:
13 EMBED Equation.3 1415 11 13 EMBED Equation.3 1415 21 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 12 13 EMBED Equation.3 1415 22 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 13 13 EMBED Equation.3 1415 23 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 14 13 EMBED Equation.3 1415 24 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415dx 1513 EMBED Equation.3 1415 25 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 16 13 EMBED Equation.3 1415 26 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 1713 EMBED Equation.3 1415 27 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 1813 EMBED Equation.3 1415 28 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 1913 EMBED Equation.3 1415 29 13 EMBED Equation.3 1415
10 13 EMBED Equation.3 1415 2013 EMBED Equation.3 1415 30 13 EMBED Equation.3 1415
КОНТРОЛЬНЫЕ ВОПРОСЫ
Перечислите основные конструкции структурного программирования
Перечислите принципы Бома – Джакопини
Перечислите возможные расширения конструкций структурного программирования
Правила записи алгоритмов в соответствии с методом Дамке
Правила записи алгоритмов на языке структурограмм
Назовите основные положения модульного принципа программирования
ПРАКТИЧЕСКАЯ РАБОТА №7
Составление алгоритмов сборочным методом
ЦЕЛЬ РАБОТЫ
формирование навыков разработки алгоритмов сборочным методом.
ОБЕСПЕЧЕННОСТЬ ЗАНЯТИЯ
Чертежные принадлежности и ГОСТ 19.701-90. (ИСО 5807-85). ЕСПД. «Схемы алгоритмов, программ, данных и систем»
ЛИТЕРАТУРА
Теория алгоритмов: учеб. пособие для студ. сред. проф. учеб. заведений / В.И. Игошин. - М.: Издательский центр «Академия», 2013. - 320 с.
Алгоритмы. Построение и анализ. / Т.Х. Кормен, Ч.И. Лейзерон, Р.Л. Ривест. – М.: Вильямс, 2013. – 1328 с.
Алгоритмы. Руководство по разработке / Стивен С. Скиена. – СПб.: БХВ – Петербург, 2011. – 720 с.
СОДЕРЖАНИЕ ЗАДАНИЙ
Составление алгоритма сборочным методом.
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
ЗАДАНИЯ И ИНСТРУКЦИИ ПО ВЫПОЛНЕНИЮ
Задание 1
Составьте алгоритм решения задачи используя сборочный метод. «В задании приведены функции и их разложение в ряд Тейлора. Необходимо вычислить как саму функцию, так и сумму членов соответствующего ряда. В нечетных вариантах число слагаемых следует ограничить некоторым заранее заданным числом М (простой цикл). В четных вариантах очередной элемент включается в суму, если его значение по модулю превышает некоторое заранее заданное число Р, определяемое с требуемой точностью вычислений (итерационный цикл).
Например М=50, Р=0,001.
Вывести на экран таблицу, состоящую из 10 строк и включающую следующие графы:
Значение Значение Значение Разность
х z(x) y(x) 13 EMBED Equation.3 1415
где х меняется пределах отрезка, заданного в варианте, с шагом h; z(x) – значение функции; y(x) – значение ее разложения в функциональный ряд». Запишите составленный алгоритм на языке блок-схем.
Варианты:
z = 3x; y = 1+13 EMBED Equation.3 1415; диапазон [0.1;1]
z = cos x; y = 13 EMBED Equation.3 1415; диапазон [0.1;1]
z = -ln(2sin13 EMBED Equation.3 1415); y = cos x+13 EMBED Equation.3 1415; диапазон [13 EMBED Equation.3 1415]
z = 13 EMBED Equation.3 1415; y = sin x-13 EMBED Equation.3 1415; диапазон [13 EMBED Equation.3 1415]
z = ex; y = 1+13 EMBED Equation.3 1415; диапазон [1;2]
z = (1-x)-1/ 2; y = 13 EMBED Equation.3 1415; диапазон [-0.9;0.9]
z = cos(sin x)ecos x; y = 13 EMBED Equation.3 1415; диапазон [0.1;1]
z = x; y = 2(sin x-13 EMBED Equation.3 1415); диапазон [-13 EMBED Equation.3 1415]
z = (1+2x2)13 EMBED Equation.3 1415; y = 1+3x2+13 EMBED Equation.3 1415; диапазон [0.1;1]
z = 13 EMBED Equation.3 1415;y=-cos x+13 EMBED Equation.3 1415;диапазон [0.1;1]
z = 13 EMBED Equation.3 1415lnx; y = 13 EMBED Equation.3 1415;диапазон [0.2;1]
z = x2; y =13 EMBED Equation.3 1415; диапазон [-13 EMBED Equation.3 1415]
z=x;y=13 EMBED Equation.3 1415; диапазон [0;13 EMBED Equation.3 1415]
z = x2; y = 13 EMBED Equation.3 1415; диапазон [-13 EMBED Equation.3 1415]
z=13 EMBED Equation.3 1415; y=1+13 EMBED Equation.3 1415; диапазон [0.1;1]
z = (0.68x)2 + 0.273; y = 13 EMBED Equation.3 1415;[-13 EMBED Equation.3 1415]
z = e2x; y = 1+13 EMBED Equation.3 1415; диапазон [0.1;1]
z = x3-x13 EMBED Equation.3 14152; y = -12(sinx-13 EMBED Equation.3 1415); диапазон [-13 EMBED Equation.3 1415]
z = 13 EMBED Equation.3 1415; y = x +13 EMBED Equation.3 1415; диапазон [0.1;1]
z = 2(cosx-1);13 EMBED Equation.3 1415; диапазон [0.1;1]
13 EMBED Equation.3 1415; y = 3x + 8x2 ++ n(n+2)xn; диапазон [0.1;0.8]
z = arctg x; y = x-13 EMBED Equation.3 1415; диапазон [0.1;0.5]
z = x; y =13 EMBED Equation.3 1415; диапазон[0;213 EMBED Equation.3 1415]
z =13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415; диапазон 13 EMBED Equation.3 1415
z = x;13 EMBED Equation.3 1415); диапазон [-1;1]
z = x2;13 EMBED Equation.3 1415; диапазон 13 EMBED Equation.3 1415
z = cos x; 13 EMBED Equation.3 1415; диапазон [-1;1]
z = e3x; 13 EMBED Equation.3 1415; диапазон [0.1;1]
z = x; 13 EMBED Equation.3 1415; диапазон -13 EMBED Equation.3 1415
30 z = arctg x; y = x-13 EMBED Equation.3 1415; диапазон [-0.5;0.5]
КОНТРОЛЬНЫЕ ВОПРОСЫ
Приведите определение модуля.
Опишите сборочный метод построения алгоритмов.
Что такое заглушка.
Что такое драйвер.
ПРАКТИЧЕСКАЯ РАБОТА №8
Оценка сложности алгоритмов методом Кирхгофа
ЦЕЛЬ РАБОТЫ
формирование навыков оценки сложности алгоритмов методом Кирхгофа.
ОБЕСПЕЧЕННОСТЬ ЗАНЯТИЯ
Чертежные принадлежности и ГОСТ 19.701-90. (ИСО 5807-85). ЕСПД. «Схемы алгоритмов, программ, данных и систем»
ЛИТЕРАТУРА
Теория алгоритмов: учеб. пособие для студ. сред. проф. учеб. заведений / В.И. Игошин. - М.: Издательский центр «Академия», 2013. - 320 с.
Алгоритмы. Построение и анализ. / Т.Х. Кормен, Ч.И. Лейзерон, Р.Л. Ривест. – М.: Вильямс, 2013. – 1328 с.
Алгоритмы. Руководство по разработке / Стивен С. Скиена. – СПб.: БХВ – Петербург, 2011. – 720 с.
Лавров С.С. Программирование. Математические основы, средства, теория. Мастер. Учебное пособие. СХБ-Петербург, 2001.- 320 с.
СОДЕРЖАНИЕ ЗАДАНИЙ
Оценка сложности алгоритма методом Киргофа.
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Предметом дальнейшего рассмотрения будет задача оценки трудоемкости алгоритма.
годен любой выбор.
ЗАДАНИЯ И ИНСТРУКЦИИ ПО ВЫПОЛНЕНИЮ
Задание 1
Оцените, используя метод Кирхгофа, сложность алгоритма разработанного для решения Задания 1 Практической работы 5 «Составление и запись на языке блок-схем алгоритмов содержащих циклы с параметром».
МЕТОДИКА АНАЛИЗА РЕЗУЛЬТАТОВ, ОБРАЗЕЦ ОТЧЕТА
Вариант 0
Выполнить слияние двух упорядоченных массивов в один, упорядоченный таким же порядком.
13 EMBED Visio.Drawing.11 1415
Изменим операторную схему, адаптировав ее для оценки трудоемкости алгоритма методом Кирхгофа. Дополнительную дугу изобразим пунктирной.
Например: g0=1, g4=g6=g9=g11=0, тогда вычислив остальные значения, получим: g1=g3=g8=g10=g12=1, g2=g5=g7=0.
Получено решение (1; 1; 0; 1; 0; 0; 0; 0; 1; 0; 1; 0; 1) которое может быть использовано для оценки трудоемкости, т.к. не содержит отрицательных значений переменных.
T=t0+t1+t3+t8+t10+t12.
КОНТРОЛЬНЫЕ ВОПРОСЫ
По каким направлениям осуществляется оценка алгоритмической сложности.
Перечислите этапы построения операторной схемы.
Опишите алгоритм оценки алгоритмической сложности, в соответствии методу Кирхгофа.
13 PAGE \* MERGEFORMAT 142315
40
15
15 15 20
15 5 5
начало
Y
Y=x2-7x+6
х
конец
начало
Х, y
F=(x<=0) И (y>=0) И (2x-3y+6>=0) ИЛИ (x>=0) И (y>=0) И (x*x+y*y<=4)
F
конец
начало
а, в
с=180-а-в
с
конец
-
+
Q
P
-
+
Q
P
T
-
-
-
-
-
+
+
+
+
+
начало
Введите значение аргумента x
x>5
x13 EMBED Equation.3 1415 8
Y=13 EMBED Equation.3 1415
y
«решения нет»
x<-5
x13 EMBED Equation.3 1415 -7
Y=13 EMBED Equation.3 1415
y
«решения нет»
x13 EMBED Equation.3 1415 3
Y=13 EMBED Equation.3 1415
y
«решения нет»
конец
i=1 (1) N
P
i=i0 (h) in
a=0
b
b=a mod 10
a=a div 10
a=|a|
а
-
+
Q
Р
конец
S2
n
a=1/f
s1=s2+a
f=f*i
i=i+1
K<=n
f=1
i=1
s2=s1
n=n+1
|s1-s2|>=10-3
n=2
a=0,5
s1=1,5
n=1
a=1
s1=1
начало
-
P
Q
+
j=1 (1) M
A[i;j]
"$&*,.0T
·
·
·
·
·
·
·
·
·
·
·Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeРисунок 31Рисунок 32Рисунок 33Рисунок 35Рисунок 37Рисунок 38Рисунок 41Рисунок 43