Линейная сортировка (сортировка отбором)

5 6 7 8 9 10 11

Const

count=20; {число элементов массива}

Type

Vector = array[1..count] of integer;

Var

a: vector = (9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5);

i,j,M:integer;

Begin

for i:=1 to count-1 do

{Сравниваем поочередно первый элемент неотсортированой}

{части массива со всеми остальными до конца }

for j:=i+1 to count do

if a[i]<a[j] then {меняем местами элементы}

begin

M:=a[i];

a[i]:=a[j];

a[j]:=M;

end;

For i:=1 to count do

Writeln(a[i]);

end;

Идея линейной сортировки по невозрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наибольший элемент и поменять его местами с первым элементом. Затем просматриваются элементы, начиная со второго, снова находится наибольший, который, в свою очередь, меняется местами со вторым и так далее. Этот метод требует меньшего числа перестановок, чем «пузырек», но количество итераций (повторений цикла) у обоих методов одинаково.

УМНОЖЕНИЕ МАТРИЦЫ НА ВЕКТОР:

For i:=1 to n do {цикл по строкам – элементам будущего }

Begin

s:=0;

For j:=1 to m do

s:=s+a[i,j]*x[j];

y[i]:=s; {находим компоненты вектора ()}.

End;

ПЕРЕДАЧА В ПРОЦЕДУРУ МАССИВОВ ПЕРЕМЕННЫХ РАЗМЕРОВ:

Речь идет об использовании массивов как параметров подпрограмм. Чтобы снять ограничения размерности для параметров – одномерных массивов, можно использовать открытые массивы. Открытые массивы – это конструкция описания типа массива без указания типа индексов, например: array of real; array of integer. Такое определение массива возможно только при описании формальных параметров подпрограммы.

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

Var

a: array[1..5] of integer;

b: array[0..2] of integer;

i: integer;

procedure print1(a:array of integer; n:integer);

{способ 1 – задаем кол-во элементов в качестве параметров}

var k:integer;

begin

for k:=0 to n-1 do Writeln(a[k]);

end;

procedure print2(a:array of integer);

{Способ 2 – используем функцию high}

{эта функция для обычного массива возвращает верхнюю границу}

{индекса массива, для открытого – максимальное значение индекса}

var k:integer;

begin

for k:=0 to high(a) do Writeln(a[k]);

end;

begin

for i:=1 to 5 do a[i]:=random(10);

for i:=0 to 2 do b[i]:=random(50);

{Программа выводит массивы разных размеров}

print1(a,5);

print1(b,3);

print2(a);

print2(b);

end.

ЗАДАЧИ.

Одномерные массивы:

Подсчитать количество элементов одномерного массива, кратных трем. Размерность массива задается с клавиатуры. Значения элементов генерируются случайно.
Задан одномерный массив, состоящий из одних цифр. Посчитать сумму четных и нечетных значений элементов массива. Число элементов и их значения вводятся с клавиатуры (с проверкой).
!Заданы натуральное число и последовательность вещественных чисел . Сформировать одномерный массив такой, что ; . Отсортировать массив по возрастанию. Значение задать с клавиатуры, последовательность чисел определить случайным образом.
! Дан одномерный массив положительных целых чисел. Последовательно преобразовать этот массив по следующему алгоритму: Находится первый максимальный элемент и устанавливается первым в массиве, затем из оставшихся находится минимальный элемент и устанавливается вторым в массиве, после чего отыскивается из оставшихся элементов максимальный и устанавливается третьим в массиве и т.д. Размерность массива задается с клавиатуры.
Составить программу для выполнения заданных действий над одномерным массивом – вектором из элементов:

5.1. Выполнить нормировку вектора по максимальному элементу

5.2. Определить количество элементов вектора, значения которых больше среднего арифметического всех его элементов.

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

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

5.5. Переставить местами первый и максимальный элемент, последний и минимальный элемент.

5.6 В заданном векторе найти его оригинальные (неповторяющиеся) элементы и сформировать из них вектор .

5.7.! В заданном векторе поменять местами первый элемент с последним, второй – с предпоследним и т.д.

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

5.9.! В заданном векторе найти его максимальный и минимальный элементы. Выполнить сортировку элементов вектора, стоящих между минимальным и максимальным элементами: по возрастанию, если минимальный элемент стоит в векторе левее максимального; по убыванию, если максимальный элемент стоит левее минимального.

5.10.! Задать 2 одномерных массива и из и элементов соответственно. Сформировать вектор , включив в него элементы, присутствующие в и одновременно. Вектор не должен содержать одинаковых элементов.

