Примеры алгоритмов, использующих одномерные массивы

а) Простейший пример

Задача 1. Ввести с клавиатуры массив, а затем вывести только его положительные элементы:

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

void main()

{

int a[100],n,i;

M: cout<<"Vvedite n<=100:";

cin>>n;

if(n>100) goto M;

cout<<"Vvedite massiv:\n";

for (i=0; i<n; i++)

cin>>a[i];

cout<<"Polozhitelnye elementy: ";

for (i=0; i<n; i++)

if (a[i]>0)

cout<<a[i]<<" ";

cout<<endl;

getch();

}

б) Нахождение суммы, произведения, количества

Задача 2. Найти сумму элементов массива.

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

void main()

{

int a[100],n,i,s;

M: cout<<"Vvedite n<=100:";

cin>>n;

if(n>100) goto M;

cout<<"Vvedite massiv:\n";

for (i=0; i<n; i++)

cin>>a[i];

s=0;

for (i=0; i<n; i++)

s+=a[i];

cout<<"summa="<<s<<endl;

getch();

}

Задача 3. Найти сумму положительных элементов массива.

От предыдущей задачи она отличается только добавлением оператора if:

s=0;

for (i=0; i<n; i++)

if (a[i]>0)

s+=a[i];

Задача 4. Найти произведение положительных элементов массива.

Содержательный участок программы имеет вид:

s=1;

for (i=0; i<n; i++)

if (a[i]>0)

s*=a[i];

Задача 5. Найти количество положительных элементов массива.

s=0;

for (i=0; i<n; i++)

if (a[i]>0)

s++;

Задача 6. Найти сумму четных (по значению) элементов массива.

s=0;

for (i=0; i<n; i++)

if (a[i]%2==0)

s+=a[i];

в) Нахождение порядковых номеров элементов

Задача 7. Найти сумму четных (по порядковому номеру) элементов массива.

Поскольку индексы элементов считаются с 0, а порядковые номера - с 1, четный порядковый номер означает нечетный индекс:

s=0;

for (i=0; i<n; i++)

if (i%2==1)

s+=a[i];

Задача 8. Найти индексы отрицательных элементов массива.

for (i=0; i<n; i++)

if (a[i]<0)

cout<<i<<" ";

cout<<endl;

Задача 9. Найти индекс первого из отрицательных элементов массива.

for (i=0; i<n; i++)

if (a[i]<0) {

cout<<i<<endl;

break;

}

Задача 10. В массиве найти первый и последний нулевой элементы. Все элементы, лежащие между ними, увеличить на 1.

for (i=0; i<n; i++)

if (a[i]==0) {

cout<<i<<endl;

break;

}

for (k=n-1; k>=0; k--)

if (a[k]==0) {

cout<<k<<endl;

break;

}

for (p=i+1; p<k; p++)

a[p]++;

for (i=0; i<n; i++)

cout<<a[i]<<" ";

cout<<endl;

г) Проверка условия, относящегося к массиву.

Задача 11. Проверить, все ли элементы массива меньше 5.

Для этого достаточно подсчитать количество элементов,не меньших 5:

for (i=s=0; i<n; i++)

if (a[i]>=5)

s++;

if (s)

cout<<"Ne vse elementy men\'she 5!";

Заметим, что s++ можно заменить на s=1, т.к. конкретное количество элементов здесь несущественно.

Таким образом, для проверки условия, относящегося к массиву в целом, обычно нужна дополнительная переменная и цикл.

д) Удаление и вставка в массивах

Задача 11. Удалить из массива второй по счету элемент.

Поскольку полное количество элементов в массиве задано в его объявлении, физически "удалить" элемент из массива невозможно. Но с практической точки зрения, "удалить" элемент можно путем "сдвига" всех следующих за ним элементов "влево" (т.е. на предыдущую позицию, с меньшим на 1 индексом) и уменьшения на 1 количества используемых элементов:

1

Здесь используемые элементы выделены жирным цветом, а неиспользуемые - бледным.

Фрагмент программы имеет вид:

for (i=2; i<n; i++)

a[i-1]=a[i];

n--;

Задача 12. Удалить из массива элементы, большие 10.

В этой задаче требуется удалить заранее неизвестное количество элементов; поэтому неясно, на сколькр позиций нужно производить сдвиг. Потому лучше просто ввести две разные переменные: индекс элемента "до сдвига" и его индекс "после".

Сдвинуть нужно все неудаляемые элементы. Их количество и будет новым числом используемых элементов массива.

Индекс "до сдвига", очевидно, принимает все значения от 0 до n-1. А индекс "после" увеличивается на 1 после каждой записи очередного элемента:

for (k=i=0; i<n; i++)

if (a[i]<=10) a[k++]=a[i];

n=k;

Задача 13. Вставить в массив число 5 на вторую по счету позицию.

Подобно удалению, "вставка элемента" по сути означает "сдвиг" части элементов массива "вправо" (т.е. на последующие позиции, с б о льшими индексами) и помещение вставляемого числа на освободившуюся позицию. При этом число используемых элементов возрастает.

При программировании этого алгоритма нужно быть осторожным, чтобы не испортить последующие элементы массива раньше, чем они будут сдвинуты. Например, следующая программа:

for (i=0; i<n; i++)

a[i+1]=a[i];

n++;

заполнит все n элементов массива одним и тем же значением, равным первоначальному значению a[0]. Действительно, при первой итерации цикла i=0, и будет выполнено a[1]=a[0]. При второй итерации будет a[2]=a[1] (а значение a[1] уже равно a[0]) и т.д.

Одним из выходов является использование второго массива:

b[0]=a[0];

b[1]=5;

for (i=1; i<n; i++)

b[i+1]=a[i];

n++;

for (i=0; i<n; i++)

a[i]=b[i];

Другой способ - изменить порядок сдвига:

for(i=n; i>1; i--)

a[i]=a[i-1];

a[1]=5;

n++;

Дата добавления: 2014-01-05