В данной задаче обработку массива будем проводить с начала. Выход из цикла по дополнительному условию будет выполнен, если в массиве найден элемент больший либо равный 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 <stdio.h>
main()
{
int f, k, n, poz, i, x[100], a;
puts("Введите число элементов массива:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("x[%2d]=",i);
scanf("%d",&x[i]);
}
puts("Введите число a:");
scanf("%d",&a);
f=0; poz=n; k=0;
for(i=0;i<n&&k==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<n;i++)
printf("x[%d]=%d\n",i,x[i]);
return 0;
}
Рисунок 2.15. Графический алгоритм и программа для примера 2.7
Описанный алгоритм можно дополнить предварительным сравнением последнего элемента массива X[n-1] с числом A, если X[n-1]=A – то заданное число находится на последнем месте, а в случаe выполнения X[n-1]>A – то, число A должно находится в массиве на позиции n. Если ни одно из этих условий не выполнено, то это означает, что необходимо выполнить поиск числа A в массиве.
12.3.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), то переменная min принимает значение ai, а n_min – на i: min=ai, n_min= i.
Графическая схема алгоритма и фрагмент программы поиска минимального элемента в массиве приведены на рисунке 2.16.
Рисунок 2.16. Графический алгоритм и фрагмент программы поиска минимального элемента в массиве
Заметим, что при наличии в массиве нескольких минимальных элементов, найден будет первый из них (самый левый минимальный элемент) при просмотре массива слева направо. Если в неравенстве ai< min знак >поменять на знак ≥, то будет найден последний из них (самый правый минимальный элемент).
Для поиска максимального элемента max и его индекса n_max используется аналогичный алгоритм, в котором сначала надо принять max =ain, n_ max= in, вместо неравенства ai < min используется неравенство ai > max. В случаи выполнения условия ai > max записать в max=ai и в n_ max= i.
Для поиска в массиве экстремума можно не использовать вспомогательную переменную min (max). В этом случаи минимальный элемент массива определяется только по его индексу n_min (n_max) (рисунок 2.17).
Рисунок 2.17. Графический алгоритм и фрагмент программы поиска минимального элемента в массиве по его индексу
Пример использования рассмотренных алгоритмов представлен в приложении 2.
12.3.10 Копирование массивов
В ряде задач для организации дополнительных или промежуточных вычислений, требуется создание копии всего массива или части его элементов. Для этого можно воспользоваться алгоритмом представленным на рисунке 2.18.
k=0;
for(i=in;i<ik;i++)
{
y[k]=a[i];
k++;
}
Рисунок 2.18 Алгоритм и фрагмент программы создания
копии массива
В зависимости от параметров in и ik, в массив y[ ] копируются элементы из исходного массива a[ ]. Так для копирования всех элементов массива a[ ] необходимо задать in=0, ik=n (n – количество элементов массива a[ ]). При копировании части массива, например с 3 по 9, принимаем in=2 (посколькунумерация элементов массива в С++, начинается с нуля) и ik=9.
12.3.11 Формирование нового массива
В задачах формирования нового массива требуется создать массив из элементов существующего массива (массивов) удовлетворяющих заданному условию. В новый массив элементы заносятся, последовательно начиная с нулевого индекса. Максимально число элементов в формируемом массиве может достигать количества элементов в исходном массиве (массивах), минимальное значение равняется нулю. В этом случаи считается, что новый массив не сформирован.
При формировании новых массивов удобно использовать динамические массивы, поскольку число его элементов заранее не известно. Алгоритм создания нового массива схож с алгоритмом копирования (рисунок 2.19).
k=0;
for(i=in;i<ik;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.
