Максимальный и минимальный элементы массива.сортировка

Пример 1. Поменять местами максимальный и минимальный элементы массива

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

Для решения задачи необходимо знать где находятся максимальный и минимальный элементы массива. Для этого вводятся две вспомогательные переменные, в которые заносятся индексы искомых элементов.

#include <iostream.h>

#include <iomanip.h>

#include <math.h>

main()

{ const int n=10;

int i,j,k,max,min,tmp,m[n]={6,3,1,5,9,-1,-9};

max=m[0];

min=m[0];

for(i=0;i<n;i++)

{ if(m[i]>max)

{ max=m[i]; j=i; }

if(m[i]<min)

{ min=m[i]; k=i; }

}

tmp=m[k];

m[k]=m[j];

m[j]=tmp;

cout<<min<<max;

}

Пример 2. Поиск максимального и минимального элементов в массиве в сочетании с условием отбора.

Поскольку необходим поиск min и max среди элементов массива, удовлетворяющих заданному условию, то величина первого такого элемента заранее неизвестна. Начальное значение переменной, в которой хранится min (max) должно быть заведомо большим (меньшим) , чем любой из элементов массива, удовлетворяющих заданному условию. В качестве начального значения может служить максимально возможная величина, представимая в ЭВМ для типа данных элементов массива. Эти значения имеют именованные константы, определеные в библиотеках limits.h для целых типов и float.h для вещественных типов.

Программа ,печатающая значения именованных констант

#include <iostream.h>

#include<iomanip.h>

#include<limits.h>

#include<float.h>

main()

