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

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

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

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

Задачи подсчёта

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

Название

Действие до цикла

Действие в цикле Действия после цикла
сумма s: = 0; s: = s + a [ i ] write ('s=',s);
произведение p:= 1 ; p: = p * a [ i ] write ('p=',p);
количество k: = 0; if условие then k: = k + 1 write ('k=',k);

Задача 1. Составить программу нахождения суммы и произведения всех элементов одномерного массива.(.pas)

Исходные данные: массив x, содержащий n вещественных чисел.
Результат: сумма s и произведение p всех элементов массива.
Метод решения:
- начиная с нулевого значения суммы, добавляем поочередно новый элемент ряда и находим значение искомой суммы;
- начиная с начального, единичного произведения, находим искомое произведение, умножая текущее значение произведения на очередной элемент ряда.

program SPMas;
         var  x: array [1..100] of  real;
         n, i: integer;
         s, p: real;
begin
         cls;
         writeln ('Введите размерность массива :');
         readln (n);
         {инициализируем s}
         s:=0;
         {инициализируем p}
         p:=1;
         writeln ('Введите элементы массива:');
           for i:=1 to n do
                                 begin
                                             write ('x[',i,']=');
                                             readln (x[i]);
                                             {вычисляем сумму}
                                             s:=s+x[i];
                                             {вычисляем произведение}
                                             p:=p*x[i];
                                 end;
         writeln ('Полученная сумма равна ', s);
         writeln ('Полученное произведение равно ', p);
end. 

Задача 2. Составить программу нахождения количества элементов целочисленного массива с нечетными индексами, запись которых оканчивается на 5. (.pas)

Исходные данные: массив a, содержащий n целых чисел.
Результат: k - количество элементов массива, запись которых оканчивается на 5 и имеющих нечетные индексы.
Метод решения:
- в цикле: вводим элемент массива, если он удовлетворяют условию задачи, то значение переменной k увеличиваем на 1, затем вводим следующий элемент.
- выводим k.

program kol;
         const n=30;
         {Описываем массив}
         var a: array [1..n] of integer;
                 k,i: integer;
begin
         cls;
         {инициализируем k}
         k:=0;
         for i:=1 to n do begin
                  {Вводим элемент массива}
                  read (a[i]);
                  {Проверяем}
                  if (a[i] mod 10=5) and (i mod 2<>0)
                                     then k:=k+1;
                end;
         writeln(k);
end.

Задача 3. Найти среднее арифметическое всех элементов массива.(.pas)

Исходные данные: массив x, содержащий n вещественных чисел.
Результат: sr - среднее арифметическое всех элементов массива.
Метод решения:
- начиная с нулевого значения суммы sum, добавляем поочередно новый элемент ряда и находим значение суммы всех элементов массива;

- среднее арифметическое sr находим делением sum на n.

program SPMas;
var  x: array [1..100] of  real;
n, i: integer;
sum, sr: real;
begin
         writeln ('Введите размерность массива :');
         readln (n);
         {инициализируем s}
           sum:=0;
           {инициализируем sr}
           sr:=0;
           writeln ('Введите элементы массива:');
            for i:=1 to n do
                                      begin
                                                write ('x[',i,']=');
                                                readln (x[i]);
                                                {вычисляем сумму}
                                                sum:=sum+x[i];
                                      end;
                sr:=sum/n;
                writeln ('среднее арифметическое равно ', sr);
end. 

Нахождение минимального или максимального среди элементов массива.

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

Название Действие до цикла Цикл Действия после цикла
Поиск максимального (минимального) элемента произвольного массива
максимум max: = a [ 1 ];

for i:=2 to n do
if a [ i ] > max then max:=a [ i ];

 write ('max=',max) ;
максимум

n_max:=1;
(номер максимального элемента)

 for i:=2 to n do
if a [ i ] > a[n_max] then n_max:= i;		 write ('max=',a [ n_max ]) ;
минимум min : = a [ 1 ]; for i:=2 to n do
if a [ i ] < min then min:=a [ i ];		 write ('min =',min) ;
Поиск максимального (минимального) элемента массива, про значения элементов которого известно, что они принадлежат определенному диапазону [a; b].
максимум max: = a;

for i:=1 to n do
if a [ i ] > max then max:=a [ i ];

 write ('max=',max) ;
минимум min : = b; for i:=1 to n do
if a [ i ] < min then min:=a [ i ];		 write ('min =',min) ;
Поиск номера максимального элемента произвольного массива

номер максимального
элемента массива

 n_max:=1; for i:=2 to n do
if a [ i ] >a [ n_max] then n_max:= i ;		 write ('n_max =',n_max) ;

Задача 4. Составить программу нахождения максимального элемента произвольного одномерного массива.(.pas)

