Задачи по теме "Работа с массивами"

Список задач

1. Вычислить среднее арифметическое положительных элементов массива вещественных чисел. Результат является корректным при наличии в массиве хотя бы одного положительного числа.
2. Переставить элементы массива вещественных чисел в обратном порядке.
3. Заменить каждый элемент a[k] массива вещественных чисел на значение суммы всех элементов от начала массива вплоть до a[k] включительно, т.е. на сумму a[0]+...+a[k]. Результат является корректным при наличии в массиве хотя бы одного числа.
4. Циклически сдвинуть элементы массива целых чисел одну позицию вправо (по направлению к концу массива).
5. Определить количество различных значений в массиве целых чисел.
6. Определить, какое значение встречается наибольшее число раз в заданном массиве целых чисел. Результат корректен при наличии в массиве хотя бы одного числа.
7. Удалить из массива целых чисел все отрицательные значения, а оставшиеся неотрицательные сдвинуть (уплотнить) к началу массива с сохранением их исходного порядка. "Освободившиеся" элементы в конце массива заполнить нулями.
8. Каждый элемент массива вещественных чисел заменить на полусумму соседних с ним элементов. Для элементов, стоящих в начале и в конце массива, считать, что недостающее значение для вычисления полусуммы (для отсутствующего соседа) равно нулю.
9. Назовем массив целых чисел "плотным", если множество значений элементов этого массива целиком заполняет некоторый отрезком [p,q] в множестве целых чисел, т.е. для любого целого x найдется элемент a[i], равный x. Массив, состоящий из одинаковых элементов, равных x, считается плотным, и его отрезок значений есть [x,x]. Определить, является ли массив целых чисел "плотным". Результат является корректным при наличии в массиве хотя бы одного числа. Ответ: два числа p,q, если массив является "плотным", и одно число -1, если нет.
10. Назовем массив целых чисел "парным", если сумма элементов с четными индексами совпадает с суммой элементов с нечетными индексами. Определить является ли массив целых чисел "парным". Результат является корректным при наличии в массиве хотя бы двух чисел. Ответ: 1, если массив является "парным", и 0, если не является.
11. Назовем массив a[i] длины n "счастливым", если сумма некоторой непустой начальной его части совпадает с суммой оставшейся непустой части, т.е. если существует такое k<n и s, что s = a[0]+...+a[k-1] = a[k]+...+a[n-1]. Определить является ли массив целых чисел "счастливым" Результат является корректным при наличии в массиве хотя бы двух чисел. Ответ: два числа k и s, если массив "счастливый", и одно число -1, если нет. Если задача имеет несколько решений, то найти любое из них.
12. Выполнить сортировку массива вещественных чисел по возрастанию любым алгоритмом. Массив a[i] считается отсортированным по возрастанию, если для любой пары соседних элементов массива выполнено неравенство a[i]≤a[i+1].
13. Переставить элементы массива вещественных чисел таким образом, чтобы в начале массива оказались неотрицательные элементы, идущие по возрастанию, а в конце массива — отрицательные элементы, идущие по убыванию.
14. Переставить элементы массива вещественных чисел таким образом, чтобы в начале массива оказались отрицательные элементы, а в конце массива — неотрицательные. При этом взаимный порядок отрицательных элементов и взаимный порядок неотрицательных элементов должны остаться такими же, как и в исходном массиве.
15. Переставить элементы массива вещественных чисел по убыванию их модулей (сортировка по абсолютной величине).
16. Переставить элементы массива вещественных чисел так, чтобы элементы с четными индексами остались на своих местах, а элементы с нечетными индексами стали упорядоченными по возрастанию.
17. Для заданного натурального числа n заполнить массив целых чисел размера n+1 биномиальными коэффициентами C_n^k, k=0, 1, ..., n. Для вычисления биномиальных коэффициентов использовать треугольник Паскаля.
18. Коэффициенты многочлена степени d содержатся в массиве a вещественных чисел размера d+1 по возрастанию степеней (т.е. a[i] содержит коэффициент при xⁱ). Получить в том же массиве коэффициенты производной многочлена (дополнительный массив использовать нельзя!).
19. Коэффициенты многочлена степени d содержатся в массиве a вещественных чисел размера d+2 по возрастанию степеней (т.е. a[i] содержит коэффициент при xⁱ, последний элемент массива не используется). Получить в том же массиве коэффициенты первообразной многочлена (дополнительный массив использовать нельзя!).
20. Массив размера n содержит целые положительные числа. Изменить в нем знаки некоторых его элементов так, чтобы сумма всех элементов массива стала равной нулю. Если это сделать невозможно, то оставить элементы массива без изменения. Функция, решающая данную задачу, должна вернуть true, если это сделать удалось, и false в противном случае.

Общие указания

Во всех задачах исходные данные (набор чисел) задаются в файле "input.txt". При этом возможны 2 варианта заданий:

• первое число в файле задает длину массива чисел, а последующие числа есть элементы массива, который требуется обработать;
• файл содержит последовательность элементов массива без указания длины массива в начале файла.

В обоих случаях результат работы программы должен быть записан в файл "output.txt". Результатом программы в зависимости от задания может быть либо преобразованный массив, либо одно или несколько чисел, полученных в результате обработки массива. Числа при записи в файл разделяются пробелами или переводами строк. При записи преобразованного массива в файл записывать в начало файла его длину не нужно.

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

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

Если программа не может корректно решить задачу (файлы не открылись, при чтении возникли ошибки, указанное или фактическое количество чисел в файлах не позволяет корректно вычислить ответ, отказы в выделении памяти и т.п.), то результат не вычисляется, а функция main должна возвратить значение -1. При успешном решении задачи функция main должна возвратить 0.

Автоматический тестер

Задачи из данного списка можно проверять с помощью автоматического тестера. Для получения условия задачи с номером N (здесь N — целое число от 1 до 16) надо выполнить команду

    tasktest array1 N -text

    tasktest array1 N file1 file2 file3 ...

Пример: пусть мы решаем задачу номер 2 (переставить элементы массива в обратном порядке). Для получения точной формулировки задачи надо выполнить команду

    tasktest array1 2 -text

    tasktest array1 2 invert.cpp