Перебор элементов массива по два

Элементы массива можно обрабатывать по два элемента, двигаясь с обеих сторон массива к его середине:

int i=0, j=n-1;

while (i<j)

{обработка a[i] и a[j];i++;j--;}

Пример: «перевернуть» массив (поменять порядок следования его элементов так, чтобы первый стал последним, второй – предпоследним, …, последний – первым).

#include<stdio.h>

#include<stdlib.h>

include<time.h>

void main()

{

int a[100];

int n;

printf(“\nEnter the size of array: ”);

scanf(“%i”,&n);

srand((unsigned)(time(NULL));

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

a[i]=rand()%101-50;//случайные числа из [-100..100]

printf(“%i “, a[i]);

}

for(int i=0,j=n-1; i<j; i++,j--){

int tmp=a[i];

a[i]=a[j];

a[j]=tmp;

}

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

printf(“%d “,a[i]);

}

1) Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 1(т. е. обрабатываются пары элементов a[1] и a[2], a[2] и a[3] и т. д.):

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

{обработка a[i] и a[i+1]}

Пример: найти пару последовательных элементов, произведение которых максимально. Если таких пар несколько, выдать последнюю из них.

#include<stdio.h>

#include<stdlib.h>

include<time.h>

int main()

{

int a[100];

int n;

printf(“\nEnter the size of array: ”);

scanf(“%i”,&n);

srand((unsigned)(time(NULL));

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

a[i]=rand()%101+50;//значения из [50..150]

printf(“%i “, a[i]);

}

int max=a[0]*a[1];

int index=0;//индекс левого из искомой пары элементов

for(int i=1; i<n-1; ++i)/*обратите внимание на i<n-1: в последней пареучаствуют предпоследний и последний элементы массива*/

if(a[i]*a[i+1]>=max){

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

index=i;

}

printf(“%d %d\n”,a[index],a[index+1]);

return 0;

}

2) Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 2 (т. е. обрабатываются пары элементов a[1] и a[2], a[3] и a[4] и т. д.)

int i=0;

while (i<n-1)

{обработка a[i] и a[i+1];

i+=2;}

Пример: массив содержит n пар элементов. Первый из пары элементов – идентификатор подразделения (целое трехзначное число), второй – количество сотрудников в нем.

Найти подразделение с наименьшим числом сотрудников.

#include<stdio.h>

int main()

{

int a[100];

int n;

printf(“\nEnter the number of parts n (n<=100): ”);

scanf(“%i”,&n);

printf(“\nEnter information about %d parts\n,n);

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

printf(“Identificator of part and number of it’s workers: “);

scanf(“%d %d”, &a[2*i-1],&a[2*i];

}

int min=a[1];

int nomer=a[0];

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

if(a[i+1]<min){

min=a[i+1];

nomer=a[i];

}

printf(“\nmin=%d, nomer=%d\n”,min,nomer);

return 0;

}

8.3. Классы задач по обработке массивов

1) К задачам 1 класса относятся задачи, в которых выполняется однотипная обработка всех или указанных элементов массива.

2) К задачам 2 класса относятся задачи, в которых изменяется порядок следования элементов массива.

3) К задачам 3 класса относятся задачи, в которых выполняется обработка нескольких массивов или подмассивов одного массива. Массивы могут обрабатываться по одной схеме – синхронная обработка или по разным схемам – асинхронная обработка массивов.

4) К задачам 4 класса относятся поисковые задачи в массиве.

Задачи 1-ого класса

Решение таких задач сводится к установлению того, как обрабатывается каждый элемент массива или указанные элементы, затем подбирается подходящая схема перебора, в которую вставляются операторы обработки элементов массива. Примером такой задачи является нахождение максимального элемента массива или среднего арифметического массива.

Пример: в массиве натуральных чисел найти элемент с наибольшей суммой цифр.

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

int main()

{

int a[100];

int n;

printf(“\nEnter the size of array:”);

scanf(“%d”,&n);

int max=0;int elem;

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

a[i]=rand()%2001+1000;//значения из [1000..2000]

printf(“%d “,a[i];

int sum=0;

int tmp=a[i];//находим сумму цифр

while(tmp){

sum+=tmp%10;

tmp/=10;

}//while tmp>0

if(sum>max){

sum=max;

elem=a[i];

}//if sum>max

}//for i

printf(“\nmax_summa=%d, elem=%d\n”,max,elem);

return 0;

}

Задачи 2-ого класса

Обмен элементов внутри массива выполняется с использованием вспомогательной переменной:

int tmp=a[i];a[i]=a[j]; a[j]:=tmp; // обмен a[i] и a[j] элементов массива.

