Программирование алгоритмов с использованием массивов

Массив — это группа последовательно расположенных в памяти элементов одинакового типа (double, float, int и т.д.), имеющих одно общее имя. Из описания массива компилятор должен получить информацию о типе элементов массива и их количестве. Поэтому описание массива отличается от описания простой переменной наличием после имени массива квадратных скобок, в которых указывается количество элементов массива.

Синтаксис:

тип имя_массива [константное_выражение]…;

или

тип имя массива [ ];

 

Квадратные скобки, следующие за именем_массива, являются атрибутом синтаксиса, а не признаком необязательности конструкции.

При описании массива могут использоваться те же модификаторы (класс памяти, const и инициализатор), что и для простых переменных (см. раздел 2. Базовые средства языка С/С++).

Описатель тип определяет тип элементов объявляемого массива (это может быть любой тип, кроме типов void и функция), а константное_выражение – размер массива (количество элементов в массиве). Компилятор отводит под массив память размером (sizeof (тип) * размер массива) байтов.

Во второй синтаксической форме (см. выше) константное_выражение в квадратных скобках опущено. Эта форма используется в следующих случаях:

– при объявлении массив инициализируется (см. далее);

– массив объявлен как формальный параметр функции;

– массив объявлен как ссылка на массив, явно определенный в другом файле.

 

Допускается использование многомерных массивов. Многомерный массив, или массив массивов, объявляется путём задания последовательности константных выражений в квадратных скобках, следующей за именем массива:

 

тип имя_массива [константное_выражение][константное_выражение]...;

 

Количество пар скобок определяет размерность массива, а константное_выражение – размер массива по данному измерению. Различают одномерные (линейные) массивы, двумерные массивы (матрицы) и т.д., так что объявление двумерного массива содержит два константных_выражения, трехмерного — три и т.д.

 

Примеры:

double vector [10];

unsigned int matrix [3][5];

 

В первом примере определён линейный массив vector из 10 элементов типа double. Во втором примере объявляется двумерный массив с именем matrix (строго говоря, matrix представляет собой массив из 3 элементов, каждый из которых является массивом из 5 элементов типа unsigned int).

Нумерация элементов в массиве начинается с нуля по любому измерению. Элементы многомерного массива хранятся в памяти построчно. Например, двумерный массив, объявленный как

int a[3][4]; программист представляет в виде матрицы a[0][0] a[0][1] a[0][2] a[0][3] a[1][0] a[1][1] a[1][2] a[1][3] a[2][0] a[2][1] a[2][2] a[2][3]

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

 

Примеры: vector[3], matrix[2][k+1], vector[2*i+3];

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

={<список инициализаторов>}

Список инициализаторов заключается в фигурные скобки. Каждый инициализатор в списке – это либо константное выражение, либо новый список инициализаторов, разделяемых запятыми. Таким образом, заключенный в фигурные скобки список может появиться внутри другого списка инициализаторов. Значения константных выражений из каждого списка инициализаторов последовательно присваиваются элементам массива в порядке их следования.

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

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

Примеры:

int b[5]= {1,2,3,4,5}; //инициализируется вектор из 5 элементов, имеющих тип int int w[3][4] = { { 1, 1, 1, 1 }, { 2, 2, 2, 2 }, { 3, 3, 3, 3 } };

В последнем примере объявлен и инициализирован двумерный массив w размером 3 строки и 4 столбца. Списки, выделенные в фигурные скобки, соответствуют строкам массива. Если список инициализаторов не имеет вложенной структуры, аналогичной структуре двумерного массива, то элементы списка присваиваются построчно элементам массива в порядке их следования. Поэтому вышеприведенная инициализация эквивалентна следующей:

int w[3][4] = { 1,1,1,1, 2,2,2,2, 3, 3, 3, 3 };

Если же объявлен массив

int w[3][4] = { { 1, 1, 1}, { 2, 2, 2 }, { 3 } };

то это равносильно такой инициализации:

int w[3][4] = { 1,1,1,0, 2,2,2,0, 3, 0, 0, 0 };

Возможно, что в случае отсутствия внутренних скобок инициализация будет выполнена не в полном соответствии с вашим замыслом.

В языке С/С++ можно использовать сечения массива, однако на использование сечений накладывается ряд ограничений. Сечения формируются вследствие опускания одной или не­сколь­ких пар квадратных скобок. Пары квадратных скобок можно отбрасы­вать только справа налево и строго последовательно. Сечения массивов нередко используются при передаче в функцю параметров–массивов.

Примеры:

int s[2][3];

Если при обращении к некоторой функции использовать параметр s[1], то будет передаваться первая строка массива s.

int b[2][3][4];

