Сортировка и упорядочение массива.

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

Пример 9.3. Упорядочить массив. А(n) по возрастанию.

Алгоритм имеет следующий вид.

1) В массиве А(n) найти минимальный элемент и запомнить его номер.

2) Найденный элемент поменять местами с первым элементом массива.

3) Повторить поиск минимального элемента со второго до последнего.

4) Новый минимальный элемент поменять местами со вторым элементом массива.

5) Этапы 3 и 4 повторить с уменьшающимся остатком массива до полного упорядочивания массива

Рис.9.5. Блок схема алгоритма сортировки массива. А(n) по возрастанию.

Накапливание результата

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

Пример 9.4. Найти сумму ряда

Фрагмент кода для вычисления суммы

s:=0;

for i:=1 to n do

s:=s+a[i]

Пример 9.5. Найти произведение ряда

Фрагмент кода для вычисления произведения

s:=1;

for i:=1 to n do

s:=s*a[i]

Вычисление математического ожидания случайной дискретной величины

Математическое ожидание M [ X ] случайной дискретной величины X, для которой известно n реализаций x_i i=1,…, n вычисляется по формуле: где x_i – i -я реализация, n – размер массива x =(x ₁,…, x_n), p_i – вероятность появления реализации x_i, равная отношению количества элементов имеющих значение x_i к количеству элементов массива x за вычетом повторяющихся.

Фрагмент кода для нахождения математического ожидания M [ X ]:

s:=0; for i:=1 to n do s:s+x[i]*p[i];

Порядок выполнения работы

1) Для указанного варианта задания составить программу в Delphi для решения поставленной задачи. В программе предусмотреть вывод исходного массива и результата в наглядной форме.

2) Отладить программу и выполнить задание на компьютере.

3) Составить в соответствии с требованиями отчёт о проделанной работе на ПК в виде файла.

4) При сдаче лабораторной работы студент должен показать и объяснить результаты выполнения задания на компьютере, представить отчет и ответить на контрольные вопросы.

7. Контрольные вопросы

Варианты заданий

Исходным массивом является один из вариантов массива а (n) (см. табл.9.1) и массив с (n) (см. табл.9.2) массив d (m, n) брать как m массивов с (n). Программа должна быть составлена для произвольного n. В ней следует предусмотреть ввод исходных данных и вывод результатов вычислений в виде таблицы.

1) Cформировать массив b (8) в котором элементы массива а (10) размещены в порядке убывания их величины, а наименьшее и наибольшие числа из массива а (10) отброшены

2) Cформировать массив b (10) в котором разместить элементы

3) Cформировать массив c (10) по условию .

4) Cформировать массив b (10) в котором разместить элементы массива а(10) в порядке возрастания величин . Массив а (10) сохранить.

5) Cформировать массив g (10) в котором разместить элементы в порядке убывания модулей q _i.

6) Cформировать массивы X ₁ и Y ₁, в которых разместить нечетные и четные элементы массива а (10). Считая X ₁ и Y ₁ координатами точек на плоскости, переставить элементы с одинаковыми индексами i в таком порядке, чтобы ломаная линия, соединяющая последовательно точки 1-2-…k, имела наименьшую длину, для чего в качестве последующей точки надо выбирать ближайшую к предыдущей. Если исходный массив содержит нечетное количество элементов, дополнить его одним нулевым элементом.

7) Составить программу, вычисляющую математическое ожидание M [ X ] случайной дискретной величины Х заданной в виде массива размерности n, которая задается при запуске программы. Массив сгенерирован с помощью датчика случайных чисел. Для тестирования программы применить массив а (10) из табл.9.1.

8) Дан массив а (10) найти элементы массива, которые повторяются в массиве два и три раза, и вывести их порядковые номера.

9) Даны два массива а (10) и с (10) из них получить массив b (n) путем соединения массивов а (10) и с (10) так чтобы не было повторяющихся элементов. Получившийся массив упорядочить по возрастанию.

10) Даны два массива а (10) и с (10) из них получить массив b (n) в котором будут присутствовать элементы входящие как в а (10) так и в с (10). Получившийся массив упорядочить по возрастанию.

