Основные алгоритмы обработки массивов

1.

ЛЕКЦИЯ 10 .
Основные алгоритмы обработки массивов
• Сортировка
• Подсчет количества….
• накопление суммы и произведения
• поиск минимального и максимального
элементов массива.

2.

Сортировка
• Сортировка простым обменом (метод
“пузырька”)
Данный алгоритм основан на принципе
сравнения и обмена пар соседних
элементов до тех пор, пока не будут
рассортированы все элементы.

3.

метод “пузырька”
• 44
06
• 55
44
• 12
55
• 42
12
• 94
42
• 18
94
• 06
18
• 67
67
Проходы
1
06
12
44
55
18
42
94
67
06
12
18
44
55
42
67
94
06
12
18
42
44
55
67
94
06
12
18
42
44
55
67
94
06
12
18
42
44
55
67
94
2
3
4
5
6

4.

Сортировка массива методом “пузырька”
блок-схема
i=1; i<N;
i++
J=N-1; j>i; j-X[j]<X[j-1]
B=X[j]
X[j]=X[j-1]
X[j-1]=B

5.

Задача 1. Дан массив состоящий из
N элементов Найти сумму
элементов этого массива
Основное правило:
• Создается переменная S;
• Ей присваивается значение равное нулю;
• затем последовательно (поэлементно)
суммируются с ней элементы массива

6.

Задача 1
Фрагмент блок-схемы
Реализация на Cи.
const int N=50;
int _tmain(){
…
float X[N];
S=0
i=0; i<N ; i++
s=s+X[i]
for(i=0;
i<N; i++)
X[i]= rand()/100.050;/*заполнение массива
случайными числами */
float s=0;
for(i=0; i<N;
i++)
s=s+X[i];
…

7.

Задача 2. Дан массив из N
элементов. Найти произведение
элементов этого массива
Решение этой задачи сводится к тому,
Основное правило:
• Создается переменная P;
• Ей присваивается значение равное единице;
• затем последовательно (поэлементно)
домножается P на каждый элемент массива.

8.

• P=1
i=0; i<N ; i++
P=P*X[i]
• Реализация на Cи.
float X[N];
• …..
float
P=1;
for(i=0;i<N;i++)
{
P=P*X[i];}

9.

Задача 3. Подсчет количества..
• Дан целочисленный массив В = {bi} размером n элементов
i= 1..n.
Определить количество элементов массива, кратных трем, т.е.
которые делятся на 3 без остатка (остаток от деления равен
нулю)
Основное правило:
• Создается переменная, например k;
• Ей присваивается значение равное нулю;
• затем последовательно ( в цикле ) просматриваются все
элементы массива. К переменной k прибавляется 1, если
будет найден элемент массива, значение которого
удовлетворяет условию в задаче.

10.

Задача 3
• Блок-схема
K=0
i=0; i<N; i++
B[i]%3==0
K++
• Реализация на Си
int _tmain()
{
int B[20];
int i,N,k;
cout<<“N="; cin>>N;
cout<<"Massiv B=\n“);
for(i=0; i<N; i++)
cin>>B[i];
K=0;
for(i=0;i<N; i++)
if (B[i]%3= =0) k++;

11.

Задача 4 .
• Дан массив X из n вещественных чисел.
Вычислить среднее арифметическое и среднее
геометрическое чисел массива, используя
формулы:
1 n
S xi
n i 1
n
P n xi
i 1

12.

Задача 5. Поиск максимального
элемента массива и его номера
• Дан вещественный массив: X = {xi}; i= 1..N
Найти максимальный элемент массива и
его порядковый номер.
• Введем обозначения:
max - максимальный элемент;
nmax - индекс максимального элемента

13.

Задача 5
Блок-схем алгоритма
Реализация на С++
#include<stdafx.h>
max=X[0]
nmax=0
i=1; i<N; i++
int _tmain() {
float x[10],max;
int N, nmax;
printf("\n N=");
scanf("%d",&N);
printf("\n Введите массив X \n");
printf("\n Массив X=\n");
for(i=0;i<N;
i++)
scanf("%f",&X[i]);
max=X[0];
nmax=0;
X[i]>max
max=X[i]
nmax=i
for(i=1;
i<N;
if (X[i]>max)
{ max=X[i];
nmax=i;
}
i++)

14.

Задача 6. Поиск минимального
элемента массива и его номера
• Дан вещественный массив: X= {xi}; i= 1..N
Найти минимальный элемент массива и его
номер.
• Введем обозначения:
min - минимальный элемент;
nmin - индекс минимального элемента;

15.

Задача 6
Блок-схем алгоритма
Реализация на С++
#include<stdafx.h>
min=X[0]
nmin=0
int main() {
float x[100],min;
int N, nmin;
printf("\n N=");
scanf("%d",&N);
printf("\n Введите массив X \n");
i=1; i<N; i++
printf("\n Массив X\n");
for(i=0;i<N;
i++)
scanf("%f",&X[i]);
min=X[0];
nmin=0;
X[i]<min
for(i=1;
i<N;
if (X[i]<min)
{ min=X[i];
nmin=i;
min=X[i]
nmin=i
}
i++)

16.

Задача 7. Поиск минимального и
максимального элементов массива
• Дан вещественный массив: T = {ti}; i= 1..10
Поменять местами минимальный и
максимальный элементы массива и вывести
массив после обмена.
• Введем обозначения:
min - минимальный элемент;
nmin - индекс минимального элемента;
max - максимальный элемент;
nmax - индекс максимального элемента

17.

Задача 8. Формирование нового
массива из элементов исходного
массива
• Переписать в новый массив элементы
исходного массива , кратные 5.

18.

K=0
i=0; i<N;
i++
X[i]%5==0
B[k++]=X[i]
• Реализация алгоритма на С
++
int main()
{ float X[20],B[20];
int i,n,k;
cout<<“N="; cin>>N;
cout<<"Massiv X\n”;
for(i=0;i>a[i];
cin>>X[i];
for(k=i=0; i<n; i++)
if (X[i]%5= =0)
B[k++]=X[i];
…