--PAGE_BREAK--1.2 Динамические массивы
Если до начала работы программы неизвестно, сколько в массиве элементов, в программе используют динамические массивы. Память под них выделяется с помощью оператора new во время выполнения программы. Адрес начала массива хранится в переменной, называемой указателем. Например.
int n=20;
int *a = new int[n];
Здесь описан указатель a на целую величину, которому присваивается адрес начала непрерывной области динамической памяти, выделенной с помощью оператора new. Выделяется столько памяти, сколько необходимо для хранения n величин типа int. Величина n может быть переменной.
Примечание: Обнуление памяти при ее выделении не происходит. Инициализировать динамический массив нельзя.
Обращение к элементу динамического массива осуществляется также, как и к элементам обычного массива. Например: a[0], a[1], …, a[9].
Можно обратиться к элементу массива другим способом: *(a+9), *(a+i), т.к. в переменной – указателе a хранится адрес начала массива. Для получения адреса, например, 9 – го его элемента к этому адресу прибавляется 9·sizeof(int) (9 умножить на·длину элемента типа int), т.е. к начальному адресу a прибавляется смещение 9. Затем с помощью операции *(разадресации) выполняется выборка значения из указанной области памяти.
После использования массива выделенная динамическая память освобождается с помощью опереатора: delete [ ] имя массива. Так например, для одномерного массива a:
delete [ ] a;.
Время «жизни» динамического массива
определяется с момента выделения динамической памяти до момента ее освобождения.
2. Алгоритмы обработки одномерных массивов 2.1 Инициализация массива
Инициализация массива– это присваивание элементам массива начальных значений. Инициализацию массива можно выполнить на этапе описания массива, как это показано в п.1.1. Но в том случае, когда начальные значения получают лишь некоторые элементы массива, а остальные вычисляются в процессе выполнения программы, в программе записывают операторы присваивания. Например:
a[0]= –1; a[1]=1.1;
Присваивание всем элементам массива одного и того же значения осуществляется в цикле. Например, чтобы всем элементам массива a присвоить значение 0, можно воспользоватся алгоритмом изображенный на рис. 2.1.
for(i=0;i
a[i]=0;
// или с помощью цикла while
i=0;
while (i
{
a[i]=0;
i=i+1;
}
Рисунок 2.1 Алгоритм и фрагмент программы инициализации массива
В представленном алгоритме все элементы массива в цикле последовательно инициализируются значением – 0.
2.2. Ввод – вывод одномерного массива
Для ввода n элементов одномерного массива, назовем его А, требуется организовать цикл, для ввода каждого i – го элемента, где i=0,1,2, …, n–1. Аналогичный цикл требуется организовать и для вывода элементов массива. На рисунке 2.2 изображена графическая схема ввода и вывода элементов массива.
/* Ввод – вывод статического массива*/
#include
#define n 50;
void main()
{
int n,i;
float A[n];
puts(«Введите число элементов массива „);
scanf(“%d»,&n);
// Ввод массива
for (i=0; i
{ printf(«Введите число A[%2d]=»,i);
scanf("%f",&A[i]);
}
// Вывод массива
puts(«Массив A»);
for(i=0;i
printf("%6.3f ",A[i]);
printf("\n");
}
Рисунок 2.2 Алгоритм и программа ввода – вывода статического массива
Ввод–вывод динамического массива осуществляется по тому же алгоритму. Из приведенного ниже примера программы ввода и вывода динамического массива видно, что отличие заключается лишь в описании массива.
/* Ввод – вывод динамического массива*/
#include
void main()
{
int n,i;
puts(«Введите число элементов массива a»);
scanf("%d",&n);
float *a=new float[n]; // Описание динамического массва
// Ввод массива
for (i=0;i
{ printf(«Введите число a[%2d]=»,i);
scanf("%f",a+i); // или scanf("%f",&a[i]);
}
// Вывод массива
puts(«Массив a»);
for(i=0;i
printf("%.3f ",*(a+i)); // или printf("%.3f ",a[i]);
printf("\n");
delete[] a; // Освобождение памяти выделенной под массив
}
продолжение
--PAGE_BREAK--2.3 Перестановка двух элементов массива
Для перестановки двух элементов массива x[] с индексами k и m, необходимо использование дополнительной переменной (tmp), для хранения копии одного из элементов (рисунок 2.3 а), но можно обойтись и без использования дополнительной переменной tmp. В этом случаи алгоритм перестановки имеет следующий вид (рисунок 2.3 б).
В большинстве случаев предпочтительнее использовать первый способ, поскольку он не содержит дополнительных вычислений, что особенно важно при перестановке вещественных чисел.
tmp=x[k];
x[k]=x[m];
x[m]=tmp;
x[k]=x[k]+x[m];
x[m]=x[k]-x[m];
x[k]=x[k]-x[m];
(а)
(б)
Рисунок 2.3 Алгоритм и фрагмент программы перестановки двух элементов массива c использованием дополнительной переменной (а) и без нее (б)
Пример 2.1
Переставить первый и последний элемент массива x[] местами. Количество элементов массива n.
Решение
В С нумерация элементов массива начинается с нуля, поэтому номер последнего элемента массива (n–1) .
1 способ: tmp=x[0]; x[0]=x[n-1]; x[n-1]=tmp;
2 способ: x[0]=x[0]+x[n-1]; x[n-1]=x[0]-x[n-1]; x[0]=x[0]-x[n-1];
Пример 2.2
Поменять местами заданный элемент массива x[k] с последующим.
Решение
При решении этой задачи необходимо учитывать, что если заданный элемент массива x[k] является последним, то обмен выполнить не возможно, поскольку последующий элемент отсутствует.
if(k == n-1)
puts(«Обмен не возможен.»);
else
{
tmp=x[k];
x[k]=x[k+1];
x[k+1]=tmp;
}
Рисунок 2.4 Алгоритм и фрагмент программы перестановки заданного элемент массива x[k] с последующим
При перестановке с предыдущим элементом, обмен невозможен если заданный элемент является первым (k=0).
2.4 Вычисление суммы элементов массива
Часто возникают задачи, требующие вычислить сумму всех или некоторых элементов массива, например, сумму элементов, стоящих в массиве на заданных местах, или сумму элементов, удовлетворяющих некоторому условию (сумму только положительных элементов, сумму ненулевых элементов второй половины массива и т.д.).
Пусть а[] – заданный массив из n элементов. Сумма всех его элементов в математической форме выглядит следующим образом:
(2.1)
Для вычисления суммы элементов части массива, например, с in–го до ik–го. Следует использовать формулу:
(2.2)
Очевидно, что формула (2.2) получается из формулы (2.1) при in=0 и ik=n–1.
Алгоритм вычисления суммы состоит в следующем:
1. установить значение переменой для накопления суммы (s) в нулевое значение (s=0);
2. в цикле изменяя i отin до ik вычислить суммуэлементов массива по выражениию s=s+ai.
При первой итерации цикла (i=in) получим s=s+ain= 0+ ain. На второй (i=in+1) – s=s+ain+1= ain + ain+1 и т. д. На последней итерации цикла будем иметь s=s+aik= ain + ain+1+…+ aik. Т.е. в цикле по параметру i «старое» значение s, содержащее накопленную сумму на предыдущей итерации, изменяется на значение ai. На рисунке 2.5 представлен алгоритм и фрагменты программ вычисления суммы элементов массива.
Рисунок 2.5 Графическая схема и фрагмент программы вычисления суммы элементов массива
Если в алгоритме (рисунок 2.5) в блоке 2 записать i=0, а блоке 3 – (i, то получим алгоритм вычисления суммы всех элементов массива.
Рассмотренный алгоритм вычисления суммы, можно применить для вычисления суммы элементов, стоящих в массиве на заданных местах (рисунок 2.6). В этом случаи шаг изменения параметра цикла определяется переменной step.
/* с помощью цикла for */
s=0;
for(i=in;i
s+=a[i]; // или s=s+a[i];
/* с помощью цикла while */
s=0; i=in;
while (i
{
s+=a[i];
i=i+step;
}
Рисунок 2.6 Графическая схема и фрагмент программы вычисления суммы элементов массива стоящих на заданных местах
Например, чтобы вычислить сумму элементов, стоящих в массиве на четных местах, необходимо «заставить» i принимать значения 1, 3, 5, … (поскольку нумерация элементов массива в С начинается с нуля т.е. элемент массива с индексом a[0] – первый элемент массива). Для этого достаточно в блоке 2 записать i=1, в блоке 3 – (i, а в блоке 5 записать i=i+2 (step=2). В программе на языке С соответствующий фрагмент будет выглядеть следующим образом:
s=0;
for(i=1;i
s+=a[i]; // или s=s+a[i];
Для вычисления суммы только тех элементов, которые удовлетворяют некоторому условию, необходимо в алгоритме вычисления суммы (рисунок 2.6) блок 4 заменить на ветвление, которое обеспечивает выполнение команды s=s+ai только тогда, когда условие выполнено для рассматриваемого элемента массива ai. В этом случаи алгоритм вычисления суммы примет следующий вид (рисунок 2.7).
/* с помощью цикла for */
s=0;
for(i=in;i
if( условие ) s+=a[i]; // или s=s+a[i];
/* с помощью цикла while */
s=0; i=in;
while (i
{
if( условие ) s+=a[i];
i=i+step;
}
Рисунок 2.7 Графическая схема и фрагмент программы вычисления суммы элементов массива стоящих на заданных местах
Применим полученный алгоритм для вычисления суммы положительных элементов массива стоящих на нечетных местах. Для этого в блоке 2 запишем i=0, в блоке 3 (i, в 4 условие – (a[i]>0), а в блоке 6 изменение параметра цикла (step=2) i=i+2. Тогда соответствующий фрагмент программы можно записать в виде:
s=0;
for(i=0;i
if( a[i]>0 ) s+=a[i]; // или s=s+a[i];
Рассмотрим примеры использования рассмотренных алгоритмов.
продолжение
--PAGE_BREAK--Пример 2.3.
В одномерном массиве aразмерностью n, вычислить сумму элементов массива, меньших заданного значения В и стоящих на местах, кратных трем.
Решение
Объединим алгоритмы ввода – вывода массива (рисунок 2.2) и вычисления суммы (рисунок 2.7). Для сокращения записи графической схемы алгоритма ввода и вывода массива, здесь и в дальнейшем используем простые блоки вида:
В алгоритме для вычисления искомой суммы рассматриваются только те элементы, которые в массиве стоят на местах, кратных трем, при этом необходимо учитывать что нумерация элементов массива в С начинается с нуля т.е. элемент массива с индексом a[0] это первый элемент массива. Таким образом, элементы стоящие на местах кратных трем – а2, а5, а8, …, индекс элемента массива (он же – параметр цикла) должен последовательно принимать значения 2, 5, 8, …, т.е. изменяться от 2 с шагом 3, что и достигается изменениями в блоках 2и 6алгоритма вычисления суммы (рисунок 2.7). Так в блоке 2 запишем i=2, в блоке 3 (i, а в блоке 6 – (step=3) i=i+3. Для суммирования из рассмотренных элементов только тех, которые меньше заданного В, используется ветвление с условием аi (блок 4). Окончательный алгоритм вычисления суммы заданных элементов примет, следующий вид (рисунок 2.8). В задаче будем использовать динамический способ задания массива. В данном примере для обращения к элементам массива используются указатели. Как уже отмечалось в разделе 1.1, имя массива является указателем на его первый элемент.
Используемые переменные:
n – число элементов массива;
a[] – динамический массив;
s – сумма элементов массива;
B – заданное число;
i – параметр цикла;
#include
main()
{
int n,i;
float s, B;
puts(«Введите число элементов массива a»);
scanf("%d",&n);
float *a=new float[n];
for (i=0;i
{ printf(«Введите число a[%2d]=»,i);
scanf("%f",a+i);
}
puts(«Введите B»);
scanf("%f",&B);
s=0;
for(i=2;i
if(*(a+i)
puts(«Массив a»);
for(i=0;i
printf("%.1f ",*(a+i));
printf("\n");
printf(«Сумма чисел, меньших %.1f, стоящих на местах, кратных 3, равна %.2f\n»,B,s);
delete[] a; // освобождение памяти
return(0);
}
Рисунок 2.8 Графическая схема и программа примера 2.3
2.5 Подсчет количества элементов массива, удовлетворяющих заданному условию
Подсчет количества элементов массива, удовлетворяющих заданному условию, производится по алгоритмам, аналогичным вычислению суммы. Отличие заключается в том, что вместо добавления элемента массива к сумме, переменная – счетчик (k) увеличивается на единицу (k=k+1). Таким образом, если в графических схемах алгоритмов, рисунок 2.5–2.7, вместо s=0 и s=s+ai записать k=0 и k=k+1, то получим алгоритмы подсчета количества элементов массива.
Пример 2.4.
В одномерном массиве aразмерностью n, вычислить количество элементов равных заданному числу B и стоящих на четных местах.
Решение.
Графическая схема алгоритма решения задачи и фрагмент программы изображена на рисунке. 2.9.
/* с помощью цикла for */
k=0;
for(i=1;i
if(a[i]==b ) k++; // или k=k+1;
/* с помощью цикла while */
k=0; i=1;
while (i
{
if(a[i]==b) k++;
i=i+2;
}
Рисунок 2.9 Графическая схема и программа для примера 2.4
Следующий пример показывает, как в одном алгоритме находить сумму и количество элементов, удовлетворяющих заданному условию.
продолжение
--PAGE_BREAK--Пример 2.5.
В одномерном массиве aразмерностью n, вычислить среднее арифметическое положительных элементов второй половины массива, стоящих на нечетных местах.
Решение
Среднее арифметическое чисел (sr) – частное от деления их суммы (s) на их количество (k): sr=s/k, где k≠0. Таким образом, задача сводится к нахождению суммы и количества положительных элементов второй половины массива, стоящих на нечетных местах. Для решения данной задачи применим алгоритм, приведенный на рисунке 2.7, в соответствии с которым можно найти сумму и количество части элементов массива (второй половины), удовлетворяющих заданному условию (положительных элементов).
Определим номер in того элемента, с которого будем просматривать элементы второй половины массива. Поскольку по условию задачи обрабатываются элементы стоящие на нечетных местах то начальное значение in тоже должно быть четным (поскольку нумерация элементов массива начинается с нуля). Значение переменной in можно определить по формуле (2.3) где пара квадратных скобок [ ] определяет операцию вычисления целой части числа:
(2.3)
Значение ik совпадает с n, поскольку массив надо просматривать до конца. Параметр цикла i (номер элемента массива) необходимо изменять с шагом 2, чтобы обеспечить четные значения индекса (значения номеров элементов массива), т.е. i=i+2. Вычисление суммы и количества будем вычислять в одном цикле по параметру i, что значительно сократит алгоритм.
При вычислении среднего арифметического sr=s/k необходимо избежать возможного деления на ноль, поскольку если во второй половине массива на нечетных местах не окажется положительных элементов то k будет равным нулю. Например, для массива X={2, 0, –6, 7, 9, 0, –14, –5,, –4, –32}; n=11; in=[n/2]+1=6, в цикле по i будут просматриваться только выделенные элементы, а среди них нет положительных чисел, поэтому переменная k останется равной нулю. В графической схеме (рисунок 2.10) для этой цели используется ветвление, в котором проверяется условие k=0. Если это условие выполнено, то выводится сообщение о том, что среднее значение не может быть вычислено, в противном случае вычисляется и выводится значение sr.
В приведенном ниже фрагменте программы четность [n/2] определяется по остатку от деления n на 2 с помощью операции % – определения остатка целочисленного деления (примечание: результат операции целочисленный, т.к. n и 2 – целочисленные операнды).
Используемые переменные:
n – число элементов массива;
a[] – статический массив;
in – первый четный номер второй половины массива;
s – сумма элементов массива удовлетворяющих условию;
k – количество элементов массива удовлетворяющих условию;
sr – среднее значение элементов массива удовлетворяющих условию;
i – параметр цикла;
#include
main()
{
float a[20];
int n, i, in, k;
float s, sr;
puts(«Введите число элементов массива a»);
scanf("%d",&n);
for (i=0;i
{ printf(«Введите число a[%2d]=»,i);
scanf("%f",&a[i]);
}
if ((n/2)%2==0) in=n/2;
else in=n/2+1;
s=0; k=0;
for(i=in;i
if(a[i]>0) { s+=a[i]; k++;}
puts(«Массив a»);
for(i=0;i
printf(«a[%2d]=%6.2f \n», i, a[i]);
if (k==0)
puts(«Среднее арифметическое вычислить нельзя!»);
else
{
sr=s/k;
printf(«Среднее ариф. полож. элементов на нечетных. местах второй полов. массива =%6.3f\n», sr);
}
return(0);
}
Рисунок 2.10 Графическая схема и программа для примера 2.5
продолжение
--PAGE_BREAK--2.6 Вычисление произведения элементов массива
Формулы, по которым вычисляется произведение элементов массива, аналогичны формулам вычисления сумм:
, (2.4)
.(2.5)
Поэтому вычисление произведения элементов массива выполнятся по алгоритмам аналогичным вычислению суммы. Отличие заключается в том, что начальное значение произведения p должно быть равным 1, а в цикле по параметру i надо вычислять p=p*ai. Таким образом, если в графических схемах алгоритмов, рисунок 2.5 – 2.7 вместо s=0 и s=s+ai записать p=1 и p=p*ai, то получим алгоритмы вычисления произведения элементов массива.
Пример 2.6.
В одномерном массиве aразмерностью n, вычислить среднее геометрическое ненулевых элементов массива.
Решение
Среднее геометрическое k элементов массива – это корень степени k из произведения этих элементов. Таким образом, сначала необходимо вычислить произведение Р ненулевых элементов массива и их количество k, а затем среднее геометрическое Sg по формуле:
. (2.6)
Например, если элементы массива равны A= {1, 0, 2, 4, 0} то –
Графическая схема алгоритма решения задачи изображена на рисунке 2.11. В приведенном алгоритме в цикле по i(блоки 5 – 9) помимо вычисления произведения вычисляется и количество ненулевых элементов массива. После цикла с помощью ветвления, проверяется, есть ли в массиве ненулевые элементы (k>0 – условие наличия в массиве ненулевых элементов), в этом случае вычисляется и выводится среднее геометрическое. В противном случае выводится сообщение "В массиве все элементы равны нулю". В программе переменные Р и Sg имеют вещественный тип двойной точности (double), т.к. произведение вещественных чисел может быть очень большим числом.
Используемые переменные:
n – число элементов массива;
a[] – статический массив;
P – произведение не нулевых элементов массива;
k – количество не нулевых элементов массива;
Sg – среднее геометрическое элементов массива;
i – параметр цикла;
#include
#include
main()
{
float a[20];
int n, i, k;
double P, Sg;
puts(«Введите число элементов массива a»);
scanf("%d",&n);
for (i=0;i
{ printf(«Введите число a[%2d]=»,i);
scanf("%f",&a[i]);
}
P=1; k=0;
for(i=0;i
if(a[i]!=0) {P*=a[i]; k++;}
puts(«Массив a»);
for(i=0;i
printf(«a[%2d]=%6.2f \n», i, a[i]);
if(k>0)
{
if(P>0) Sg=powl(P,1.0/k);
else Sg= –powl(fabs(P),1.0/k);
printf(«Среднее геометрическое ненулевых элементов массива =%.4lf \n», Sg);
printf(«P=%.4lf k=%d \n», P, k);
}
else puts(«В массиве все элементы равны нулю! „);
return(0);
}
Рисунок 2.11 Графическая схема и программа для примера 2.6
В программе для возведения P в степень 1/k используется функция powl(основание, степень), первый аргумент которой может быть только положительным числом. Поэтому для отрицательного P использовано выражение , запись которого на языке С имеет вид: –powl(fabs(P), 1.0/k).
продолжение
--PAGE_BREAK--2.7 Поиск элементов, обладающих заданным свойством
При поиске элементов, обладающих заданным свойством, необязательно просматривать все элементы массива. Например, требуется определить, есть ли в массиве хотя бы один нулевой элемент. Для ответа на этот вопрос, достаточно в цикле просматривать элементы массива до тех пор, пока не закончится массив или не встретится равный нулю элемент. Если, например, уже третий элемент равен нулю, то остальные элементы просматривать нет необходимости.
В таких случаях для просмотра массива обычно используется оператор цикла while со сложным условием. Графическая схема для рассматриваемого примера изображена на рисунке 2.12. После цикла достаточно проверить, чему равно i. Если окажется, что i=n, т.е. были просмотрены все элементы, то в массиве нет нулевых элементов.
i=0;
while(i
If(i == n)
puts(«В массиве нет нулевых элементов»);
else
puts(«В массиве есть нулевой элемент»);
Рисунок 2.12 Графическая схема и фрагмент программы поиска нулевого элемента в массиве
Встречаются задачи, в которых требуется не только определить, есть ли элемент, обладающим заданным свойством в массиве, но и номер (индекс) такого элемента. Например, найти максимальный элемент в части массива, находящейся после последнего нуля. Решение задачи следует начать с вычисления индекса последнего нулевого элемента. Для определения индекса самого правого элемента, обладающего заданным свойством, массив следует просматривать с конца до тех пор, пока не закончатся элементы и текущий элемент не равен нулю (рисунок 2.13).
i=n–1;
while(i>=0 && a[i]!=0) i=i–1;
If(i
puts(«В массиве нет нулевых элементов»);
else
printf(«Индекс последнего нуля – %d \n», i);
Рисунок 2.13 Графическая схема и фрагмент программы поиска номера последнего нулевого элемента в массиве
Номер (индекс) первого встретившегося нулевого элемента можно узнать по значению параметра цикла i. Этот номер можно использовать в дальнейших вычислениях например как номер начального элемента для поиска максимума.
2.8 Поиск в упорядоченном массиве
Упорядоченность элементов массива позволяет значительно увеличить скорость его обработки, за счет снижения числа проверяемых элементов массива. В таких алгоритмах массив проверяется пока выполняется (или не выполняется) дополнительное условие, определяющее досрочный выход из цикла. Также при составлении алгоритма необходимо учитывать возрастающим или убывающим является проверяемый массив, что оказывает влияние на то как удобнее обрабатывать массив с начала или с конца. В общем случаи алгоритм обработки упорядоченного массива имеет следующий вид – рисунок 2.14.
Рисунок 2.14. Графический алгоритм обработки упорядоченного массива с перебором с начала (а), с конца (б)
Как видно из блок–схемы, дополнительное условие управляет досрочным выходом из цикла. Пока дополнительное условие истина и не конец массива i, цикл выполняется, как только одно из условий будет не выполнено происходит выход из цикла.
Пример 2.7
В возрастающем одномерном массиве X с количеством элементов n, определить есть ли число равное A и на какой позиции оно находится, если числа A нет определить место на котором оно должно находиться чтобы не нарушить упорядоченность массива.
Решение
В данной задаче обработку массива будем проводить с начала. Выход из цикла по дополнительному условию будет выполнен, если в массиве найден элемент больший либо равный A (k=1). Для индикации наличия в массиве элемента равного A, введем вспомогательную переменную f с начальным значением f=0. При обнаружении элемента A, переменная f=1. Для определения номера позиции числа A в массиве введем дополнительную переменную poz с начальным значением n, т.е. предполагая, что все элементы массива меньше A. При обнаружении в массиве числа большего или равного A в переменной poz сохраняется его индекс – i. После выхода из цикла, по значению переменной f определяется наличие и место переменной A в массиве. Описанный алгоритм поиска и программа представлены на рисунке 2.15.
Используемые переменные:
n – число элементов массива;
a[] – статический массив;
k
– переменная для досрочного выхода из цикла при нахождении элемента большего или равного
a
;
f
– вспомогательная переменная для индикации наличия в массиве числа равного
a
;
poz
– номер элемента массива на котором должно находится число
a
;
i – параметр цикла;
#include
main()
{
int f, k, n, poz, i, x[10], a;
puts(«Введите число элементов массива:»);
scanf("%d",&n);
for(i=0;i
{
printf(«x[%2d]=»,i);
scanf("%d",&x[i]);
}
puts(«Введите число a:»);
scanf("%d",&a);
f=0; poz=n; k=0;
for(i=0;i
{
if(x[i]>a) { poz=i;k=1;}
else
{
if(x[i]==a)
{poz=i; f=1; k=1;}
}
}
if(f==1)
printf(«В массиве есть число =%d, на позиции-%d\n», a, poz);
else
printf(«Число %d должно находиться на позиции-%d\n» ,a, poz);
for(i=0;i
printf(«x[%d]=%d\n»,i,x[i]);
return 0;
}
Рисунок 2.15. Графический алгоритм и программа для примера 2.7
Описанный алгоритм можно дополнить предварительным сравнением последнего элемента массива X
[
n
-1]с числом A, если X
[
n
-1]=A
– то заданное число находится на последнем месте, а в случаи выполнения X
[
n
-1]>A
– то, число Aдолжно находится в массиве на позиции n. Если ни одно из этих условий не выполнено, то это означает что необходимо выполнить поиск числа Aв массиве.
2.9 Поиск минимального и максимального элемента массива и его порядкового номера (индекса)
Пусть требуется найти минимальный элемент (min) и его индекс (n_min) во всем массиве (in=0и ik=n) или какой то его части (с in – го по ik – ый), в этом случаи алгоритм решения задачи можно записать так:
1. в качестве начального значения переменной min выберем любой из рассматриваемых элементов (обычно выбирают первый). Тогда min=ain, n_min= in;
2. затем в цикле по параметру i начиная со следующего элемента (i=in+1, …, ik) будем сравнивать элементы массива ai текущим минимальным min. Если окажется, что текущий (i – ый) элемент массива меньше минимального (ai ), то переменная min принимает значение ai, а n_min – на i: min=ai, n_min= i.
Графическая схема алгоритма и фрагмент программы поиска минимального элемента в массиве приведены на рисунке 2.16.
Рисунок 2.16. Графический алгоритм и фрагмент программы поиска минимального элемента в массиве
Заметим, что при наличии в массиве нескольких минимальных элементов, найден будет первый из них (самый левый минимальный элемент) при просмотре массива слева направо. Если в неравенстве ai знак > поменять на знак ≥, то будет найден последний из них (самый правый минимальный элемент).
Для поиска максимального элемента max и его индекса n_max используется аналогичный алгоритм, в котором сначала надо принять max =ain, n_ max = in, вместо неравенства ai используется неравенство ai > max. В случаи выполнения условия ai > max записать в max =ai и в n_ max= i.
Для поиска в массиве экстремума можно не использовать вспомогательную переменную min (max). В этом случаи минимальный элемент массива определяется только по его индексу n_min (n_max) (рисунок 2.17).
/*поиск минимального элемента*/
n_min=in;
for(i=in+1; i
if(a[i]
n_min=i;
/*поиск максимального элемента*/
n_max=in;
for(i=in+1; i
if(a[i]>a[n_max])
n_max=i;
Рисунок 2.17. Графический алгоритм и фрагмент программы поиска минимального элемента в массиве по его индексу
Пример использования рассмотренных алгоритмов представлен в приложении 2.
2.10 Копирование массивов
В ряде задач для организации дополнительных или промежуточных вычислений, требуется создание копии всего массива или части его элементов. Для этого можно воспользоваться алгоритмом представленным на рисунке 2.18.
k=0;
for(i=in;i
{
y[k]=a[i];
k++;
}
Рисунок 2.18 Алгоритм и фрагмент программы создания копии массива
В зависимости от параметров in и ik, в массив y[ ] копируются элементы из исходного массива a[ ]. Так для копирования всех элементов массива a[ ] необходимо задать in=, ik=n (n – количество элементов массива a[ ]). При копировании части массива, например с 3 по 9, принимаем in=2 (посколькунумерация элементов массива в С++, начинается с нуля) и ik=9.
продолжение
--PAGE_BREAK--2.10 Формирование нового массива
В задачах формирования нового массива требуется создать массив из элементов существующего массива (массивов) удовлетворяющих заданному условию. В новый массив элементы заносятся, последовательно начиная с нулевого индекса. Максимально число элементов в формируемом массиве может достигать количества элементов в исходном массиве (массивах), минимальное значение равняется нулю. В этом случаи считается, что новый массив не сформирован.
При формировании новых массивов удобно использовать динамические массивы, поскольку число его элементов заранее не известно. Алгоритм создания нового массива схож с алгоритмом копирования (рисунок 2.19).
k=0;
for(i=in;i
{
if (условие)
{
y[k]=a[i];
k++;
}
}
Рисунок 2.19 Алгоритм и фрагмент программы формирования нового массива
Для последовательной записи элементов в новый массив используется дополнительная переменная k– счетчик элементов в новом массиве. Начальное значение этой переменной принимается равной нулю, т.е считается что в новом массиве нет элементов. При обнаружении в исходном массиве элемента удовлетворяющего заданному условию, его значение заносится в новый массив на позицию k, а после счетчик элементов увеличивается на единицу (k
=
k
+1). Таким образом, после обработки всего исходного массива по значению счетчика kможно определить, сформирован новый массив (k
>0) и сколько в нем элементов (k).
Пример 2.8
Даны два одномерных массива Xи Y. Необходимо сформировать массив Zиз положительных элементов массива Xстоящих на четных местах и элементов массива Yбольших первого элемента массива X.
массив одномерный программа алгоритм
Решение
Если число элементов массива X– n, а массива Y– m, то с учетом того, что из первого массива выбираются элементы стоящие только на четных местах, максимальное число элементов в новом массиве Zможет достигать m
+
n
/2элементов. Поэтому для массива Zс помощью оператора динамического выделения памяти (new) выделим m
+[
n
/2]ячейки памяти ([n
/2]– целая часть от деления). Начальное значение счетчика элементов нового массива kпринимается равным нулю.
При обработке массива Xнеобходимо проверять только элементы, стоящие на четных местах, т.е. параметр цикла iизменяется от in=1 до ik=n
с шагом 2. Условие отбора элементов из первого массива X
[
i
]>0. При обработке массива Yучитываются все его элементы, т.е. параметр цикла iизменяется от in=0 до ik=m
с шагом 1. Условие отбора элементов из второго массива – Y[
i
]>
X
[0].
Описанный алгоритм формирования нового массива и программа представлены на рисунке 2.20.
--PAGE_BREAK--Литература
1. М\ук №3089. Кравченко О.А., Мартыненко А.М. Программирование ввода–вывода данных и линейных вычислительных алгоритмов на языке С: практ. пособие к выполнению лаб. и контрол. работ по дисциплине «Вычислительная техника и программирование» для студентов техн. специальностей днев. и заоч. форм обучения Гомель: ГГТУ им. П.О. Сухого, 2005. – 33 с.
2. М\ук №3106. Кравченко О.А., Коробейникова Е.В. Программирование разветвляющихся и циклических алгоритмов на языке С: пособие по выполнению лабораторных и контрольных работ по дисциплине«Вычислительная техника и программирование» для студентов техн. специальностей днев. и заоч. форм обучения Гомель: ГГТУ им. П.О. Сухого, 2005. – 33 с
3. Информатика. Базовый курс: учеб. пособие / под ред. С. В. Симоновича. — 2-е изд. — Санкт-Петербург: Питер, 2007. — 639с.: ил. — (Учебник для вузов). — Библиогр.: с.631-632. — ISBN 5-94723-752-0
4. С/С ++. Программирование на языке высокого уровня / Т. А. Павловская. — Санкт-Петербург: Питер, 2006. — 460с.: ил. — (Учебник для вузов). — Библиогр.: с.383. — ISBN 5-94723-568-4.
5. С#. Программирование на языке высокого уровня / Т. А. Павловская. — Сант-Петербург: Питер, 2007. — 432с.: ил. — (Учебник для вузов). — Библиогр.: с.425-426. — ISBN 5-91180-174-4.
6. Информатика: учеб. для вузов / В. А. Острейковский. — Москва: Высш. шк., 2000. — 511с.: ил. — Библиогр.: с.508. — ISBN 5-06-003533-6.
7. Информатика: Учебник /Под ред. Проф. Н.В.Макаровой. –М.: Финансы и статистика, 1998.
8. Касаткин А.И., Вальвачев А.Н. Профессиональное программирование на языке СИ: от Turbo C к Borland C++: Справ.пособие. – Мн.: Выш.шк., 1992. – 240 с.
9. Топп У., Форд У. Структуры данных в С++: Пер. с англ.–М.: БИНОМ, 1994. – 816 с.
10. Крячков А.В., Сухина И.В., Томшин В.К. Программирование на С и С++. Практикум: Учебн. Пособие для вузов. – М.: Горячая лининия – Телеком, 2000 – 344 с.
11. Страуструп Б. Язык программирования Си++: Пер. с англ.– М.: Радио и связь, 1991. – 352 с.
--PAGE_BREAK--