Задания на домашнюю контрольную работу по учебной дисциплине «Структуры и алгоритмы обработки данных»

Теоретические вопросы

1. Дайте понятие термину «структура данных». Классификация структур данных.

2. Статические и динамические структуры данных.

3. Указатель. Базовые операции с указателями в языке Паскаль.

4. Структура данных «стек»: определение, основные операции – создание, добавление элемента, удаление элемента. Алгоритм преобразования выражения в обратную польскую запись.

5. Структура данных «односвязный список»: определение, основные операции – создание, добавление элемента, удаление элемента.

6. Структура данных «двусвязные список»: определение, основные операции – создание, добавление элемента, удаление элемента.

7. Структура данных «очередь»: определение, основные операции – создание, добавление элемента, удаление элемента.

8. Структура данных «кольцо»: определение, основные операции – создание, добавление элемента, удаление элемента.

9. Структура данных «бинарное дерево»: определение, основные операции над бинарным деревом – создание, добавление элемента, удаление элемента.

10. Опишите алгоритмы поиска по ключу и полного обхода в бинарном дереве.

11. Структура данных «прошитое бинарное дерево»: определение, основные операции – создание, добавление элемента, удаление элемента.

12. Опишите алгоритм поиска по ключу в прошитом бинарном дереве

13. Структура данных «красно-черное бинарное дерево»: определение, основные свойства, создание, размещение очередного элемента.

14. Комбинаторика. Размещения. Алгоритмы генерации размещений.

15. Комбинаторика. Сочетания. Алгоритмы генерации сочетаний.

16. Комбинаторика. Перестановки. Алгоритмы генерации перестановок.

17. Опишите алгоритмы генерирования множества всех подмножеств множества.

18. Опишите алгоритмы генерирования множества всех к-элементных подмножеств множества.

19. Понятие графа. Основные свойства графов.

20. Способы представления графов в памяти компьютера.

21. Опишите вычислительную схему алгоритма поиска в глубину на графе.

22. Опишите вычислительную схему алгоритма поиска в ширину на графе.

23. Опишите вычислительную схему алгоритма поиска кратчайшего пути между двумя вершинами на графе.

24. Опишите понятие «сеть». Дайте определение понятию максимального потока на сети.

25. Опишите алгоритм нахождения максимального потока методом Форда-Фанкерсона.

26. Опишите алгоритм нахождения потока минимальной стоимости.

27. Опишите общую схему полного перебора.

28. Опишите вычислительную схему алгоритма решения задачи о коммивояжере методом полного перебора.

29. Опишите вычислительную схему алгоритма решения задачи о шахматном коне методом полного перебора.

30. Опишите вычислительную схему алгоритма решения задачи о лабиринте методом полного перебора.

31. Опишите общие схемы сокращения полного перебора.

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

33. Опишите алгоритмы решения задачи о расстановке ферзей на шахматной доске.

34. Опишите технологии динамического программирования: восходящее динамическое программирование, нисходящее динамическое программирование.

35. Опишите способ реализации метода динамического программирования на примере задачи о ранце.

36. Опишите способ реализации метода динамического программирования на примере задачи генерирования чисел Фибоначчи.

37. Опишите способ реализации метода динамического программирования на примере задачи поиска наибольшей общей последовательности.

38. Опишите вычислительную схему метода ветвей и границ.

39. Опишите принципы работы алгоритма жадного выбора.

40. Опишите применение жадного алгоритма в задаче о поиске кратчайшего пути между двумя вершинами графа.

41. Опишите применение жадного алгоритма в задаче о ранце.

42. Опишите применение жадного алгоритма в задаче о сумме элементов подмножества.

43. Опишите вычислительную схему алгоритма Хоффмана.

44. Вычислительная геометрия. Опишите алгоритмы определения взаимного расположения отрезков, прямых и плоскостей.

45. Вычислительная геометрия. Опишите алгоритмы построения выпуклой оболочки.

