Обработка массива —Перестановка
  • Основные задачи
  • Шпаргалка
  • Вопросы и задания

Большинство задач на обработку массива сводятся к комбинированию следующих алгоритмов:

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

´В задачах из таблицы массив задан (под словом "задан" будем понимать, что массив описан и значения его элементов определены).

Задачи, в которых требуется поменять местами элементы массива.
Перестановка элементов массива в обратном порядке(.pas)

Метод решения:
1.Решаем путем перестановки элементов массива попарно - первый с последним, второй с предпоследним, и т.д. Значит, i-ый элемент меняем местами с (n-i+1)-ым
2. Количество таких перестановок в два раза меньше количества элементов.

for i:=1 to n div 2  do
                     begin
                             c:=a[i];
                             a[i]:=a[n+1-i];
                              a[n+1-i]:=c;
                      end;

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

Метод решения:
1.Решаем путем перестановки элементов массива попарно - первый со вторым, третий с четвёртым т.е. элемент с нечетным номером с элементом, имеющим четный номер и т.д. Значит, (2*i-1)-ый элемент меняем местами с (2*i)-ым
2. Количество таких перестановок в два раза меньше количества элементов.

for i:=1 to n div 2 do
begin
         k:=x[2*i-1];
         x[2*i-1]:=x[2*i];
         x[2*i]:=k;
end;

Обмен половин массива(.pas)
 

Метод решения:
1.Решаем путем перестановки элементов массива попарно - i-ый c( i+k)-ым, где k=n div 2.
2. Количество таких перестановок в два раза меньше количества элементов.

k:=n div 2;
for i:=1 to n div 2 do
                            begin
                            c:=a[i];
                            a[i]:=a[k+i];
                            a[k+i]:=c;
  end;

Перестановка максимального и минимального элементов массива.(.pas)
 

Метод решения:
1.Находим номер наибольшего и наименьшего элементов массива.
2. Меняет наибольший и наименьший элементы местами.

imax:=1;
imin:=1;
for i:=2 to n do
         if a[i]>a[imax] then imax:=i
                  else if a[i]<a[imin] then imin:=i;
c:=a[imin];
a[imin]:=a[imax];
a[imax]:=c;
Задачи циклической перестановки.
Циклический сдвиг элементов массива на один элемент вправо, последний элемент при этом должен оказаться на первом месте.(.pas)
  c:=a[n];
for i:=n downto 2 do a[i]:=a[i-1];
a[1]:=c;
Циклический сдвиг элементов массива на один элемент влево, первый элемент при этом должен оказаться на последнем месте.(.pas)
  c:=a[1];
for i:=2 to n do a[i-1]:=a[i];
a[n]:=c;
Задачи сортировки элементов массива.

Сортировка «пузырьком» (.pas)

Метод решения:
- Сравниваются пары соседних элементов массива и, если значения элементов в паре стоят в неправильном порядке (правый меньше левого), то меняем их местами. В результате одного такого прохода по массиву самый большой элемент окажется на последней позиции.
- Всю процедуру повторяем столько раз, сколько элементов нужно поставить на нужное место то есть n-1.

for k:=n-1 downto 1 do
for i:=1 to k do
                  if a[i+1]<a[i] then begin
                                                      c:=a[i];
                                                      a[i]:=a[i+1];
                                                      a[i+1]:=c;
                                             end;
Сортировка выбором(.pas)

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

for k:=1 to n do
                 begin
                 min := a[k];
                 imin := k;
                 for j := k+1 to n do
                                  if a[j] < min then begin
                                                                    min:= a[j];
                                                                    imin:=j
                                                             end;
                 a[imin] := a[k];
                 a[k] :=min;
end;
Сортировка методом прямого включения(.pas)

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

for k := 2 to n do
                 begin
                          w := a[k];
                          j := k-1;
                          while (j > 0) and (w <= a[j]) do
                                                                    begin
                                                                    a[j+1] := a[j];
                                                                    j:=j-1;
                                                                    end;
                            a[j+1] := w;
                 end;

 Вопросы:

