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

1. Анализ всего или части массива, то есть найти какую–нибудь его характеристику (см. задачи 2, 4, 7 — 11, 14, 15, 17, 20).

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

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

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

5. Сортировка по одному или нескольким критериям. При этом в качестве критерия используются либо значения элементов, либо их характеристики, например, сортировка по последней (первой) цифре целого числа, по количеству единиц в двоичном представлении и т. п. (см. 19, 20е).

6. Вывод массива в специальном виде (см. 6.3).

Одна и та же задача может состоять из нескольких частей, каждая из которых относится к разным типам. Например, в задаче 1 поиск наибольшего и наименьшего элементов массива относятся к первому типу, а их перестановка — к четвёртому.

При этом возможна обработка одного или одновременно нескольких массивов, например, как это имеет место при работе с массивом точек на плоскости (см. задачу 20).

Задачи и упражнения

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

int main()

{ clrscr(); const n=5; int a[10], i, max1, min1, Nmin, Nmax;

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

{ cout<<"a["<<i<<"] "; cin>>a[i];

}

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

Nmin=0; Nmax=0;

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

if (min1>a[i])

{ min1=a[i]; Nmin=i;

}

else if (max1<a[i])

{ max1=a[i]; Nmax=i;

}

cout<<"Max "<<max1<<" number "<<Nmax<<endl;

cout<<"Min "<<min1<<" number "<<Nmin<<endl;

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

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

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

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

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

getch(); return 0;

}

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

int main()

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

for(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 of all elements = "<<s;

else { cout<<"Yes, "<< "number of the first 0 = "<<n2;

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

}

cout<<endl;

getch(); return 0;

}

3. Сформировать целочисленный массив с помощью датчика случайных чисел. Построить массив положительных и массив отрицательных чисел и вывести их.

int main()

{ const int n = 10; int a[n], b[n], d[n];

clrscr(); 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. Определить целочисленный массив при объявлении. Найти количество положительных, отрицательных и нулевых чисел и вывести их разным цветом.

int main()

{ const int n=10, c1=2, c2=WHITE;

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

int i; clrscr(); int k=0, k2=0;

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

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

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

else textcolor (3);

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

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

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

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

getch(); return 0; }

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

for (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; }

6. Определить, есть ли нуль в массиве. Если есть, получить индекс первого нуля. В противном случае вывести “нет нулей”. Привести несколько вариантов алгоритма, отличных от задачи 2.

7. Пусть const n=10; int a[n], k=0;. Проанализировать и сравнить приведенные ниже варианты, отличающиеся наличием и расстановкой фигурных скобок:

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

if (a[i]>0) k++;

cout<<k<<” “;

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

{ if (a[i]>0) k++;

cout<<k<<” “;

}

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

if (a[i]>0)

{ k++;

cout<<k<<” “;

}

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

if (a[i]>0) k++;

else cout<<k<<” “;

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

9. В числовом массиве найти отрицательное наибольшее число, его номер положительное наименьшее число и его номер. Определить все номера, если таких чисел несколько.

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

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

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

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

14. Задан массив оценок по новой 10-балльной системе, например, оценки одного студента, полученные на восьми экзаменах:

а) получить 5, если студент отличник, и 0 в противном случае;

б) получить 2, если студент двоечник, и 0 в противном случае;

в) если нет 1, 2 или 3, найти средний балл;

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

д) преобразовать оценки из 10-балльной системы в 5-балльную.

15. Решить аналогичные задачи (см. 14a — 14д), если задан массив оценок по 5-балльной системе.

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

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

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

19. Рассортировать одномерный целочисленный массив по возрастанию последней цифры числа.

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

а) найти количество точек в каждой из четвертей;

б) сколько точек находится внутри кольца, ограниченного окружностями, радиус которых r и R (r < R);

в) найти точку (одну, любую), расстояние от которой до заданной точки наименьшее;

г) найти все точки, расстояние от которых до заданной точки наименьшее;

д) найти две любые точки с наименьшим расстоянием между ними;

е) точки плоскости рассортировать по возрастанию расстояния от начала координат.

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

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

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

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

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

2) с подпрограммами;

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

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

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

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

§ 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 в данном случае означает, что функция не возвращает результаты. Далее следует имя функции по обычным правилам записи идентификаторов (см. 1.5). Пустые круглые скобки означают, что функция не имеет никаких параметров, ни входных, ни выходных (результатов). Слово void при этом в круглых скобках (но не в начале!) можно не писать, как это было в “старом” языке С. Заметим, что после прототипа обязательно записывается символ “;” (точка с запятой), а при описании функции этот символ не пишем.

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

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

 

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

int main()

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

LINE2 (20, 5, '*');

int LEN, Y, C=196;

cout<<" 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 выполняется, как и на Pascal, без использования дополнительного оператора, как это имеет место в некоторых других языках. Достаточно записать имя функции и в скобках, если есть, параметры. Если параметры отсутствуют, то и в прототипе, и в описании, и при вызове функции необходимо обязательно записать пустые круглые скобки.