Задача поиска «самого-самого» всегда актуальна. Кто из футболистов забил больше всего голов? У кого самая большая зарплата? Кто имеет максимальный рейтинг? Подобные вопросы возникают повсюду, но далеко не все представляют себе алгоритм нахождения этих «звезд». Мы изучим этот алгоритм на примере поиска максимального элемента в целочисленном массиве, а распространить его на перечисленные выше задачи не составит труда.
Для поиска максимального элемента в массиве существует стандартный алгоритм, который заключается в том, что заводится переменная (назовем ее 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];
}
}
Однако данный подход нежелателен, поскольку нет гарантии, что число меньше «очень маленького числа» не встретится, и, кроме того, выполняется одно лишнее сравнение. Полный пример поиска максимума выглядит так:
#include <clocale>
#include <iostream>
using namespace std;
#define MAX_SIZE 100
int main() {
setlocale(LC_ALL, "Russian");
int numbers[MAX_SIZE];
cout << "Введите размер массива: ";
int size;
cin >> size;
for (int i=0; i<size; i++) {
numbers[i] = rand()%100;
}
cout << "Задан следующий массив:\n";
for (int i=0; i<size; i++) {
cout << numbers[i] << " ";
}
cout << endl;
int max = numbers[0];
for (int i=1; i<size; i++) {
if (max < numbers[i]) {
max=numbers[i];
}
}
cout << "Максимальный элемент = " << max << endl;
system("pause");
return 0;
}
Если требуется найти не максимальный элемент, а его индекс, то программа несколько изменится:
int ind_max = 0;
for (int i=1; i<size; i++) {
if (numbers[ind_max] < numbers[i]) {
ind_max = i;
}
}
Примеры решения задач
Задача 1. Написать программу, которая принимает с клавиатуры число N, задает массив из N случайных целых чисел и выводит его на экран. Затем необходимо вывести элементы этого массива, которые не принадлежат отрезку [5,15].
#include "stdafx.h"
#include <clocale>
#include <iostream>
using namespace std;
int main() {
setlocale(LC_ALL, "Russian");
int N;
cout << "Введите число N:\n";
cin >> N;
int numbers[100];
for (int i=0; i<N; i++) {
numbers[i] = rand()%50;
}
for (int i=0; i<N; i++) {
cout << numbers[i] << " ";
}
cout << "\nЭлементы из отрезка [5,15]:\n";
for (int i=0; i<N; i++) {
if (5<=numbers[i] && numbers[i]<=15) {
cout << numbers[i] << " ";
}
}
cout << endl;
system("pause");
return 0;
}
Задача 2. Написать программу, которая принимает с клавиатуры число N, задает массив из N случайных целых чисел и выводит его. Затем необходимо подсчитать количество трехзначных элементов этого массива.
#include "stdafx.h"
#include <clocale>
#include <iostream>
using namespace std;
int main() {
setlocale(LC_ALL, "Russian");
int N;
cout << "Введите число N:\n";
cin >> N;
int numbers[100];
for (int i=0; i<N; i++) {
numbers[i] = rand()%2000;
}
for (int i=0; i<N; i++) {
cout << numbers[i] << " ";
}
cout << "\n";
int digits3 = 0;
for (int i=0; i<N; i++) {
if (100<=numbers[i] && numbers[i]<=999) {
digits3++;
}
}
cout << "Число трехзначных чисел = " << digits3;
cout << "\n";
system("pause");
return 0;
}
Задача 4. Написать программу, которая принимает с клавиатуры число N, задает массив из N случайных целых чисел и выводит его. Затем необходимо отсортировать его методом прямого выбора по убыванию.
#include "stdafx.h"
#include <clocale>
#include <iostream>
using namespace std;
int main() {
setlocale(LC_ALL, "Russian");
int N;
cout << "Введите число N:\n";
cin >> N;
int numbers[100];
for (int i=0; i<N; i++) {
numbers[i] = rand()%100;
}
cout << "\nИсходный массив:\n";
for (int i=0; i<N; i++) {
cout << numbers[i] << " ";
}
for (int i=0; i<N-1; i++) {
int max_index = i;
for (int j=i+1; j<N; j++) {
if (numbers[max_index]<numbers[j]) {
max_index = j;
}
}
int temp = numbers[i];
numbers[i] = numbers[max_index];
numbers[max_index] = temp;
}
cout << "\nОтсортированный массив:\n";
for (int i=0; i<N; i++) {
cout << numbers[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
ВОПРОСЫ ДЛЯ САМОПРОВЕРКИ
1. Объясните своими словами, зачем нужны массивы.
2. Опишите алгоритм поиска максимального (минимального) элемента в массиве.
3. Объясните своими словами, зачем сортировать данные.
4. Опишите алгоритм метода прямого выбора.
5. Опишите алгоритм пузырьковой сортировки.
6. Опишите алгоритм сортировки вставками.
7. Описать алгоритм последовательного поиска.
8. Опишите алгоритм двоичного поиска. Каким должен быть массив для его применения?
9. Как вывести матрицу на экран, чтобы столбцы были ровными.
10. Как вывести на экран диагональные элементы матрицы?
