Типы задач при работе с массивами

1. Анализ всего или части массива, то есть найти какую–нибудь его характеристику: наименьшее, наибольшее значение, сумму или произведение всех элементов или элементов с некоторым условием, количество элементов с некоторым условием и т.п.

Пример 10. Найти количество положительных, отрицательных и нулевых чисел и вывести их разным цветом.

int main() { const n=10, c1=10, c2=11, с3=12; int k1=0, k2=0;

int a[n]={1, 0,-3,22, -33,-4,0,0, -22};

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

{ if (a[i]>0) { textcolor(c1); k1++; }

else if (a[i]<0) { textcolor(c2); k2++; }

else textcolor (с3);

cprintf("%d ", a[i]); }

textcolor(c1); cprintf ("\r\n Number of positive %d", k1);

textcolor(c2); cprintf ("\r\n Number of negative %d ", k2);

textcolor(с3); cprintf ("\r\n Number of 0 %d", n-k1-k2);

getch(); return 0; }

2. Поиск в массиве, т. е. определить, есть ли элемент с некоторым условием. Найти индекс и (или) значение первого (последнего) такого элемента, всех таких элементов.

Пример 11. Определить, есть ли в одномерном массиве отрицательные числа. Если есть, вывести “ Yes ” и номер последнего такого числа, в противном случае вывести “ No ”.

int main() { const n=10; int a[n]={1, 22, -3, 40, -55,-6, 0, -0, -99};

/* Второй тест: нет отрицательных

int a[n]={1, 22, 3, 40, 55, 6, 0, 0, 99};*/

int N0=-1; /* Пусть нет отрицательных.Для поиска последнего отрицательного числа просматриваем массив в обратном порядке .*/

for (int i=n-1; i>=0; i--) if (a[i] <0) { N0=i; break; }

/* Нашли первое с конца, или последнее в массиве отрицательное число, и дальше массив не просматриваем, вышли из цикла с помощью break; */

if (N0 == -1) cout<<”\nNo”;

/* В массиве нет отрицательного числа, вышли из цикла после того, когда просмотрели все элементы, то есть когда i>=0 стало ложным. */

else /* В массиве было отрицательное число и вышли из цикла с помощью break. */

cout<<"\n Yes, number of the last "<< N0+1;

getch(); return 0; }

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

int main() { const n=5; int a[n]; for(int i=0; i<n; i++) cin>>a[i];

int n2=-1, /* Номер первого нуля. */

s=0, i=0;

while (i<n) { if (a[i]==0) { n2=i+1; break; }

s+=a[i++]; }

if (n2 == -1) cout<<"No 0, sum = "<<s;

else { cout<<"Number of the first 0 " <<n2;

if (n2!=1) cout<<", sum before the first 0 = "<<s; }

getch(); return 0; }

3. Построение массива по некоторому правилу, используя при этом индексы, одно или несколько чисел и (или) один или несколько массивов.

Пример 13. Построить массив положительных и массив отрицательных чисел и вывести их.

int main()

