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], где (xi, yi ) — координаты 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. Функции без результатов.
Передача параметров по значению