11) Из массива а (10) выбрать все элементы, принадлежащие интервалу (d ₁; d ₂) а их порядковые номера поместить в массив с (n) упорядочив по убыванию.

12) Даны массивы а (10) и b (10). Найти массив с (10) элементы которого вычислены, как и упорядочены по возрастанию.

13) Даны массивы а (10) и b (10) найти массив с (10) элементы которого вычислены, как и упорядочены по убыванию.

14) Дан массив а (10) найти массив с (10) элементы которого вычислены, как и упорядочены по убыванию.

15) Дан массив а (10) найти массив с (10) элементы которого вычислены, как и упорядочены по возрастанию.

16) Даны массивы а (10) и b (10) упорядочить их по возрастанию. Найти массив с (10) элементы которого вычислены, как и упорядочены по убыванию.

17) Дан двумерный массив d (2,10). Упорядочить по возрастанию первую строку, элементы второй строки вычислить так

18) Дан массив d (7,7). Упорядочить диагонали по возрастанию и поменять местами

19) Дан массив d (7,7). Упорядочить главную диагональ по возрастанию. Вторую строку массива и упорядоченную диагональ поменять местами.

20) Дан массив d (7,7). Найти на главной диагонали максимальный элемент d _max, элементы второго столбца заменить на новые, вычисленные как .

Табл.9.1

Табл.9.2

СПИСОК ЛИТЕРАТУРЫ

1. Маликов А.И. Лабораторный практикум по информатике. I. – Казань: КГТУ им. А.Н.Туполева, 1998. – 87 с.

2. Информатика. Базовый курс. Учебник для ВУЗов. Под ред. Симоновича С.В. Санкт-Петербург: Питер, 2000. – 640 с.

3. Савельев А. Я.. Основы информатики: Учеб. для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. – 328 с

4. Бобровский С.И. Delphi 7. Учебный курс. СПб.: Питер, 2003. 736 с.

5. Епанешников А.М., Епанешников В.А. Программирование в среде DELPHI 2.0: Учебное пособие в 4 частях. Ч.2. Язык Object Pascal 9.0. – М.: ДИАЛОГ-МИФИ, 1997. 319 с.

6. Боглаев Ю.П. Вычислительная математика и программирование. Учеб. пособие для студентов втузов. – М.:Высш.шк., 1990. – 544 с.

7. Демидович Б.П. Марон И.А. Основы вычислительной математики. – М.: Гос. изд. физ-мат лит., 1963. – 660 с.

8. Гук М. Дисковая подсистема персонального компьютера. – СПб.: Питер, 2001. – 336 с.

9. Программирование на языке Паскаль: задачник /Под ред. Усковой О.Ф. СПб: Питер, 2003. – 336 с.

10. Единая система программной документации: ГОСТ 19.002-80 Схемы алгоритмов и программ. Правила выполнения (Заменен на ГОСТ 19.701-90 (ИСО 5807-85)); ГОСТ 19.003-80 Схемы алгоритмов и программ. Обозначения условные графические (Заменен на ГОСТ 19.701-90 (ИСО 5807-85)); ГОСТ 19.004-80 Термины и определения (Заменен на ГОСТ 19.781-90); ГОСТ 19.401-78 Текст программы. Требования к содержанию и оформлению; ГОСТ 19.402-78 Описание программы; ГОСТ 19.404-79 Пояснительная записка. Требования к содержанию и оформлению.

Приложение 1. Варианты контрольных заданий

1). Массив a (n) n < 25 пронормировать, чтобы , т.е. разделить каждое а_i на сумму квадратов всех элементов массива.

2). Дан массив d(n) n < 20. Указать (напечатать) номера положительных элементов, после которых следуют отрицательные.

3). В массиве а (50) произвести перестановку, сгруппировав в начале массива все положительные числа. Вывести на печать только положительные числа по 5 штук в строке.

