Депобразования и молодежи Югры

бюджетное учреждение профессионального образования

Ханты-Мансийского автономного округа – Югры

«Мегионский политехнический колледж»

(БУ «Мегионский политехнический колледж»)

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ПО ВЫПОЛНЕНИЮ ПРАКТИЧЕСКИХ РАБОТ

ПО ДИСЦИПЛИНЕ «ТЕОРИЯ АЛГОРИТМОВ»

Мегион, 2015

РАССМОТРЕНО

на заседании ЦМК естественнонаучных дисциплин

БУ «Мегионский политехнический колледж»

Протокол №198 от «8»июня 2015 г.

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

Шулика Ф.И., преподаватель 

Методические указания разработаны для оказания помощи обучающимся в выполнении практических работ и подготовки к экзамену по дисциплине «операционные системы» (специальность «230115 Программирование в компьютерных системах»).

Содержание

Оглавление

Пояснительная записка        4

Практическая работа №1        5

Практическая работа №2        6

Практическая работа №3        7

Практическая работа №4        8

Практическая работа №5        9

Практическая работа №6        10

Практическая работа №7        11

Практическая работа №8        13

Практическая работа №9        14

Практическая работа №10        15

Практическая работа №11        16

Практическая работа №12        17

Практическая работа №13        18

Практическая работа №14        19

Практическая работа №15        20

Пояснительная записка

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

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

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

Практическая работа №1

Тема: ПР 1-2 Словесная форма представления алгоритма.

Цель: Закрепление общего понятия «алгоритм». Решение простейших алгоритмических задач

Задание 1. Определить площадь трапеции по введенным значениям оснований (a и b) и высоты (h).

Задание 2. Определить среднее арифметическое двух чисел, если a положительное и частное (a/b) в противном случае.

Задание 3. Составить алгоритм нахождения суммы целых чисел в диапазоне от 1 до 10.

Практическая работа №2

Тема: ПР 3-4 Графическая форма представления алгоритма

Цель: Получение практических навыков в работе с графической формой представления алгоритма

1. Линейный алгоритм, выполненный в практической работе №1, переделать на циклический с заданным количеством циклов по примеру 4.
2. Найти сумму значений переменной Р, полагая, что начальное значение этой переменной равно нулю , т.е. Р=0. В каждом цикле переменная изменяется на 2, т.е. Р=Р+2. Количество циклов равно 5. В результате данного алгоритма значение переменной будет равна Р=10.
3. Пусть заданы начальные значения переменных:
   x:=1; y:=5.
   Начало цикла;
   пока y>x
   y: = y – x;
   конец цикла.
   Определить количество циклов и значения переменных x, y после выхода из цикла.

Практическая работа №3

Тема: 5-6 Представление алгоритма на псевдокоде.

Цель: Получение практических навыков в работе с алгоритмом, написанном на псевдокоде.

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

1. Вычислить площадь поверхности и объем усеченного конуса по следующим формулам

S = π (R + r) l + πR2 + πr2 ;

V = (1/3) π (R2 + r2 + Rr) h .

2. Вычислить координаты центра тяжести трех материальных точек с массами m1, m2, m3 и координатами (x1,y1), (x2,y2), (x3,y3) по формулам:

xc = (m1x1 + m2x2 + m3x3) / (m1 + m2 + m3) ;

yc = (m1y1 + m2y2 + m3y3) / (m1 + m2 + m3) .

3. Вычислить площадь треугольника со сторонами a, b, c по формуле Герона:

 ,

где p – полупериметр, вычисляемый по формуле

  ,

4. Вычислить координаты точки, делящей отрезок а1а2 в отношении n1:n2 по формулам:

 ;

 ,

где  .

5. Вычислить медианы треугольника со сторонами a, b, c по формулам:

 ;

 ;

 ;

6. Вычислить площадь круга и длину окружности по введенному значению радиуса.
7. Вычислить площадь S и периметр L эллипса по введенным значениям полуосей a и b:

 ;

Практическая работа №4

Тема: ПР7-8 Составление программ для машины Тьюринга.

Цель: Получение практических навыков в написании программ для «Машины Тьюринга»

Практическая работа №5

Тема: ПР9-10 Составление программ для машины Поста.

Цель: Получение практических навыков в написании программ для «Машины Поста»

Практическая работа №6

Тема: ПР 11-12 Составление нормальных алгоритмов Маркова.

Цель: Получение практических навыков в составлении алгоритмов Маркова.

Практическая работа №7

Тема: ПР 13-14 Решение задач по составлению линейных алгоритмов.