46. Вычислительная геометрия. Опишите алгоритмы отыскания пары ближайших точек.

47. Вычислительная геометрия. Опишите алгоритмы нахождения площадей фигур.

48. Опишите методы генерирования равномерно распределенных случайных чисел.

49. Опишите методы генерирования нормально распределенных случайных чисел.

50. Опишите методы генерирования случайных чисел, распределенных по показательному закону.

51. Опишите классы задач, решаемых с помощью генераторов случайных чисел.

52. Понятия хеш-функции и хеш-таблицы.

53. Опишите методы хеширования: метод деления, метод середины квадратов, метод свертывания.

54. Коллизии при хешировании. Методы разрешения коллизий.

55. Опишите классы задач, решаемых с помощью построения хеш-таблиц.

Практические задания

1 Задания 56-67. Дан одномерный массив целых чисел. Реализовать алгоритм сортировки указанным методом.

56. Реализовать алгоритм сортировки массива методом простого выбора по возрастанию.

57. Отсортировать методом простого обмена элементы, стоящие на нечетных местах по убыванию.

58. Реализовать алгоритм сортировки массива методом вставок по возрастанию.

59. Отсортировать четные элементы массива методом простого выбора по убыванию.

60. Реализовать алгоритм сортировки массива методом простого обмена по возрастанию.

61. Отсортировать методом простого выбора элементы, стоящие на нечетных местах по убыванию.

62. Реализовать алгоритм сортировки массива методом вставок по убыванию.

63. Отсортировать отрицательные элементы массива методом простого выбора по возрастанию.

64. Реализовать алгоритм сортировки массива методом простого выбора по убыванию.

65. Отсортировать методом вставок элементы, стоящие на нечетных местах по возрастанию.

66. Реализовать алгоритм сортировки массива методом простого обмена по убыванию.

67. Отсортировать четные элементы массива методом простого выбора по возрастанию.

2 Задания 68-100. В задачах требуется обработать заданную динамическую структуру данных. Элементы исходной структуры данных вводятся с клавиатуры. Результат выводится на экран.

68. Информационное поле элемента стека - числовое. Разбить стек на два стека - из положительных и отрицательных элементов.

69. Задан массив чисел. Скопировать элементы массива в информационное поле элементов стека.

70. Информационное поле элемента стека - числовое. Найдите максимальный элемент стека и поменять его местами с первым элементом стека.

71. Информационное поле элемента стека - числовое. Найдите минимальный и максимальный элементы стека и поменять их местами.

72. Выбросить из стека повторяющиеся элементы, идущие подряд.

73. Информационное поле элемента стека - числовое. Выбросить из стека отрицательные числа, идущие подряд.

74. Информационное поле элемента стека - числовое. Вычислить среднее арифметическое элементов стека и выбросить из стека элементы, превышающие среднее арифметическое.

75. Информационное поле элемента стека - числовое. Удалить из стека нулевые элементы.

76. Подсчитать количество элементов списка, у которых "соседи" равны между собой.

77. Информационное поле элемента списка - числовое. Подсчитать и вывести на экран элементы списка не равные нулю.

78. Объединить два списка в один, присоединив хвост второго списка к голове первого.

79. Объединить два списка в один, чередуя элементы первого и второго списка.

80. Информационное поле элемента списка - числовое. Разбить список на два списка - из положительных и отрицательных элементов.

81. Информационное поле элемента списка - числовое. Найдите максимальный элемент списка и поменять его местами с первым элементом списка.

82. Информационное поле элемента списка - числовое. Найдите минимальный и максимальный элементы списка и поменять их местами.

83. Выбросить из списка повторяющиеся элементы, идущие подряд.

84. Информационное поле элемента списка - числовое. Выбросить из списка отрицательные числа, идущие подряд.

85. Информационное поле элемента списка - числовое. Вычислить среднее арифметическое элементов списка и выбросить из списка элементы, превышающие среднее арифметическое.

86. Информационное поле элемента списка - числовое. Удалить из списка нулевые элементы.