Пример 1. Перевернуть массив.

//пусть массив уже сформирован

for(int i=0,j=n-1; i<j; i++,j--) {

int tmpr=a[i];

a[i]=a[j];

a[j]=tmp;}

Пример 2. Поменять местами пары элементов в массиве: 1 и 2, 3 и 4, 5 и 6 и т. д.

for(int i=0; i<n-1; i+=2){

int tmp=a[i];

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

a[i+1]=tmp;}

Пример 3. Циклически сдвинуть массив на k элементов влево (вправо).

int k,i,t,r;

printf(“\nk=");

scanf(“%d”, &k);

for(t=0;t<k;t++){ // k раз

r=a[0];

for(int i=0;i<n-1;i++) // циклический сдвиг на 1

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

a[n-1]=r;

}

Задачи 3-ого класса

При синхронной обработке массивов индексы при переборе массивов меняются одинаково.

Пример 1. Заданы два массива из n целых элементов. Получить массив c, где c[i]=a[i]+b[i].

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

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

При асинхронной обработке массивов индекс каждого массива меняется по своей схеме.

Пример 2. В массиве целых чисел все отрицательные элементы перенести в начало массива.

int i=0,j=n-1;

while(i<j){

while(i<n && a[i]<0) // очередной неотрицательный слева

++i;

while(j>=0 && a[j]>=0)//очередной отрицательный справа

j--;

if(i<j) { // обмен

int tmp=a[i];a[i]=a[j];a[j]=tmp;

}

}

В предложенном выше варианте порядок следования неотрицательных не сохраняется, так же как и отрицательных. Если этот порядок существенен, можно использовать следующий фрагмент кода:

int io= 0;//место очередного отрицательного

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

if(a[i]<0){

//сдвиг вправо элементов a[io]..a[i-1]

int tmp=a[i];

for(int j=i-1; j>=io; --j)

a[j+1]=a[j];

a[io++]=tmp;

}

Пример3. Удалить из массива все четные числа.

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

if(a[i]%2==0) { // удаление a[i]

for(int j=i+1; j<n; ++j) // сдвиг вправо элементов a[i+1]..a[n-1]

a[j-1]=a[j];

--n; // уменьшение количества элементов

}

Задачи 4-ого класса

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

- нужный элемент найден;

- элемент не найден, но просмотр массива закончен.

Пример 1. Найти первое вхождение элемента key в массиве целых чисел.

int key;

printf(“\nkey=");

scanf(“%d”,&key);

int ok=0;//признак найден элемент или нет

int i,nom;

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

if(a[i]==key){

ok=1;nom=i;break;

}

if(ok==1)

printf("\nnom=%d\n",nom);

else

printf("\nthere is no such element!\n");

Можно в качестве признака ok использовать nom:

int i,nom=-1;

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

if(a[i]==key){

nom=i;break;

}

if(nom==-1)

printf("\nnom=%d\n",nom);

else

printf("\nthere is no such element!\n");

8.4. Сортировка массивов

Сортировка – это процесс перегруппировки заданного множества объектов в некотором установленном порядке. Элементы массива могут быть расположены по возрастанию (каждый элемент меньше следующего), по неубыванию (каждый элемент не больше следующего), по убыванию (каждый элемент больше следующего), по невозрастанию (каждый элемент не меньше следующего). Далее будем считать, что массив сортируется по неубыванию, что не уменьшает общности рассуждений.

Сортировки массивов подразделяются по быстродействию. Существуют простые методы сортировок, количество сравнений в которых пропорционально n*n, где n – количество элементов массива, и быстрые сортировки, количество сравнений в которых пропорционально n*ln(n). Простые методы удобны для объяснения принципов сортировок, имеют простые и короткие алгоритмы. Усложненные методы требуют меньшего числа операций, но сами операции более сложные, коды соответствующих функций нетривиальны, больше вероятность появления в них ошибок. Кроме того, для небольших массивов улучшенные методы сортировок могут работать даже дольше, преимущество их проявляется лишь в асимптотике. Функции, сортирующие большие массивы с помощью улучшенных методов сортировки, есть во многих современных средах разработки программ, поэтому не нужно разрабатывать их заново самим, но нужно уметь ими пользоваться. Одна из самых известных и распространенных сортировок – быстрая сортировка, обычно ее называют qsort.

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

Простые методы подразделяются на три основные категории:

- сортировка методом простого включения;

- сортировка методом простого выделения;

- сортировка методом простого обмена.

Date: 2016-11-17; view: 637; Нарушение авторских прав