Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Цель работы: Разработка программ для работы с элементами массивов

Теоретические основы:

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

Пусть дан одномерный неупорядоченный массив, содержащий целые числа М={mi}, i=1,n; n - число элементов. Необходимо упорядочить элементы этого массива по возрастанию их значений.

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

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

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

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

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

Поскольку мы пока не знакомы с работой с файлами в ТР, рассмотрим алгоритм сортировки слиянием на примере слияния двух предварительно упорядоченных массивов Х и Y в один массив Z. Данные в массивах расположены в порядке возрастания их значений.

Обозначим через переменные dx, dy - длину (размер) массивов X, Y соответственно. Переменные ix, iy - счетчики (адреса) тех же массивов. Переменная iz - счетчик числа элементов нового массива Z. Тескт программы расмотрен в типовых примерах ниже.

 

Типовые примеры:

 

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

 

       Uses crt;

       Var

                   M:array[1..1000] of integer;

                   n, i, j, Min, i_min:integer;

       Begin

                   Clrscr;

                   Write(' Введите длину массива n = ');

                   Readln(n);

{ Вместо ввода с клавиатуры заполним массив случайными числами из диапазона от 0 до 500}

                   For i:=1 to n do M[i]:=Random(500);

                   For i:=1 to n-1 do

                   Begin

                   {принимаем за минимум i-й элемент}

                   Min:=M[i]; i_min:=i;

                              For j:=i+1 to n do

                                          If M[j]<Min then

                                                      Begin

                              {найдено меньшее число - запоминаем его и его адрес}

                                                                  Min:=M[j]; i_min:=j;

                                                      End;

                              {Обмен}

                              M[i_min]:=M[i];

                              M[i]:=Min;

                   End;

Writeln(' Упорядоченный массив');

For i:=1 to n do write(M[i],' ');

readkey;

   End.

Текст программы обменной сортировки

 

       Uses crt;

Var M:array[1..1000] of integer;

       i,Z,n:integer; Key:byte;

Begin Clrscr;

{Ввод n и формирование массива М как в предыдущей программе}

       Repeat

                   Key:=0;

              For i:=1 to n-1 do

                   If M[i] > M[i+1] then

                                          begin

                                                      Z:=M[i];

                                                      M[i]:=M[i+1];

                                                      M[i+1]:=Z;

                                                      Key:=1;

                                          end;

       Until Key=0;

Writeln(' Упорядоченный массив');

For i:=1 to n do write(M[i],' '); readkey;

     End.

Текст программы сортировки слиянием

       Uses crt;

       Var { Описание массивов и переменных}

X, Y: array[1..1000] of integer;

                   Z: array[1..2000] of integer;

                   dx,dy,ix,iy,iz,i:integer;

Begin Clrscr;         { Ввод данных}

Write(' Введите длину массива Х '); readln(dx);

Writeln(' Введите упорядоченный по возрастанию массив Х');

 For i:=1 to dx do read(X[i]); readln;

Write(' Введите длину массива Y '); readln(dy);

Writeln(' Введите упорядоченный по возрастанию массив Y');

For i:=1 to dy do read(Y[i]); readln;

ix:=1; iy:=1; iz:=0;

While (ix<=dx) and (iy<=dy) do

       if X[ix]<Y[iy] then

                              begin {Перезапись значения из массива Х в массив Z}

                                          inc(iz); Z[iz]:=X[ix]; inc(ix);

                              end

       else

                              begin {Перзапись значения из массива Y в массив Z}

                                          inc(iz); Z[iz]:=Y[iy]; inc(iy);

                              end;

       { Один из массивов полностью переписан }

       if ix>dx then { Переписан массив Х, дописываем все оставшееся из Y}

                   for i:=iy to dy do

                              begin

                                          inc(iz); Z[iz]:=Y[i];

                              end

       else { Переписан массив Y, дописываем все оставшееся из X }

                   for i:=ix to dx do

                              begin

                                          inc(iz); Z[iz]:=X[i];                           

                              end;

{ Вывод результата слияния на экран}

writeln(' Полученный массив Z');

for i:=1 to iz do write(Z[i],' '); readln;

End.

Варианты самостоятельных заданий

Задание №1

1. Дана матрица размера M × N и целые числа K1 и K2 (1 ≤ K1 < K2 ≤ M). Поменять местами строки матрицы с номерами K1 и K2

2. Дана матрица размера M × N и целые числа K1 и K2 (1 ≤ K1 < K2 ≤ N). Поменять местами столбцы матрицы с номерами K1 и K2

3. Дана матрица размера M × N. Преобразовать матрицу, поменяв местами минимальный и максимальный элемент в каждой строке.

4. Дана матрица размера M × N. Преобразовать матрицу, поменяв местами минимальный и максимальный элемент в каждом столбце.

5. Дана матрица размера M × N. Поменять местами строки, содержащие минимальный и максимальный элементы матрицы.

6. Дана матрица размера M × N. Поменять местами столбцы, содержащие минимальный и максимальный элементы матрицы.

7. Дана матрица размера M × N. Поменять местами столбец с номером 1 и последний из столбцов, содержащих только положительные элементы. Если требуемых столбцов нет, то вывести матрицу без изменений.

8. Дана матрица размера M × N. Поменять местами столбец с номером N и первый из столбцов, содержащих только отрицательные элементы. Если требуемых столбцов нет, то вывести матрицу без изменений.