При обращении к массиву b можно написать, например, b[1][2] и будет передаваться вектор из четырех элементов, а обращение b[1] даст двумерный массив размером 3 на 4.

Пример объявления символьного массива.

char str[] = "объявление символьного массива";

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

 

 

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

#include <iostream.h>

#include <conio.h>

int main()

{

const int n=100;

float z[n], s, maxz, nalog[n];

int i, m;

cout<<"Количество служащих ";

cin>>m;

cout<<"Введи зарплату каждого работника "<<"\n";

cout<<"\n\n";

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

{

cout<<"z["<<i+1<<"]= ";

cin>>z[i];

}

s=0; maxz=z[0];

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

{

s+=z[i];

if (z[i]>maxz)

maxz=z[i];

nalog[i]=0.17*z[i];

}

cout<<"Максимальная зарплата = "<<maxz<<"\n";

s/=m;

cout<<"Средняя зарплата = "<<s<<"\n";

cout<<"Зарплата выше средней: ";

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

if (z[i]>=s)

cout<<i+1<<". "<<z[i]<<"\n";

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

cout<<"Выдать "<<i+1<<"-му работнику сумму "<<z[i]-nalog[i]<<"\n";

getch();

return 0;

}

 

 

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

#include <iostream.h>

#include <conio.h>

int main()

{

const int m=5;

 

int a[]={1, 2, 3, 4, 6}, b[m], i, k=m;

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

{

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

cout<<b[i]<<"\n";

}

getch();

return 0;

}

 

 

Задача 78. Изменить порядок следования элементов заданного массива на обратный (вспомогательный массив не использовать).

#include <iostream.h>

#include <conio.h>

int main()

{

const int m=5;

 

int a[]={1, 2, 3, 4, 6}, p, k=m, i;

for (i=0; i<m/2; i++)

{

p=a[--k];

a[k]=a[i];

a[i]=p;

}

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

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

getch(); return 0;

}

 

 

Задача 79. Сгенерировать массив из n случайных чисел, равномерно распределенных в заданном интервале от A до B и вывести его в виде таблицы по 10 элементов в строке.

 

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

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

функция rand() непосредственно генерирует очередное псевдослучайное целое число из диапазона от 0 до RAND_MAX (обычно RAND_MAX = 32767); например, оператор

int x = rand() % (B-A+1) + A;

генерирует случайное число x из интервала от А до В.

 

Вот примеры использования этих функций.

 

 

#include <time.h>

#include <stdlib.h>

…

srand((unsigned)time(NULL)); // базовое число

int x = rand()%9+1; // случайное число от 1 до 9

 

 

Более изощренный способ: если А, В – границы диапазона равномерно распределенных случайных чисел, то строка

 

int x = A+(int)((B-A+1)*rand()/(RAND_MAX+1.0));

 

генерирует требуемое случайное число x. В частности, конструкция

 

int x = 1+(int)((9.0)*rand()/(RAND_MAX+1.0));

 

возвращает случайное число x от 1 до 9.

 

 

// программа отлажена в Visual Studio 2008

#include "stdafx.h"

#include <iostream>

#include <time.h>

#include <conio.h>

#include <stdlib.h>

using namespace std;

 

int main()

{

const int m=200, A=1, B=m;

int a[m], n, i;

srand((unsigned)time(NULL)); // базовое число

 

cout<<"Введите размер массива <= "<<n<<" ";

cin>>n;

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

a[i]= A+(int)((B-A+1)*rand()/(RAND_MAX+1.0));

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

printf("%6d%c", a[i], (i%10)?' ':'\n');

getch(); return 0;

}

 

Задача 80. Сформировать и вывести на экран единичную матрицу размером 5х5.

 

//Первый вариант

#include<iostream>

#include<conio.h>

using namespace std;

const int M=5;

int main()

{

int em[M][M], k, i;

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

{

for(k=0; k<M; k++)

{ if(i==k)

em[i][k]=1;

else

em[i][k]=0;

cout<<em[i][k]<<' ';

}

cout<<"\n";

}

getch(); return 0;

}

 

 

//Второй вариант

#define M 5

#include<iostream>

#include<conio.h>

using namespace std;

int main()

{

 

int em [M][M]={0},i,k;

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

em[i][i]=1;

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

{ cout<<"\n";

for (k=0; k<M; k++)

cout<<"\t"<<em[i][k];

}

getch(); return 0;

}

 

 

//Третий вариант.

#include<iostream>

#include<conio.h>

using namespace std;

const int M=6;

 

int main()

