Вычисление суммы элементов массива
Дан массив X, состоящий из n элементов. Найти сумму элементов этого массива. Процесс накапливания суммы элементов массива достаточно прост и практически ничем не отличается от суммирования значений некоторой числовой последовательности. Переменной S присваивается значение равное нулю, затем последовательно суммируются элементы массива X. Блок-схема алгоритма расчета суммы перед вами:
Соответствующий фрагмент алгоритма программы будет иметь вид:
for (S=0, i=0; i<N; S+=X[i], i++); cout<<"S="<<"\n";
Поиск максимального элемента в массиве
Дан массив X, состоящий из n элементов. Найти максимальный элемент массива и номер, под которым он хранится в массиве.
Алгоритм решения задачи следующий. Пусть в переменной с именем Max хранится значение максимального элемента, а в переменной Nmax — его номер. Предположим, что нулевой элемент массива является максимальным и запишем его в переменную Max, а в Nmax — его номер (ноль). Затем все элементы начиная с первого сравниваем в цикле с максимальным. Если текущий элемент массива оказывается больше максимального, то записываем его в переменную Max, а в переменную Nmax — текущее значение индекса i.
Все выше описанное можно представить следующим фрагментом кода:
for (Max=X[0], Nmax=0, i=0; i<n; i++)
if (Max<X[i])
{
Max=X[i];
Nmax=i;
}
cout<<"Max="<<Max<<"\n";
cout<<"Nmax="<<Nmax<<"\n";
Алгоритм поиска минимального элемента в массиве будет отличаться лишь тем, что в конструкции if знак поменяется с < на >.
Сортировка элементов в массиве
Сортировка представляет собой процесс упорядочения элементов в массиве в порядке возрастания или убывания их значений. Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:
Представим, что нам необходимо разложить по порядку карты в колоде. Для сортировки карт обменом можно разложить карты на столе лицевой стороной вверх и менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной.
Для сортировки выбором из разложенных на столе карт выбирают самую младшую (старшую) карту и держат ее в руках. затем из оставшихся карт вновь выбирают наименьшую (наибольшую) и помещают ее позади той карты, которая была выбрана первой. Этот процесс повторяется до тех пор, пока вся колода не окажется в руках. Поскольку каждый раз выбирается наименьшая (наибольшая) по значению карта из оставшихся на столе карт, по завершению такого процесса карты будут отсортированы по возрастанию (убыванию).
Для сортировки вставкой из колоды берут две карты и располагают их в необходимом порядке по отношению друг к другу. Каждая следующая карта, взятая из колоды, должна быть установлена на соответствующее место по отношению к уже упорядоченным картам.
Сортировка методом «пузырька»
Данный метод является наиболее популярным. Возможно это из за того, что название (метод пузырька) хорошо запоминается и сам алгоритм достаточно прост. Здесь используется метод обменной сортировки, который мы рассмотрим более подробно.
Сравним нулевой элемент массива с первым, если нулевой окажется больше первого, то поменяем их местами. Те же действия выполним для первого и второго, второго и третьего, i-го и (i+1)-го, предпоследнего и последнего элементов. В результате этих действий самый большой элемент станет на (n-1)-е место. Теперь повторим данный алгоритм сначала, но последний элемент рассматривать не будем. После проведения данной операции самый большой элемент оставшегося массива станет на (n-2)-е место. Так нужно повторять до тех пор, пока не упорядочим весь массив. Блок-схема алгоритма:
Обратите внимание на то, что для перестановки элементов используется буферная переменная b, в которой временно хранится значение элемента, подлежащего замене.
Также, думаю стоит продемонстрировать текст программы, сортирующей элементы массива по возрастанию методом «пузырька»:
#include "stdafx.h"
#include <iostream>
using namespace std;
int main ()
{
int y[10], n, i, b, j;
cout<<"\n N="; cin>>n;
for (i=0; i<n; i++) //вывод массива
{
cout<<"\n Y["<<i<<"]=";
cin>>y[i];
}
//упорядочивание элементов в массиве по возрастанию их значений
for (j=1; j<n; j++)
for (i=0; i<n-j; i++)
if (y[i]>y[i+1]) //если текущий элемент больше следущего, то
{
b=y[i]; //сохранить значение текущего элемента;
y[i]=y[i+1]; //заменить текущий элемент следующим;
y[i+1]=b; //заменить следующий элемет текущим.
}
for (i=0; i<n; i++) cout<<y[i]<<"\t"; //вывод упорядоченного массива
system("pause");
return 0;
}
Результат работы программы:
Для перестановки элементов в массиве по убыванию их значений необходимо при сравнении заменить знак > на <.
Сортировка выбором
Идея алгоритма заключается в следующем. В массиве Y, состоящем из n элементов, ищем самый большой элемент и меняем его местами с последним элементом. Повторяем алгоритм поиска максимального элемента, но последний (n-1)-й элемент не рассматриваем, так как он уже занял свою позицию. Найденный максимум ставим на (n-2)-ю позицию. Описанную выше операцию поиска проводим n-1 раз до полного упорядочивания элементов в массиве.
Часть кода программы, которая выполняет сортировку массива по возрастанию методом выбора:
for (j=1; j<n; b=y[n-j], y[n-j]=y[nom], y[nom]=b; j++)
for (max=y[0], nom=0, i=1; i<=n-j; i++)
if (y[i]>max) {max=y[i]; nom=i;}
for (i=0; i<n; i++) cout<<y[i]<<"\t"; //вывод упорядоченного массива
Сортировка вставкой
Сортировка вставкой заключается в том, что сначала упорядочиваются два элемента массива. Затем делается вставка третьего в соответствующее место по отношению к первым двум элементам. Четвертый элемент помещают в список из уже упорядоченных трех элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены.
Удаление элемента из массива
Пусть нужно удалить из массива X, состоящего из n элементов, m-й по номеру элемент. Для этого достаточно записать (m+1)-й элемент на место элемента m, (m+2)-й на место (m+1)-го и т.д., n-1 на место (n-2) и при дальнейшей работе с этим массивом использовать n-1 элемент:
Фрагмент программы на C++:
cout<<"\n m="; cin>>m; //ввод номера элемента, подлежащего удалению for (i=m; i<n-1; X[i+1],i++); //удаление m-го элемента for (i=0; i<n-1; i++) cout<<X[i]<<"\t"; //вывод измененного массива n--; //уменьшение количества элементов в массиве
На этом заканчивается тема про одномерные массивы, далее мы разберем указатели и динамические массивы, что касается двумерных массивов, то я еще раз напомню что они будут подробно рассмотрены в уроках про матрицы.