Одномерные массивы (стр. 4 из 6)
Упорядоченность элементов массива позволяет значительно увеличить скорость его обработки, за счет снижения числа проверяемых элементов массива. В таких алгоритмах массив проверяется пока выполняется (или не выполняется) дополнительное условие, определяющее досрочный выход из цикла. Также при составлении алгоритма необходимо учитывать возрастающим или убывающим является проверяемый массив, что оказывает влияние на то как удобнее обрабатывать массив с начала или с конца. В общем случаи алгоритм обработки упорядоченного массива имеет следующий вид – рисунок 2.14.
 |  |
| (а) | (б) |
Рисунок 2.14. Графический алгоритм обработки упорядоченного массива с перебором с начала (а), с конца (б)
Как видно из блок–схемы, дополнительное условие управляет досрочным выходом из цикла. Пока дополнительное условие истина и не конец массива i<n, цикл выполняется, как только одно из условий будет не выполнено происходит выход из цикла.
Пример 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 <stdio.h>main(){ int f, k, n, poz, i, x[10], 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 – то заданное число находится на последнем месте, а в случаи выполнения 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), то переменная min принимает значение ai, а n_min – на i: min=ai, n_min= i.
Графическая схема алгоритма и фрагмент программы поиска минимального элемента в массиве приведены на рисунке 2.16.
 | min=a[in]; n_min=in; for(i=in+1; i<ik; i++) if(a[i]<min) { min=a[i]; n_min=i; } |
Рисунок 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).
 | /*поиск минимального элемента*/ n_min=in; for(i=in+1; i<ik; i++) if(a[i]<a[n_min]) n_min=i;/*поиск максимального элемента*/ n_max=in; for(i=in+1; i<ik; i++) if(a[i]>a[n_max]) n_max=i; |
Рисунок 2.17. Графический алгоритм и фрагмент программы поиска минимального элемента в массиве по его индексу
Пример использования рассмотренных алгоритмов представлен в приложении 2.
В ряде задач для организации дополнительных или промежуточных вычислений, требуется создание копии всего массива или части его элементов. Для этого можно воспользоваться алгоритмом представленным на рисунке 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.
2.10 Формирование нового массива
В задачах формирования нового массива требуется создать массив из элементов существующего массива (массивов) удовлетворяющих заданному условию. В новый массив элементы заносятся, последовательно начиная с нулевого индекса. Максимально число элементов в формируемом массиве может достигать количества элементов в исходном массиве (массивах), минимальное значение равняется нулю. В этом случаи считается, что новый массив не сформирован.
При формировании новых массивов удобно использовать динамические массивы, поскольку число его элементов заранее не известно. Алгоритм создания нового массива схож с алгоритмом копирования (рисунок 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.
массив одномерный программа алгоритм
Решение
Если число элементов массива X – n, а массива Y – m, то с учетом того, что из первого массива выбираются элементы стоящие только на четных местах, максимальное число элементов в новом массиве Z может достигать m+n/2 элементов. Поэтому для массива Z с помощью оператора динамического выделения памяти (new) выделим m+[n/2] ячейки памяти ([n/2] – целая часть от деления). Начальное значение счетчика элементов нового массива k принимается равным нулю.