87. Подсчитать количество элементов очереди, у которых "соседи" равны между собой.

88. Информационное поле элемента очереди - числовое. Подсчитать и вывести на экран элементы очереди, не равные нулю.

89. Информационное поле элемента очереди - числовое. Разбить очередь на две очереди - из положительных и отрицательных элементов.

90. Информационное поле элемента очереди - числовое. Найдите максимальный элемент очереди и поменять его местами с первым элементом очереди.

91. Информационное поле элемента очереди - числовое. Найдите минимальный и максимальный элементы очереди и поменять их местами.

92. Выбросить из очереди повторяющиеся элементы, идущие подряд.

93. Информационное поле элемента очереди - числовое. Выбросить из очереди отрицательные числа, идущие подряд.

94. Информационное поле элемента очереди - числовое. Вычислить среднее арифметическое элементов очереди и выбросить из очереди элементы, превышающие среднее арифметическое.

95. Информационное поле элемента очереди - числовое. Удалить из очереди нулевые элементы.

96. Информационное поле двоичного упорядоченного дерева содержит целое число. Вывести на экран среднее арифметическое этих чисел, а также наибольшее и наименьшее из них.

97. Информационное поле двоичного упорядоченного дерева содержит целое число. Удалить из дерева все узлы, информационное поле которых превышает некоторое вводимое пользователем число.

98. Информационное поле двоичного упорядоченного дерева содержит целое число. Удалить из дерева нулевые элементы, а также подсчитать их количество.

99. Информационное поле двоичного упорядоченного дерева содержит целое число. Выбросить из дерева повторяющиеся элементы.

100. Информационное поле двоичного упорядоченного дерева содержит целое число. Подсчитать количество элементов, больших среднего арифметического всех элементов дерева.

3 Задания 101- 129. Во всех задачах под термином "граф" понимается: (а) "неориентированный граф"; (б) "ориентированный граф" (организо­вать выбор). Ввод должен осуществляться либо с клавиатуры либо из файла (организовать выбор пользователя).

101. Определите степень каждой вершины (количество ребер, инцидентных данной вершине) в графе, заданном матрицей смежностей. Указание. Необходимо найти сумму чисел в строке матрицы смежности, соответствующей данной вершине.

102. Определите степень каждой вершины (количество ребер, инцидентных данной вершине) в графе, заданном матрицей инцидентности.

103. Посчитайте количество ребер в графе, заданном матрицей смежности вершин. Указание. Найдите сумму элементов, стоящих на и выше главной диагонали матрицы смежности.

104. . Проверьте, есть ли в графе, заданном матрицей смежности ребер, кратные ребра. Указание. Проверьте наличие в матрице смежности элементов >1. Если такие элементы есть, то номера этих элементов соответствуют вершинам, имеющим кратные ребра.

105. Проверьте, имеет ли граф, заданный матрицей смежности вершин, петли. Указание. Проверьте наличие на главной диагонали матрицы смежности элементов, не равных 0.

106. Посчитайте количество кратных ребер в графе, заданном матрицей смежности вершин.

107. В графе, заданном матрицей смежности вершин, определите количество петель.

108. Определите максимальную кратность ребер в графе, заданном матрицей смежности вершин. Указание. Найдите максимальный элемент в матрице смежности.

109. Посчитайте число вершин в графе (граф задан матрицей смежности вершин), от которых отходит более m ребер. Указание. Найдите количество сумм строк в матрице смежности, больших m.

110. Напишите программу, определяющую существуют ли в графе, заданном матрицей смежности вершин, изолированные вершины? Указание. Суммы строк в матрице смежности равны 0.

111. Определите, каково максимальное (минимальное) количество ребер, выходящих от одной вершины в графе, заданном матрицей смежности? Указание. Найдите максимум сумм строк в матрице смежности.

112. Напишите программу, определяющую среднее количество ребер в графе, заданном матрицей смежности вершин? Указание. Среднее арифметическое элементов матрицы смежности.

