Задачи для изучающих программирование самостоятельно 30 Задания на лабораторную работу по теме "Обработка одномерных массивов" 39

Вид материала

Документы

Содержание Проверка соседних элементов массива Сортировка массива и работа с отсортированным массивом 0|3 1 9 2 min=a[3]=1 Переставляем a[2]a[3] 2: 0 1 Var {дополнительные переменные}

Подобный материал:

• Обработка одномерных массивов, 21kb.
• Поэтому при написании программы будьте особенно внимательны, не путайте индексы элементов, 363.59kb.
• Лекция № Распределение памяти. Динамические переменные, 73.48kb.
• Алгоритмы сортировки одномерных массивов, 53.15kb.
• Урок 6 (1 час) Тема урока, 169.57kb.
• Поняття масиву. Одновимірний масив, 62.45kb.
• План урока Выступление со словами: Нередко… Показ презентации, 73.14kb.
• Курс является базовым как для изучения других математических дисциплин, так и для более, 36.89kb.
• В. А. Давыденко программирование и основы алгоритмизации лабораторный практикум, 1951.1kb.
• Методические указания могут быть полезны для студентов экономических специальностей,, 198.11kb.

Проверка соседних элементов массива

Задача 18: Подсчитать, сколько в массиве элементов, равных 0, справа и слева от которых стоят отрицательные элементы.


Фрагмент программы:

…

k:=0; {количество таких элементов}


{проходим по всем элементам массива A}

{начинаем не с первого, а со второго, потому что у первого элемента

нет стоящего слева от него}

{заканчиваем на n-1 элементе, а не на n, потому что у последнего

n-го элемента нет элемента, стоящего от него справа}

for i:=2 to n-1 do

{если i-ый элемент равен 0 и элемент слева от него и

элемент справа от него отрицательные}

if (A[i]=0) and (A[i-1]<0) and (A[i+1]<0)

then Inc(k); {тогда увеличиваем счетчик}

…

Задача 19: Найти номер первого элемента массива, который находится между двумя положительными элементами.


Фрагмент программы:

…

k:=0; {k - номер искомого элемента}

i:=2; {начинаем со второго элемента}

while (i<=n-1) and (k=0) do {пока не нашли искомый элемент

и не просмотрели все элементы массива}

begin

{если элемент тот, что надо, то запоминаем его индекс}

if (A[i-1]>0) and (A[i+1]>0) then k:=i;

Inc(i); {переходим к следующему элементу}

end;

{выводим позицию искомого элемента}

if k=0

then writeln('искомых элементов в массиве нет')

else writeln('искомый элемент занимает позицию ',k);

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

Задача 20: Отсортировать массив по возрастанию.


Массив A является отсортированным (упорядоченным) по возрастанию, если для всех i из интервала [1..n-1] выполняется условие A[i]<=A[i+1].


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


Суть этого метода сортировки заключается в следующем:

1. В массиве находим минимальный элемент.

2. Меняем минимальный элемент с первым.

3. В усеченном (исключая первый элемент) массиве находим

минимальный элемент.

4. Ставим его на второе место.

И так далее n-1 раз.


Пример:

Массив A, исходное состояние 1 3 0 9 2


Процесс сортировки

0: 1 3 0 9 2 min=a[3]=0 Переставляем a[1]<->a[3]

1: 0|3 1 9 2 min=a[3]=1 Переставляем a[2]<->a[3]

2: 0 1|3 9 2 min=a[5]=2 Переставляем a[3]<->a[5]

3: 0 1 2|9 3 min=a[5]=3 Переставляем a[4]<->a[5]

4: 0 1 2 3 9 Готово


Здесь знак | отделяет уже отсортированную часть массива от еще не отсортированной.


На Turbo Pascal этот алгоритм будет выглядеть следующим образом:

Var {дополнительные переменные}

buf: integer; {через buf будем менять значения двух элементов

массива}

imin:IndexEl; {индекс минимального элемента неотсортированной

части массива}

…

Begin

…

{n-1 раз ищем минимальный элемент массива}

for i:=1 to n-1 do

begin

{Ищем минимальный элемент в несортированной

части массива (от i-го элемента)}

imin:=i; {imin - это индекс минимального элемента массива}

for j:=i+1 to n do

if A[j]

{переставляем i-ый и imin-ый элементы}

buf:=A[i];

A[i]:=A[imin];

A[imin]:=buf;

End;

…


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


Алгоритм решения задачи следующий:

1. Ищем в массиве тот элемент, который больше вставляемого, – для этого последовательно просматриваем все элементы, начиная с первого.
   
2. Увеличиваем длину массива на 1.
   
3. После этого все элементы, стоящие правее от найденного, включая его самого, сдвигаются вправо.
   
4. На освободившуюся позицию вставляется искомый элемент.
   

Замечание: если все элементы массива меньше вставлямого, то новый элемент надо вставить в конец массива. Если все элементы массива больше вставляемого, то новый элемент надо вставить в начало массива.


Пример: Надо вставить 5 в массив A: 3 4 7 9

1. Ищем элемент, больший вставляемого. Это элемент A[3]=7.
   
2. Увеличиваем длину массива на 1.
   

Получаем массив A: 3 4 7 9 X

3. Сдвигаем элементы, начиная с 3-го, вправо.

Получаем массив A: 3 4 7 7 9

4. В элемент A[3] заносим 5.

Получаем массив: 3 4 5 7 9


Фрагмент программы, реализующей данный алгоритм:

…

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

read(g);

{1. Ищем элемент больше вставляемого }

k:=1; {k – индекс сравниваемого элемента}

while (k<=n) and (g>=a[k]) do {если k не вышла за границу n,

и вставляемый элемент меньше или равен A[k]}

k:=k+1; {то переходим к следующему элементу}

{2. Увеличиваем длину массива на 1}

n:=n+1;

{3. Сдвигаем элементы начиная с k-го вправо}

for i:=n downto k+1 do

a[i]:=a[i-1];

{4. В A[k] заносим g}

a[k]:=g;

…