{

int em[M][M],i,k;

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

for (k=1; k<M; k++)

em[i][k]=(k/i)*(i/k); // хитрый прием

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

{ cout<<"\n";

for (k=1; k<M; k++)

cout<<"\t "<<em[i][k];

}

getch();return 0;

}

 

Задача 81. Определить одномерный массив А из m вещественных чисел. Вычислить сумму элементов массива, расположенных за последним отрицательным элементом. По заданному массиву А построить новый массив В, содержащий вначале все положительные элементы исходного массива, затем – отрицательные и нулевые элементы массива А.

 

// Программа отлажена в Visual Studio 2008 (13.03.2010г)

#include<conio.h>

#include<stdio.h>

#include <iostream>

using namespace std;

 

const int n= 10;

 

float sum(float a[],float b[],int n);

 

int main()

{

//float a[n]={8,3,-2,6,0,-5,0,-8,9,1};

float a[n]={8,3,2,6,0,5,0,8,9,1};

float s, b[n]={0}; int i;

//*************************

s=sum(a,b,n);

//*************************

setlocale(NULL, ".1251");

if(s!= -1)

{

cout<<"\nСумма крайних положительных="<<s<<endl;

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

cout<<b[i]<<endl;

}

else

cout << "\nНет отрицательных элементов ";

getch();return 0;

}

 

//сумма элементов, стоящих за последним отрицательным

float sum(float a[],float b[],int n)

{ int i,k; float s;

s=0; k=-1;

//поиск последнего отрицательного числа в массиве

//a)

/* for(i=n-1; i>=0; i--)

if (a[i]<0) {k=i; break;}

*/

//б)

 

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

if(a[i]<0) k=i;

 

if(k == -1)

{ //cout << "\nНет отрицательных элементов ";

return k;

}

//вычисление суммы

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

s=s+a[i];

//пересылка положительных элементов к началу массива

k=0;

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

if(a[i]>0)

{ b[k]=a[i];

k++;

}

//пересылка отрицательных элементов массива

 

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

if(a[i]<0)

{ b[k]=a[i];

k++;

}

return s;

}

 

 

Задача 82. Сформировать и напечатать таблицу Пифагора

#define M 10

#include <conio.h>

#include <stdio.h>

#include <iostream.h>

int main()

{

int em[M][M],i,k;

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

for (k=1;k<M;k++)

em[i][k] = i*k;

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

{ cout<<"\n\n";

for (k=1;k<M;k++)

cout<<"\t "<<em[i][k];

}

getch();return 0;

}

 

 

Задача 83. Вывести матрицу размером 9х9 следующего вида: наддиагональный треугольник — нули, диагональ — девятки, под ними — восьмёрки, затем — семёрки и т. д.

//Программа отлажена в Visual Studio 2008

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

int main()

{

const int m=9;

int a[m][m], k, i;

 

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

{

for(k=0; k<m; k++)

{ if(k<=i)

a[i][k]=m-i+k;

else

a[i][k]=0;

cout<<a[i][k]<<' ';

}

cout<<"\n";

}

getch(); return 0;

}

 

 

Задача 84. Программа с помощью функции nozero() пересылает элементы массива a[m]= {8, 0, 3, 0, -5, 0, 0, 9 } в массив b[m] следующим образом: сначала с сохранением порядка записываются ненулевые элементы, а все нулевые — записываются в конец массива b[m].

 

//Программа отлажена в Visual Studio 2008

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

// Функция пересылки:

void nozero(const int x[], int y[], int n)

{

int i, k=0;

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

if(x[i]!=0)

y[k++]=x[i];

while(k<n)

y[k++]=0;

}

// Основная:

const int m=8;

int main()

{

int i, k, a[m]={8, 0, 3, 0, -5, 0, 0, 9}, b[m];

cout<<"Массив до обработки:\n";

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

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

cout<<"\n";

//****************

nozero(a, b, m);

//****************

cout<<"Массив после обработки:\n";

for(k=0; k<m; k++)

cout<<b[k]<<" ";

cout<<"\n";

getch();return 0;

}

 

Задача 85. Программа с помощью функции nozero() преобразуетет заданный массив a[m]= {8, 0, 3, 0, -5, 0, 0, 9 } следующим образом: в начало массива с сохранением порядка записываются ненулевые элементы, а все нулевые — записываются в конец массива. Вспомогательный массив не используется.

 

 

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

 

В предыдущей программе первый формальный параметр функции nozero() имеет описатель const, что делает невозможным его изменение в теле функции. В следующей программе элементы массива x[], подвергаясь изменениям в теле функции nozero(), обеспечивают требуемое преобразование фактического параметра – массива a[].

 

//Программа отлажена в Visual Studio 2008

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

// Функция пересылки

void nozero(int x[], int n)