113. Установите, является ли граф, заданный матрицей смежности вершин, регулярным (в регулярном графе степень всех вершин одинакова)? Указание. Суммы в строках матрицы смежности одинаковы.

114. Установите, является ли граф, заданный матрицей смежности вершин, полным (в полном графе любые две вершины смежны)? Указание. Все элементы матрицы смежности равны 1.

115. Определите степень каждой вершины (количество ребер, инцидентных данной вершине) в графе, заданном матрицей инцидентности.

116. Посчитайте количество ребер в графе, заданном матрицей инцидентности.

117. Проверьте, есть ли в графе, заданном матрицей инцидентности, кратные ребра.

118. Проверьте, имеет ли граф, заданный матрицей инцидентности, петли.

119. Посчитайте количество кратных ребер в графе, заданном матрицей инцидентности.

120. В графе, заданном матрицей инцидентности, определите количество петель.

121. Определите максимальную кратность ребер в графе, заданном матрицей инцидентности.

122. Посчитайте число вершин в графе (граф задан матрицей инцидентности), от которых отходит более m ребер.

123. Определите, существуют ли в графе, заданном матрицей инцидентности, изолированные вершины?

124. Определите, каково максимальное (минимальное) количество ребер, отходящих от одной вершины в графе, заданном матрицей инцидентности?

125. Определите, каково минимальное количество ребер, отходящих от одной вершины, в графе, заданном матрицей инцидентности?

126. Определите, является ли граф, заданный матрицей инцидентности, регулярным (в регулярном графе степень всех вершин одинакова)?

127. Определите, является ли граф, заданный матрицей инцидентности, полным (в полном графе любые две вершины смежны)?

128. Определите, является ли граф, заданный матрицей инцидентности, звездой (звезда - граф, у которого одна вершина соединена со всеми, а у остальных степень равна 1)?

129. Определите, является ли граф, заданный матрицей инцидентности, кольцом (кольцо - связный граф, степень каждой вершины которого равна 2)?

4 Задания 130- 135. Комбинаторные задачи. Задачи решаемые методами полного перебора, сокращенного перебора либо перебора с возвратом. Если по условию задачи требуется задание исходных данных, то они вводятся с клавиатуры.

130. Напишите программу генерации всех возможных сочетаний из n элементов по m.

131. Напишите программу генерации всех возможных перестановок из n элементов по m.

132. Напишите программу генерации всех возможных размещений из n элементов по m.

133. Игра "Ханойская башня" состоит в следующем. Есть три стержня. Hа первый из них надета пирамидка из N колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составьте программу, указывающую требуемые действия.

134. Задача о ферзях. Требуется составить программу нахождения всех возможных способов расстановки 8-ми ферзей на шахматной доске 8 на 8, при которых они не бьют друг друга.

135. Задача о лабиринте. Прямоугольное клеточное поле ограничено препятствиями. Кроме того, на поле задается произвольная система препятствий, начальная клетка, на которой находится Черепашка и конечная клетка. Найти маршрут выхода из лабиринта, если он существует, и пронумеровать клетки маршрута в том порядке, в котором проходит их Черепашка. Черепашка может делать шаг в любом из четырех направлений: влево, вправо, вверх, вниз.

5 Задания 136- 162. Условие вида «дана матрица размера М х М означает, что вначале дается фактический размер двумерного массива-матрицы (количество строк М и ко­личество столбцов N), а затем приводятся элементы этого массива (количество элементов равно M*N). Если в задании явно не указывается, какие значения мо­гут принимать размеры исходной матрицы, то предполагается, что и число строк, и число столбцов может меняться в пределах от 2 до 10. Порядковые но­мера начальной строки и начального столбца матрицы считаются равными 1.

Ввод и вывод элементов матрицы осуществляются по строкам.

Организовать ввод матрицы как с клавиатуры так и из файла.

Используя алгоритм полного перебора решить поставленную задачу.