Применение алгоритма задач перестановок для решения практических задач
  1. Известны результаты конкурса "ИнфоКоТ" для 21 участника. Расположить данные результаты в порядке возрастания набранных баллов (.pas).
  2. Задан список ID брокеров товарной биржи из n человек. Обменяйте местами ID брокеров: первого и последнего, второго и предпоследнего, третьего от начала и третьего от конца и т.д.

     Вопросы:

  1. В программе описан одномерный целочисленный массив с индексами от 0 до 10 и целочисленные переменные k, i. В приведенном ниже фрагменте программы массив сначала заполняется, а потом изменяется:
    for i:=0 to 10 do A[i]:=i;
    for i:=0 to 4 do
    begin
    k:=A[i];
    A[i]:=A[10-i];
    A[10-i]:=k;
    end;
    Чему будут равны элементы этого массива?
    10 9 8 7 6 5 4 3 2 1 0
    0 1 2 3 4 5 6 7 8 9 10
    0 1 2 3 4 5 4 3 2 1 0
    10 9 8 7 6 5 6 7 8 9 10

  2. В программе описан одномерный целочисленный массив с индексами от 0 до 10 и целочисленные переменные k, i. В приведенном ниже фрагменте программы массив сначала заполняется, а потом изменяется:
    for i:=0 to 10 do A[i]:=i;
    for i:=0 to 10 do
    begin
    k:=A[i];
    A[i]:=A[10-i];
    A[10-i]:=k;
    end;
    Чему будут равны элементы этого массива?
    10 9 8 7 6 5 4 3 2 1 0
    0 1 2 3 4 5 6 7 8 9 10
    0 1 2 3 4 5 4 3 2 1 0
    10 9 8 7 6 5 6 7 8 9 10

  3. В программе описан одномерный целочисленный массив с индексами от 0 до 10 и целочисленные переменные k, i. В приведенном ниже фрагменте программы массив сначала заполняется, а потом изменяется:
    for i:=0 to 10 do A[i]:=i;
    for i:=0 to 4 do
    begin
    k:=A[2*i];
    A[2*i]:=A[2*i+1];
    A[2*i+1]:=k;
    end;
    Чему будут равны элементы этого массива?
    5 6 7 8 9 0 1 2 3 4 10
    10 9 8 7 6 5 4 3 2 1 0
    0 1 2 3 4 5 4 3 2 1 0
    1 0 3 2 5 4 7 6 9 8 10

  4. В программе описан одномерный целочисленный массив A с индексами от 0 до 10. Ниже представлен фрагмент этой программы, в котором значения элементов массива сначала задаются, а затем меняются.
    for i:=0 to 10 do A[i]:=i+3;
    for i:=10 downto 0 do
    begin
    k:=A[i];
    A[i]:=A[10-i];
    A[10-i]:=k;
    end;
    Чему будут равны элементы этого массива?
    13 12 11 109 8 7 6 5 4 3
    3 4 5 6 7 8 9 10 11 12 13
    13 12 11 10 9 8 9 10 11 12 13
    3 4 5 6 7 8 7 6 5 4 3

  5. В программе описан одномерный целочисленный массив A с индексами от 0 до 10. Ниже представлен фрагмент этой программы, в котором значения элементов массива сначала задаются, а затем меняются.
    for i:=0 to 10 do A[i]:=i;
    t:=A[0];
    for i:=1 to 10 do
    A[i-1]:=A[i];
    A[10]:=t;
    Чему будут равны элементы этого массива?
    10 10 10 10 10 10 10 10 10 10
    1 2 3 4 5 6 7 8 9 10 0
    0 0 0 0 0 0 0 0 0 0
    1 2 3 4 5 6 7 8 9 10 1

    
№
Фрагмент программы
Блок - схема
1

Вычисление суммы всех элементов массива
sum:=0;
for i:=1 to n do sum:=sum+x[i];

Исследовательская деятельность обучающихся

2

Вычисление среднего арифметического чётных элементов массива
sum:=0;
kol:=0;
for i:=1 to n do begin
sum:=sum+a[i];
kol:=kol + 1;
end;
if kol=0 then writeln ('чётных чисел нет')
else writeln ('среднее чётных чисел равно', sum/kol);

  
3

Найти произведение всех элементов массива
pr:=1;
for i:=1 to n do pr:=pr*a[i];

 
4

Количество четных элементов массива
kol:=0;
for i:=1 to n do
if (a[i] mod 2=0) then kol:=kol+1;

 
5

Удвоить все положительные элементы массива, и поменять знак у остальных
for i:=1 to n do
if a[i]>0 then a[i]:=a[i]*2
else a[i]:=-a[i];

 
6

Перестановка всех элементов массива в обратном порядке
for i:=1 to n div 2 do
begin
k:=x[i];
x[i]:=x[n+1-i];
x[n+1-i]:=k;
end;

 
7

Перестановка соседних элементов массива
for i:=1 to n div 2 do
begin
k:=x[2*i-1];
x[2*i-1]:=x[2*i];
x[2*i]:=k;
end;

 
8

Обмен половин массива
k:=n div 2;
for i:=1 to n div 2 do
begin
c:=a[i];
a[i]:=a[k+i];
a[k+i]:=c;
end;

 
9

Проверить, есть ли в массиве четные числа
kol:=0;
for i:=1 to n do
if a[i] mod 2 = 0 then kol:=kol+1;
if kol=0 then writeln (‘нет четных’)
else writeln (‘есть четные’);

 
10

Проверить, что массив упорядочен строго по возрастанию
flag:=0;
for i:=1 to n-1 do
if a[i]>a[i+1] then flag:=flag+1;
if flag=0 then writeln (‘ упорядочен ’)
else writeln (‘неупорядочен ’);

 
11

Поиск максимального элемента массива (границы изменения значений элементов массива неизвестны)
max:=a[1];
for i:=2 to n do
if a[i]>max then max:=a[i];
write('максимальный элемент max= ', max);
end.

 
12