9. Дана матрица размера M × N (M — четное число). Поменять местами верхнюю и нижнюю половины матрицы.

10. Дана матрица размера M × N (N — четное число). Поменять местами левую и правую половины матрицы.

11. Дана матрица размера M × N (M и N — четные числа). Поменять местами левую верхнюю и правую нижнюю четверти матрицы

12. Дана матрица размера M × N (M и N — четные числа). Поменять местами левую нижнюю и правую верхнюю четверти матрицы.

13. Дана матрица размера M × N. Зеркально отразить ее элементы относительно горизонтальной оси симметрии матрицы (при этом поменяются местами строки с номерами 1 и M, 2 и M − 1 и т. д.).

14. Дана матрица размера M × N. Зеркально отразить ее элементы относительно вертикальной оси симметрии матрицы (при этом поменяются местами столбцы с номерами 1 и N, 2 и N − 1 и т. д.).

15. Дана матрица размера M × N и целое число K (1 ≤ K ≤ M). Удалить строку матрицы с номером K.

16. Дана матрица размера M × N и целое число K (1 ≤ K ≤ N). Удалить столбец матрицы с номером K.

17. Дана матрица размера M × N. Удалить строку, содержащую минимальный элемент матрицы.

18. Дана матрица размера M × N. Удалить столбец, содержащий максимальный элемент матрицы.

19. Дана матрица размера M × N. Удалить ее первый столбец, содержащий только положительные элементы. Если требуемых столбцов нет, то вывести матрицу без изменений.

20. Дана матрица размера M × N. Удалить ее последний столбец, содержащий только отрицательные элементы. Если требуемых столбцов нет, то вывести матрицу без изменений.

Задание №2

1. Дана матрица размера M × N. Перед первым столбцом, содержащим только положительные элементы, вставить столбец из единиц. Если требуемых столбцов нет, то вывести матрицу без изменений

2. Дана матрица размера M × N. После последнего столбца, содержащего только отрицательные элементы, вставить столбец из нулей. Если требуемых столбцов нет, то вывести матрицу без изменений.

3. Дана матрица размера M × N. Элемент матрицы называется ее локальным минимумом, если он меньше всех окружающих его элементов. Заменить все локальные минимумы данной матрицы на нули. При решении допускается использовать вспомогательную матрицу.

4. Дана матрица размера M × N. Элемент матрицы называется ее локальным максимумом, если он больше всех окружающих его элементов. Поменять знак всех локальных максимумов данной матрицы на противоположный. При решении допускается использовать вспомогательную матрицу.

5. Дана матрица размера M × N. Упорядочить ее строки так, чтобы их первые элементы образовывали возрастающую последовательность.

6. Дана матрица размера M × N. Упорядочить ее столбцы так, чтобы их последние элементы образовывали убывающую последовательность.

7. Дана матрица размера M × N. Упорядочить ее строки так, чтобы их минимальные элементы образовывали убывающую последовательность.

8. Дана матрица размера M × N. Упорядочить ее столбцы так, чтобы их максимальные элементы образовывали возрастающую последовательность Диагонали квадратной матрицы

9. Дана квадратная матрица A порядка M. Найти сумму элементов ее главной диагонали, то есть диагонали, содержащей следующие элементы: A1,1, A2,2, A3,3, . . ., AM,M.

10. Дана квадратная матрица A порядка M. Найти среднее арифметическое элементов ее побочной диагонали, то есть диагонали, содержащей следующие элементы: A1,M, A2,M−1, A3,M−2, . . ., AM,1

11. Дана квадратная матрица A порядка M. Найти сумму элементов каждой ее диагонали, параллельной главной (начиная с одноэлементной диагонали A1,M).

12. Дана квадратная матрица A порядка M. Найти сумму элементов каждой ее диагонали, параллельной побочной (начиная с одноэлементной диагонали A1,1).

13. Дана квадратная матрица A порядка M. Найти среднее арифметическое элементов каждой ее диагонали, параллельной главной (начиная с одноэлементной диагонали A1,M).

14. Дана квадратная матрица A порядка M. Найти среднее арифметическое элементов каждой ее диагонали, параллельной побочной (начиная с одноэлементной диагонали A1,1).

15. . Дана квадратная матрица A порядка M. Найти минимальный элемент для каждой ее диагонали, параллельной главной (начиная с одноэлементной диагонали A1,M).

16. Дана квадратная матрица A порядка M. Найти максимальный элемент для каждой ее диагонали, параллельной побочной (начиная с одноэлементной диагонали A1,1).

17. Дана квадратная матрица порядка M. Обнулить элементы матрицы, лежащие ниже главной диагонали. Условный оператор не использовать.

18. Дана квадратная матрица порядка M. Обнулить элементы матрицы, лежащие выше побочной диагонали. Условный оператор не использовать

19. Дана квадратная матрица порядка M. Обнулить элементы матрицы, лежащие на побочной диагонали и ниже нее. Условный оператор не использовать.

20. Дана квадратная матрица порядка M. Обнулить элементы матрицы, лежащие на главной диагонали и выше нее. Условный оператор не использовать.

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

1. Элементы какого типа может содержать массив?

2. Какие типы данных допустимы для индексов элементов массива?

3. Опишите порядок действий при вычислении суммы элементов массива

4. Опишите порядок действий при определении максимального элемента в массиве.