136. Дана целочисленная матрица размера M х N. Найдите номер первой из ее строк, содержащих равное количество положительных и отрицательных элементов (нулевые элементы матрицы не учитываются). Если таких строк нет, то вывести 0.

137. Дана целочисленная матрица размера M х N. Найдите номер последнего из ее столбцов, содержащих равное количество положительных и отрица­тельных элементов (нулевые элементы матрицы не учитываются). Если та­ких столбцов нет, то вывести 0.

138. Дана целочисленная матрица размера М х N. Найдите номер последней из ее строк, содержащих только четные числа. Если таких строк нет, то вывести 0.

139. Дана целочисленная матрица размера М х N. Найдите номер первого из ее столбцов, содержащих только нечетные числа. Если таких столбцов нет, то вывести 0.

140. Дана целочисленная матрица размера М х N, элементы которой могут принимать значения от 0 до 100. Различные строки матрицы назовем по­хожими, если совпадают множества чисел, встречающихся в этих строках. Найдите количество строк, похожих на первую строку данной матрицы.

141. Дана целочисленная матрица размера М х N, элементы которой могут принимать значения от 0 до 100. Различные столбцы матрицы назовем по­хожими, если совпадают множества чисел, встречающихся в этих столб­цах. Найдите количество столбцов, похожих на последний столбец данной матрицы.

142. Дана целочисленная матрица размера M х N. Найдите количество ее строк, все элементы которых различны.

143. Дана целочисленная матрица размера M х N. Найдите количество ее столбцов, все элементы которых различны.

144. Дана целочисленная матрица размера M х N. Найдите номер последней из ее строк, содержащих максимальное количество одинаковых элементов.

145. Дана целочисленная матрица размера M х N. Найдите номер первого из ее столбцов, содержащих максимальное количество одинаковых элемен­тов.

146. Дана матрица размера M х N. Найдите количество ее строк, элементы которых упорядочены по возрастанию.

147. Дана матрица размера M х N. Найдите количество ее столбцов, элемен­ты которых упорядочены по убыванию.

148. Дана матрица размера M х N. Найдите минимальный среди элементов тех строк, которые упорядочены либо по возрастанию, либо по убыванию. Если упорядоченные строки в матрице отсутствуют, то вывести 0.

149. Дана матрица размера М х N. Найдите максимальный среди элементов тех столбцов, которые упорядочены либо по возрастанию, либо по убыва­нию. Если упорядоченные столбцы в матрице отсутствуют, то вывести 0.

150. Дана целочисленная матрица размера M х N. Найдите элемент, являю­щийся максимальным в своей строке и минимальным в своем столбце. Ес­ли такой элемент отсутствует, то вывести 0.

151. Дана матрица размера M х N. В каждой строке матрицы найдите мини­мальный элемент и максимальный элемент среди этих минимальных.

152. Дана матрица размера M х N. В каждом столбце матрицы найдите мак­симальный элемент и минимальный среди этих максимальных.

153. Дана матрица размера M х N. Найдите номер ее строки с наибольшей суммой элементов и вывести данный номер, а также значение наибольшей суммы. Среди этих наибольших сумм найдите наименьшую.

154. Дана матрица размера M х N. Найдите номер ее столбца с наименьшим произведением элементов и вывести данный номер, а также значение наи­меньшего произведения.

155. Дана матрица размера M х N. Найдите максимальный среди минималь­ных элементов ее строк.

156. Дана матрица размера M х N. Найдите минимальный среди максималь­ных элементов ее столбцов.

157. Дана матрица размера M х N. В каждой ее строке найдите количество элементов, меньших среднего арифметического всех элементов этой стро­ки.

158. Дана матрица размера M х N. В каждом ее столбце найдите количество элементов, больших среднего арифметического всех элементов этого столбца.

159. Дана целочисленная матрица размера M х N. Найдите номер последней из ее строк, содержащих равное количество положительных и отрицательных элементов (нулевые элементы матрицы не учитываются). Если таких строк нет, то вывести 0.

