Методические указания по теме "Одномерные массивы"
методическая разработка по информатике и икт по теме

САНКТ-ПЕТЕРБУРГСКИЙ

КОЛЛЕДЖ  ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ЗАНЯТИЮ ПО ТЕМЕ

«Массивы»

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

Преподаватель: Шапкина Л.М.

Массивы

Массив (array) — это коллекция переменных одинакового типа, обращение к которым происходит с применением общего для всех имени. В C++ массивы могут быть одно- или многомерными. Массивы представляют собой удобное средство группирования связанных переменных.

Одномерные массивы

Одномерный массив — это список связанных переменных. Для объявления одномерного массива используется следующая форма записи.

тип имя_массива [размер] ;

Здесь с помощью элемента записи тип объявляется базовый тип массива. Базовый тип определяет тип данных каждого элемента, составляющего массив. Количество элементов, которые будут храниться в массиве, определяется элементом размер. Например, при выполнении приведенной ниже инструкции объявляется int-массив (состоящий из 10 элементов) с именем sample.

int   sample[10];

Индекс идентифицирует конкретный элемент массива.

Доступ к отдельному элементу массива осуществляется с помощью индекса. Индекс описывает позицию элемента внутри массива.

В C++ первый элемент массива имеет нулевой индекс.

Поскольку массив sample содержит 10 элементов, его индексы изменяются от 0 до 9. Чтобы получить доступ к элементу массива по индексу, достаточно указать нужный номер элемента в квадратных скобках. Так, первым элементом массива sample является sample [ 0 ], а последним — sample [ 9]. Например, следующая программа помещает в массив sample числа от 0 до 9.

#include

#include

#include