5.11.! Задать 2 одномерных упорядоченных массива и из и элементов соответственно. Необходимо «слить» их в один вектор , не нарушив при этом упорядоченности.

Даны m векторов x₁=(x₁₁, x₂₁, x₃₁),. .., x_m=(x_1m, x_2m, x_3m). Написать программу нахождения суммы этих векторов.
Даны векторы а=(a₁, a₂, a₃) и b=(b₁, b₂, b₃). Написать программу вычисления скалярного и векторного произведений этих векторов.
!Даны три вектора а=(a₁, a₂, a₃), b=(b₁, b₂, b₃) и c=(c₁, c₂, c₃). Написать программу вычисления смешанного произведения этих векторов.
Даны два вектора а=(a₁, a₂, a₃) и b=(b₁, b₂, b₃). Написать программу, которая находит угол между этими векторами.
! Даны векторы а=(a₁, a₂, a₃), b=(b₁, b₂, b₃), c=(c₁, c₂, c₃) и d=(d₁, d₂, d₃). Написать программу, вычисляющую скалярное произведение (ахb)*(cxd).
Даны две точки в n -мерном пространстве X=(х₁, х₂,..., х_n), Y=(y₁, y₂,...,y_n). Написать программу нахождения расстояния между этими точками и вектора XY.
Дан n -мерный вектор х=(х₁, х₂,...,х_n). Написать программу, которая может находить вектор y=(x_n, x_n-1, x_n-2,..., x₂, x₁) и скалярное произведение x*y.

Двумерные массивы:

Задана вещественная матрица размерности , все элементы которой задаются случайно. В каждой строке выбрать минимальный элемент, затем среди этих чисел выбрать максимальное. Размерность матрицы вводится с клавиатуры.
Вычислить сумму двух одинаковых матриц произвольного размера (с проверкой размеров). Размерность задается с клавиатуры. Значения элементов генерируются случайно.
Вычислить произведение двух матриц произвольного размера (с проверкой размеров). Размерность задается с клавиатуры. Значения элементов генерируются случайно.
На плоскости заданы N точек, координаты которых записаны в двумерном массиве. Составить программу, которая определяет порядок соединения точек непересекающейся незамкнутой ломаной. Размерность массива задается с клавиатуры. Значения элементов генерируются случайно. Сортировка -координаты по возрастанию.
Задан двумерный массив вещественных чисел. Заменить все отрицательные элементы нулями и подсчитать сумму положительных элементов в каждом столбце. Размерность массива ввести с клавиатуры, элементы массива определить случайным образом.
Дан двумерный массив чисел. Составить программу подсчета количества нулей в четных строках и количества единиц в нечетных. Размерность массива задается с клавиатуры. Значения элементов генерируются случайно.
Задан двумерный массив размерности . Сформировать массив , в который записать суммы элементов строк и массив , в который записать суммы элементов столбцов исходного массива . и ввести с клавиатуры, элементы массива определить случайным образом.
Составить программу выполнения заданных действий над двумерным массивом вещественных чисел – матрицей . Предусмотреть любой удобный способ заполнения массива , вывод исходной и, при необходимости, преобразованной матриц:

8.1. Вычислить сумму и число положительных элементов каждого столбца. Вывести результаты в виде 2 строк.

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

8.3. Найти наибольший и наименьший элементы и поменять их местами.

8.4.! Найти наибольший и наименьший элементы и поменять местами строки, содержащие их.

8.5. Найти строку с наибольшей и наименьшей суммой элементов. Вывести найденные строки и суммы.

8.6.! Выполнить циклическую перестановку столбцов, при которой -ый столбец становится на место -го, а последний столбец становится первым.

8.7. Упорядочить по возрастанию элементы каждой строки.

8.8.! Выполнить сортировку нечетных строк по возрастанию, четных – по убыванию.

8.9.! Проверить, образуют ли элементы матрицы «магический квадрат» (т.е. суммы чисел по всем вертикалям, всем горизонталям и двум диагоналям одинаковы).

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

