Тема. Перестановка элементов массива. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Тема. Перестановка элементов массива.



Рассмотрим задачу о перестановки двух столбцов (аналогично и для строк), так как многие задачи используют именно это действие.

Задача. Поменять местами столбцы с номерами m1 и m2.

Эту задачу можно реализовать несколькими способами. Мы составим две процедуры, причем процедура обмена столбцами содержит в себе процедуру обмена значениями двух переданных ей ячеек массива. Рассмотрите их.

Procedure Swap2(Var X: MyArray2; n, m, m1, m2: integer;);

Var

i, j: integer;

 

Procedure Swap1(Var elem1, elem2: integer);

Var

z: integer;

Begin

z:=elem1;

elem1:=elem2;

elem2:=z;

End;

 

Begin

if((m1<1) or (m1>m)) or ((m2<1) or (m2>m))

then

writeln('?')

else

for i:= 1 to m do

Swap1(X[i, m1], X[i, m2]);

End;

Вопрос. Какое сообщение должно быть выведено оператором writeln вместо знака вопроса и почему?

Задание. Выберите с учителем задачи из предложенного списка. Решите их, применяя подпрограммы, приготовьте для проверки 3-4 различных теста.

Задачи для самостоятельного решения

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

2. Поменять местами каждые две строки массива.

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

4. Если количество столбцов нечетно, то поменять первый и средний столбец, если четно, то средние два столбца поменять с первым и последним соответственно.

5. Поменять местами первую строку и строку, в которой находится первый нулевой элемент.

6. В двумерном массиве переставить строки следующим образом: первую с последней, вторую с предпоследней и так далее. Если строк нечетное количество, то средняя останется неизменной, иначе средние строки тоже меняем местами.

7. Дан двумерный массив. Расставить его столбцы следующим образом: последний, предпоследний,..., второй, первый.

8. Дан двумерный массив. Начиная с первой строки, сдвинуть все строки на две вниз, а последние две перенести на место первых двух строк.

9. Первые k столбцов сдвинуть назад, а последние k поставить на место первых.

10. Дан двумерный массив. Расставить его строки следующим образом: первая, последняя, вторая, предпоследняя, третья,....

11. Начиная с k-го столбца, сдвинуть их вперед, а первые k поставить на место последних.

Файл сохраните на дискете, листинг сдайте учителю для оценки.


 

Занятие V

Тема. Самостоятельное решение задач.

Выберите с учителем задачи из предложенного ниже списка.

I. Заполнение и анализ элементов массива

1. Заполнить квадратный двумерный массив таким образом, чтобы на главной диагонали были расположены числа от N до 1, под главной диагональю нули, а над главной диагональю по строкам числа в порядке возрастания от заданного. Используйте подпрограммы для решения каждой частной задачи.

2. Заполнить квадратный двумерный массив по следующему правилу: элементы главной диагонали равны 1, ниже главной диагонали – 0, а выше – сумме индексов. Используйте подпрограммы для решения каждой частной задачи.

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

4. Заполните двумерный массив с клавиатуры только числами кратными трем, предусмотрите защиту элементов этого массива от неправильного ввода и найдите сумму тех элементов массива, которые без остатка делятся на 9. Используйте подпрограммы для решения каждой частной задачи.

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

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

7. Заполняя двумерный массив с клавиатуры, предусмотрите замену вводимых отрицательных элементов на (-1), положительных на 1, нулевые оставить без изменения. Найдите число элементов, равных (-1), расположенных в четных строках. Используйте подпрограммы для решения каждой частной задачи.

8. Для данного двумерного массива найти среднее арифметическое наибольшего и наименьшего значений ее элементов и замените им все элементы заданной строки. Используйте подпрограммы для решения каждой частной задачи.

9. Определите, имеются ли в двумерном массиве строки, равные первой строке. Если есть, выведите их индексы на экран. Используйте подпрограммы для решения каждой частной задачи.

10. Для данного двумерного массива укажите индексы тех элементов, сумма которых равна заданному числу (если такие есть). Если таких элементов нет, вывести об этом сообщение. Используйте подпрограммы для решения каждой частной задачи.

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

II. Работа с одномерным и двумерным массивами

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

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

3. Вычислите сумму элементов, находящихся на пересечении текущей строки и двух диагоналей двумерного квадратного массива, и запишите их в одномерный массив. Найдите наибольший из этих элементов. (Элементами i-й строки, лежащими на диагоналях, являются ai,j и ai,n-j+1). Используйте подпрограммы для решения каждой частной задачи.

4. Дан двумерный массив. Заполнить одномерный массив суммами элементов строк, вывести полученную информацию на экран и номера строк, в которых сумма наименьшая. Используйте подпрограммы для решения каждой частной задачи.