{ const n = 10; int a[n], // Исходный массив

b[n], // Массив положительных чисел

d[n]; // Массив отрицательных чисел

cout<<"Array: "; randomize();

for (int i=0; i<n; i++) { a[i]=random(100)-50;

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

int nd=0, nb=0;

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

if (a[i]<0) d[nd++] = a[i];

else if (a[i]>0) b[nb++] = a[i];

cout<<"\nPositive array: "; for (int i=0; i<nb; i++)printf ("%5d",b[i]);

cout<<"\nNegative array: "; for (int i=0; i<nd; i++)printf ("%5d",d[i]);

getch(); return 0; }

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

Пример 14. Массив преобразовать следующим образом: все числа из отрезка [0,1] увеличить в 10 раз, отрицательные уменьшить в (–2) раза, остальные уменьшить в 10 раз. Преобразованный массив оставить на том же месте.

int main()

{ const n=5; float a[n]= { 0.12, -3.4,.5, 67, 8 };

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

if(a[i]>=0 && a[i]<=1) a[i] = a[i]*10;

else if (a[i]<0) a[i]=a[i] / (-2);

else a[i] = a[i]/10.;

for (int i=0; i<n; i++) printf ("%10.3f", a[i]);

getch(); return 0; }

5. Вывод массива в специальном виде (см. § 3).

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

Пример 15. Ввестимассив с экрана. Найти его наибольший и наименьший элементы и переставить их, т. е. на место каждого наибольшего поместить наименьший элемент, на место каждого наименьшего поместить наибольший элемент.

Поиск наибольшего и наименьшего элементов массива относятся к первому типу, а их перестановка — к четвёртому.

int main() { const n=5; int a[n], i;

for (i=0; i<n; i++) { cout<<"a["<<i<<"] "; cin>>a[i]; }

int min1=a[0], max1=a[0];

for (i=1; i<n; i++) if (min1>a[i]) min1=a[i];

else if (max1<a[i]) max1=a[i];

cout<<endl<<"Max "<<max1; cout<<" Min "<<min1;

for (i=0; i<n; i++) if (max1==a[i]) a[i]=min1;

else if (min1==a[i]) a[i]=max1;

cout<<"\n The new array\n";

for (i=0;i<n;i++) cout<<"a["<<i<<"]= "<<a[i]<<endl; getch(); return 0; }

Упражнения и тесты

1. Что будет выведено в каждом из четырех вариантов?

const n=10; int Sum, i;

int a[n]={11, 2, -3, -4, 5, 0, 7, -8, 9 };

/* Вариант 1 */ Sum=0;

for (i=0; i<n; i++) if (a[i]<0) Sum+=a[i]; cout<<Sum<<" ";

/*2*/ for (i=0, Sum=0; i<n;) { if (a[i]<0) Sum+=a[i++]; else i++;

cout<<Sum<<" "; }

/*3*/ for (Sum= i=0; i<n-1; Sum+=a[++i]); cout<<Sum;

/*4*/ for (Sum=0, i=-1; i<n-1;) { Sum+=a[++i]; cout<<" "<<Sum; }

2. Что будет выведено в каждом из вариантов, отличающихся наличием фигурных скобок и их расстановкой? Как и в предыдущем упражнении, объявлен и определен конкретный массив.

int K=0; cout<<endl;

/*Вариант 1*/ for (int I=0; I<n; I++) if (a[I]>0) K++; cout<<" "<<K;

/* 2 */ for (int I=0; I<n; I++) { if (a[I]>0) K++; } cout<<" "<<K;

/* 3 */ for (int I=0; I<n; I++) { if (a[I]>0) K++; cout<<" "<<K; }

/* 4 */ for (int I=0; I<n; I++) if (a[I]>0) { K++; cout<<" "<<K; }

/* 5 */ for (int I=0; I<n; I++) if (a[I]>0) K++; else cout<<" "<<K;

3. Если ошибок нет, записать, что будет выведено, или указать, где ошибка.

int i=9; const n=10;

int a[n]={1,2,-3,-4, -5, 6,7,8, 90, -100 }; //1

for (int S=0;;) //2

{ if (i<0) break; //3

if (a[i]>0) //4

{ S+=a[i]; //5

cout<< S<<" "; } //6

i--; } //7

4. Что будет выведено?

int s=0, k=0; const n=10; int a[n]={1, 2, -3, -4, -5, 6, 7, 8 };

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

{ if (a[i]>0) continue; s+=a[i];

cout<<endl<< s<<" "<<(++k);

}

Задачи

Уровень А

1. В массиве получить разность между наибольшим и наименьшим элементами.

2. В числовом массиве найти среднеарифметическое значение среди положительных чисел.

3. Преобразовать целочисленный массив следующим образом: числа, кратные 5, но не кратные 10, уменьшить в 5 раз; числа, кратные 10, уменьшить в 10 раз; остальные увеличить в 10 раз. Дополнительный массив не формировать.

4. Из массива оценок получить 5, если студент (школьник) отличник, и 0 в противном случае.

5. Из масива оценок получить 2, если студент (школьник) двоечник, и 0 в противном случае.

В задачах 7 — 9 даны n точек плоскости своими координатами в виде двух массивов x [ n ] и y [ n ], где (x_i, y_i) — координаты i -й точки.

6. Найти количество точек в каждой из четвертей.

7. Сколько точек находится внутри кольца, ограниченного окружностями, радиус которых r и R (r < R)? Если r>R, вывести соответствующее сообщение и повторить ввод радиусов.

8. Найти одну, любую точку, расстояние от которой до заданной точки наименьшее.

 

Уровень В

1. Из масива оценок получить средний балл, если нет 1, 2 или 3.

2. Из массива оценок получить 5, 4, 3 или 2 в зависимости от того, является ли студент (школьник) отличником, хорошистом, троечником или двоечником.

3. В числовом массиве найти отрицательное наибольшее число, его номер, положительное наименьшее число и его номер. Определить все номера, если таких чисел несколько. Предусмотреть случай, когда положительных (или отрицательных) чисел нет.

4. В целочисленном массиве найти первое и второе наименьшие числа и количество их повторений. Например, в массиве {11, 2, 99, –10, 10, –5, –5, 6, –10, –5} первое наименьшее –10 повторяется два раза, второе наименьшее –5 повторяется три раза. Предусмотреть случай, когда все числа одинаковы и второго наименьшего числа нет.

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

6. Известно, что в массиве есть только числа 0, 1, 2 в любом количестве и порядке следования. Преобразовать массив следующим образом: в начало поместить единицы, затем двойки и, наконец, нули. Например, для массива {2, 1, 1, 2, 0, 2, 0, 1, 2, 2} получим {1, 1, 1, 2, 2, 2, 2, 2, 0, 0}. Дополнительный массив не формировать.

7. Все элементы массива, не равные нулю, переписать в начало массива, сохраняя их порядок, а нулевые элементы — в конец массива. Можно формировать новый массив (см также уровень С).

8. Рассортировать одномерный целочисленный массив по возрастанию последней цифры числа. Использовать обменную сортировку.

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

10. Среди точек плоскости, заданных своими координатами в виде двух массивов, найти все точки, расстояние от которых до заданной точки наименьшее.

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

 

Уровень С

1. Все отрицательные элементы массива, не равные нулю, переписать в начало этого же массива, положительные — в его конец. Исходный порядок элементов массива должен сохраниться. Новый массив не формировать.

2. В целочисленном массиве найти длину самой длинной последовательности одинаковых, подряд идущих чисел и это повторяющееся число. Например, в массиве {5, 2, 5, 5, 5, 2, 2, 2, 7, 7, 7, 7, 2, 0, 5, 7, 8} самая длинная последовательность состоит из четырех семерок.

3. Даны два упорядоченных числовых массива размерности n и m. Получить из них новый упорядоченный массив размерности n + m, не используя алгоритма сортировки.

4. Рассортировать одномерный целочисленный массив по возрастанию первой цифры числа. Для сортировки использовать алгоритм выбора наименьшего элемента.

5. Точки плоскости, заданные в виде двух одномерных массивов, рассортировать по возрастанию расстояния от начала координат. Использовать сортировку вставками.

 

 

Г л а в а 4
МОДУЛЬНОЕ ПРОГРАММИРОВАНИЕ. ФУНКЦИИ

Одновременно с возникновением языков высокого уровня (Aлгол, Basic, Фортран, PL/1, Pascal, C и др.) широкое распространение получил метод модульного программирования. Согласно ему, проект (задача, программа) разбивается на логически завершённые части, которые оформляются по определённым правилам. В некоторых других системах их называли подпрограммами. Во многих языках использовались и остались два их вида, например, процедуры и функции на языке Pascal, которые отличаются правилами их оформления и вызова.

С точки зрения использования рассматриваемой здесь технологии можно выделить следующие уровни программирования:

1) без использования подпрограмм, кроме, быть может, встроенных (стандартных), как было показано в первых трех главах;

