Одномерные массивы: задачи поиска, замены и перестановок элементов массива

Цель лекции: изучить алгоритмы поиска, замены, перестановок и научиться решать задачи на применение алгоритмов поиска, замены, перестановок в одномерных массивах в языке C++.

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

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

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

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

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

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

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

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

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

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

Пример 1. Найдем минимальный элемент в одномерном целочисленном массиве, заданном случайными числами на промежутке [-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;
}

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

//Поиск среднего арифметического элементов массива
#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;
}

Задачи замены в массивах

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

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

Для решения задачи выполним просмотр массива с начала. Каждый элемент сравним с нулем, при этом отрицательные значения элементов заменим им противоположными ( if (x[i]<0) x[i]=-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]); 
//прототип функции вывода массива
void zamena (int k, int x[max]);
//прототип функции замены

int _tmain(int argc, _TCHAR* argv[]){
  int mas[max];
  int n; 
  do {
    printf("\nВведите количество элементов массива n (n<=100):");
    scanf ("%d",n);
  }
  while (n>max);
  gen(n,-50,50,mas);
  printf("Вывод сгенерированного массива из %d элементов: \n", n);
  out(n,mas); 
  zamena (n,mas);
  printf("\nВывод массива после замены отрицательных 
          элементов на протипоположные:\n");
  out(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;
   }
}
//Описание функции вывода массива в строку
void out (int k,int x[max]){
  int i;
  for (i=0;i<k;i++)
  printf("%-6d",x[i]);
} 
//Описание функции замены
void zamena(int k,int x[max]){
  int i;
  for (i=0;i<k;i++) 
    if (x[i]<0) x[i]=-x[i];
}

Задачи перестановок в массивах

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

Пример 4. Дан одномерный целочисленный массив, заданный случайными числами на промежутке [-10; 10). Выполните циклический сдвиг элементов с нулевой позиции вправо на одну позицию. То есть должна быть реализована схема перестановок: x[0] -> x[1], x[1] -> x[2], ... , x[k-1] -> x[0].

Одним из алгоритмов такого циклического сдвига является следующая последовательность действий. Поместим в буфер последний элемент массива ( buf=x[k-1] ). Выполним смещение остальных элементов вправо на одну позицию ( x[i]=x[i-1] ). При этом важен порядок смещения: на освободившееся место последнего элемента перемещается предпоследний, на место предпоследнего – предшествующий ему и т.д. В результате таких перемещений освобождается место нулевого элемента, на которое перемещается элемент из буфера. В данной задаче целесообразно выполнить вывод массива дважды: до и после циклического сдвига.

/*Циклический сдвиг элементов в массиве с нулевой позиции на одну позицию вправо*/
#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]);
//прототип функции вывода массива
void sdvig (int k, int x[max]);
//прототип функции циклического сдвига элементов массива

int _tmain(int argc, _TCHAR* argv[]){
  int mas[max];
  int n; 
  do {
    printf("\nВведите количество элементов массива n (n<=100):");
    scanf ("%d",n);
  }
  while (n>max);
  gen(n,-10,10,mas);
  printf("Вывод сгенерированного массива из %d элементов: \n",n);
  out(n,mas); 
  sdvig (n,mas);
  printf("\nВывод массива после циклического сдвига 
          элементов: \n");
  out(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;
   }
}

//Описание функции вывода массива в строку
void out (int k,int x[max]){
  int i;
  for (i=0;i<k;i++)
  printf("%d   ",x[i]);
} 
//Описание функции циклического сдвига элементов массива
void sdvig(int k,int x[max]){
  int i,buf;
  buf=x[k-1];
  for (i=k-1;i>0;i--) 
    x[i]=x[i-1];
  x[0]=buf;
}

Ключевые термины

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

Задачи замены в массивах – это изменение значений элементов массива в соответствии с условием.

Задачи перестановок в массивах – это выполнение обмена местами элементов в первоначально заданном массиве в соответствии с условием.

Задачи поиска в массивах – это нахождение элементов массива, соответствующих заданным условиям

Задачи сортировок массивов – это расположение элементов массива по заданной закономерности.

Комбинированные задачи – это задачи, сочетающие в себе алгоритмы решения нескольких классов задач одновременно.

Краткие итоги

Лабораторная работа 11. Одномерные массивы: задачи поиска, замены и перестановок элементов массива

Цель работы: изучить алгоритмы поиска, замены, перестановок и научиться решать задачи на применение алгоритмов поиска, замены, перестановок в одномерных массивах в языке C++.

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

Теоретические сведения.

Ознакомьтесь с материалом лекции 11.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

Указания к выполнению работы.

Каждое задание необходимо решить в соответствии с изученными методами объявления, генерации и вывода одномерных массивов в языке С++. Обработку данных необходимо выполнить, используя алгоритмы поиска, замены и перестановок данных в одномерных массивах. При разработке программного кода требуется использовать метод процедурной абстракции и комментировать фрагменты кода.

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

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

Контрольные вопросы