5. Дан двумерный массив. Заполнить одномерный массив наименьшими значениями элементов строк, вывести полученную информацию на экран и номера строк, в которых значения наименьшие. Используйте подпрограммы для решения каждой частной задачи.

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

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

8. Для данного двумерного массива вычислите и запомните в другом двумерном массиве сумму и число положительных элементов каждой строки и расположенных не ниже главной диагонали заданного двумерного массива. Используйте подпрограммы для решения каждой частной задачи.

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

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

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

Дополнительные задачи (на усмотрение учителя)

1. Заполните одномерный массив произведениями элементов строк заданного двумерного массива и выведите его на экран. Найдите сумму этих произведений. Используйте подпрограммы для решения каждой частной задачи.

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

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

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

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

6. Дан двумерный квадратный массив. Найти номера строк, все элементы которых четны. Используйте подпрограммы для решения каждой частной задачи.

7. Сколько в произвольном двумерном массиве содержится различных элементов? Занесите их в одномерный массив и выведите на экран. Используйте подпрограммы для решения каждой частной задачи.

8. Дан двумерный массив. Найти наибольший и наименьший элементы массива и,чередуя, заполнить ими одномерный массив заданной размерности. Используйте подпрограммы для решения каждой частной задачи.

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

10. Дан двумерный квадратный массив. В каждой строке двумерного массива наибольший элемент поместить на место первого элемента массива, а наименьший элементы – на место последнего. Создать одномерный массив, элементы которого являются суммой этих элементов. Вывести на экран полученный массив и сумму его элементов. Используйте подпрограммы для решения каждой частной задачи.

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

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

13. Дан двумерный массив. Найти наибольшее из значений элементов первой и последней строки. Используйте подпрограммы для решения каждой частной задачи.

14. Дан двумерный массив. Найдите сумму наибольших значений элементов его строк. Используйте подпрограммы для решения каждой частной задачи.

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

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

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

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

19. Дан двумерный массив. Найдите сумму минимальных элементов диагоналей массива. Используйте подпрограммы для решения каждой частной задачи.

20. Дан двумерный массив. Преобразовать его по следующему правилу: строку с номером N сделать столбцом с номером N, а столбец – строкой.

21. Дан двумерный массив. Найти наибольшее из значений элементов, расположенных в заштрихованной части (a).

22. Дан двумерный массив. Найти наибольшее из значений элементов, расположенных в заштрихованной части (b).

23. Дан двумерный массив. Найти наибольшее из значений элементов, расположенных в заштрихованной части (c).

24. Дан двумерный массив. Найти наибольшее из значений элементов, расположенных в заштрихованной части (d).

25. Дан двумерный массив. Найти наибольшее из значений элементов, расположенных в заштрихованной части (e).

26. Дан двумерный массив. Найти наибольшее из значений элементов, расположенных в заштрихованной части (f).

27. Дан двумерный массив. Найти наибольшее из значений элементов, расположенных в заштрихованной части (g).

28. Дан двумерный массив. Найти наибольшее из значений элементов, расположенных в заштрихованной части (k).

29*. "Магическим" квадратом называется квадратная таблица целых чисел от 1 до N, расположенных так, что суммы элементов каждой строки, каждого столбца и обеих диагоналей одинаковы и равны (1/2)*N*(1+N)2.

Построить "магический" квадрат для N=3, N=4, N=5.

30*. Построить и вывести на экран "латинский" квадрат - таблицу, состоящую из n различных чисел, всех по n раз расположенных так, что в каждой строке и столбце каждое число встречается только один раз.


 

Сортировка

 

Занятие I

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

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

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

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

"Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею! Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования." /Д. Кнут/

"Создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки." /Н. Вирт/

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

Сегодня существует множество методов сортировки, но для понимания сути сортировки рассмотрим некоторые из них.

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

Задача. Даны две целочисленные переменные х и y. Составить фрагмент программы, после выполнения которого значения этих переменных распределяются в порядке убывания.

Обмен значений переменных нужно производить лишь в том случае, если х<у. Для того чтобы не потерять начальное значение переменной х, введем дополнительную переменную t.

if x<y

then

begin

t:=x;

x:=y;

y:=t;

end;

Задача. Составить фрагмент программы поиска максимального числа из трех введенных с клавиатуры чисел.

Пусть а, b, c – вводимые с клавиатуры числа, Max – максимальное из их значений. На первом шаге предположим, что а – максимальное из чисел и поэтому Max:=a. Затем сравним значение предполагаемого максимума со значениями переменных b и с. Если значение m окажется меньше, чем значение очередной переменной, то переопределим значение максимума.