2) с подпрограммами; Это будет рассмотрено в этой главе;

3) подпрограммы можно объединять в библиотеки (язык Фортран), модули (Pascal) и т. п.;

4) с возникновением объектно-ориентированного программирования подпрограммы включаются в классы и называются их методами.

С одной стороны, на языке С++ формально нет деления подпрограмм на два вида, как это сделано, например, в Pascal. Здесь можно составлять и использовать только функции, которые могут быть как самостоятельными, не включёнными в класс, так и его методами. Но по аналогии с другими языками для эффективного их изучения функции можно также разделить на два вида. Функция типа void аналогична процедуре Pascal (procedure), а функция с возвращаемым с помощью return единственным значением частично похожа на function языка Pascal, но проще.

 

§1. Функции без результатов.
Параметры-значения

1.1. Примеры. Правила оформления и вызова функций

Пример 1. Пусть необходимо дважды вывести горизонтальную линию, состоящую из 40 символов псевдографики “-” с кодом 196.

// 1-й вариант (без функции)

int main()

{ cout<<"Testing of function: \n the first line ";

cout<<endl; for (int i=1; i<=40; i++) cout<<'-'; cout<<endl;

cout<<" The second line";

cout<<endl; for (int i=1; i<=40; i++) cout<<'-'; cout<<endl;

getch(); return 0; }

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

