– перестановка его элементов в обратном порядке.
Выделим в
отдельную функцию процедуру инвертирования:void invert(int *a,int n)
{
for(int j=0,tmp; j
tmp=a[j];
a[j]=a[n-j-1];
a[n-j-1]=tmp;
}
}
- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Обработка массивов
Содержание
- 2. Обработка числовых массивовПример 1. Переворот одномерного целочисленного
- 3. Обработка числовых массивовДля проверки ее работоспособности можно
- 4. Пример 2. Перестановка головы и хвоста массива
- 5. Пример 2. Для проверки описанного выше алгоритма
- 6. Пример 3. Количество "счастливых" билетов. Билеты для
- 7. Работу этой программы можно ускорить почти в
- 8. Пример 4. Определение количества разных элементов в
- 9. Обработка числовых массивов
- 10. Вариант 2. При первом просмотре определяем, содержится
- 11. Пример 5. Вычисление нормы вектора.#include #include //здесь находится
- 12. Пример 7. Нормирование вектора.#include #include //здесь находится
- 13. Пример 8. Вычисление скалярного произведения двух векторов.#include
- 14. Пример 9. Сумма векторов.#include #include void sum_vec(double *a,double *b,double *c,int n) { for(int i=0; i
- 15. Работа с матрицамиРаботу с двумерными массивами можно
- 16. Работа с матрицамиПример 10. Формирование единичной матрицы
- 17. Работа с матрицамиvoid main(){ int i,j,v[5][5]; eye((int*)v,5); for(i=0;i
- 18. Работа с матрицамиПример 11. Сложение квадратных матриц.
- 19. Работа с матрицамиvoid main(){ int i,j,v3[3][3]; int v1[3][3]={{1,2,3},{4,5,6},{7,8,9}}; int v2[3][3]={{0,0,1},{0,0,2},{0,0,3}}; add_mat((int*)v1,(int*)v2,(int*)v3,3); for(i=0;i
- 20. Работа с матрицамиПример 12. Умножение квадратных матриц
- 21. Работа с матрицамиvoid main(){ int i, j,
- 22. Работа с матрицамиПример 13. Транспонирование матрицы с
- 23. Работа с матрицами//массив указателей на строки int *p[4]={(int *)&v[0],(int *)&v[1],(int *)&v[2],(int *)&v[3]}; transp(p,4); for(int i=0; i
- 24. Работа с матрицамиМассив указателей p на строки двумерного массива v может
- 25. ПОИСКЗадача поиска формулируется следующим образом: задан массив a,
- 26. Последовательный ПОИСККлассический алгоритм последовательно поиска в неупорядоченном массиве состоит
- 27. Последовательный ПОИСКФункция ssearch, реализующая последовательный поиск, устроена довольно просто:int
- 28. Двоичный поискДвоичный поиск можно применить только в
- 29. Двоичный поискФункция bsearch, реализующая двоичный поиск, может быть
- 30. Сортировка массивов сортировка методом пузырькаИдея метода состоит
- 31. сортировка методом пузырькаФункция bubble, реализующая первый алгоритм
- 32. сортировка методом пузырькаБолее известный алгоритм пузырьковой сортировки
- 33. сортировка методом отбораИдея метода: находится элемент с
- 34. сортировка методом отбораОценка трудоемкости метода отбора:• количество сравнений
- 35. сортировка методом вставкиИдея метода: последовательное пополнение ранее
- 36. Скачать презентацию
- 37. Похожие презентации
Обработка числовых массивовПример 1. Переворот одномерного целочисленного массива – перестановка его элементов в обратном порядке. Выделим в отдельную функцию процедуру инвертирования:void invert(int *a,int n){ for(int j=0,tmp; j
![Работа с матрицамиvoid main(){ int i,j,v[5][5]; eye((int*)v,5); for(i=0;i](/img/tmb/13/1237549/d84d6a2c8c0b94a781a9c03fd2e07066-720x.jpg "Обработка массивов")
![Работа с матрицамиvoid main(){ int i,j,v3[3][3]; int v1[3][3]={{1,2,3},{4,5,6},{7,8,9}}; int v2[3][3]={{0,0,1},{0,0,2},{0,0,3}}; add_mat((int*)v1,(int*)v2,(int*)v3,3); for(i=0;i](/img/tmb/13/1237549/c42cf9b10235da7cdc6fa21a2138eb01-720x.jpg "Обработка массивов")
![Работа с матрицамиvoid main(){ int i, j, v3[2][2]; int v1[2][2]={{1,2}, {3,4}}; int](/img/tmb/13/1237549/44e0b39f475cf64a22f0a208e6449760-720x.jpg "Обработка массивов")
![Работа с матрицами//массив указателей на строки int *p[4]={(int *)&v[0],(int *)&v[1],(int *)&v[2],(int *)&v[3]}; transp(p,4); for(int i=0; i](/img/tmb/13/1237549/e0c3a5204638cf40f5daf9c71c8fb003-720x.jpg "Обработка массивов")
Слайд 2
Обработка числовых массивов
Пример 1. Переворот одномерного целочисленного массива
– перестановка его элементов в обратном порядке.
отдельную функцию процедуру инвертирования:void invert(int *a,int n)
{
for(int j=0,tmp; j
tmp=a[j];
a[j]=a[n-j-1];
a[n-j-1]=tmp;
}
}
Слайд 3
Обработка числовых массивов
Для проверки ее работоспособности можно воспользоваться
следующей программой:
#include
#include
#define N 20
void invert(int *a,int n);
void
main(){ int j,a[N];
printf("Before reverse:\n");
for(j=0; j
invert(a,N);
printf("\nAfter reverse:\n");
for(j=0; j
}
Слайд 4 Пример 2. Перестановка головы и хвоста массива без
использования промежуточного массива.
Алгоритм этой процедуры заключается в том,
что надо последовательно выполнить 3 инвертирования – головы массива, хвоста массива и всего массива целиком. Для этой цели воспользуемся модификацией ранее написанной процедурой invert:void invert1(int *a, int k, int n){
//k – индекс первого элемента инвертируемого фрагмента массива
//n – количество инвертируемых элементов
int j,tmp;
for(j=k; j
a[j]=a[2*k+n-j-1];
a[2*k+n-j-1]=tmp; }
}
Обработка числовых массивов
Слайд 5 Пример 2. Для проверки описанного выше алгоритма можно
воспользоваться следующей программой:
#include #include #define N 20
#define M 15void invert1(int *a, int k, int n);
void main()
{ int j,a[N];
printf("Before reverse:\n");
for(j=0; j
invert1(a,0,M);
printf("\nAfter reverse head:\n");
for(j=0; j
printf("\nAfter reverse tail:\n");
for(j=0; j
printf("\nAfter reverse all:\n");
for(j=0; j
}
Обработка числовых массивов
Слайд 6 Пример 3. Количество "счастливых" билетов. Билеты для общественного
транспорта хранятся в рулонах и идентифицируются номерами от 000000
до 999999. «Счастливым" считается билет, у которого сумма трех первых цифр совпадала с суммой трех последних цифр.Самый простой способ заключается в организации 6 вложенных друг в друга циклов, где каждый счетчик перебирает цифры от 0 до 9, а во внутреннем цикле сравниваются суммы первых трех и последних трех счетчиков:
#include
#include
{ int n=0;
for(int j1=0; j1<10; j1++) for(int j2=0; j2<10; j2++)
for(int j3=0; j3<10; j3++) for(int j4=0; j4<10; j4++)
for(int j5=0; j5<10; j5++) for(int j6=0; j6<10; j6++)
if(j1+j2+j3==j4+j5+j6) n++;
cout << n;
getch();
}
Обработка числовых массивов
Слайд 7 Работу этой программы можно ускорить почти в 1000
раз за счет использования массивов. Сумма трех цифр принадлежит
диапазону [0,27]. Допустим, мы подсчитали, сколько раз встретилась каждая сумма – s0 (количество сочетаний, давших сумму 0), s1 (количество сочетаний, давших сумму 1), ... . Тогда количество "счастливых" билетов будет равно (s0)2+(s1)
2+ ....
Поэтому гораздо более быстрой программой будет следующая:
#include
void main()
{ int n=0,k,s[28];
for(k=0; k<28; k++) s[k]=0;
for(int j1=0; j1<10; j1++)
for(int j2=0; j2<10; j2++)
for(int j3=0; j3<10; j3++) s[j1+j2+j3]++;
for(k=0; k<28; k++) n += s[k]*s[k];
cout << n;
getch();
}
Обработка числовых массивов
Слайд 8 Пример 4. Определение количества разных элементов в целочисленном
массиве.
Первый вариант программы основан на предварительной сортировке исходного
массива. После того как массив отсортирован, следует проанализировать соседние элементы и, как только встречается пара разных чисел, к счетчику надо добавлять 1.#include
void sort(int *a,int n)
{ int tmp;
for(int i=0;i
int difference(int *a,int n)
{ int i,m=1;
sort(a,n); //сортировка исходного массива
for(i=0; i
return m;
}
Обработка числовых массивов
Слайд 10 Вариант 2. При первом просмотре определяем, содержится ли
в исходном массиве хотя бы один нулевой элемент. Если
содержится, то в переменную k0 заносим 1, в противном случае в k0 заносим 0. При втором проходе нулевые элементы исключаем из рассмотрения и сравниваем a[i] c a[j]. В случае равенства в элемент a[i] заносим 0. При третьем проходе подсчитываем ненулевые элементы и добавляем к сумме k0. Мы ограничимся только видоизмененной функцией difference:int difference(int *a,int n)
{ int i,j,k0=0,m=0;
for(i=0; i
for(i=0; i
for(j=i+1; j
{ a[i]=0; break; } } //забой дубликата
for(i=0;i
return m+k0;
}
Обработка числовых массивов
Слайд 11
Пример 5. Вычисление нормы вектора.
#include
#include //здесь находится прототип
функции sqrt
#include
double norm(double *a, int n)
{ double s=0;
for(int i=0; i
void main()
{ double v1[5]={1.,2.,3.,4.,5.};
printf("norm=%f",norm(v1,5));
getch();}
//=== Результат работы ===norm=7.416198
Функцией norm можно воспользоваться и для того, чтобы вычислить "норму" любого фрагмента вектора – достаточно вместо первого аргумента задать адрес начальной компоненты (например, &v1[2] ), а в качестве второго аргумента количество обрабатываемых компонент.
Работа с векторами
Слайд 12
Пример 7. Нормирование вектора.
#include
#include //здесь находится прототип
функции sqrt
#include
void norm_vec(double *a, int n)
{ double s=0;
for(int i=0; i
for(int i=0; i
void main()
{ double v1[5]={1.,2.,3.,4.,5.};
norm_vec(v1,5);
for(int i=0;i<5;i++)
cout << v1[i]<< " ";
getch();
}
//=== Результат работы ===
0.13484 0.26968 0.40452 0.53936 0.6742
Работа с векторами
Слайд 13
Пример 8. Вычисление скалярного произведения двух векторов.
#include
#include
double scal_prod(double *a, double *b,int n)
{ double s=0;
for(int
i=0; i}
void main()
{ double v1[5]={1.,2.,3.,4.,5.}; printf("scal_prod=%f",
scal_prod(v1,v1,5));
getch();}
//=== Результат работы ===scal_prod=55.000000
Работа с векторами
Слайд 14
Пример 9. Сумма векторов.
#include
#include
void sum_vec(double *a,double
*b,double *c,int n)
{ for(int i=0; i
main(){ double v1[5]={1.,2.,3.,4.,5.};
double v2[5]={1.,0.,1.,0.,1.};
double v3[5];
sum_vec(v1,v2,v3,5);
for(int i=0;i<5;i++)
printf("%3.0f",v3[i]);
getch();
}
//=== Результат работы === 2 2 4 4 6
Работа с векторами
Слайд 15
Работа с матрицами
Работу с двумерными массивами можно организовать
двумя способами. Во-первых, операции над элементами двумерных массивов можно
свести к операциям над одномерными массивами, используя приведенные индексы. Во-вторых, можно воспользоваться указателями на строки матрицы (как известно, имя массива одновременно является указателем на ее первую строку).
Слайд 16
Работа с матрицами
Пример 10. Формирование единичной матрицы с
приведенными индексами.
#include
#include
#include
void eye(int *a, int n)
{
int i,j;for(i=0; i
else a[i*n+j]=0;
}
}
Слайд 17
Работа с матрицами
void main()
{ int i,j,v[5][5];
eye((int*)v,5);
for(i=0;i
{ for(j=0;j
printf("\n");}
getch();
}
//=== Результат работы
Слайд 18
Работа с матрицами
Пример 11. Сложение квадратных матриц.
Поскольку
в операции сложения участвуют n2 одноименных компонент матриц-слагаемых, то матрицы можно
рассматривать как длинные вектора и производить сложение как с векторами:#include
#include
#include
void add_mat(int *a,int *b,int *c,int n)
{ int i;
for(i=0; i
Слайд 19
Работа с матрицами
void main()
{ int i,j,v3[3][3];
int v1[3][3]={{1,2,3},{4,5,6},{7,8,9}};
int v2[3][3]={{0,0,1},{0,0,2},{0,0,3}};
add_mat((int*)v1,(int*)v2,(int*)v3,3);
for(i=0;i
printf("%3d",v3[i][j]);printf("\n");
}
getch();
}
//=== Результат работы ===
Слайд 20
Работа с матрицами
Пример 12. Умножение квадратных матриц с
использованием приведенных индексов.
#include
#include
void mult_mat(int *a,int *b,int *c,int
n){ int i,j,k,s;
for(i=0; i
for(k=0;k
c[i*n+j]=s; //ci,j=s
}
}
Слайд 21
Работа с матрицами
void main()
{ int i, j, v3[2][2];
int v1[2][2]={{1,2}, {3,4}};
int v2[2][2]={{5,6}, {7,8}};
mult_mat((int*)v1, (int*)v2,(int*)v3,2);
for(i=0;i
{ for(j=0;j<2;j++)printf("%4d",v3[i][j]);
printf("\n");
}
getch();
}
//=== Результат работы ===
Слайд 22
Работа с матрицами
Пример 13. Транспонирование матрицы с использованием
массива указателей на строки.
#include
#include
void transp(int *p[],int n)
{
int tmp,i,j;for(i=0; i
}
void main()
{ int v[4][4]={{ 1, 2, 3, 4},
{ 5, 6, 7, 8},
{ 9,10,11,12},
{13,14,15,16}};
Слайд 23
Работа с матрицами
//массив указателей на строки
int *p[4]={(int
*)&v[0],(int *)&v[1],(int *)&v[2],(int *)&v[3]};
transp(p,4);
for(int i=0; i
{ for(int j=0;j<4;j++)printf("%3d",v[i][j]);
printf("\n");
}
getch();
}
//=== Результат работы ===
Слайд 24
Работа с матрицами
Массив указателей p на строки двумерного массива v может быть
сформирован и другими способами:
int *p[4]={(int *)v,(int *)(v+1),(int *)(v+2),(int *)(v+3)};
int *p[4]={v[0],v[1],v[2],v[3]};
int *p[4]={*v,*(v+1),*(v+2),*(v+3)};
Очевидно, что указатель p[0] "смотрит" на элемент v[0][0]. Поэтому указатель p[0][1]=p[0]+1 "смотрит" на элемент v[0][1], указатель p[0][2] – на элемент v[0][2] и т.д. Можно было бы видоизменить заголовок функции transp следующим образом:
void transp(int **p,int n)
Все эти модификации ничего не меняют в алгоритмах работы программ.
Слайд 25
ПОИСК
Задача поиска формулируется следующим образом: задан массив a, содержащий n однотипных
элементов (чисел, строк, записей и т.п.). Нужно установить, содержится
ли в этом массиве заданный объект q. При положительном ответе следует дополнительно сообщить порядковый номер (индекс j ), найденного объекта ( a[j]=q ).
Слайд 26
Последовательный ПОИСК
Классический алгоритм последовательно поиска в неупорядоченном массиве состоит из
четырех следующих шагов:
шаг S1: Установить начальный индекс j=1 ;
шаг S2: Проверить
условие q=a[j]. Если условие выполнено, то решение найдено и работа прекращается;шаг S3: Увеличить индекс j на 1;
шаг S4: Проверить условие окончания цикла j
Слайд 27
Последовательный ПОИСК
Функция ssearch, реализующая последовательный поиск, устроена довольно просто:
int ssearch(int
q, int *a, int n)
{ register int j;
for(j=0; j
if(q==a[j]) return j;
return -1;
}
Слайд 28
Двоичный поиск
Двоичный поиск можно применить только в том
случае, если исходный массив упорядочен, например, по возрастанию величин
объектов. Тривиальные случаи типа q
Слайд 29
Двоичный поиск
Функция bsearch, реализующая двоичный поиск, может быть организована
следующим образом:
int bsearch(int q, int *a, int n)
{ register
int left=0,right=n-1,mid;if(q
for(;left<=right;)
{ mid=(left+right)/2;
if(q
else return mid;
}
return -1;
}
Максимальное количество шагов, которое требуется для двоичного поиска, оценивается ближайшим целым к log2n. Для массива в 1000 элементов прямой поиск в среднем затрачивает 500 шагов, тогда как двоичный поиск ограничивается 10 шагами.
Слайд 30
Сортировка массивов
сортировка методом пузырька
Идея метода состоит в сравнении
двух соседних элементов, в результате чего меньшее число (более
легкий "пузырек") перемещается на одну позицию влево. Обычно просмотр организуют с конца, и после первого прохода самое маленькое число перемещается на первое место. Затем все повторяется от конца массива до второго элемента и т.д. Известен и другой вариант пузырьковой сортировки, в котором также сравнивают два соседних элемента, и если хотя бы одна из смежных пар была переставлена, то просмотр начинают с самого начала
Слайд 31
сортировка методом пузырька
Функция bubble, реализующая первый алгоритм пузырьковой
сортировки приведена ниже:
void bubble(int *x, int n)
{ register int
i,j;int tmp;
for(i=1;i
if(x[j-1]>x[j])
{ tmp=x[j-1]; x[j-1]=x[j]; x[j]=tmp; }
}
Слайд 32
сортировка методом пузырька
Более известный алгоритм пузырьковой сортировки реализован
в функции bubble1. В ней использована флажковая переменнаяq, которая
принимает ненулевое значение в случае перестановки какой-либо смежной пары:void bubble1(int *x, int n)
{ register int i,j;
int tmp,q;
m: q=0;
for(i=1;i
{ tmp=x[i]; x[i]=x[i+1]; x[i+1]=tmp; q=1;}
if(q) goto m;
}
Пузырьковая сортировка эффективна, когда в исходных данных многие элементы уже упорядочены. Если исходный массив уже отсортирован, то работа функции ограничивается первым проходом. В худшем случае (массив упорядочен по убыванию) количество сравнений составляет n*(n-1)/2, а количество перестановок достигает 3*n*(n-1)/2. Среднее количество перестановок равно 3*n*(n-1)/4.
Слайд 33
сортировка методом отбора
Идея метода: находится элемент с наименьшим
значением и меняется местами с первым элементом. Среди оставшихся
элементов ищется наименьший, который меняется со вторым и т.д. Функция select, реализующая такую процедуру, приведена ниже:void select(int *x, int n)
{ register int i,j,k;
int q,tmp;
for(i=0; i
for(j=i+1; j
}
if(q) { x[k]=x[i]; x[i]=tmp; }
}
}
Слайд 34
сортировка методом отбора
Оценка трудоемкости метода отбора:
• количество сравнений –
n*(n-1)/2 ;
• количество перестановок:
o в лучшем случае – 3*(n-1)
o в худшем случае
– n2/4+3*(n-1)o в среднем – n*(log n +0.577216)
Слайд 35
сортировка методом вставки
Идея метода: последовательное пополнение ранее упорядоченных
элементов. На первом шаге сортируются два первых элемента. Затем
на свое место среди них вставляется третий элемент. К трем упорядоченным добавляется четвертый, который занимает свое место в четверке и т.д. Примерно так игроки упорядочивают свои карты при сдаче их по одной. Функция insert, реализующая описанную процедуру:void insert(int *x, int n)
{ register int i,j;
int tmp;
for(i=1;i
for(j=i-1;j>=0 && tmp
x[j+1]=tmp;
}
}
Трудоемкость метода: количество сравнений зависит от исходной упорядоченности массива. Если массив уже отсортирован, то все равно потребуется 2*(n-1) сравнение. Если массив упорядочен по убыванию, то число сравнений возрастает до n*(n+1)/2.
