Задания к зачету

Компьютерные науки, 1 семестр. Задачи к зачету

Общая задача 1. Разработать шаблоны функций, реализующих любые два из описанных ниже алгоритмов (по одному из частей 1 и 2). Применить разработанные функции к массивам (матрицам) типов short и float.

Предполагается, что элементы массивов и матриц могут иметь произвольный тип (и, следовательно, являются параметрами шаблонов). Матрицы хранятся в виде одномерных массивов по строкам (т. е. сначала элементы первой строки, затем второй и т. д.). Под диагоналями квадратной матрицы подразумеваются главная (a₁₁, a₂₂, , a_nn) и обратная (a_1n, a_{2, n  1}, , a_n1).

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

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

Общая задача 2. Пусть тип T определен следующим образом: struct T {}; Применяя к массивам (матрицам) типа T разработанные шаблоны функций и доопределяя необходимые для успешной компиляции операторы и функции, работающие с типом T (и содержащие только оператор return), составить синтаксическое и семантическое описание интерфейса, которым должен обладать тип T для того, чтобы к массивам (матрицам) этого типа могли быть применены созданные обобщенные алгоритмы.

Общая задача 3. Протестировать разработанную программу на утечку памяти, погрузив все тело функции main в бесконечный цикл и отключив операции ввода/вывода (исходные данные для функций при этом генерируются случайным образом). Добиться, чтобы объем памяти, выделенной программе, не увеличивался в процессе ее работы (в Windows объем используемой процессом памяти отображается, например, в Диспетчере задач).

Часть 1. Арифметические операции над элементами массивов и матриц

1. Каждый элемент a_ij матрицы A(m, n) заменить а) суммой, б) про­из­ве­де­ни­ем элементов подматрицы A(i, j), расположенной в левом верхнем углу матрицы A.

2. В массиве A(n) каждый элемент a_i, кроме крайних, заменить выражением а) a_i  1  2a_i  a_i  1, б) a_i  1  a_i²  a_i  1, первый и последний элементы — выражениями а) 2(a₁  a₂) и 2(a_n  1  a_n), б) (a₁  a₂)² и (a_n  1  a_n)², соответственно.

3. В матрице A(m, n) каждый элемент, кроме граничных, заменить а) сум­мой, б) произведением непосредственно примыкающих к нему элементов по вертикали, горизонтали и диагонали.

4. Вычислив для заданной квадратной матрицы A(n, n) средние значения а) сум­мы, б) произведения элементов в каждой строке, столбце и диагонали, найти все строки, столбцы и диагонали, для которых а) сум­ма, б) произведение элементов отлично от среднего.

5. Задано число x. Найти все строки, столбцы и диагонали заданной квадратной матрицы A(n, n), содержащие все числа вида а) x, 2x, …, nx, б) x, x², …, xⁿ.

6. Задано число x. Матрицу A(m, n) заполнить числами а) x, 2x, …, mnx, б) x, x², …, x^mn по спирали, начинающейся в левом верхнем углу и закрученной по часовой стрелке.

7. Задано число x. Матрицу A(m, n) заполнить числами а) x, 2x, …, mnx, б) x, x², …, x^mn в следующем порядке: a₁₁, a₁₂, a₂₁, a₁₃, a₂₂, a₃₁, … (диагонализация).

8. Задано число x. Матрицу A(m, n) заполнить следующим образом: граничным элементам присвоить значение x, границе оставшейся подматрицы — а) 2x, б) x², сле­дую­щей границе — а) 3x, б) x³ и т. д.

9. Задано число x и индексы k, l. Матрицу A(m, n) заполнить следующим образом: элементу a_kl присвоить значение x, окаймляющим его по вертикали, горизонтали и диагонали — а) 2x, б) x², элементам следующего окаймления — а) 3x, б) x³ и т. д.

10. Найти все строки заданной матрицы A(m, n), элементы которых образуют арифметическую или геометрическую последовательность.

11. Задано число x. Заполнить массив A(n) числами а) x, p(2)x, …, p(n)x, б) x, x^p(2), …, x^p(n), где p(i) — i‑е простое число.

12. Задано число x. Заполнить массив A(n) числами а) x, 2x, …, nx, б) x, x², …, xⁿ следующим образом: на первое место поместить x, далее все числа, коэффициенты (степени) которых кратны 2, затем все числа с коэффициентами (степенями), кратными 3, кроме тех, которые уже находятся в массиве, и т. д.