4). Из массива а (100) в массив b (100) переписать элементы, модуль которых меньше среднего значения всех элементов массива а. Вместо остальных элементов в массив b записать нули. Массив b вывести на печать по 10 чисел в строку.

5). В массиве dd (200) указать номер элемента (со 2 по 199), сумма которого с предыдущим и последующим имеет максимальное значение.

6). Из массива d (100) в массив dd (20) записать средние значения 5 последовательных элементов массива d. Вывести на печать dd по 4 элемента в строку.

7). Из массива JJ (100) в массив NN (100) перенести числа (элементы массива) сначала нечетные, а затем четные. Вывести массив NN на печать по 10 элементов в строке.

8). Дан массив d (20,4). Сформировать массив c (4,4) в каждую строку которого записана сумма 5 строк из d. Вывести с на печать в виде матрицы 4´4.

9). Из массива z (20,20) в массив d (20) переписать наибольшие по модулю элементы каждого столбца z. Результат вывести на печать.

10). Вычислить вектор b =(b_i), i = 1,..., n, n < 10, по заданной матрице z =(z_ij), i, j = 1,..., n и заданному х:

i = 1,…, n

11). Массив d (60) разделить на три отдельных массива по принципу

d₁ = (d₁, d₄, d₇,...)

d₂ = (d₂, d₅, d₈,...)

d₃ = (d₃, d₆, d₉,...)

Вывести d₁, d₂, d₃ в три столба

d₁ d₂ d₃

12). Найти максимальные элементы матрицы d (n, n), n < 20 среди элементов, расположенных выше диагонали.

13). Вычислить суммы всех элементов массива f (n, n), n < 50, расположенных выше и ниже его главной диагонали.

14). Вычислить значение функции z по заданному массиву q (n, n), n < 15 и массиву x (n), .

15). Вычислить значение функции y по заданному х и матрице d =(d_ij) i,j =1,…, n, n < 10,

.

16). Вычислить величину х ₁ х_n + х ₂ х_{n -1}+…+ x_nx ₁, где х_i – максимальный элемент i ‑ой строки матрицы a =(a_ij), i, j =1,…, n, n < 30.

17). Вычислить величину х ₁ х_n + х ₂ х_{n -1}+…+ x_nx ₁, где х_i – минимальный элемент j- ого столбца матрицы b = (b_ij), i, j =1,…, n, n < 30.

18). Вычислить значение f по заданным массивам c (n, n), d (n, n) и заданным х и y

19). Для матрицы g (10, 10) найти сумму отрицательных элементов главной диагонали и их количество.

20). Из массива а (50, 50) в массив d (2500) переписать все элементы массива а, модуль которых меньше 1. Результат вывести на печать.

21). Из массива q сформировать массив d (20, 20) в котором на главной диагонали расположить элементы массива в порядке возрастания, а остальные элементы обнулить.

22). Для массива d (20, 20) найти и вывести на печать номера всех элементов, равных 0, 1 и –10.

23). Определить и вывести на печать все номера элементов, максимальных в каждой из столбцов матрицы q (25, 25).

24). Из массива d (100) в массив t (20) записать средние значения 5 последовательных элементов массива d. Результат вывести на печать.

25). По заданному массиву r (10, 10) сформировать массив s (45), в котором разместить элементы массива r, расположенные под главной диагональю (по строкам).

26). В массиве d (200) указать номер элемента (со 2 по 199), сумма которого с предыдущим и последующим имеет минимальное значение.

27). Для матрицы z (10, 10) найти максимальный элемент на главной диагонали и определить сумму 9-ти элементов с ним в центре.

28). Из массива J (100) в массив N (100) перенести числа (элементы массива) сначала нечетные, а затем четные. Результат вывести на печать.

29). В массиве s (100, 100) поменять местами минимальный и максимальный элементы и вывести их номера на печать.

30). Из массива d (100) в массив g (100) переписать положительные элементы, в массив q —отрицательные элементы, и определить количество нулевых элементов. Результат вывести на печать.

31). Для массива g (10, 10) найти сумму всех положительных, сумму всех отрицательных элементов и определить количество нулей. Результат вывести на печать.