Исходные данные: массив x, содержащий m вещественных чисел.
Результат: максимальный элемент массива max.
Метод решения:
- в качестве начального значения максимума возьмем значение первого элемента массива;
- начиная со второго, переберем все элементы и проверим, есть ли элемент, который больше, чем этот выбранный максимум. Если такой нашелся - будем считать его максимальным и сравним с остальными.

program maximum;
const n = 7;
var x: array [1..n] of real;
         max: real;
         i: integer;
begin
         for i:=1 to n do read (x[i]);
         max:=x[1];
         for i:=2 to n do
                             if (x [i]>max) then
                                                      max:= x [ i ];
         writeln('max = ',max);
end.

Задача 5. Составить программу нахождения номера максимального элемента произвольного одномерного массива.(.pas)

Исходные данные: массив a, содержащий n вещественных чисел .
Результат: n_max - номер максимального элемента массива.
Метод решения:
- в программе можно выделить две части: заполнение массива числами (первый цикл for) и непосредственно поиск индекса максимального элемента (второй цикл for);
- изначально делается предположение, что первый элемент массива и есть максимум. Поэтому переменной n_max присваивается значение 1 (т.е. указатель на первый элемент массива), а max[n_max] – непосредственно значение, хранящееся в первой ячейке массива;
- начиная со второго элемента, каждое очередное значение массива сравнивается со значением max[n_max]. В случае, если текущее значение массива больше, чем хранящиеся в n_max, происходит новое присваивание индекса.

program numer_max;
const n = 7;
var a: array[1..n] of real;
n_max, i: integer;
begin
                for i:=1 to n do read (a[i]);
                n_max:=1;
                for i:=2 to n do
                if a [ i ] >a [ n_max] then
                                                n_max:= i;
                writeln ( n_max);
end.

 Вопросы:

Задачи, в которых требуется найти какие-то характеристики массива.

Задача 6. Проверить, что массив упорядочен по возрастанию.(.pas)

Исходные данные: массив a, содержащий n целых чисел .
Результат: сообщение "массив упорядочен " или сообщение "массив неупорядочен".
Метод решения:
- введем дополнительную переменную-флажок flag (критерий упорядоченности). Присвоим ей начальное значение, равное нулю.
- посчитаем в каком количестве случаев порядок элементов в паре будет верным. Для этого переберём все соседние пары элементов (их будет n-1). Если в паре элемент с меньшим номером оказался больше, чем элемент с большим номером, то увеличим на единицу переменную-флажок flag.
- после окончания цикла проверим, изменилось ли значение переменной flag. Если оно осталось равным нулю - значит, во всех парах порядок верный и массив упорядочен. Иначе массив неупорядочен.

  program z;
const n=5;
var flag,i: integer;
a: array [1..n] of real;
begin
                flag:=0;
                for i:=1 to n do read(a[i]);
                for i:=1 to n-1 do
                if a[i]>a[i+1] then flag:=flag+1;
                if flag=0 then writeln ('упорядочен')
                                else writeln ('неупорядочен');
end.
Применение алгоритма задач анализа для решения практических задач

 Задачи:

  1. Пусть известно, что в автопарке, имеется 21 машина марки ТАТРА. Каждый из автомобилей перевез за день определенный объем груза. Определить суммарный объем перевозок грузов за день (.pas).
  2. Известна среднегодовая зарплата 15 сотрудников одного предприятия. Найти величину наименьшей среднемесячной зарплаты этих сотрудников (.pas).
  3. Известны результаты экзамена 15 выпускников школы по истории. Определить, сколько выпускников сдали экзамен на 5 (.pas).
  4. На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат: <Фамилия> <Имя> <оценки>, где <Фамилия> – строка, состоящая не более чем из 20 символов, <Имя> – строка, состоящая не более чем из 15 символов, <оценки> – через пробел три целых числа, соответствующие оценкам по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и <оценки> разделены одним пробелом. Пример входной строки: Иванов Петр 4 5 4. Требуется написать программу на языке Паскаль или Бейсик, которая будет выводить на экран фамилии и имена трех лучших по среднему баллу учеников. Если среди остальных есть ученики, набравшие тот же средний балл, что и один из трех лучших, то следует вывести и их фамилии и имена.(.exe)(.pas)

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

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

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

  4. Значения двух массивов A и B с индексами от 1 до 100 задаются при помощи следующего фрагмента программы:
    for i:=1 to n do A[i]:=i*i;
    for i:=1 to n do B[i]:=A[i]-100;
    Сколько положительных значений будет в массиве B?
    0
    10
    90
    91

    
;

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

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

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

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

2

Вычисление среднего арифметического чётных элементов массива
sum:=0;
kol:=0;
for i:=1 to n do
if a[i] mod 2 = 0 then
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