Цель: Получение практических навыков при решении задач для составления линейных алгоритмов

1. Вычислить и вывести на экран значение функции: Y = sin (x+30°)/(a + x)+b⋅a.

2. Вычислить медианы треугольника со сторонами a, b, c по формулам:

 ;

 ;

 ;

3. Вычислить площадь круга и длину окружности по введенному значению радиуса.

4. Вычислить площадь S и периметр L эллипса по введенным значениям полуосей a и b:

 ;

 .

5. Вычислить объем V и площадь боковой поверхности цилиндра S по введенным значениям радиуса основания R и высоты цилиндра H.

 ;

 .

6. Вычислить объем V и площадь боковой поверхности конуса S по введенным значениям радиуса основания r, высоты h и образующей l:

 ;

 .

7. Вычислить объем V и площадь поверхности S сферы по введенному значению радиуса r:

 ;

 .

Практическая работа №8

Тема: ПР 15-16 Решение задач по составлению ветвящихся алгоритмов.

Цель: Получение практических навыков при решении задач для составления ветвящихся  алгоритмов

1. Составить программу для решения квадратного уравнения ax2 + bx + c = 0.
2. Определить максимальное четное число из двух введенных.
3. Определить, можно ли из отрезков с длинами х, y и z построить треугольник.
4. Ввести два числа а и b. Большее число заменить утроенным произведением, меньшее – полусуммой.
5. Если среди трех чисел a, b, c имеется хотя бы одно четное, то найти максимальное число, иначе – минимальное.
6. Определить, в каком квадранте находится точка с координатами x и y и вывести номер квадранта на экран.
7. Найти квадрат наибольшего из двух чисел а и b. Вывести на экран число 1, если наибольшим является число а, число 2 – если наибольшим числом является b.
8. Определить, попадает ли точка с координатами x и y в круг радиусом R. Если точка попадает в круг, вывести на экран единицу, в противном случае – ноль.
9. Написать алгоритм решения задачи, которая решает уравнение ax + b = 0 относительно x для любых чисел a и b, введенных с клавиатуры. Все числа считаются действительными.
10. Написать алгоритм решения задачи, которая определяет, лежит ли точка А(х,у) внутри некоторого кольца («внутри» понимается в строгом смысле, т.е. случай, когда точка А лежит на границе кольца, недопустим). Центр кольца находится в начале координат. Для кольца заданы внутренний и внешний радиусы r1, r2. Координаты x и у вводятся с клавиатуры.

Практическая работа №9

Тема: ПР 17-18 Решение задач по составлению циклических алгоритмов.

Цель: Получение практических навыков при решении задач для составления циклических алгоритмов

1. Найти сумму чисел, кратных трем, в диапазоне от 0 до 50.
2. Найти сумму первых десяти чисел, кратных пяти.
3. Найти произведение четных чисел в диапазоне от 2 до 30.
4. Вводятся положительные числа. Прекратить ввод, когда сумма введенных чисел превысит 100.
5. Требуется найти сумму чисел, кратных 7, в диапазоне от 0 до 100. Вывести на экран сумму чисел и их количество.
6. Определить количество целых чисел, кратных 3 (от 3 и далее), дающих в сумме число, превышающее 200.
7. Вводятся 10 чисел. Вывести на экран суммы положительных и отрицательных чисел и их количество.
8. Вывести на экран значения функции у=sin(x) для 0≤x≤180 c шагом в 10.
9. Подсчитать площади десяти кругов с радиусами от 1 см с шагом 2 см и вывести значения площадей на экран.
10. Вводятся положительные числа. Прекратить ввод чисел, когда их сумма превысит 100. Результат вывести на экран.

Практическая работа №10

Тема: ПР 19-20 Составление алгоритма поиска в неупорядоченном массиве.

Цель: Получение практических навыков в работе с  алгоритмами поиска в неупорядоченном массиве

1. Определить порядковые номера нулей в массиве.
2. Все отрицательные элементы массива заменить нулями. Выдать сообщение о количестве таких замен.
3. Найти порядковый номер минимального числа в массиве.
4. Найти значение и координаты первого по порядку положительного элемента в массиве.
5. Найти количество единиц в массиве.
6. Каких чисел в массиве больше: положительных или отрицательных? (массив может содержать нулевые значения).
7. Исходные данные: В таблице 10 строк. Первый столбец – фамилия работника, второй – стаж работника.
8. По стажу работника определить, к какой группе он относится, если 1 группа – стаж до 3-х лет, 2 группа – до 5 лет, 3 группа – до 10 лет, 4 группа – свыше 10 лет.
9. Найти сумму диагональных элементов блока ячеек, состоящего из 5 строк и 5 столбцов.
10. Двадцати переменным массива присвоить одно и то же значение, равное наибольшему из них.