Дана матрица А(nxn) и вектор а = (a₁, a₂,..., a_n). Написать программу вычисления вектора b = A*a.
Дана матрица А(nxn). Построить n -мерный вектор по правилу: если в строке матрицы с номером i есть отрицательные элементы, то b_i = 0, в противном случае b_i = 1.
Дана матрица А(nxn). Написать программу вычисления матрицы Аk, где k>0 - целое число.
Даны два вектора b = (b₁, b₂,..., b_n), x = (x₁,x₂,..., x_n) и матрица А(nxn). Написать программу вычисления длины вектора Ах - b.
Даны две матрицы А(nxn) и B(nxn). Написать программу нахождения суммы диагональных элементов А*В.
Даны квадратные матрицы А(nxn), B(nxn), C(nxn). Написать программу вычисления матрицы (А+В)*С.
! Даны две матрицы А(nxn) и B(nxn), а также два вектора х = (x₁, x₂,..., x_n) и y = (y₁, y₂,..., y_n). Написать программу нахождения скалярного произведения (Ах)*(Ву).
! Дана матрица А(nxn) и вектор х = (х₁, х₂,...,х_n). Написать программу нахождения скалярного произведения (х*Ах).
! Дана матрица А(nxn). Написать программу вычисления max(S_k), где .
* Даны две матрицы А(nxn) и B(nxn). Написать программу нахождения матрицы, равной (А-В)^т.
! Задана целочисленная матрица . Из этой матрицы выбрать столбец, который обладает наибольшей суммой элементов. Если таких столбцов несколько, то выбрать первый из них. Далее в данном столбце определить наименьший и наибольший по значению элемент.
* Задана двумерная матрица целых чисел. Найти определитель матрицы. Массив заполнить случайным образом, размерность массива вводится с клавиатуры.
! Определить, является ли заданная целая квадратная матрица 10-го порядка симметричной (относительно главной диагонали).
* Задана двумерная матрица размерности . Необходимо, не используя дополнительный массив, транспонировать данную матрицу. Размерность матрицы вводится с клавиатуры, элементы матрицы определяются случайным образом.
! Заданы два одномерных массива и размерности соответственно и . Сформировать двумерный массив размерности , каждый элемент которого ; ; , и обнулить отрицательные элементы . Значения элементов определить случайным образом. и ввести с клавиатуры.
! Дан одномерный массив, элементами которого являются числа 1, 2, 3. Составить программу, которая преобразует массив таким образом, чтобы в начале располагались одни единицы, затем тройки и двойки. Размерность массива задается с клавиатуры. Значения элементов генерируются случайно.
! Задана матрица размерности и размерности . Определить матрицу размерности , равную произведению матриц и .
! Создать массив размерности . Элементы массива определяются случайным образом. Записать в этот же массив все отрицательные числа, затем все положительные и нули, сохраняя порядок их следования. Значения и вводятся с клавиатуры.
!. Дана вещественная матрица размером , все элементы которой различны. Найти скалярное произведение строки, в которой находится наибольший элемент матрицы, на столбец с наименьшим элементом.
* Задана одномерная матрица вещественных чисел. Расположить в порядке возрастания сначала целые числа, затем действительные. Размерность массива вводится с клавиатуры.
* Сформировать из матрицы А матрицу В по следующим правилам:

· элементы матриц принимают только значения 0 или 1.

· соседями элемента А[i,j] являются все элементы, расположенные рядом с данным по горизонтали, вертикали и диагонали.

· если сумма значений соседей элемента А[i,j] меньше двух или больше трех, то значение B[i,j] = 0.

· если сумма значений соседей элемента А[i,j] равна трем, то значение B[i,j] = 1.

Вывести массив на экран, заменив 0 символом пробела, а 1 — символом звездочки (*).

* Создать динамический массив размерности . Элементы массива определяются случайным образом. Записать в этот же массив все отрицательные числа, затем все положительные и нули, отсортированные по возрастанию. Значения и вводятся с клавиатуры.
* Задан двумерный массив действительных чисел. Упорядочить массив в порядке возрастания элементов указываемой пользователем строки. Массив заполнить случайным образом, размерность массива и номер строки, по которой будет проводиться сортировка, вводится с клавиатуры.
* Задана квадратная матрица целых чисел. Определить, равны ли сумма первой строки и последнего столбца, сумма второй строки и предпоследнего столбца, и так далее. Массив заполнить случайным образом, размерность массива вводится с клавиатуры.
* Задана двумерная матрица целых чисел. При помощи элементарных операций над матрицей привести её к треугольному виду. Массив разместить в памяти динамически и заполнить случайным образом, размерность массива вводится с клавиатуры.
* Проверить, является ли заданная целая квадратная матрица 10-го порядка ортонормированной, т.е. такой, в которой скалярное произведение каждой пары различных строк равно 0, а скалярное произведение каждой строки на себя равно 1.
* По заданным коэффициентам и правым частям решить систему линейных уравнений , считая, что ее определитель отличен от нуля. (Решать методом Гаусса, предусматривающим приведение системы к «треугольному» виду).
В матрице А(nxn) найти максимальный и минимальный элементы. Указать их разность, а также строки и столбцы, на пересечении которых они находятся.
Дана матрица А(nxn). Написать программу нахождения минимального элемента из (max₁,...,max_n), где max_i - максимальный в i - той строке.