Массивы - 2

Передача массива в качестве параметра

Массивы можно передавать функции в качестве параметра. Но при этом размер создаваемого массива может быть неопределен на момент компиляции программы, поэтому функция не может знать размер полученного массива. Поэтому в функции нужно передавать два параметра - указатель на начала массива (например, для массива целых чисел это int *, и количество элементов в массиве.

Например, функция поиска наименьшего значения в массиве int A[n] может быть объявлена так: 

int Min (int * A, int n)
{
    int result;
    // Вычисляем ответ
    return result;
}

Соответственно, внутри функции main мы объявляем массив int A[n] и вызываем функцию Min, передав в качестве параметров массив A и его размер n: 

int main()
{
    int n, i;
    cin >> n;
    int A[n];
    for (i = 0; i < n; ++i)
    {
        cin >> A[i];
    }
    cout << Min(A, n) << endl;
    return 0;
}

Упражнения

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

Во всех задачках этого листка, кроме I, J, O нельзя использовать вспомогательные массивы. В задачах Q, R, S - три массива, два со входными данными и один для записи результата. В задаче Y - три массива со входными данными.

A: Линейный поиск

Напишите функцию int Search (int * A, int n, int val), которая находит в массиве int A[n] элемент, значение которого равно val. Функция возвращает индекс найденного элемента или -1, если такого элемента в массиве нет.

Программа получает на вход количество элементов в массиве n, затем n целых чисел — элементы массива, затем число val и должна вывести индекс найденного элемента или число -1, если данный элемент в массиве отсутствует.

Попропуйте реализовать данный алгоритм без условия if внутри цикла.

Ввод Вывод 
3
1 7 9
9
 
2
 
3
1 7 9
8
 
-1

B: Монотонный ли массив?

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

Решение оформите в виде функции bool IsAscending (int * A, int n). Постарайтесь не использовать условие if внутри цикла.

Выведите YES, если массив монотонно возрастает и NO в противном случае.

Ввод Вывод 
3
1 7 9
 
YES

C: Последнее появление максимума

Найдите наибольшее значение в массиве и индекс последнего элемента, который имеет данное значение за один проход по массиву. Решение оформите в виде функции void Max (int * A, int n, int & max, int & max_idx), где max  передаваемая по ссылке переменная для записи в нее наибольшего значения в массиве, max_idx  передаваемая по ссылке переменная для записи в нее индекса последнего элемента, равного наибольшему.

Программа считывает массив и выводит два числа: наибольшее значение в массиве и индекс последнего элемента с таким значением.

Ввод Вывод 
5
1 2 1 2 1
 
2 3

D: Количество максимумов

Найдите наибольшее значение в массиве и количество элементов, имеющих такое значение за один проход по массиву. Решение оформите в виде функции void Max (int * A, int n, int & max, int & max_count).

Программа считывает массив и выводит два числа: наибольшее значение в массиве и количество таких элементов в массиве.

Ввод Вывод 
5
2 1 2 1 2
 
2 3

E: Максимум суммы соседних

Дан массив. Найдите наибольшее значение суммы двух соседних элементов в нем.

Решение оформите в виде функции int MaxNeighborsSum (int * A, int n).

Выведите значение этой суммы.

Ввод Вывод 
5
1 2 3 4 5
 
9

F: Второй максимум

Дан массив, состоящий из попарно различных целых чисел. Определите второй по величине элемент этого массива. Решение оформите в виде функции int SecondMax (int * A, int n). Функция должна выполнять однократный просмотр массива.

Выведите значение этого элемента.

Ввод Вывод 
5
4 3 2 5 1
 
4

G: Снова второй максимум

Найдите второй максимум в массиве — элемент, который будет максимальным, если из массива удалить максимальный элемент. Решение оформите в виде функции int SecondMax (int * A, int n). Функция должна выполнять однократный просмотр массива.

Выведите значение этого элемента.

Ввод Вывод 
5
4 3 2 5 1
 
4
 
5
1 2 1 2 1
 
2

H: Второе по величине значение

Определите второе по величине значение в массиве — второй максимум в множестве чисел, которые встречаются в массиве. Решение оформите в виде функции int SecondMaxValue (int * A, int n). Функция должна выполнять однократный просмотр массива.

Выведите найденное значение. Гарантируется, что в исходном массиве есть два различных элемента.

Ввод Вывод 
5
1 2 1 2 1
 
1

I: Количества цифр

Дан массив, заполненный цифрами (то есть числами от 1 до 9). Определите, сколько раз встречаются в нем значения 1, 2, ..., 9.

Программа должна вывести ровно 9 чисел: количество единиц, двоек, ..., девяток в данном массиве.

Ввод Вывод 
10
1 2 3 4 5 1 1 1 2 2
 
4 3 1 1 1 0 0 0 0

J: Еще раз количество цифр

Дана последовательность чисел, состоящая только из чисел 1, ..., 9. Последовательность завершается числом 0. Подсчитайте, сколько раз в этой последовательности встречаются значения 1, 2, ..., 9. Программа должна вывести ровно 9 чисел: количество единиц, двоек, ..., девяток в данной последовательности. Последовательность может быть настолько большой, что сохранить ее всю в массиве невозможно.

Ввод Вывод 
1 2 3 4 5 1 1 1 2 2 0
 
4 3 1 1 1 0 0 0 0

K: Противоположные элементы в массиве

Дан массив. Определите, есть ли в нем два противоположных (то есть дающих в сумме 0) числа.

Если такие числа есть в массиве, выведите их индексы в порядке возрастания. Если таких чисел в массиве нет, ничего не выводите.

Ввод Вывод 
5
1 2 3 -2 -4
 
1 3

L: Сортировка выбором

Дан массив целых чисел. Отсортируйте его в порядке невозрастания значений. Выведите полученный массив на экран.

Решите эту задачу при помощи алгоритма сортировки выбором. Решение оформите в виде функции void SelectionSort(int * A, int n).

В алгоритме сортировки выбором мы находим наибольший элемент в массиве и ставим его на первое место, затем находим наибольший элемент из оставшихся и ставим его на второе место и т.д. Таким образом, в решении имеется цикл for(i = 0; i < n - 1; ++i), внутри которого находится наибольший элемент среди A[i], A[i+1], ..., A[n-1], который устанавливается на место A[i].

Вспомогательным массивом пользоваться нельзя.

Ввод Вывод 
5
1 4 2 3 4
 
4 4 3 2 1

M: Сортировка вставкой

Дан массив целых чисел. Отсортируйте его в порядке неубывания значений. Выведите полученный массив на экран.

Решите эту задачу при помощи алгоритма сортировки вставкой. Решение оформите в виде функции void InsertionSort(int * A, int n).

В алгоритме сортировки вставкой в каждый произвольный момент начальная часть массива уже отсортирована. В решении имеется цикл for(i = 1; i < n; ++i), внутри которого в предположении, что элементы массива A[0], A[1], ..., A[i-1] уже отсортированы, элемент A[i] добавляется в отсортированную часть. Для этого находится позиция, в которую необходимо вставить элемент A[i], затем осуществляется циклический сдвиг фрагмента уже отсортированной части.

Вспомогательным массивом пользоваться нельзя.

Ввод Вывод 
5
1 4 2 3 4
 
1 2 3 4 4

N: Сортировка пузырьком

Дан массив целых чисел. Отсортируйте его в порядке невозрастания значений. Выведите полученный массив на экран.

Решите эту задачу при помощи алгоритма пузырьковой сортировки. Решение оформите в виде функции void BubbleSort(int * A, int n).

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

Вспомогательным массивом пользоваться нельзя.

Ввод Вывод 
5
1 4 2 3 4
 
4 4 3 2 1

O: Сортировка подсчетом

Дан массив из N (N≤106) элементов, которые принимают целые значения от 0 до 100.

Отсортируйте этот массив в порядке неубывания элементов.

Ввод Вывод 
5
1 3 2 3 1
 
1 1 2 3 3

P: Равные элементы

Дан массив. Опеределите, какое наибольшее число равных друг другу элементов этого массива идет подряд.

Решение оформите в виде функции int MaxEqualPart(int * A, int n).

Ввод Вывод 
10
1 7 7 3 3 2 2 2 2 1
 

4
 

 
 

 



Q: Пересечение множеств



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


Решение оформите в виде функции
int Intersection(int * A, int n, int * B, int m, int * C).
Функция должна возвращать количество элементов в пересечении этих массивов.


Программа получает на вход количество элементов первого массива n,
затем n элементов первого массива в порядке возрастания, затем количество элементов
второго массива m, затем m элементов второго массива в порядке возрастания.


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


 
 

 
Ввод 
Вывод 

 

 

5
1 3 4 7 9
5
2 3 7 10 11
 

3 7
 

 
 

 


R: Слияние массивов



Даны два массива int A[n] и int B[m] упорядоченных по неубыванию.
Объедините их в один упорядоченный массив int C[n+m]. Решение оформите в виде
функции void merge (int * A, int n, int * B, int m, int * C). Алгоритм
должен иметь сложность O(n+m).


Программа получает на вход число n, затем последовательность из n неубывающих чисел –
элементы первого массива, затем число m, затем последовательность из m неубывающих чисел –
элементы второго массива.


Программа должна вывести n+m чисел, полученных объединением двух массивов в порядке неубывания.


 
 

 
Ввод 
Вывод 

 

 

3
1 5 7
4
2 4 4 5
 

1 2 4 4 5 5 7
 

 
 

 


S: Объединение множеств



Даны два массива, упорядоченных по возрастанию (каждый массив состоит из различных элементов).
Найдите объединение множеств элементов этих массивов, то есть те числа, которые являются элементами
хотя бы одного из этих массивов. Элементы, присутствующие в двух массивах одновременно
должны быть включены в объединение только один раз. Алгоритм должен иметь сложность O(n+m).


Решение оформите в виде функции
int Union (int * A, int n, int * B, int m, int * C).
Функция должна возвращать количество элементов в объединении этих массивов.


Формат входных данных аналогичен задаче Q. Программа должна вывести последовательность
возрастающих чисел, являющихся элементами хотя бы одного из данных массивов.


 
 

 
Ввод 
Вывод 

 

 

5
1 3 4 7 9
5
2 3 7 10 11
 

1 2 3 4 7 9 10 11
 

 
 

 


T: Решето Эратосфена



Определите const int N=10000000 и создайте массив bool IsPrime[N].
Заполните его нулями и единичками так, чтобы IsPrime[i]==1, если i -
простое число и IsPrime[i]==0, если i - составное.


Для этого сначала заполняем массив единицами. Затем “вычеркиваем”
(то есть помечаем нулями) те элементы, которые делятся на 2, начиная с 4.
Затем вычеркиваем те элементы, которые делятся на 3, начиная с 9. Затем вычеркиваем
элементы, которые делятся на 5, начиная с 25... И так далее - находим следующее
невычеркнутое число p и вычеркиваем все кратные p начиная с p2.


В результате невычернутыми останутся только простые числа. Такая процедура называется
“Решето Эратосфена”.


Напишите программу, которая строит решето Эратосфена, потом считывает натуральное
число n и выводит n-е по счету простое число. Гарантируется, что это число не превосходит
N.


 
 

 
Ввод 
Вывод 

 

 

5
 

11
 

 
 

 



U: Шарики



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


Напишите программу, которая по данной ситуации определяет, сколько шариков будет сейчас уничтожено.


Программа получает на вход количество шариков в цепочке (не более 1000) и цвета шариков
(от 0 до 9, каждому цвету соответствует свое целое число).


Требуется вывести количество шариков, которое будет уничтожено.


 
 

 
Ввод 
Вывод 

 

 

5
1 3 3 3 2
 

3
 

 

 

10
3 3 2 1 1 1 2 2 3 3
 

10
 

 
 

 



V: Наибольшее  произведение двух чисел



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


Решение должно иметь сложность O(n), где n - размер массива.


 
 

 
Ввод 
Вывод 

 

 

5
4 3 5 2 5
 

5 5
 

 

 

5
-4 3 -5 2 5
 

-5 -4
 

 
 

 



W: Наибольшее произведение трех чисел



В данном массиве из n≤106 найдите три числа,
произведение которых максимально.


Решение должно иметь сложность O(n), где n - размер массива.


Выведите три искомых числа в любом порядке.


Тесты к этой задаче закрытые.


 
 

 
Ввод 
Вывод 

 

 

9
3 5 1 7 9 0 9 -3 10
 

9 10 9
 

 

 

3
-5 –30000 –12
 

-5 –30000 -12


 
 

 



X: Период дроби



Известно, что рациональную дробь 1/n можно записать в виде периодической десятичной дроби.
По данному числу n≤1000 определите минимальную длину периода десятичной записи числа
1/n.


Тесты к этой задаче закрытые.


 
 

 
Ввод 
Вывод 

 

 

7
 

6
 

 

 

2
 

0
 

 
 

 



Y: Поиск в трех массивах



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


Алгоритм должен иметь сложность O(n+m+k), где n, m, k - размеры данных массивов.


Тесты к этой задаче закрытые.

 
 

 
Ввод 
Вывод 

 

 

5
2 4 4 6 7
3
1 4 8
4
1 2 3 4
 

4
 

 
 

 



Z: Максимальная непрерывная сумма



В массиве из n элементов, заполненном произвольными целыми числами,
за один проход найдите непрерывный фрагмент, сумма чисел в котором максимальна,
то есть найдите такие i и j, что сумма A[i]+A[i+1]+...+A[j] максимальна.
Решение должно иметь сложность O(n).


Программа получает на вход массив из n≤106 элементов и должна
вывести два индекса i и j таких, что сумма 
элементов от i-го до j-го максимальна. Если таких пар - несколько, то 
выведите ту пару, у которой j минимально возожмное, а при равных j выведите
ту пару, у которой i максимально возможно.


Тесты к этой задаче закрытые.


 
 

 
Ввод 
Вывод 

 

 

5
-1 2 3 -2 2
 

1 2
 

 

 

7
2 -2 3 -1 5 -2 7
 

2 6