160. Дана целочисленная матрица размера M х N. Найдите номер первого из ее столбцов, содержащих равное количество положительных и отрица­тельных элементов (нулевые элементы матрицы не учитываются). Если та­ких столбцов нет, то вывести 0.

161. Дана матрица размера M х N. Найдите максимальный среди элементов тех строк, которые упорядочены либо по возрастанию, либо по убыванию. Если упорядоченные строки в матрице отсутствуют, то вывести 0.

162. Дана матрица размера М х N. Найдите минимальный среди элементов тех столбцов, которые упорядочены либо по возрастанию, либо по убыва­нию. Если упорядоченные столбцы в матрице отсутствуют, то вывести 0.

6 Задания 163- 172. Найдите корень уравнения методом деления отрезка пополам. Второй конец отрезка найдите самостоятельно путем построения графика заданной функции. В отчете приведите описание метода решения, программу и результат.

163. Найдите корень уравнения

e^x – 2x – 10 = 0

с точностью  = 10^-4 при заданном значении начала отрезка а = 0.

164. Найти корень уравнения

с точностью e = 10^-4 при заданном значении начала отрезка а = -2.

165. Найдите корень уравнения

x + 0.5sin x + 1 =0

с точностью e = 10^-4 при заданном значении начала отрезка а = -1.

166. Найдите корень уравнения

x – cos x = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

167. Найдите корень уравнения

1.4^x – x = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

168. Найдите корень уравнения

0.5x – ln |x| = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = -1.

169. Найдите корень уравнения

x³ + sin x – 3.5x + 1 = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

170. Найдите корень уравнения

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

171. Найдите корень уравнения

(4 + x²)(e^x – e^-x) = 18

с точностью e = 10^-5 при заданном значении начала отрезка а = 1.

172. Найдите корень уравнения

3x² – cos 2x = 1

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

7 Задания 173- 182. Найти корень уравнения методом хорд. Второй конец отрезка найти самостоятельно путем построения графика заданной функции. В отчете привести описание метода решения, программу и результат.

173. Найдите корень уравнения

e^x – 2x – 10 = 0

с точностью  = 10^-4 при заданном значении начала отрезка а = 0.

174. Найдите корень уравнения

с точностью e = 10^-4 при заданном значении начала отрезка а = -2.

175. Найдите корень уравнения

x + 0.5sin x + 1 =0

с точностью e = 10^-4 при заданном значении начала отрезка а = -1.

176. Найдите корень уравнения

x – cos x = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

177. Найдите корень уравнения

1.4^x – x = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

178. Найдите корень уравнения

0.5x – ln |x| = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = -1.

179. Найдите корень уравнения

x³ + sin x – 3.5x + 1 = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

180. Найдите корень уравнения

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

181. Найдите корень уравнения

(4 + x²)(e^x – e^-x) = 18

с точностью e = 10^-5 при заданном значении начала отрезка а = 1.

182. Найдите корень уравнения

3x² – cos 2x = 1

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

8 Задания 183- 192. Найти корень уравнения методом Ньютона. Второй конец отрезка найти самостоятельно путем построения графика заданной функции. В отчете привести описание метода решения, программу и результат.

183. Найдите корень уравнения

e^x – 2x – 10 = 0

с точностью  = 10^-4 при заданном значении начала отрезка а = 0.

184. Найдите корень уравнения

с точностью e = 10^-4 при заданном значении начала отрезка а = -2.

185. Найдите корень уравнения

x + 0.5sin x + 1 =0

с точностью e = 10^-4 при заданном значении начала отрезка а = -1.

186. Найдите корень уравнения

x – cos x = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

187. Найдите корень уравнения

1.4^x – x = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

188. Найдите корень уравнения

0.5x – ln |x| = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = -1.

189. Найдите корень уравнения

x³ + sin x – 3.5x + 1 = 0

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

190. Найдите корень уравнения

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

191. Найдите корень уравнения