...

m:=a;

if m<b

then

m:=b;

if m<c

then

m:=c;

...

Задача. Дан массив а, состоящий из 10 элементов. Составить программу поиска максимального элемента массива.

Используем идею предыдущей задачи. Перед началом поиска выберем условно в качестве максимального первый элемент массива Max:=a[1]. Затем по очереди каждый элемент массива сравним со значением переменной m. Если он окажется больше, то изменим значение Max. После анализа всех элементов массива переменная Max содержит значение максимального элемента массива.

...

Max:=a[1];

for i:= 2 to 10 do

if Max<a[i]

then

Max:= a[i];

...

До написания программ Вам необходимо выполнить некоторую подготовительную работу – написать шаблон программы следующего содержания:

Рrogram Sorting;

Сonst

n =...; {количество элементов в массиве}

Type

TArray = array [1..n] of integer;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Procedure FillArray (Var a: TArray);

Var

i: integer;

Begin

for i: = 1 to n do

a [i]:= Random(100);

End; {конец процедуры}

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Procedure PrintArray (a: TArray);

Var

i: integer;

Begin

for i: = 1 to n do

write (a [i]: 3, ' ');

writeln;

End;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Begin {Главная программа}

writeln('Сортировка МЕТОДОМ...');

writeln('Заполняем исходный массив: ');

FillArray (a);

PrintArray (a);

AnySort (a, b);{имя процедуры, реализующей данный метод}

writeln('Отсортированный массив: ');

PrintArray (b);

End.

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

1. Функция, которая ищет минимальный элемент правее некоторого заданного и возвращает его номер в качестве результата. Аргументами функции являются номер элемента массива и обрабатываемый массив:

2. Большинство методов сортировок основаны на обмене двух чисел. Для этой цели предназначена процедура, которая в качестве параметров берет два числа и меняет их значения

3. Также Вам пригодится процедура, которая берет элемент с индексом i, перемещает его на место элемента с номером j. А все элементы, которые имеют индексы от j до i-1 сдвигает на одну позицию вправо.

Задание. Подготовьте программу-шаблон, содержащую все рассмотренные выше процедуры и функции.


 

Занятие II

Тема. Сортировка вставкой. Сортировка выбором.

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

Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:

- количество присваиваний;

- количество сравнений.

Все методы сортировки можно разделить на две большие группы:

- прямые методы сортировки;

- улучшенные методы сортировки.

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

1) сортировка вставкой (включением);

2) сортировка выбором (выделением);

3) сортировка обменом (так называемая "пузырьковая" сортировка).

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

Рассмотрим сортировку методом вставки.

Принцип метода заключается в следующем:

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

Таким образом, алгоритм будет состоять из (n-1)-го прохода (n – размерность массива), каждый из которых будет включать четыре действия:

• взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной;

• поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;

• сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки;

• вставка взятого элемента в найденную i-ю позицию.

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

Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:

Procedure Vstavka(Var a: Array1);

Var

i, j,e,g:integer;

Begin

for i:=2 to c do

begin

e:=A[i];

j:=1;

while (e>a[j]) do

Inc(j);

for g:=i-1 downto j do

a[g+1]:=a[g];

a[j]:=e;

end;

End;

Задание. Составьте программу сортировки одномерного массива рассмотренным методом.

Сортировка выбором

Принцип метода:

Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.

Рассмотрите схему алгоритма прямого выбора.

Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:

Procedure Vibor(Var a: Array1);

Var

i, j, Min, MinI: integer;

Begin

for i:=1 to c do

begin

Min:=a[i];

MinI:=i;

for j:=i+1 to c do

if a[j]<Min

then

begin

Min:=a[j];

MinI:=j;

end;

a[MinI]:=a[i];

a[i]:=Min;

end;

End;

Задание. Составьте программу сортировки одномерного массива рассмотренным методом.


 

Занятие III

Тема. Сортировка методом простого обмена. Рекурсивная сортировка

Принцип метода:

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

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный (или минимальный) элемент ("всплыл" первый "пузырек"). Поскольку максимальный (или минимальный) элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до (n-1)-го элемента. И так далее. Всего требуется (n-1) проход.

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

Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:

Procedure Obmen(Var a: Array1);

Var

i,j,f,g:integer;

Begin

for i:=n downto 2 do

for j:=1 to i-1 do

if a[j]>a[j+1]

then

begin

f:=a[j];

a[j]:=a[j+1];

a[j+1]:=f;

end;

End;

Задание. Составьте программу сортировки одномерного массива рассмотренным методом.



Поделиться:


Последнее изменение этой страницы: 2016-12-30; просмотров: 692; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.224.90.25 (0.146 с.)