Значения элементов массива принадлежат промежутку от -500 до 500. Найти максимальный элемент массива.
max:=-501;
for i:=1 to n do
if a[i]>max then max:=a[i];

 
13

Поиск количества элементов произвольного массива равных максимальному
max:=a[1];
nmax:=1;
for i:=2 to n do
if a[i] > max then begin
max:=a[i];
nmax:=1;
end
else
if a[i]=max then
nmax:=nmax+1;

 
14

Найти номер максимального элемента массива, если он единственный, или количество максимальных элементов, если их несколько.
max:=a[1];
nmax:=1;
for i:=2 to n do
if a[i] > max then begin
max:=a[i];
nmax:=1;
j:=i;
end
else
if a[i]=max then
nmax:=nmax+1;
if nmax=1 then writeln(‘j=‘,j) else writeln (‘nmax=‘, nmax);

 
15 Поиск второго по величине максимального элемента массива
max:=a[1];
max2:=a[2];
if max<max2 then begin
max:=a[2];
max2:=a[1];
end;
for i:=3 to n do
if a[i]>max then begin
max2:=max;
max:=a[i];
end
else if a[i]>max2 then max2:=a[i];		  
16

Поиск номера максимального элемента
imax:=1;
for i:=2 to n do
if a[i]>a[imax] then imax:=i;

 
17

Значения элементов массива принадлежат диапазону от – 500 до 500. найти максимальный отрицательный элемент массива. Гарантируется, что отрицательные элементы есть.
max:=-501;
for i:=1 to n do
if (a[i]<0) and (a[i]>max) then max:=a[i];

 
18

Номера двух элементов массива наименее отличающихся друг от друга
const N=7;
var a:array [1..N] of integer;
i,j,min,min2,s:integer;
begin
for i:=1 to N do read (a[i]);
s:=abs(a[1]-a[2]);
min:=1;
min2:=2;
for i:=1 to N -1 do
for j:=i+1 to N do
if abs(a[i]-a[j])<s then begin
s:=abs(a[i]-a[j]);
min:=i;
min2:=j;
end;
writeln(‘номера двух элементов массива наименее отличающихся друг от друга:',min,'и', min2);
end.

  
19

Номера двух последовательных элементов массива наименее отличающихся друг от друга
const N=7;
var a:array [1..N] of integer;
i,j,min,min2,s:integer;
begin
for i:=1 to N do read (a[i]);
s:=abs(a[1]-a[2]);
min:=1;
min2:=2;
for i:=1 to N -1 do
if abs(a[i]-a[i+1])<s then begin
s:=abs(a[i]-a[i+1]);
min:=i;
min2:=i+1;
end;
writeln('номера двух соседних элементов наименее отличающихся друг от друга:',min,'и', min2);
end.

  
Тест
Задачи

Задача 1 (..pas) Дан целочисленный массив из 30 элементов. Элементы могут принимать значения от 0 до 100 ­– баллы, полученные на ЕГЭ. Опишите на русском языке или на одном из языков программирования алгоритм, который подсчитывает и выводит средний балл учащихся, сдавших экзамен (получивших оценку более 20 баллов). Гарантируется, что хотя бы один ученик в классе успешно сдал экзамен. Исходные данные объявлены так, как показано ниже. Использовать другие переменные запрещается.

const N = 30;
var A: array[1..N] of integer;
i, x, y: integer;
s: real;
begin
for i:=1 to N do readln(A[i]);
...
end.

Задача 2 (..pas) Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 100 – баллы учащихся выпускного класса за итоговый тест по информатике. Для получения положительной оценки за тест требовалось набрать не менее 20 баллов. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит минимальный балл среди учащихся, получивших за тест положительную оценку. Известно, что в классе хотя бы один учащийся получил за тест положительную оценку. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.
 

const N=30;
var a: array [1..N] of integer;
i, j, min: integer;
begin
for i:=1 to N do readln(a[i]);
...

end.

Задача 3 (.pas) Дан массив, состоящий из 30 вещественных чисел. Вычислить сумму всех элементов. Массив вводится с клавиатуры.
а) Наберите программу или воспользуйтеть файлом .pas, заменив многоточие на необходимые команды:
Program z;
Const n=5;
type mas=array[1..n] of real;
var a: mas;
s: real;
i: integer;
begin
for i:=........ to ....... do
begin
writeln (‘введите элемент массива’);
......................;
S:=S+........ ;
end;
writeln (‘ Сумма равна’,.......);
End.
б) запустите данную программу и посмотрите результат её работы.

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

Задача 5 (.pas) Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до 1000. Опишите на русском языке или на одном из языков программирования алгоритм, позволяющий найти и вывести минимальное значение среди элементов массива, которые имеют чётное значение и не делятся на три. Гарантируется, что в исходном массиве есть хотя бы один элемент, значение которого чётно и не кратно трем. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но использовать все описанные переменные не обязательно.

const
N = 20;
var
a: array [1..N] of integer;
i, j, min: integer;
begin
for i := 1 to N do
readln(a[i]);
….......
end.

 


Hosted by uCoz