int main () {  clrscr();

int sample[10];   // Эта инструкция резервирует область памяти для 10 элементов типа int.

  int t;

// Помещаем в массив значения.

for(t=0; t<10; t++) sample[t]=t;

// Отображаем массив.

for(t=0; t<10; ++t) cout<

В C++ все массивы занимают смежные ячейки памяти.

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

int i[7]; int j; for(j=0; j<7; j+ + )    i[j] = j;

массив будет выглядеть следующим образом.

Для одномерных массивов общий размер массива в байтах вычисляется так:

всего байтов = размер типа в байтах умножить на количество элементов.

В С++ нельзя определять произвольные диапазоны для индексов. Размер массива, указанный в описании, всегда на единицу больше максимального значения индекса.

Инициализация массива

int a[7]={1,2,3,4,5,6,7};

int a[7]={0};   Все элементы массива получат значение 0, или неопределенные.

int a[7]={1,2,3}; Первые три элемента получат значения 1, 2, 3, остальные – 0, или неопределенные.

«Безразмерная» инициализация массива

Размер массива может явно не указываться, если при его объявлении производится инициализация значений элементов. Например:     int   p[]={2,    4,    6,    10,    1};

В этом случае создается массив из пяти элементов со следующими значениями:

р[0]=2,   р[1]=4,   р[2]=6,   р[3]=10,   р[4]=1

В результате следующего объявления массива  int  М[б]={5,    3,   2} ;

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

Константное выражение определяет размер массива, т. е. число элементов этого массива. Например, согласно описанию int  A[10]; объявлен массив с именем А, содержащий 10 элементов целого типа. Элементы массива обозначаются индексированными именами. Нижнее значение индекса равно 0:    А[0],   А[1],   А[2],   А[3],   А[4],   А[5],   А[б],   А[7], А[8],   А[9]

В качестве константного выражения может быть арифметическое выражение, например:

int m = 6, n = 5; int a[m * n];

Константа, определяющая размер массива может быть объявлена один раз в начале программы, это создает удобство при изменении программы, если надо изменить размер массива.

const m=10;     int a[m];  for (i=0; i

В C++ нельзя присвоить один массив другому. В следующем фрагменте кода, например, присваивание а = b; недопустимо.

int а[10] , b[10] ;

a =  b;   //   Ошибка!!!

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

На границах массивов погранзаставы нет

C++ не выполняется никакой проверки "нарушения границ" массивов, т.е. ничего не может помешать программисту обратиться к массиву за его пределами. Если это происходит при выполнении инструкции присваивания, могут быть изменены значения ячейках памяти, выделенных некоторым другим переменным или даже вашей программе. Другими словами, обращение к массиву (размером N элементов) за границей N-го элемента может привести к разрушению программы при отсутствии каких-либо замечаний со стороны компилятора и без выдачи сообщений об ошибках во время работы программы. Это означает, что вся ответственность за соблюдение границ массивов лежит только на программистах, которые должны гарантировать корректную работу с массивами. Другими словами, программист обязан использовать массивы достаточно большого размера, чтобы в них можно было без осложнений помещать данные, но лучше всего в программе предусмотреть проверку пересечения границ массивов.

Рассмотрим несколько примеров программ обработки одномерных массивов.

Пример. Ввод с клавиатуры и вывод на экран одномерного массива.

//Ввод  и  вывод  массива

#include

#include  

#include  

void main() { int  i,   A[5]; clrscr();

for(i=0;   i<5;   i++)  {   cout<<"A["<>A[i];}

for(i=0;   i<5;   i++)   cout<<"A [ "<

Пример. Ввод вещественного массива и вычисление среднего значения.

//Среднее   значение  массива

#include  

#include  

#include

void main() {  const  n=10;

int  i;   double  A[n],   SA;  сlrsсr() ;

for(i=0;   i>A[i] ; }

SA=0;  for(i=0; i

cout<<"/n среднее значение="<

В этой программе обратите внимание на определение размера массива через константу.

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

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

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

Пример. Сортировка массива «методом пузырька».

//Сортировка массива

#include

#include

#include

void main() { int X[]={6,4,9,3,2,1,5,7,8,10};

int i,j,n,A; clrscr() ;

n=sizeof(X)/sizeof(X[0]);

for(i=0; i

for(j=0;   j

   if (X[j]>X[j+1] )     {A=X[j];    X[j]=X[j+1];    X[j+1]=A;}

for(i=0; i

/*  1 2 3 4 5 6 7 8 9 10   */

В данной программе массив инициализирован. Его размер равен числу заданных значений. Чтобы сделать программу универсальной по отношению к размеру массива, значение размера вычисляется автоматически и заносится в переменную n. Для этого используется операция sizeof () — определение размера в байтах. Результат sizeof (X) равен размеру в памяти всего массива X — 20 байтам. Результат sizeof (Х[0] ) равен размеру одного элемента массива — 2 байтам. Отношение этих величин равно 10 — числу элементов массива. Внимательно проанализируйте организацию перебора значений параметров вложенных циклов — i,   j.

В результате выполнения этой программы на экран выведется упорядоченная числовая последовательность    1 2 3 4 5 6 7 8 9 10

Алгоритмы обработки одномерных массивов

1. Заполнение массива

2. Вывод значений массива на экран

3. Подсчет значений элементов массива

4. Упорядочение значений массива

5. Поиск значений в массиве

6. Реорганизация массива

7. Работа с несколькими массивами

Библиотеки для работы приведенных ниже программ:

#include         ввод, вывод cin, cout

#include             очистка экрана clrscr(); ожидание нажатия любой клавиши getch();

#include              ввод, вывод  scanf, printf

#include             получение случайных чисел

1. Заполнение массива

Заполнение массива нулями, замена значений элементов 0 и 2, вывод на экран

void main(){ clrscr();

    int i, a[3]; for(i=0; i<3; i++) a[i]=0;

    a[0]=8; a[2]=10; s=0; for(i=0; i<3; i++) cout<

getch(); }   ./*  8 0 10 */

Заполнение массива значениями индекс плюс один, вывод на экран, изменение значений элементов массива по принципу – последующий элемент получает значение предыдущего, вывод на экран.

void main() { clrscr();

    int i, a[5]; for(i=0; i<5; i++){ a[i]=i+1;   cout<<" "<

     for(i=0; i<4; i++) a[i+1]=a[i];

     for(i=0; i<5; i++) cout<<" "<

getch(); }

/*      1 2 3 4 5

         1 1 1 1 1    */

Заполнение массива значениями с клавиатуры.

См. пример стр. 2

Заполнение массива случайными числами.

#include      // для функции получения случайного числа

void main(){ clrscr(); randomize();

    int i, a[10]; for(i=0; i<10; i++) {a[i]=random(100); cout<

getch(); }  

2. Вывод значений массива на экран

В одну строку         for(i=0; i

В столбец                for(i=0; i

По значению, заданному с клавиатуры

cout<<”\n vvedi number >”; cin>>k;

for(i=0; ik) cout<

3. Подсчет значений элементов массива

Сумма элементов массива

s=0;  for(i=0; i

Сумма нечетных элементов массива

s=0;  for(i=1; i

Сумма четных элементов массива

s=0;  for(i=0; i

Среднее значение элементов массива

s=0;  for(i=0; i

Сумма элементов массива по заданному условию (положительные)

s=0;  for(i=0; i0) s+=a[i];  cout<

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

cout<<”\n vvedi number >”; cin>>k;

s=0;  for(i=0; ik) s+=a[i];  cout<

4. Упорядочение значений массива

Пузырьковая сортировка Вариант 1, см. стр. 3)

Пузырьковая сортировка Вариант 2 (по возрастанию)

#include

int main() { clrscr(); randomize();

int nums[10]; int a, b, t; int size;

size = 10; // Количество элементов, подлежащих сортировке.

// Помещаем в массив случайные числа.

 for(t=0; t

// Отображаем исходный массив.

cout << "Исходный массив: ";

for(t=0; t

cout << '\n';

// Реализация метода пузырьковой сортировки.        

for(a=l; a

for (b=size-l; b>=a; b--) {

if(nums[b-l] > nums[b]) { // Элементы неупорядочены.

                                          // Меняем элементы местами.

t = nums[b-1];

nums[b-l] = nums[b];

nums[b] = t; } } // Конец пузырьковой сортировки.

// Отображаем отсортированный массив.

cout << "Отсортированный массив: ";

for(t=0; t

return 0; getch(); }

Сортировка массива прямым выбором

В массиве, начиная с первого элемента, выбирается наименьший элемент и ставится на первое место, а первый – на место наименьшего. Затем, начиная со второго элемента, процедура повторяется.

#define SZ 10

void main (){clrscr();

int a[SZ]={30,53,11,35,17,42,21,84,75,61};

int i;     // счетчик циклов

int k;     // текущий индекс элемента массива

int buf,t,indmin,min;

cout<<"\nisxodnyi array\n";

for(t=0;t

for (i = 0; i < SZ; i++) {

   min=a[i]; indmin=i;

for (k =i+1; k < SZ; k++) {

if (a[k] < min) {

 indmin=k ; min=a[k];

 }

 }

 buf=a[i]; a[i]=a[indmin]; a[indmin]=buf;

 cout<<"indmin="<

for (t = 0; t < SZ; t++)

cout<<" "<

cout<<"\n"; }

cout<<"**********Массив отсортирован\n";

for (t =0; t < SZ; t++)

cout<<" "<

getch ();  }

5. Поиск значений в массиве

Поиск максимального значения

max=a[0];  for(i=0; imax) max=a[i];  cout<

Поиск максимального значения с индикацией положения максимума

max=a[0]; indmax=0;  for(i=0; imax) {max=a[i]; indmax=i;}

cout<<”max=”<

Однопроходный алгоритм подсчета числа минимумов

void main() { clrscr();

const n=10;

int a[n]={25,3,16,-2,1,10,0,5,-2,10};

int i,min,k;

for (i=0;i

min=a[0]; k=1;

for(i=0; i

  if (a[i]

  if (a[i]==min) k++;

  }

cout<<"\n min="<

getch(); }

/*  25 3 16 -2 1 10 0 5 -2 10

 min=-2 kol=2   */

Бинарный поиск в упорядоченном массиве

void main() { clrscr();

const n=1000;

int m[n];

int i,c,k,zc,a,b,kol,pr;

for (i=0;i

cout<<"\n vvod 0-999 ->"; cin>>k;

zc=0; kol=0; a=0; b=n-1;pr=0;

c=(a+b)/2; cout<<"\n******1/2 diapasona= "<

while(c>=a && c<=b && kol<=n){

   if (m[c]==k) { zc=c; pr=1; break;}

   if (k>m[c]) {a=c+1; c=(a+b)/2;kol++;cout<

   if (k

}

if (pr)cout<<"\n poz="<

   else cout<<"\n no number";

cout<<"\n kol="<

Поиск совпадающих элементов в двух упорядоченных массивах разной длины

int main(void){

clrscr();

const n=8; const m=9;

int i,j,k;

int a[n]={1,1,2,3,3,7,8,9};

int b[m]={2,3,4,5,7,7,8,8,9};

for(i=0; i

for(i=0; i

i=0; j=0;  k=0;

while(i

  while(a[i]==a[i+1]){if (i==0) k+=2; else k++; i++; cout<<"\n a "<

    j=0; while(j

       if (a[i]==b[j]){k+=2;

         while(b[j]==b[j+1]){j++; k++; cout<<"\n b "<

          break;}

          j++;}

i++; }

cout<<"\nsovpadaet "<

getch(); return 0; }

Поиск последовательности одного знака

randomize();

const n=20; int i, j1, t, k, j; int a[n];

for (i=0; i

j1=0; if(a[0]>0) j=1; else j=0;

for(i=1; i

    {if((a[i]>0 && j==1)||(a[i]<0 && j==0));

    else {for(t=j1; t

    j1=i;     if(a[i]>0) j=1; else j=0;}}

for(t=j1; t

6. Реорганизация массива

Вставка элемента после заданного значения (после 0 вставить 99)

i=0; while(ii;j--){a[j+1]=a[j];}   i++; a[i]=99;   }i++;  }

Инвертирование массива с четным и нечетным числом элементов

const r=8;

int a[r]={3,28,5,7,6,3,1,2};  int i,j,m,p;  

clrscr();  m=r/2;

for(i=0; i

Циклический сдвиг на одну позицию вправо (в первую позицию – последний элемент)

cout<<"\n vvedite nomer pos sdviga-> "; cin>>t;

i=0; for(j=0;j

 p=a[n-1];   for(i=n;i>0;i--)  a[i]=a[i-1]; a[0]=p; }

Циклический сдвиг на одну позицию влево (в последнюю позицию – первый элемент)

cout<<"\n vvedite nomer pos sdviga-> "; cin>>t;

for(j=0;j

   for(i=0;i

Поменять местами четные и нечетные элементы

for(i=1; i

7. Работа с несколькими массивами

Объединение двух упорядоченных массивов в один, также упорядоченный размеры разные

const n=10,m=7; int a[n]={1,3,4,6,7,8,9,10,14,17};

int b[m]={2,5,11,12,13,15,16}; int c[m+n]; int i,j,k,pr1,pr2; clrscr();

i=0; j=0; k=-1; pr1=0; pr2=0;

while (i

    if(a[i]==b[j]){k++;c[k]=a[i];k++;c[k]=b[j];

       if (i==n-1) {pr1=1; break;}

    if (j==m-1) {pr2=1; break;}

       i++;j++;}

    if(a[i]

       if (i==n-1) {pr1=1; break;}

       i++;}

    if(a[i]>b[j]) {k++;c[k]=b[j];

       if (j==m-1) {pr2=1; break;}

       j++;}       }

if (pr1) i++; if (pr2) j++;

   if(!pr1){for(;i

   if(!pr2){for(;j

Формирование двух массивов из одного, в один - нечетные элементы, во второй - четные

const n=7; int i, t=0, k=0;

int a[n]={1,2,1,2,1,2,1}; int b[n/2+1], c[n/2+1];  for(i=0; i

for(i=0; i

  if (i%2!=0){b[t]=a[i]; t++;}

  else{c[k]=a[i]; k++;}

Одномерные массивы. Практические работы

Практическая работа №1 «Формирование нового массива по заданному условию»

Задание на «удовлетворительно»

В целочисленной последовательности есть нулевые элементы. Создать массив из номеров этих элементов.

Задание на «хорошо»

Дана последовательность целых чисел а1, а2, …, аn. Создать массив из четных чисел этой последовательности. Если таких чисел нет, то вывести сообщение об этом факте.

Задание на «отлично»

Дан массив из целых чисел. Образовать новый массив, элементами которого будут элементы исходного, заканчивающиеся на цифру K.

Практическая работа №2 «Подсчет значений элементов массива»

Задание на «удовлетворительно»

В последовательности действительных чисел а1, а2, …, аn. есть положительные и отрицательные элементы. Вычислить произведение отрицательных элементов Р1 и произведение положительных элементов Р2. Сравнить модуль Р1 с модулем Р2, указать, какое из произведений по модулю больше.

Задание на «хорошо»

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

Задание на «отлично»

Задан массив действительных чисел. Определить, сколько раз меняется знак в данной последовательности чисел, запомнить номера позиций, в которых происходит смена знака.

Практическая работа №3 «Поиск значений в массиве»

Задание на «удовлетворительно»

Даны целые положительные числа а1, а2, …, аn. Найти среди них те, которые являются квадратами некоторого числа m.

Задание на «хорошо»

Дан массив целых чисел. Найти в этом массиве минимальный элемент А и максимальный элемент В. Получить в порядке возрастания все целые числа из интервала [А; В], которые не входят в данный массив.

Задание на «отлично»

В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число. Если таких чисел несколько, то определить наименьшее из них.

Практическая работа №4 «Упорядочение значений массива»

Задание на «удовлетворительно»

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

Задание на «хорошо»

Сортировка обменами. Дана последовательность чисел а1, а2, …, аn. Требуется переставить числа в порядке возрастания. Для этого сравниваются два соседних числа ai и ai+1. Если ai > ai+1, то делается перестановка. Так продолжается до тех пор, пока все элементы не станут расположены в порядке возрастания. Программа должна подсчитывать количество перестановок.

Задание на «отлично»

Сортировка вставками. Дана последовательность чисел а1, а2, …, аn. Требуется переставить числа в порядке возрастания. Делается это следующим образом. Пусть а1, а2, …, аi – упорядоченная последовательность , т.е. а1 <= а2 <=…<= аi. Берется следующее число аi+1 и вставляется в последовательность так, чтобы новая последовательность была тоже возрастающей. Процесс производится до тех пор, пока все элементы от i+1 до n не будут перебраны.

Практическая работа №5 «Реорганизация массива»

Задание на «удовлетворительно»

Дана последовательность действительных чисел а1 <= а2 <=…<= аn. Вставить в нее действительное число b так, чтобы последовательность осталась неубывающей.

Задание на «хорошо»

Дан целочисленный массив с количеством элементов n. Сжать массив, выбросив из него каждый второй элемент.

Задание на «отлично»

Последовательность чисел а1, а2, …, аn состоит из нулей и единиц. Поставить в начало этой последовательности нули, а затем единицы.

Практическая работа №6 «Работа с несколькими массивами»

Задание на «удовлетворительно»

Даны две последовательности целых чисел а1, а2, …, аn  и  b1, b2, …, bn. Преобразовать последовательность b1, b2, …, bn. по следующему правилу: если ai <= 0, то bi увеличить в десять раз, в противном случае bi заменить нулем (i = 1, 2, …n).

Задание на «хорошо»

В области 10 районов. Заданы площади, засеваемые в каждом районе пшеницей, и урожай, собранный в каждом районе. Определить среднюю урожайность пшеницы по каждому району и по области в целом.

Задание на «отлично»

Известно количество посетителей технической выставки за неделю ее работы:

Определите:      - сколько посетителей принимала выставка ежедневно;

                            - сколько человек каждой возрастной группы посетило выставку;

                            - сколько всего было посетителей;

                            - в какой день было наименьшее число посетителей;

                            - посетители какой возрастной группы проявили к выставке наибольший интерес.