2015-07-14
443
Задача поиска «самого-самого» всегда актуальна. Кто из футболистов забил больше всего голов? У кого самая большая зарплата? Кто имеет максимальный рейтинг? Подобные вопросы возникают повсюду, но далеко не все представляют себе алгоритм нахождения этих «звезд». Мы изучим этот алгоритм на примере поиска максимального элемента в целочисленном массиве, а распространить его на перечисленные выше задачи не составит труда.
Для поиска максимального элемента в массиве существует стандартный алгоритм, который заключается в том, что заводится переменная (назовем ее max), которая инициализируется первым элементом массива, а затем в цикле переприсваивается очередным элементом массива, если он больше ее.
int max = numbers[0];
for (int i=1; i<size; i++) {
if (max < numbers[i]) {
max = numbers[i];
}
}
Заметим, что часто переменную max инициализируют не первым элементом, а некоторым «очень маленьким числом», а цикл начинают не с 1, а с 0. Подобный алгоритм выглядит так:
int max = -1000000;
for (int i=0; i<size; i++) {
if (max < numbers[i]) {
|
|
|
max = numbers[i];
}
}
Однако данный подход нежелателен, поскольку нет гарантии, что число меньше «очень маленького числа» не встретится, и, кроме того, выполняется одно лишнее сравнение. Полный пример поиска максимума выглядит так:
#define MAX_SIZE 100
int main() {
int numbers[MAX_SIZE];
printf("Введите размер массива: ");
int size;
scanf("%d", &size);
for (int i=0; i<size; i++) {
numbers[i] = rand()%100;
}
printf("Задан следующий массив:\n");
for (int i=0; i<size; i++) {
printf("%d ", numbers[i]);
}
printf("\n");
int max = numbers[0];
for (int i=1; i<size; i++) {
if (max < numbers[i]) {
max=numbers[i];
}
}
printf("Максимальный элемент = %d\n", max);
return 0;
}
Если требуется найти не максимальный элемент, а его индекс, то программа несколько изменится:
int ind_max = 0;
for (int i=1; i<size; i++) {
if (numbers[ind_max] < numbers[i]) {
ind_max = i;
}
}