Практическая работа №11

Тема: ПР 21-22 Некоторые методы решения типовых задач в одномерном массиве.

Цель: Получение практических навыков в составлении алгоритмов для обработки линейных массивов

1. Дан массив чисел. В клетке С1 записано некоторое число. Определить порядковый номер этого числа в массиве. Если в массиве такого числа нет, выдать об этом сообщение.
2. Просуммировать положительные и отрицательные числа в массиве. Записать полученные суммы в ячейки В1 и В2. (в массиве могут быть нулевые значения).
3. В клетку А1 записать число, если количество положительных элементов массива больше количества отрицательных. В противном случае записать в клетку А1 любой текст.
4. Найти сумму положительных элементов массива, имеющих индекс 3, 5, 7 и т.д.
5. В блоке ячеек записана матрица чисел. Ячейки с отрицательными значениями закрасить синим цветом, с положительными – красным, с нулями – желтым.
6. Найти количество отрицательных элементов в массиве С1, С2,…, С20, используя оператор цикла do until_loop.
7. Дана последовательность Х(10). Найти сумму отрицательных элементов и вывести на печать номера этих элементов, используя оператор цикла do_loop while.
8. Вычислить произведение элементов, стоящих на нечетных местах в последовательности Х(20), используя оператор цикла do while_loop.
9. Дана последовательность Х1, Х2, …, Х20. Заменить в ней отрицательные значения элементов на их квадраты. Вывести на печать полученную последовательность, используя оператор цикла do while_loop.

Практическая работа №12

Тема: ПР 23-24 Некоторые методы решения типовых задач в двумерном массиве.

Цель: Получение практических навыков в составлении алгоритмов для обработки матриц.

1. Задан массив А(6,5). Найти номер строки и номер столбца с минимальным значением.
2. Задан массив А(4,5). Найти минимальное значение.
3. Задан массив х(5,5). Найти сумму отрицательных значений в каждой строке.
4. Задан массив х(5,5). Найти сумму положительных значений в каждом столбце.
5. Задан массив с(5,5) и число а. Найти количество элементов, равных по значению а.
6. Задан массив с(5,5) и число а. Найти сумму элементов, равных по значению а.
7. Задан массив х(5,5) и число а. Найти номера строк и столбцов элементов, равных по значению а.
8. Задан массив х(5,5) и интервал (а,b). Найти номера строк и столбцов элементов, попавших по значению в этот интервал.
9. Задан массив х(5,5) и интервал х[а,b]. Найти количество элементов, попавших по значению в этот интервал.
10. Задан массив х(5,5) и интервал х[а,b]. Найти сумму элементов, попавших по значению в этот интервал.

Практическая работа №13

Тема: ПР 25-26 Разработка рекурсивных алгоритмов.

Цель: Получение практических навыков в работе с рекуррентными алгоритмами

Практическая работа №14

Тема: ПР 27-28 Решение задач на определение сложности алгоритма.

Цель: Получение практических навыков в работе с задачами  на определение сложности алгоритма.

Составить алгоритм и определить его сложность для следующих задач:

1. Задан массив А(6,5). Найти номер строки и номер столбца с минимальным значением.
2. Найти количество отрицательных элементов в массиве С1, С2,…, С20, используя оператор цикла do until_loop.
3. Найти максимальное значение из значений элементов последовательности x1, x2, …, x20 (одномерного массива), используя оператор do while…loop
4. Составить блок-схему и разработать функцию пользователя для вычисления годовой процентной ставки контракта по кредиту, взятого на определенный срок при известных сумме долга и сумме, подлежащей возврату. Используйте формулу:

 ,

5. Определите произведение трех переменных.

Практическая работа №15

Тема: ПР 29-30 Анализ алгоритмов поиска.

Цель: Получение практических навыков в работе с алгоритмами поиска.

Задание 1

1. Сгенерировать массив целых случайных чисел размером N = 1000. (Для генерации случайных чисел используйте класс System.Random).

2. Отсортировать полученный массив любым методом сортировки.

3. Ввести с клавиатуры некоторое целое число.

4. Используя метод интерполяционного поиска, определить, позицию введенного числа в массиве, если оно в нем присутствует.

Задание 2

Составить программу, которая в заданном текстовом файле ищет все вхождения, введенного пользователем слова, формируя список позиций (от начала файла) искомого слова. Метод поиска – любой, кроме линейного поиска подстроки.

Задание 3

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