13. В массиве A(n) каждый элемент, кроме первого, разделить на среднее арифметическое (среднее геометрическое) всех предыдущих элементов.

14. Для заданной квадратной матрицы A(n, n) найти суммы (произведения) элементов на каждой из линий, параллельных главной диагонали.

15. Рациональное алгебраическое выражение задано массивами коэффициентов A(n) и показателей степеней K(n). Привести в нем подобные члены и сформировать массив коэффициентов полученного многочлена.

16. Многочлены p(x) и q(x) заданы массивами P(m) и Q(n) своих коэффициентов. Определить коэффициенты их композиции p(q(x)).

17. В заданном массиве A(n) каждый элемент разделить на количество равных ему элементов данного массива.

Часть 2. Сравнения элементов массивов и матриц

1. Седловой точкой матрицы называется элемент, являющийся одновременно наибольшим в столбце и наименьшим в строке. В заданной матрице A(m, n) найти все седловые точки или установить, что их нет.

2. В заданном массиве A(n) найти индексы i и j такие, что сумма элементов a_i, a_i  1, …, a_j максимальна.

3. В заданном массиве A(n) найти наиболее длинную цепочку элементов, упорядоченную по неубыванию.

4. Последовательность элементов a₁, a₂, … называется пилообразной, если a₁  a₂  a₃  … или a₁  a₂  a₃  … В заданном массиве A(n) найти наиболее длинную пилообразную цепочку элементов.

5. За один проход заданного массива A(n) найти k наибольших элементов данного массива.

6. В массиве A(2n  1), не содержащем одинаковых элементов, найти без использования сортировки такой элемент a (и его индекс), что в данном массиве ровно n меньших его элементов и ровно n больших.

7. В массиве H(n) хранятся значения высот некоторого профиля местности (ее вертикального сечения) с постоянным шагом по горизонтали. Найти номера точек измерения высоты, невидимых для наблюдателя, находящегося в точке (1, H(1)).

8. Упорядочить заданный массив A(n) по возрастанию, удалив повторяющиеся элементы и заполнив остаток наибольшим элементом из A.

9. За одни проход произвести слияние двух упорядоченных по неубыванию массивов A(m) и B(n) в один упорядоченный по возрастанию массив C, удалив повторяющиеся элементы.

10. Произвести слияние упорядоченного по неубыванию массива A(m) и неупорядоченного массива B(n) в один упорядоченный по возрастанию массив C, удалив повторяющиеся элементы. Элементы массива A(m) разрешается просмотреть лишь один раз.

11. Переставить элементы матрицы A(n, n) так, чтобы на главной диагонали и всех линиях, параллельных ей, стояли неубывающие последовательности (перестановка элементов осуществляется только в пределах линии).

12. Массивы A(n), D(n) и K(n) содержат первые члены, разности и количества элементов n арифметических прогрессий. Не находя самих по­сле­до­ва­тель­нос­тей (в виде массивов), произвести их слияние в один неубывающий массив.

13. В массиве A(n) каждый элемент, кроме первого, заменить вторым по величине среди всех предыдущих элементов, если такой существует, и минимальным из предшествующих в противном случае.

14. Рассматриваются квадратные матрицы, у которых в каждой строке и каждом столбце имеется в точности один минимальный элемент, причем минимальный элемент каждой строки является минимальным и в своем столбце. Для заданной квадратной матрицы A(n, n) убедиться в том, что она удовлетворяет указанному условию, после чего перестановкой строк и столбцов добиться, чтобы все минимальные элементы располагались на главной диагонали.

15. Из элементов массива A(2n) получить массивы B(n) и C(n) следующим образом. Выбрать в массиве A два наиболее близких по значению элемента, меньший из них поместить в массив B, больший — в массив C. Продолжить выбор из оставшихся элементов до полного заполнения массивов B и C.

16. В массиве A(n) наименьший элемент поместить на первое место, наименьший из оставшихся — на последнее, следующий по величине — на второе, следующий — на предпоследнее и т. д. до середины массива.

17. Даны два массива A(m) и B(n). Найти наибольший элемент массива A, не имеющий себе равных в массиве B.