{

int i, k=0;

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

if(x[i]!=0)

x[k++]=x[i];

while(k<n)

x[k++]=0;

}

// Основная:

const int m=8;

int main()

{

int i, k, a[m]={8, 0, 3, 0, -5, 0, 0, 9};

cout<<"Массив до обработки:\n";

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

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

cout<<"\n";

//****************

nozero(a, m);

//****************

cout<<"Массив после обработки:\n";

for(k=0; k<m; k++)

cout<<a[k]<<" ";

cout<<"\n";

getch();return 0;

}

 

 

Задача 86. Программа пересылает нечетные элементы заданного целочисленного массива x[ ] в массив y[ ], а четные — в массив z[ ]. Результаты выдаются на экран. Функция mas3() использует глобальные переменные r и l для подсчета количества тех и других.

#include<iostream.h>

#include<conio.h>

int k=0,l=0; //глобальные переменные

void mas3(int x[], int n, int z[], int y[])

{

int i;

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

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

z[k++]=x[i];

Else

y[l++]=x[i];

}

void main()

{

const int n=10; int i;

int x[n]={8,3,4,8,4,5,3,6,7,1};

int z[n]={0}; int y[n]={0};

 

mas3(x,n,z,y);

 

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

cout<<z[i]<<endl;

 

cout<<endl;

 

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

cout<<y[i]<<" ";

getch();

}

 

 

Задача 87. Программа осуществляет линейный поиск заданного целого числа в массиве целых чисел. Резуль­тат поиска выводится, например, так: «2 на 7-ом месте», либо «2 не найден».

#include <iostream.h>

#include <conio.h>

// Функция поиска:

int lpoisk(int x[], int n, int Q)

{

int i, k;

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

if (x[i]==Q)

{

k=i;

break;

}

if (i<n)

return k;

Else

return -1;

}

// Основная:

const int m=8;

void main()

{

int Q, t;

int a[m]={8, 3, 97, 5, -9, 13, 0, 1};

cout<<"Введи ключ поиска: ";

cin>>Q;

t=lpoisk(a, m, Q);

if (t>=0)

cout<<Q<<" на "<<t+1<<"-м месте.";

Else

cout<<Q<<" не найден.";

getch();

}

 

 

Задача 88. Вариант предыдущей программы. Слегка изменена функция lpoisk.

#include<conio.h>

#include <iostream>

using namespace std;

 

// Функция поиска:

int lpoisk(int x[], int n, int Q)

{

int i=0;

while(x[i]!=Q && i<n)

i++;

if(i<n)

return i;

else

return -1;

}

 

// Основная:

const int m=8;

void main()

{

int Q, t;

int a[m]={8, 3, 97, 5, -9, 13, 0, 1};

setlocale (NULL, ".1251");

cout<<"Введи ключ поиска: ";

cin>>Q;

t=lpoisk(a, m, Q);

if(t>=0)

cout<<Q<<" на "<<t+1<<"-м месте.";

else

cout<<Q<<" не найден.";

getch();

}

 

 

Задача 89. Программа выполняет сортировку массива методом выбора. За один проход внешнего цикла (индекс i) во внутреннем цикле (индекс j) определяется наибольший элемент рассматриваемого массива и он меняется местами с последним элементом массива. В дальнейших операциях этот элемент не участвует. При каждом обороте внешнего цикла количество обрабатываемых во внутреннем цикле элементов уменьшается на единицу. Для оставшейся части массива снова применяется только что описанная процедура. Так продолжается вплоть до предпоследнего элемента массива, пока весь массив не станет упорядоченным.

 

// Программа отлажена в Visual Studio 2008

// Сортировка выбором

#include "stdafx.h"

#include <stdio.h>

#include <conio.h>

#include <time.h>

#include <stdlib.h>

 

int main()

{ const int M=20;

srand((unsigned)time(NULL)); //базовое число

int i, j, max, nmax, a[M];

// А, В -границы диапазона случайных чисел

int A=1, B=100;

 

// генерация случайных чисел

//rand() = случайное число от 0 до RAND_MAX(32767)

printf("До сортировки:\n");

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

{

a[i]=A+(int)((B-A+1)*rand()/(RAND_MAX+1.0));

printf("%3d ",a[i]);

}

printf("\n");

 

for (i=0; i<M-1; i++)

{ // поиск максимального элемента

max=a[0]; nmax=0;

for (j=1; j < M-i; j++)

if (a[j] > max)

{

max=a[j]; //максимальный

nmax=j; //его номер

}

// обмен максимального с последним

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

a[M -i -1] = max;

}

printf("После сортировки:\n");

 

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

printf("%3d ",a[i]);

getch(); return 0;

}