Одномерные массивы
|
Используемые переменные: n – число элементов массива; a[] – статический массив; P – произведение не нулевых элементов массива; k – количество не нулевых элементов массива; Sg – среднее геометрическое элементов массива; i – параметр цикла;
|
#include <stdio.h> #include <math.h> main() { float a[20]; int n, i , k; double P, Sg; puts("Введите число элементов массива a"); scanf("%d",&n); for (i=0;i<n;i++) { printf("Введите число a[%2d]=",i); scanf("%f",&a[i]); } P=1; k=0; for(i=0;i<n;i++) if(a[i]!=0) {P*=a[i]; k++;} puts("Массив a"); for(i=0;i<n;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).
2.7 Поиск элементов, обладающих заданным свойством
При поиске элементов, обладающих заданным свойством, необязательно просматривать все элементы массива. Например, требуется определить, есть ли в массиве хотя бы один нулевой элемент. Для ответа на этот вопрос, достаточно в цикле просматривать элементы массива до тех пор, пока не закончится массив или не встретится равный нулю элемент. Если, например, уже третий элемент равен нулю, то остальные элементы просматривать нет необходимости.
В таких случаях для просмотра массива обычно используется оператор цикла while со сложным условием. Графическая схема для рассматриваемого примера изображена на рисунке 2.12. После цикла достаточно проверить, чему равно i. Если окажется, что i=n, т.е. были просмотрены все элементы, то в массиве нет нулевых элементов.
|
|
i=0; while(i<n && a[i]!=0) i=i+1; If(i == n) puts("В массиве нет нулевых элементов"); else puts("В массиве есть нулевой элемент"); |
Рисунок 2.12 Графическая схема и фрагмент программы поиска нулевого элемента в массиве
Встречаются задачи, в которых требуется не только определить, есть ли элемент, обладающим заданным свойством в массиве, но и номер (индекс) такого элемента. Например, найти максимальный элемент в части массива, находящейся после последнего нуля. Решение задачи следует начать с вычисления индекса последнего нулевого элемента. Для определения индекса самого правого элемента, обладающего заданным свойством, массив следует просматривать с конца до тех пор, пока не закончатся элементы и текущий элемент не равен нулю (рисунок 2.13).
|
|
i=n–1; while(i>=0 && a[i]!=0) i=i–1; If(i<0) puts("В массиве нет нулевых элементов"); else printf("Индекс последнего нуля – %d n", i); |
Рисунок 2.13 Графическая схема и фрагмент программы поиска номера последнего нулевого элемента в массиве
Номер (индекс) первого встретившегося нулевого элемента можно узнать по значению параметра цикла i. Этот номер можно использовать в дальнейших вычислениях например как номер начального элемента для поиска максимума.
2.8 Поиск в упорядоченном массиве
Упорядоченность элементов массива позволяет значительно увеличить скорость его обработки, за счет снижения числа проверяемых элементов массива. В таких алгоритмах массив проверяется пока выполняется (или не выполняется) дополнительное условие, определяющее досрочный выход из цикла. Также при составлении алгоритма необходимо учитывать возрастающим или убывающим является проверяемый массив, что оказывает влияние на то как удобнее обрабатывать массив с начала или с конца. В общем случаи алгоритм обработки упорядоченного массива имеет следующий вид – рисунок 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, на позиции-%dn", a, poz); else printf("Число %d должно находиться на позиции-%dn" ,a, poz); for(i=0;i<n;i++) printf("x[%d]=%dn",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 – ый), в этом случаи алгоритм решения задачи можно записать так:
в качестве начального значения переменной min выберем любой из рассматриваемых элементов (обычно выбирают первый). Тогда min=ain, n_min= in;
затем в цикле по параметру 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.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.
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 принимается равным нулю.
При обработке массива X необходимо проверять только элементы, стоящие на четных местах, т.е. параметр цикла i изменяется от in=1 до ik=n с шагом 2. Условие отбора элементов из первого массива X[i]>0. При обработке массива Y учитываются все его элементы, т.е. параметр цикла i изменяется от in=0 до ik=m с шагом 1. Условие отбора элементов из второго массива – Y[i]> X[0].
Описанный алгоритм формирования нового массива и программа представлены на рисунке 2.20.
|
Используемые переменные: x[] – статический (исходный) массив; n – число элементов массива X; y[] – статический (исходный) массив; m – число элементов массива; z[] – динамический (формируемый) массив k – счетчик элементов нового массива Z; i – параметр цикла;
|
#include <stdio.h> main() { int k, n, m, i, x[10], y[10]; puts("Введите число элементов массива X:"); scanf("%d",&n); for(i=0;i<n;i++) { printf("x[%2d]=",i); scanf("%d",&x[i]); } puts("Введите число элементов массива Y:"); scanf("%d",&m); for(i=0;i<m;i++) { printf("y[%2d]=",i); scanf("%d",&y[i]); } int *z=new int[15]; // выделение памяти под массив Z k=0; for(i=1;i<n;i+=2) { if(x[i]>0) { z[k]=x[i]; k++; } } for(i=0;i<m;i++) { if(y[i]>x[0]) { z[k]=y[i]; k++; } } puts("Массив X:"); for(i=0;i<n;i++) printf("x[%d]=%dn",i,x[i]); puts("Массив Y:"); for(i=0;i<m;i++) printf("y[%d]=%dn",i,y[i]); if(k==0) puts("Массив Z не сформиро-ван."); else { puts("Массив Z:"); for(i=0;i<k;i++) printf("z[%d]=%dn",i,z[i]); } delete[] z; // освобождение памяти } |
Рисунок 2.20. Графический алгоритм и программа для примера 2.8
Литература
Мук №3089. Кравченко О.А., Мартыненко А.М. Программирование ввода–вывода данных и линейных вычислительных алгоритмов на языке С: практ. пособие к выполнению лаб. и контрол. работ по дисциплине "Вычислительная техника и программирование" для студентов техн. специальностей днев. и заоч. форм обучения Гомель: ГГТУ им. П.О. Сухого, 2005. – 33 с.
Мук №3106. Кравченко О.А., Коробейникова Е.В. Программирование разветвляющихся и циклических алгоритмов на языке С: пособие по выполнению лабораторных и контрольных работ по дисциплине"Вычислительная техника и программирование" для студентов техн. специальностей днев. и заоч. форм обучения Гомель: ГГТУ им. П.О. Сухого, 2005. – 33 с
Информатика. Базовый курс : учеб. пособие / под ред. С. В. Симоновича. - 2-е изд. - Санкт-Петербург : Питер, 2007. - 639с. : ил. - (Учебник для вузов). - Библиогр.: с.631-632. - ISBN 5-94723-752-0
С/С ++. Программирование на языке высокого уровня / Т. А. Павловская. - Санкт-Петербург : Питер, 2006. - 460с. : ил. - (Учебник для вузов). - Библиогр.:с.383. - ISBN 5-94723-568-4.
С#. Программирование на языке высокого уровня / Т. А. Павловская. - Сант-Петербург : Питер, 2007. - 432с. : ил. - (Учебник для вузов). - Библиогр.: с.425-426. - ISBN 5-91180-174-4.
Информатика : учеб. для вузов / В. А. Острейковский. - Москва : Высш. шк., 2000. - 511с. : ил. - Библиогр.: с.508. - ISBN 5-06-003533-6.
Информатика: Учебник /Под ред. Проф. Н.В.Макаровой. –М.: Финансы и статистика, 1998.
Касаткин А.И., Вальвачев А.Н. Профессиональное программирование на языке СИ: от Turbo C к Borland C++: Справ.пособие. – Мн.: Выш.шк., 1992. – 240 с.
Топп У., Форд У. Структуры данных в С++: Пер. с англ.–М.: БИНОМ, 1994. – 816 с.
Крячков А.В., Сухина И.В., Томшин В.К. Программирование на С и С++. Практикум: Учебн. Пособие для вузов. – М.: Горячая лининия – Телеком, 2000 – 344 с.
Страуструп Б. Язык программирования Си++: Пер. с англ.– М.: Радио и связь, 1991. – 352 с.
Приложение
Примеры решения задач по обработке одномерных массивов
Задача 1.
Вычисление сумм, количеств и произведений элементов массива
Предполагается, что задан массив чисел. Программа должна:
1) вводить размерность и элементы массива;
2) вводить некоторые дополнительные числа;
3) выполнять действия в соответствии с условием задачи;
4) выводить исходные данные и результаты вычислений.
Исходные данные для отладки программы выбрать самостоятельно. Массив объявить как статический.
Задание:
В одномерном массиве A размерностью n, найти количество чисел, меньших заданного X, и произведение отрицательных чисел, стоящих на четных местах.
Решение
Таблица соответствия переменных
| Переменные в задаче | Имя на языке Си | Тип | Комментарий |
| A[] | A[] | float | Одномерный статический массив |
| n | n | int | Количество элементов массива |
| P | P | float | Произведение отрицательных чисел |
| X | x | float | Заданное число |
| k | k | int | Количество чисел меньших X |
| – | k1 | int | Количество отрицательных чисел |
| – | i | int | Номер элемента массива; параметр цикла |
Графическая схема алгоритма

Описание алгоритма
блоки 1 – 2 вводятся исходные данные;
блоки 3 – 9 вычисление и вывод количества K меньших заданного X;
блоки 10 – 18 вычисление количества K1 и произведения P отрицательных элементов массива стоящих на четных местах;
блоки 18 – 20 проверка на наличие в массиве отрицательных чисел на четных местах и в случаи выполнения проверки вывод их произведения P.
Листинг программы
#include <stdio.h>
#include <math.h>
main ()
{
float P, A[10], x; //Описание переменных
int i, k1, k, n;
puts (“ Введите число x”);
scanf (“%f”, &x); // Ввод x
puts (“ Введите число элементов массива А”);
scanf (“%d”, &n);
for (i=0; i<n; i++) // Ввод массива
{
printf(“Введите число A[%d]=”, i);
scanf(“%f”, &A[i]);
}
puts(“Массив А”); // Вывод массива
for (i=0; i<n; i++)
printf(“%.2f “, A[i]);
printf(“n”);
printf(“ x=%.3f n”, x); // Вывод x
k=0;
for (i=0; i<n; i++)
if (A[i]<x) k=k+1; // Определение кол-ва чисел <x
printf(“ k=%dn” ,k);