{cout<<"LONG_MIN "<<LONG_MIN<<"LONG_MAX "<<LONG_MAX<<endl;

cout<<"FLT_MIN "<<FLT_MIN<<"FLT_MAX "<<FLT_MAX<<endl;

cout<<"DBL_MIN "<<DBL_MIN<<"DBL_MAX "<<DBL_MAX<<endl;

cout<<"LDBL_MIN "<<LDBL_MIN<<"LDBL_MAX "<<LDBL_MAX<<endl;

cout<<"FLT_DIG "<<FLT_DIG<<"FLT_EPSILON "<<FLT_EPSILON<<endl;

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

#include <iostream.h>

#include <iomanip.h>

#include <math.h>

#include <float.h>

main()

{ const int n=10;

double i,j,k,max,min,tmp,m[n]={6.,3.,1.,5.,9.,-1.,-9.};

min=DBL_MAX;

for(i=0;i<n;i++)

{ if(m[i]>0 && m[i]<min)

min=m[i];

}

cout<<min;

}

Пример 3. Сортировка массива методом “пузырька”

Вариант 1. Последовательным просмотром элементов массива m c индексом i от 0 до n-1 найдем наименьшее i, такое, что m[i]>m[i+1]. Поменяем местами m[i] и m[i+1] и возобновим просмотр с элемента m[i+1] и т. д. В результате самое большое число передвинется на последнее место. Следующие просмотры необходимо начинать с элемента с индексом 0, уменьшив на 1 количество просматриваемых элементов. Массив будет упорядочен после просмотра в котором участвовали первый и второй элементы.

#include <iostream.h>

#include <iomanip.h>

#include <math.h>

main()

{int i,j,n,k,max,min,tmp,m[10]={6,3,1,5,9,-1,-9,7,2,0};

n=10;

for(i=0;i<n-1;i++)

for(j=0;j<n-1-i;j++)

if(m[j]>m[j+1])

{ tmp=m[j];

m[j]=m[j+1];

m[j+1]=tmp; }

for(i=0;i<n;i++)

cout<<setw(3)<<m[i];

}

Вариант 2. Недостатком алгоритма первого варианта является независимость количества действий от степени упорядоченности элементов массива . Даже для полностью упорядоченного массива количество выполненных операций будет пропорционально n². метод сортировки можно улучшить, использовав в качестве признака окончания сортировки значение вспомогательной переменной. Вспомогательная переменная будет иметь отличную от нуля величину, если в результате просмотра всего массива произошел обмен хотя бы одной пары элементов.

#include <iostream.h>

#include <iomanip.h>

#include <math.h>

main()

{ const int n=10;

int i,j,k,tmp,m[n]={6,3,1,5,9,-1,-9,7,2,0};

i=1;

while(i>0)

{ i=0;

for(j=0;j<n-1;j++)

if(m[j]>m[j+1])

{ tmp=m[j];

m[j]=m[j+1];

m[j+1]=tmp;

i=1;

}

}

for(i=0;i<n;i++)

cout<<setw(3)<<m[i];

}

Пример 4. Бинарный поиск в упорядоченном массиве

При бинарном поиске искомое значение х сначала сравнивается с элементом в середтне массива. Если х меньше, чем это значение, то областью поиска становится верхняя половина массива, в противном случае – нижняя. Процесс половинного деления продолжается до тех пор ,пока либо будет найдено значение, совпадающее с х, либо диапазон поиска станет пустым. Поскольку на каждом шаге диапазон поиска уменьшается в два раза ,то общее количество необходимых операций будет пропорционально log₂n, где n – размерность массива.

#include<iostream.h>

#include<iomanip.h>

#include<conio.h>

void main()

{ clrscr();

const int n=9;

float m[n]={1,2,3,4,5,6,7,8,9};

float x;

int end=1;

cin>>x;

int i=0,j=n,k;

while (j>i && end!=0)

{ k=(i+j)/2;

if(m[k]>x)

j=k;

else if( m[k]<x)

i=k;

else end=0;

}

if(end==0) cout<<k;

else cout<<"no"<<endl;

}

Упражнения

1. Даны пять различных целых чисел. Упорядочить их по возрастанию, используя не более семи сравнений.

2. Определить упорядочены ли элементы массива

3. Заданы координаты n точек на плоскости. Найти прямоугольник , объемлющий все эти точки.

4. Поменять местами максимальный отрицательный и минимальный положительный элементы массива

5. Вывести на экран элементы массива целых чисел, имеющих максимальное количество делителей.

6. Вывести на экран элементы массива целых чисел, имеющих максимальную сумму цифр.

7. Вывести на экран в порядке возрастания четные элементы массива

8. Вывести на экран различные элементы массива целых чисел в порядке возрастания их числа повторения.

9. Вывести на экран элементы массива целых чисел в порядке возрастания их числа делителей.

10. Вывести на экран элементы массива целых чисел в порядке возрастания их суммы цифр.

11. Найти методом бинарного поиска в упорядоченном массиве местонахождения всех чисел от 0 до 9.

12. Заданы два одномерных упорядоченных массива а и b. Найти методом бинарного поиска все элементы массива а, которые не входят в массив b.

13. Заданы два одномерных упорядоченных массива а и b. Вывести на экран различные элементы массива а в порядке появления их в массиве b.

14. Заданы два одномерных упорядоченных массива а и b. Вывести на экран различные элементы массива а в порядке обратном появлению их в массиве b.

15. Заданы два одномерных упорядоченных массива а и b. Получить новый массив, состоящий из чисел массивов а и b без повторений, упорядоченный по возрастанию.

16. Заданы два одномерных упорядоченных массива размерностью m и n соответственно. Образовать из этих элементов упорядоченный массив размерностью m+n

17. Упорядочить массив, используя алгоритм сортировки слиянием упорядоченных групп элементов массива. Вначале весь массив рассматривается как совокупность упорядоченных групп по одному элементу в каждом. Слиянием соседних групп получаем упорядоченные группы, каждая из которых содержит два элемента. Далее упорядоченные группы укрупняются тем же способом и т.д. Алгоритм предполагает использование вспомогательного массива.

18. Упорядочить массив, используя алгоритм сортировки выбором: отыскивается максимальный элемент и переносится в конец массива; затем этот метод применяется ко всем элементам , кроме последнего (он уже находится на своем окончательном месте), и т.д.

19. Упорядочить массив, используя алгоритм сортировки вставками: пусть первые n элементов уже упорядочены; берется (n+1)-й элемент и с помощью последовательного просмотра размещается среди первых n элементов так, чтобы упорядоченными оказались уже (n+1) первых элементов, и т.д.

20. Упорядочить массив, используя алгоритм сортировки бинарными вставками , в котором место размещения элемента в упорядоченном отрезке массива определяется методом бинарного поиска.

21. Дана ведомость зарплаты сотрудников, в которой указаны табельный номер сотрудников и зарплата каждого. Вывести на экран список табельных номеров сотрудников в порядке увеличения их зарплаты.

22. В налоговой инспекции составлен реестр налогоплатильщиков, в котором для каждого из них указаны фамилия и сумма уплаченного налога. Упорядочить налогоплатильщиков по убыванию налоговой суммы.

23. В деканате составлена ведомость , в которой указаны фамилия студентов, название предметов и количество прогулов по каждому предмету. Вывести на экран фамилии студентов имеющих максимальное суммарное число прогулов по всем предметам.

24. В деканате составлена ведомость , в которой указаны фамилия студентов, название предметов и количество прогулов по каждому предмету. Вывести на экран фамилии студентов в порядке увеличения их суммарного числа прогулов по всем предметам.

25. Дана таблица стран-участниц олимпийских игр с указанием для каждой из них количества завоеванных золотых серебряных и бронзовых медалей. Упорядочить все страны по убыванию количества золотых медалей. Из двух стран с одинаковым числом золотых медалей выше должна оказаться страна, у которой больше серебряных медалей. Если и здесь равенство, то преимущество должна иметь страна с большим числом бронзовых медалей.

Поиск по сайту: