Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Обработка массивов

Содержание

Обработка числовых массивовПример 1. Переворот одномерного целочисленного массива – перестановка его элементов в обратном порядке. Выделим в отдельную функцию процедуру инвертирования:void invert(int *a,int n){ for(int j=0,tmp; j
Обработка массивов Обработка числовых массивовПример 1. Переворот одномерного целочисленного массива – перестановка его элементов Обработка числовых массивовДля проверки ее работоспособности можно воспользоваться следующей программой:#include #include #define Пример 2. Перестановка головы и хвоста массива без использования промежуточного массива. Алгоритм Пример 2. Для проверки описанного выше алгоритма можно воспользоваться следующей программой: #include Пример 3. Количество Работу этой программы можно ускорить почти в 1000 раз за счет использования Пример 4. Определение количества разных элементов в целочисленном массиве. Первый вариант программы Обработка числовых массивов Вариант 2. При первом просмотре определяем, содержится ли в исходном массиве хотя Пример 5. Вычисление нормы вектора.#include #include //здесь находится прототип функции sqrt#include double norm(double Пример 7. Нормирование вектора.#include #include //здесь находится прототип функции sqrt#include void norm_vec(double Пример 8. Вычисление скалярного произведения двух векторов.#include #include double scal_prod(double *a, double Пример 9. Сумма векторов.#include #include void sum_vec(double *a,double *b,double *c,int n) { for(int i=0; i Работа с матрицамиРаботу с двумерными массивами можно организовать двумя способами. Во-первых, операции Работа с матрицамиПример 10. Формирование единичной матрицы с приведенными индексами.#include #include #include Работа с матрицамиvoid main(){ int i,j,v[5][5]; eye((int*)v,5); for(i=0;i Работа с матрицамиПример 11. Сложение квадратных матриц. Поскольку в операции сложения участвуют n2 одноименных Работа с матрицами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 Работа с матрицамиПример 12. Умножение квадратных матриц с использованием приведенных индексов.#include #include Работа с матрицамиvoid main(){ int i, j, v3[2][2]; int v1[2][2]={{1,2}, {3,4}}; int Работа с матрицамиПример 13. Транспонирование матрицы с использованием массива указателей на строки.#include Работа с матрицами//массив указателей на строки int *p[4]={(int *)&v[0],(int *)&v[1],(int *)&v[2],(int *)&v[3]}; transp(p,4); for(int i=0; i Работа с матрицамиМассив указателей p на строки двумерного массива v может быть сформирован и другими способами:int ПОИСКЗадача поиска формулируется следующим образом: задан массив a, содержащий n однотипных элементов (чисел, строк, записей Последовательный ПОИСККлассический алгоритм последовательно поиска в неупорядоченном массиве состоит из четырех следующих шагов:шаг S1: Последовательный ПОИСКФункция ssearch, реализующая последовательный поиск, устроена довольно просто:int ssearch(int q, int *a, int Двоичный поискДвоичный поиск можно применить только в том случае, если исходный массив Двоичный поискФункция bsearch, реализующая двоичный поиск, может быть организована следующим образом:int bsearch(int q, Сортировка массивов сортировка методом пузырькаИдея метода состоит в сравнении двух соседних элементов, сортировка методом пузырькаФункция bubble, реализующая первый алгоритм пузырьковой сортировки приведена ниже:void bubble(int сортировка методом пузырькаБолее известный алгоритм пузырьковой сортировки реализован в функции bubble1. В сортировка методом отбораИдея метода: находится элемент с наименьшим значением и меняется местами сортировка методом отбораОценка трудоемкости метода отбора:• количество сравнений – n*(n-1)/2 ;• количество перестановок:o в лучшем сортировка методом вставкиИдея метода: последовательное пополнение ранее упорядоченных элементов. На первом шаге сортировка методом вставкиИдея метода: последовательное пополнение ранее упорядоченных элементов. На первом шаге
Слайды презентации

Слайд 2 Обработка числовых массивов
Пример 1. Переворот одномерного целочисленного массива

Обработка числовых массивовПример 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

следующей программой:
#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 { a[j]=j+1; printf("%3d",a[j]); }
invert(a,N);
printf("\nAfter reverse:\n");
for(j=0; jgetch();
}

Слайд 4 Пример 2. Перестановка головы и хвоста массива без

Пример 2. Перестановка головы и хвоста массива без использования промежуточного массива.

использования промежуточного массива.
Алгоритм этой процедуры заключается в том,

что надо последовательно выполнить 3 инвертирования – головы массива, хвоста массива и всего массива целиком. Для этой цели воспользуемся модификацией ранее написанной процедурой invert:
void invert1(int *a, int k, int n){
//k – индекс первого элемента инвертируемого фрагмента массива
//n – количество инвертируемых элементов
int j,tmp;
for(j=k; j { tmp=a[j];
a[j]=a[2*k+n-j-1];
a[2*k+n-j-1]=tmp; }
}

Обработка числовых массивов

Слайд 5 Пример 2. Для проверки описанного выше алгоритма можно

Пример 2. Для проверки описанного выше алгоритма можно воспользоваться следующей программой: #include

воспользоваться следующей программой:
#include #include #define N 20

#define M 15
void invert1(int *a, int k, int n);
void main()
{ int j,a[N];
printf("Before reverse:\n");
for(j=0; j { a[j]=j+1; printf("%3d",a[j]); }
invert1(a,0,M);
printf("\nAfter reverse head:\n");
for(j=0; j invert1(a,M,N-M);
printf("\nAfter reverse tail:\n");
for(j=0; j invert1(a,0,N);
printf("\nAfter reverse all:\n");
for(j=0; j getch();
}  

Обработка числовых массивов

Слайд 6 Пример 3. Количество "счастливых" билетов. Билеты для общественного

Пример 3. Количество

транспорта хранятся в рулонах и идентифицируются номерами от 000000

до 999999. «Счастливым" считается билет, у которого сумма трех первых цифр совпадала с суммой трех последних цифр.
Самый простой способ заключается в организации 6 вложенных друг в друга циклов, где каждый счетчик перебирает цифры от 0 до 9, а во внутреннем цикле сравниваются суммы первых трех и последних трех счетчиков:
#include
#include void main()
{ 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

Работу этой программы можно ускорить почти в 1000 раз за счет

раз за счет использования массивов. Сумма трех цифр принадлежит

диапазону [0,27]. Допустим, мы подсчитали, сколько раз встретилась каждая сумма – s0 (количество сочетаний, давших сумму 0), s1 (количество сочетаний, давших сумму 1), ... . Тогда количество "счастливых" билетов будет равно (s0)
2+(s1)
2+ ....
Поэтому гораздо более быстрой программой будет следующая:
#include #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. Определение количества разных элементов в целочисленном

Пример 4. Определение количества разных элементов в целочисленном массиве. Первый вариант

массиве.
Первый вариант программы основан на предварительной сортировке исходного

массива. После того как массив отсортирован, следует проанализировать соседние элементы и, как только встречается пара разных чисел, к счетчику надо добавлять 1.
#include #include
void sort(int *a,int n)
{ int tmp;
for(int i=0;i for(int j=i+1;j if(a[j]}
int difference(int *a,int n)
{ int i,m=1;
sort(a,n); //сортировка исходного массива
for(i=0; i if(a[i]!=a[i+1]) m++;
return m;
}

Обработка числовых массивов

Слайд 9 Обработка числовых массивов

Обработка числовых массивов

Слайд 10 Вариант 2. При первом просмотре определяем, содержится ли

Вариант 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 if(a[i]==0) { k0=1; break; } //поиск нулевого элемента
for(i=0; i { if(a[i]==0) continue; //обход нулей
for(j=i+1; j if(a[i]==a[j])
{ a[i]=0; break; } } //забой дубликата
for(i=0;i if(a[i]!=0) m++;
return m+k0;
}

Обработка числовых массивов

Слайд 11 Пример 5. Вычисление нормы вектора.
#include
#include //здесь находится прототип

Пример 5. Вычисление нормы вектора.#include #include //здесь находится прототип функции sqrt#include double

функции sqrt
#include
double norm(double *a, int n)
{ double s=0;


for(int i=0; i return sqrt(s);}
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 //здесь находится прототип

Пример 7. Нормирование вектора.#include #include //здесь находится прототип функции sqrt#include void

функции sqrt
#include
void norm_vec(double *a, int n)
{ double s=0;


for(int i=0; i s= sqrt(s);
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

Пример 8. Вычисление скалярного произведения двух векторов.#include #include double scal_prod(double *a,


double scal_prod(double *a, double *b,int n)
{ double s=0;
for(int

i=0; i return s;
}
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

Пример 9. Сумма векторов.#include #include void sum_vec(double *a,double *b,double *c,int n) { for(int i=0; i

*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. Формирование единичной матрицы с

Работа с матрицамиПример 10. Формирование единичной матрицы с приведенными индексами.#include #include

приведенными индексами.
#include
#include
#include
void eye(int *a, int n)
{

int i,j;
for(i=0; i for(j=0; j { if(i==j) a[i*n+j]=1;
else a[i*n+j]=0;
}
}

Слайд 17 Работа с матрицами
void main()
{ int i,j,v[5][5];
eye((int*)v,5);
for(i=0;i

Работа с матрицами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. Сложение квадратных матриц.
Поскольку

Работа с матрицамиПример 11. Сложение квадратных матриц. Поскольку в операции сложения

в операции сложения участвуют n2 одноименных компонент матриц-слагаемых, то матрицы можно

рассматривать как длинные вектора и производить сложение как с векторами:
#include
#include
#include
void add_mat(int *a,int *b,int *c,int n)
{ int i;
for(i=0; i c[i]=a[i]+b[i];}

Слайд 19 Работа с матрицами
void main()
{ int i,j,v3[3][3];
int v1[3][3]={{1,2,3},{4,5,6},{7,8,9}};

Работа с матрицами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

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. Умножение квадратных матриц с

Работа с матрицамиПример 12. Умножение квадратных матриц с использованием приведенных индексов.#include

использованием приведенных индексов.
#include
#include
void mult_mat(int *a,int *b,int *c,int

n)
{ int i,j,k,s;
for(i=0; i for(j=0; j { s=0;
for(k=0;k s += a[i*n+k]*b[k*n+j]; //s=s+ai,k*bk,j
c[i*n+j]=s; //ci,j=s
}
}

Слайд 21 Работа с матрицами
void main()
{ int i, j, v3[2][2];

Работа с матрицамиvoid main(){ int i, j, v3[2][2]; int v1[2][2]={{1,2}, {3,4}};

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. Транспонирование матрицы с использованием

Работа с матрицамиПример 13. Транспонирование матрицы с использованием массива указателей на

массива указателей на строки.
#include
#include
void transp(int *p[],int n)
{

int tmp,i,j;
for(i=0; i for(j=i+1; j { tmp=p[i][j]; p[i][j]=p[j][i]; p[j][i]=tmp; }
}
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

Работа с матрицами//массив указателей на строки int *p[4]={(int *)&v[0],(int *)&v[1],(int *)&v[2],(int *)&v[3]}; transp(p,4); for(int i=0; i

*)&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 может быть

Работа с матрицамиМассив указателей 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 однотипных

ПОИСКЗадача поиска формулируется следующим образом: задан массив a, содержащий n однотипных элементов (чисел, строк,

элементов (чисел, строк, записей и т.п.). Нужно установить, содержится

ли в этом массиве заданный объект q. При положительном ответе следует дополнительно сообщить порядковый номер (индекс j ), найденного объекта ( a[j]=q ).

Слайд 26 Последовательный ПОИСК
Классический алгоритм последовательно поиска в неупорядоченном массиве состоит из

Последовательный ПОИСККлассический алгоритм последовательно поиска в неупорядоченном массиве состоит из четырех следующих шагов:шаг

четырех следующих шагов:
шаг S1: Установить начальный индекс j=1 ;
шаг S2: Проверить

условие q=a[j]. Если условие выполнено, то решение найдено и работа прекращается;
шаг S3: Увеличить индекс j на 1;
шаг S4: Проверить условие окончания цикла jТрудоемкость классического последовательного поиска можно оценить только в среднем. В лучшем случае первое же сравнение может дать ответ ( q=a[1] ). В худшем случае придется перебрать все n элементов. В среднем на поиск будет затрачено n/2сравнений.


Слайд 27 Последовательный ПОИСК
Функция ssearch, реализующая последовательный поиск, устроена довольно просто:
int ssearch(int

Последовательный ПОИСКФункция ssearch, реализующая последовательный поиск, устроена довольно просто:int ssearch(int q, int *a,

q, int *a, int n)
{ register int j;
for(j=0; j


if(q==a[j]) return j;
return -1;
}

Слайд 28 Двоичный поиск
Двоичный поиск можно применить только в том

Двоичный поискДвоичный поиск можно применить только в том случае, если исходный

случае, если исходный массив упорядочен, например, по возрастанию величин

объектов. Тривиальные случаи типа qa[n] не рассматриваются, хотя ничего не стоит подключить к поиску и такие проверки. Идея двоичного поиска заключается в уменьшении вдвое зоны поиска на каждом шаге (отсюда и второе название метода – деление пополам). Сначала искомый объект q сравнивается со средним элементом массива. В зависимости от результата сравнения на следующий шаг остается первая или вторая половина массива. Оставшаяся половина вновь делится на 2, и так продолжается до тех пор, пока зона поиска не сузится до двух элементов. В этом случае либо объект q совпадает с одним из этих элементов, либо продолжает сохраняться строгое неравенство с обеими границами.

Слайд 29 Двоичный поиск
Функция bsearch, реализующая двоичный поиск, может быть организована

Двоичный поискФункция bsearch, реализующая двоичный поиск, может быть организована следующим образом:int bsearch(int

следующим образом:
int bsearch(int q, int *a, int n)
{ register

int left=0,right=n-1,mid;
if(qa[n-1]) return -1;
for(;left<=right;)
{ mid=(left+right)/2;
if(qelse if(q>a[mid]) left=mid+1;
else return mid;
}
return -1;
}
Максимальное количество шагов, которое требуется для двоичного поиска, оценивается ближайшим целым к log2n. Для массива в 1000 элементов прямой поиск в среднем затрачивает 500 шагов, тогда как двоичный поиск ограничивается 10 шагами.

Слайд 30 Сортировка массивов сортировка методом пузырька
Идея метода состоит в сравнении

Сортировка массивов сортировка методом пузырькаИдея метода состоит в сравнении двух соседних

двух соседних элементов, в результате чего меньшее число (более

легкий "пузырек") перемещается на одну позицию влево. Обычно просмотр организуют с конца, и после первого прохода самое маленькое число перемещается на первое место. Затем все повторяется от конца массива до второго элемента и т.д. Известен и другой вариант пузырьковой сортировки, в котором также сравнивают два соседних элемента, и если хотя бы одна из смежных пар была переставлена, то просмотр начинают с самого начала

Слайд 31 сортировка методом пузырька
Функция bubble, реализующая первый алгоритм пузырьковой

сортировка методом пузырькаФункция bubble, реализующая первый алгоритм пузырьковой сортировки приведена ниже:void

сортировки приведена ниже:
void bubble(int *x, int n)
{ register int

i,j;
int tmp;
for(i=1;i for(j=n-1;j>=i; j--)
if(x[j-1]>x[j])
{ tmp=x[j-1]; x[j-1]=x[j]; x[j]=tmp; }
}

Слайд 32 сортировка методом пузырька
Более известный алгоритм пузырьковой сортировки реализован

сортировка методом пузырькаБолее известный алгоритм пузырьковой сортировки реализован в функции bubble1.

в функции bubble1. В ней использована флажковая переменнаяq, которая

принимает ненулевое значение в случае перестановки какой-либо смежной пары:
void bubble1(int *x, int n)
{ register int i,j;
int tmp,q;
m: q=0;
for(i=1;i if(x[i]>x[i+1])
{ 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 { q=0; k=i; tmp=x[i];
for(j=i+1; j { if(x[j] { k=j; tmp=x[j]; q=1; }
}
if(q) { x[k]=x[i]; x[i]=tmp; }
}
}

Слайд 34 сортировка методом отбора
Оценка трудоемкости метода отбора:
• количество сравнений –

сортировка методом отбораОценка трудоемкости метода отбора:• количество сравнений – n*(n-1)/2 ;• количество перестановок:o в

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 { tmp=x[i];
for(j=i-1;j>=0 && tmp x[j+1]=x[j];
x[j+1]=tmp;
}
}
Трудоемкость метода: количество сравнений зависит от исходной упорядоченности массива. Если массив уже отсортирован, то все равно потребуется 2*(n-1) сравнение. Если массив упорядочен по убыванию, то число сравнений возрастает до n*(n+1)/2.

  • Имя файла: obrabotka-massivov.pptx
  • Количество просмотров: 133
  • Количество скачиваний: 0
- Предыдущая Михаил Васильевич Ломоносов
Следующая - Discover the USA

Похожие презентации

Консультация для родителей Почемучки консультация Консультация для родителей Почемучки консультация 86
nash tsentr prirody nash tsentr prirody 134
Иунæг зæрдæйы уарзт… Иунæг зæрдæйы уарзт… 118
Мы здоровью скажем - ДА! презентация Мы здоровью скажем - ДА! презентация 228
Название улиц г.Можайска. Улица 20 Января. презентация к уроку (старшая группа) по теме Название улиц г.Можайска. Улица 20 Января. презентация к уроку (старшая группа) по теме 126
Доклад на общешкольном родительском собрании Учимся быть терпимыми (о толерантности). презентация к уроку (1 класс) Доклад на общешкольном родительском собрании Учимся быть терпимыми (о толерантности). презентация к уроку (1 класс) 113
Дагестанский стоматологический институт Дагестанский стоматологический институт 128
Металлы. Металлы. 98
Руководство по прохождению тестирования в рамках модуля Педагогическая аттестация методическая разработка Руководство по прохождению тестирования в рамках модуля Педагогическая аттестация методическая разработка 98
12 Календарное планирование по теме: Кто как готовится к зиме по ФГОС подготовительная группа календарно-тематическое планирование по теме 12 Календарное планирование по теме: Кто как готовится к зиме по ФГОС подготовительная группа календарно-тематическое планирование по теме 219
Внедрение технологии раннего выявления детского неблагополучия, профилактика детских суицидов и жестокого обращения с несовершеннолетними Внедрение технологии раннего выявления детского неблагополучия, профилактика детских суицидов и жестокого обращения с несовершеннолетними 90
Детский мастер – класс как способ развития инициативы и самостоятельности в дошкольном возрасте презентация урока для интерактивной доски (подготовительная группа) Детский мастер – класс как способ развития инициативы и самостоятельности в дошкольном возрасте презентация урока для интерактивной доски (подготовительная группа) 41
Методы оценки персонала Методы оценки персонала 101
Программная инженерия Программная инженерия 136
Стихи Каниболоцкого Александра Стихи Каниболоцкого Александра 107
Выкуп долга Выкуп долга 127
Открытое занятие Воспитателя Дрожжиной О.В. Животные севера презентация к уроку (старшая группа) Открытое занятие Воспитателя Дрожжиной О.В. Животные севера презентация к уроку (старшая группа) 100
Презентация для осуществления совместной деятельности детей и взрослых по теме: Зима.зимние забавы. Технология дистанционного обучения презентация урока для интерактивной доски (старшая группа) Презентация для осуществления совместной деятельности детей и взрослых по теме: Зима.зимние забавы. Технология дистанционного обучения презентация урока для интерактивной доски (старшая группа) 83
Презентация к конкурсу педмастерства презентация по теме Презентация к конкурсу педмастерства презентация по теме 98
Анализ элементной базы устройств технического зрения и разработка роботизированной системы контроля качеста продукции Анализ элементной базы устройств технического зрения и разработка роботизированной системы контроля качеста продукции 108
Виды маркетинга: Виды маркетинга: 98
Документооборот при приеме на работу Документооборот при приеме на работу 93
СУПЕР АКЦИЯ ГОДА15марта – 15 июня 2013 СУПЕР АКЦИЯ ГОДА15марта – 15 июня 2013 71
Технология проектирования учебного занятия в контексте введения ФГОС Технология проектирования учебного занятия в контексте введения ФГОС 97
День рождения - праздник детства! День рождения - праздник детства! 108
Проект деревья осенью проект (средняя группа) по теме Проект деревья осенью проект (средняя группа) по теме 158
Руслан,с днём рождения! Руслан,с днём рождения! 102
Особенности сушки зерна Особенности сушки зерна 125
Оценка работ учащихся Оценка работ учащихся 106
The life and poetry of thomas hardy The life and poetry of thomas hardy 148