32). По заданному массиву q (10, 10) сформировать одномерный массив s (100), в котором расположить элементы q_ij в порядке возрастания.

33). Вычисление f (m, n) = n! m!/(n + m)!, где n и m —неотрицательные целые числа, с определением и без определения функции, вычисляющей факториал. Сравнить получаемые результаты и определить какая программа позволяет получить результат для больших m и n.

34). Сформировать массив z =(z_i)

,

где , x_i, y_i, z_i – элементы массивов x,y,z размерности n < 20.

35). Найти тройки чисел из множества, заданного массивами x, y, z размерности n < 10, для которой площадь треугольника со сторонами, определяемыми этой тройкой, будет минимальна.

36). Вычислить элементы массива A (n), n < 10 по членам разложения функции e^x в ряд Маклорена e^x =1+ x + x ²/2!+ x ³/3!+...+ xⁿ / n!.

37). Вычислить элементы массива d [ i, j ], i, j =1,…, n, по заданному вектору x =(x_i), i=1,…, n, n < 20 и членам разложения функции sin (x_i) в ряд Маклорена sin (x_i)= x_i — x_i ³/3!+ x_i ⁵/5!– x_i ⁷/7!+ x_i ⁹/9!...:

d_{i 1} = x_i, d_{i 2} = x_i ³/3!;...

38). По заданной дате (день и месяц года) вывести на печать название соответствующего знака Зодиака:

39). Для заданного списка студентов группы, включающего фамилию, номер группы и год рождения, определить средний возраст студентов на данный момент.

40) Вычислить матрицу F = (BCB^т –A^тC), где A- n ´ n, B- n ´ n, C- n ´ n - заданные матрицы.

41). Сформировать одномерный массив. Удалить из него элемент с заданным номером, добавить элемент с заданным номером;

42). Сформировать одномерный массив. Удалить из него элемент с заданным ключом, добавить элемент с заданным ключом;

43). Сформировать одномерный массив. Удалить из него К элементов, начиная с заданного номера, добавить элемент с заданным ключом;

44). Сформировать одномерный массив. Удалить из него элемент с заданным номером, добавить К элементов, начиная с заданного номера;

45). Сформировать одномерный массив. Удалить из него К элементов, начиная с заданного номера, добавить К элементов, начиная с заданного номера.

46). Сформировать двумерный массив. Удалить из него строку с заданным номером;

47). Сформировать двумерный массив. Удалить из него столбец с заданным номером;

48). Сформировать двумерный массив. Добавить в него строку с заданным номером;

49). Сформировать двумерный массив. Добавить в него столбец с заданным номером;

50). Сформировать двумерный массив. Удалить из него строку и столбец с заданным номером.

51). Сформировать двумерный массив. Добавить в него строку и столбец с заданным номером.

52). Сформировать двумерный массив. Удалить из него все строки, в которых встречается заданное число.

53). Сформировать двумерный массив. Удалить из него все столбцы, в которых встречается заданное число.

54). Сформировать двумерный массив. Удалить из него строку и столбец, на пересечении которых находится минимальный элемент.

55). Сформировать двумерный массив. Удалить из него строку и столбец, на пересечении которых находится максимальный элемент.

56). Сформировать массив строк. Удалить из него самую короткую строку.

57). Сформировать массив строк. Удалить из него самую длинную строку.

58). Сформировать массив строк. Удалить из него строку, начинающуюся на букву "а".

59). Сформировать массив строк. Удалить из него строку, начинающуюся и заканчивающуюся на букву "а".

60). Сформировать массив строк. Удалить из него строку, начинающуюся и заканчивающуюся на одну и ту же букву.

61). Сформировать массив строк. Удалить из него строку с заданным номером.

62). Сформировать массив строк. Удалить из него k строк, начиная со строки с заданным номером.

63). Сформировать массив строк. Удалить из него одинаковые строки.

64). Сформировать массив строк. Удалить из него k последних строк.

65). Сформировать массив строк. Удалить из него k первых строк.

66). Сформировать массив строк. Добавить в него строку с заданным номером.

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: