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

Задачи генерации и вывода массивов предполагают заполнение массива значениями элементов требуемым способом и их вывод.

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

Задачи замены в массивах предполагают изменение значений элементов массива в соответствии с условием (заменить все отрицательные значения их модулями, все четные положительные элементы уменьшить вдвое и т.д.).

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

Задачи сортировок массивов предполагают расположить элементы массива по закономерности (по возрастанию, по алфавиту, в порядке убывания модулей и т.д.).

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

Задачи поиска в массивах

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

Пример 7. Найдем минимальный элемент в одномерном целочисленном массиве, заданном случайными числами на промежутке [-100; 100).

Один из алгоритмов поиска минимального элемента в массиве таков. Будем формировать значение минимального элемента в переменной min. Предположим, что минимальный элемент массива равен нулевому (min=x[0]). Затем выполним просмотр массива с первого элемента до последнего (for (i=1;i<k;i++)). Каждый элемент массива сравниваем со значением переменной min. Если значение очередного i -го элемента массива меньше min, то выполняем присваивание min=x[i].

//Поиск наименьшего элемента в массиве #include "stdafx.h"#include <iostream>using namespace std;#include <time.h> //подключение модуля для генератора случайных чисел#define max 100 void gen (int k,int a, int b,int x[max]); //прототип функции генерации массиваvoid out (int k,int x[max]);//прототип функции вывода массиваint minimum (int k,int x[max]); //прототип функции поиска минимального элемента int _tmain(int argc, _TCHAR* argv[]){ int mas[max],n;   do { printf("\nВведите количество элементов массива n (n<=100):"); scanf ("%d",&n); } while (n>max); gen(n,-100,100,mas); out(n,mas); printf ("\nНаименьший элемент в массиве равен %d", minimum(n,mas)); system("pause"); return 0;} //Описание функции генерации массиваvoid gen(int k,int a, int b, int x[max]){   int i; srand(time(NULL)*1000);   //устанавливает начальную точку генерации случайных чисел for (i=0;i<k;i++){ x[i]= rand()%(b-a)+a;     //функция генерации случайных чисел на [a,b) }}//Описание функции вывода массива в строкуvoid out (int k,int x[max]){ int i; printf("\nВывод значений %d элементов массива в строку: \n",k);   for (i=0;i<k;i++) printf("%-6d",x[i]);}//Описание функции поиска минимального элементаint minimum (int k,int x[max]) { int i,min=x[0]; for (i=1;i<k;i++) if (min>x[i]) min=x[i]; return min;}

Пример 8. Найдем среднее арифметическое элементов одномерного вещественного массива, заданного с клавиатуры.

//Поиск среднего арифметического элементов массива#include "stdafx.h"#include <iostream>using namespace std;#include <time.h>//подключение модуля для генератора случайных чисел#define max 100 void gen (int k, float x[max]); //прототип функции генерации массиваfloat sred_arifm (int k, float x[max]); /*прототип функции поиска среднего арифметического элементов массива*/ int _tmain(int argc, _TCHAR* argv[]){ float mas[max]; int n;   do { printf("\nВведите количество элементов массива n (n<=100):"); scanf ("%d",&n); } while (n>max); gen(n,mas); printf ("\nСреднее арифметическое массива равно %f",             sred_arifm(n,mas)); system("pause"); return 0;} //Описание функции генерации массива с клавиатурыvoid gen(int k, float x[max]){  int i; printf("\nВведите значения %d элементов массива: \n",k);   for (i=0;i<k;i++){ printf("x[%d]= ",i); scanf("%f",&x[i]); }}/*Описание функции поиска среднего арифметического элементов массива*/float sred_arifm (int k, float x[max]) { int i; float sum=0.0; for (i=0;i<k;i++) sum+=x[i]; //вычисление суммы элементов массива return sum/k;}

Задачи замены в массивах предполагают решение задачи на поиск с последующим изменением найденных значений. В основе решения таких задач лежат поисковые алгоритмы с выбором подходящей схемы перебора.

Пример 9. Дан одномерный целочисленный массив, заданный случайными числами на промежутке [-50; 50). Заменить в массиве все отрицательные элементы на элементы им противоположными.

Для решения задачи выполним просмотр массива с начала. Каждый элемент сравним с нулем, при этом отрицательные значения элементов заменим им противоположными (if (x[i]<0) x[i]=-x[i]). В данной задаче целесообразно выполнить вывод массива дважды: до и после замены.