(4 + x²)(e^x – e^-x) = 18

с точностью e = 10^-5 при заданном значении начала отрезка а = 1.

192. Найдите корень уравнения

3x² – cos 2x = 1

с точностью e = 10^-5 при заданном значении начала отрезка а = 0.

9 Задания 193- 200. Найдите площадь фигуры ограниченной заданными функциями методом средних прямоугольников. В отчете приведите описание метода решения, программу и результат.

193. , x₁ = 2, x₂ = 3.5

194. f = , x₁ = 3 , x₂ = 3.5

195. f = , x₁ = 0, x₂ = 2

196. f = , x₁ = 0.5, x₂ = 2

197. f = , x₁ = 2, x₂ = 2,5

198. f = , x₁ = 0, x₂ = 1

199. f = , x₁ = 2, x₂ = 5

200. f = , x₁ = 0, x₂ = 1

10 Задания 201- 210. Найдите площадь фигуры ограниченной заданными функциями методом трапеций. В отчете приведите описание метода решения, программу и результат.

201. , x₁ = 2, x₂ = 3.5

202. f = , x₁ = 3 , x₂ = 3.5

203. f = , x₁ = 0, x₂ = 2

204. f = , x₁ = 0.5, x₂ = 2

205. f = , x₁ = 2, x₂ = 2,5

206. f = , x₁ = 0, x₂ = 1

207. f = , x₁ = 2, x₂ = 5

208. f = , x₁ = 0, x₂ = 1

209. f = , x₁ = 0, x₂ = 1

210. f = , x₁ = 0, x₂ =

11 Задания 211- 220. Найдите площадь фигуры ограниченной заданными функциями методом парабол. В отчете приведите описание метода решения, программу и результат.

211. , x₁ = 2, x₂ = 3.5

212. f = , x₁ = 3 , x₂ = 3.5

213. f = , x₁ = 0, x₂ = 2

214. f = , x₁ = 0.5, x₂ = 2

215. f = , x₁ = 2, x₂ = 2,5

216. f = , x₁ = 0, x₂ = 1

217. f = , x₁ = 2, x₂ = 5

218. f = , x₁ = 0, x₂ = 1

219. f = , x₁ = 0, x₂ = 1

220. f = , x₁ = 0, x₂ =

Методические рекомендации по оформлению практического

задания

Найдите площадь фигуры ограниченной заданными функциями методом правых прямоугольников. Заданные функции: f = sin x / x², x₁ = 1, x₂ = 3.

Описание метода

Разделим отрезок [a; b] на n равных частей, т.е. на n элементарных отрезков. Длина каждого элементарного отрезка  . Точки деления будут: x₀=a; x₁=a+h; x₂=a+2× h, ... , x_n-1=a+(n-1)× h; x_n=b. Эти числа будем называть узлами. Вычислим значения функции f(x) в узлах, обозначим их y₀, y₁, y₂, ... , y_n. Cтало быть, y₀=f(a), y₁=f(x₁), y₂=f(x₂), ... , y_n=f(b). Числа y₀, y₁,y₂, ... , y_n являются ординатами точек графика функции, соответствующих абсциссам x₀, x₁, x₂, ... , x_n (рисунок 1). Площадь криволинейной трапеции приближенно заменяется площадью многоугольника, составленного из n прямоугольников. Таким образом, вычисление определенного интеграла сводится к нахождению суммы n элементарных прямоугольников.

Формула правых прямоугольников:

Рисунок 1 – Геометрическая интерпретация

Текст программы

Program RP;

var x1,x2,h,S1,x,y:real;

begin

S1:=0;

x1:=1;

x2:=3;

h:=(x2-x1)/100;

x:=x1;

while x<x2 do

begin

y:=sin(x)/sqr(x);

S1:=S1+(y)*h;

x:=x+h;

end;

writeln(S1);

end.

Результаты работы программы представлены на рисунке 2.

Рисунок 2 – Результат работы программы