// 2-й вариант (с функцией)

#include <iostream.h>

#include <conio.h>

// Прототип (объявление) функции.

void LINE1();

int main()

{ // Начало функции main()

cout<<"Testing of function: \n the first line ";

LINE1(); // Вызов функции.

cout<<" The second line";

LINE1(); // Вызов функции.

getch(); return 0;} // Конец функции main()

/* Повторяем заголовок функции без символа “;” в конце */

void LINE1()

/* Описание (определение) функции, т. е. её текст */

{ int i; cout<<endl;

for (i=1; i<=40; i++) cout<<'-';

cout<<endl; }

Перед функцией main() записываем прототип (объявление, заголовок) функции. Ключевое слово void в данном примере означает, что функция не возвращает результаты. В следующем параграфе будет показано, что функцию типа void можно использовать и для других целей. Далее следует имя функции по обычным правилам записи идентификаторов. Пустые круглые скобки означают, что функция не имеет никаких параметров, ни входных, ни выходных (результатов). Слово void при этом в круглых скобках (но не в начале!) можно не писать, как это было в “старом” языке С. Заметим, что после прототипа обязательно записывается символ “;” (точка с запятой), а при описании функции после main этот символ не пишем.

Описание функции размещаем после текста функции main(). Повторяем заголовок, но без “;” в конце, и затем в фигурных скобках записываем её текст. При необходимости внутри функции объявляются так называемые локальные переменные (переменная i для счётчика в нашем примере). Они не являются ни входными, ни выходными переменными для функции, а предназначены для хранения промежуточных величин. Такие переменные можно использовать только внутри данной функции. Здесь, как и раньше, переменную i можно было объявить в заголовке оператора for.

Пример 2. Усложним задачу. Пусть надо первый раз вывести, например, 20 символов “*” в пятой, а не в текущей строке, а второй — линию из 40 символов псевдографики “–” в десятой строке. Поэтому функция будет иметь три входных параметра: Len для длины линии, y для номера строки экрана, в которой будем выводить линию, и ch для выводимого символа.

void LINE2(int Len, int y, char ch);

int main()

{ cout<<" \n The first call of function";

LINE2 (20, 5, '*');

int LEN, Y, C=196; cout<<" \n The second call of function";

cin>>LEN>>Y; LINE2(LEN, Y, C);

getch(); return 0;}

void LINE2(int Len, int y, char ch)

{ gotoxy(1,y); for (int i=1; i<=Len; i++) cout<<ch;

cout<<endl; }

В прототипе функции и при её описании в заголовке обязательно надо записывать типы параметров, даже если они повторяются. Поэтому следующая запись void LINE2(int Len, y, char ch) неправильна!

Имена параметров обязательны только в заголовке описания, а в прототипе можно указать только их типы: void LINE2(int, int, char).

Вызов функции типа void выполняется так, как вызов процедуры (Procedure) на языке Pascal, без использования дополнительного оператора, как это имеет место в некоторых других системах. Достаточно записать имя функции и в скобках, если есть, входные и выходные (в нашем примере их нет) фактические параметры. Если параметры отсутствуют, то и в прототипе, и в описании, и при вызове функции необходимо обязательно записать пустые круглые скобки.

Выполнение программы с функцией всегда начинается с main. Когда встретится вызов функции (а не её описание), выполняется следующая последовательность действий:

1) запоминается точка возврата, то есть адрес следующей команды;

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

3) управление передаётся на первый выполняемый оператор функции;

4) выполняется функция;

5) если выполнился последний оператор функции или встретился return, управление передаётся в ту точку, откуда функция была вызвана. Заметим, что передача управления из точки вызова функции и обратно выполняется автоматически, без дополнительных операторов.

Если встретился повторный вызов этой же функции, описанные выше действия повторяются.