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

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

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

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

Некоторые свойства элементов массива

Свойство

Запись свойства
четные a[i] mod 2 = 0

нечетные     

a[i] mod 2 <> 0

кратные k     

a[i] mod k = 0

некратные k

a[i] mod k <> 0

 на четных местах    

i mod 2 = 0
запись числа заканчивается на цифру k a[i] mod 10=k

на нечетных местах   

i mod 2 <> 0

положительные

a[i] > 0

неотрицательные 

a[i] >= 0
меньше х1 или больше х2 (a [i]<x1) or (a [i]>x2)

в интервале (х1; х2)  

(a [i]>x1) and (a [i]<x2)

Задачи поиска
Задача 1. Найти номер первого по счету положительного элемента массива.
Использование цикла с параметром (.pas)

Исходные данные: массивa, содержащий n вещественных чисел.
Результат: k - номер первого положительного элемента массива .
Метод решения:
- просматриваем массив с конца, если находим положительный элемент, то переменной k присваиваем номер данного положительного элемента;
- если находим положительный элемент с меньшим номером, то меняем значение переменной k;
- если значение k осталось равным 0, то положительных элементов в данном массиве нет.
.
  program z;
         const n=30;
         type mas= array [1..n] of real;
         var a: mas;
               i, k: integer;
begin
         k:=0;
         for i:=1 to n do read (a[i]);
         for i:=n downto 1 do
                                    if a[i]>0 then k:=i;
         if k=0 then writeln ('положительных элементов нет')
                   else writeln(k);
end.
Использование цикла с постусловием (.pas)
Исходные данные: массивa, содержащий n вещественных чисел.
Результат: k - номер первого положительного элемента массива .
Метод решения:
- просматриваем массив, начиная с первого элемента, если находим положительный элемент, то переменной k присваиваем номер данного положительного элемента;
-работа цикла заканчивается, если значение k изменилось или если просмотрен весь массив;
- если значение k осталось равным 0, то положительных элементов в данном массиве нет.
  program z;
         const n=5;
         type mas= array [1..n] of real;
         var a: mas;
               i,k: integer;
begin
         for i:=1 to n do read (a[i]);
         k:=0;
         i:=0;
         repeat
                  i:=i+1;
                  if a[i]>0 then k:=i;
         until (k>0) or (i=n);
         if k=0 then writeln ('положительных элементов нет')
                  else writeln(k);
end.
Использование цикла с предусловием (.pas)
Исходные данные: массивa, содержащий n вещественных чисел.
Результат: k - номер первого положительного элемента массива .
Метод решения:
- просматриваем массив: если текущий элемент неположительный и i < n, то значение переменной i увеличиваем на 1, иначе если текущий элемент положительны, то переменной k присваиваем номер данного положительного элемента;
- если значение k осталось равным 0, то положительных элементов в данном массиве нет.
  program z;
         const n=7;
         type mas= array [1..n] of real;
         var a: mas;
         i,k: integer;
begin
         for i:=1 to n do read (a[i]);
         k:=0;
         i:=1;
         while (a[i]<=0) and (i<n) do i:=i+1;
         if a[i]>0 then k:=i;
         if k=0 then writeln ('положительных элементов нет')
                   else writeln(k);
end.

 Вопросы:

  1. Дан фрагмент программы, обрабатывающий массив А из 10 элементов:
    j := 1;
    for i:=1 tо 10 do
    if A[i] = A[j] then j := i;
    s := j;
    Чему будет равно значение переменной s после выполнения этого алгоритма?
    1
    10
    индексу элемента, равного первому, и имеющему наибольший индекс
    индексу элемента, равного последнему, и имеющему наименьший индекс

  2. В программе описан одномерный целочисленный массив с индексами от 1 до n. Известно, что в массиве есть несколько элементов с максимальным значением. Дан фрагмент программы:
    j:=1;
    for i:=1 to n do if A[i] > A[j] then j:= i;
    значению максимального элемента
    количеству элементов в массиве A, имеющих максимальное значение
    индексу первого элемента в массиве A, имеющего максимальное значение
    индексу последнего элемента в массиве A, имеющего максимальное значение

  3. Дан фрагмент программы:
    for i:=n downto 1 do
    if a[i]>0 then k:=i;
    Чему будет равно значение переменной k после выполнения этого фрагмента программы:
    номер первого по счету положительного элемента массива
    номер последнего по счету положительного элемента массива
    максимальный элемент массива
    первый по счету положительный элемент массива

  4. Дан фрагмент программы:
    for i:=1 to n do
    if a[i]mod 2=0 then k:=a[i];
    Чему будет равно значение переменной k после выполнения этого фрагмента программы:
    последний по счету четный элемент массива
    первый по счету нечетный элемент массива
    номер последнего по счету нечетного элемента массива
    номер первого по счету четного элемента массива

    

К началу страницы

№
Фрагмент программы
Блок - схема
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