Таблица 1 – Варианты домашней контрольной работы по учебной дисциплине «Структуры и алгоритмы обработки данных»

Предпоследняя цифра шифра	Последняя цифра номера шифра
	0	1	2	3	4	5	6	7	8	9
0	1, 56, 104, 136, 179	2, 57, 105, 137, 180	3, 58, 106, 138, 181	4, 59, 107, 139, 182	5, 60, 108, 140, 183	6, 61, 109, 141, 184	7, 62, 110, 142, 185	8, 63, 111, 143, 186	9, 64, 112, 144, 187	10, 65, 113, 145, 188
1	11, 66, 117, 146, 189	12, 67, 118, 147, 190	13, 68, 119, 148, 191	14, 69, 120, 149, 192	15, 70, 121, 150, 193	16, 71, 122, 151, 201	17, 72, 123, 152, 211	18, 73, 124, 153, 194	19, 74, 125, 154, 202	20, 75, 126, 155, 212
2	21, 76, 101, 156, 195	22, 77, 102, 157, 203	23, 78, 103, 158, 213	24, 79, 127, 159, 196	25, 80, 128, 160, 204	26, 81, 129, 161, 214	27, 82, 114, 162, 197	28, 83, 115, 163, 205	29, 84, 116, 164, 215	30, 85, 107, 165, 198
3	31, 86, 108, 166, 206	32, 87, 109, 167, 216	33, 88, 110, 168, 199	34, 89, 130, 169, 207	35, 90, 131, 170, 217	36, 91, 132, 171, 200	37, 92, 133, 172, 208	38, 93, 134, 173, 218	39, 94, 135, 174, 193	40, 95, 104, 175, 209
4	41, 96, 105, 176, 219	42, 97, 106, 177, 194	43, 98, 111, 178, 210	44, 99, 112, 179, 220	45, 100, 113, 180, 195	46, 56, 114, 181, 201	47, 57, 115, 182, 211	48, 58, 116, 183, 196	49, 59, 117, 184, 202	50, 60, 118, 185, 212
5	51, 61, 119, 186, 197	52, 62, 120, 187, 203	53, 63, 121, 188, 213	54, 64, 122, 189, 198	55, 65, 123, 190, 204	1, 66, 124, 191, 214	2, 67, 125, 192, 199	3, 68, 126, 136, 205	4, 69, 127, 137, 215	5, 70, 128, 138, 200

Продолжение таблицы 1

Предпоследняя цифра шифра	Последняя цифра номера шифра
	0	1	2	3	4	5	6	7	8	9
6	6, 71, 129, 139, 206	7, 72, 130, 140, 216	8, 73, 131, 141, 193	9, 74, 132, 142, 207	10, 75, 133, 143, 217	11, 76, 134, 144, 194	12, 77, 135, 145, 208	13, 78, 101, 146, 218	14, 79, 102, 147, 195	15, 80, 103, 148, 209
7	16, 81, 113, 149, 219	17, 82, 114, 150, 196	18, 83, 115, 151, 210	19, 84, 116, 152, 220	20, 85, 117, 153, 197	21, 86, 118, 154, 201	22, 87, 119, 155, 211	23, 88, 120, 156, 198	24, 89, 121, 157, 202	25, 90, 122, 158, 212
8	26, 91, 123, 159, 199	27, 92, 124, 160, 203	28, 93, 125, 161, 213	29, 94, 126, 162, 200	30, 95, 127, 163, 204	31, 96, 128, 164, 214	32, 97, 129, 165, 193	33, 98, 130, 166, 205	34, 99, 131, 167, 215	35, 100, 132, 168, 194
9	36, 59, 133, 169, 206	37, 60, 134, 170, 216	38, 61, 135, 171, 195	39, 62, 101, 172, 207	40, 63, 102, 173, 217	41, 64, 103, 174, 196	42, 65, 104, 175, 208	43, 66, 105, 176, 218	44, 67, 106, 177, 197	45, 68, 107, 178 209