На этом шаге мы приведем задачи для самостоятельного решения.
Замечание. Найдите ошибки, описки, неточности и прочие изъяны в приведенных задачах.
1. Моделирование векторов (одномерных массивов) на базе одноуровневых списков
1*. Напишите функцию, переставляющую местами второй и предпоследний элементы заданного вектора.
2*. Определите, имеются ли в целочисленном векторе два подряд идущих элемента, равных заданному.
3*. Выберите из заданного вектора все элементы, делящиеся на заданное положительное число.
4*. Вычислите количество положительных, отрицательных и нулевых элементов в заданном числовом векторе.
5*. Напишите функцию, заменяющую максимальный элемент вектора его индексом.
6*. Напишите функцию, заменяющую минимальный элемент вектора значением его удвоенного индекса.
7*. Напишите функцию, заменяющую все положительные элементы заданного вектора заданным элементом.
8. Напишите функцию, меняющую местами в заданном векторе элементы в парах "элемент с нечётным номером - элемент с чётным номером" и не использующую дополнительных векторов.
9. Определите количество различных элементов в заданном векторе.
10. Напишите функцию, переставляющую элементы вектора в обратном порядке и не использующую нового вектора.
11. Напишите функцию, удаляющую из заданного числового вектора все отрицательные элементы путём их замены на значения предыдущих элементов вектора.
12. Все элементы числового вектора, отличные от 0, перепишите, сохраняя их порядок, в начало вектора, а нулевые - в его конец (нового вектора не заводите).
13. Напишите функцию, определяющую все локальные минимумы числового вектора.
Указание. Локальными минимумами числового вектора называются элементы, которые меньше двух рядом стоящих с ним элементов. Например, вектор с элементами 7, 4, 8, 3, 6, 5, 3, 2 имеет два локальных минимума - 4 и 3.
14. В числовом векторе каждый элемент равен 0, 1 или 2. Переставьте, не используя дополнительного вектора, элементы вектора так, чтобы сначала располагались все 0, затем 1, и, наконец, все 2.
15. Напишите функцию, возвращающую длину самой длинной последовательности нулей в целочисленном векторе.
16. Напишите функцию, проверяющую строго ли чередуются нули и единицы в заданном векторе, состоящем только из 0 и 1.
17*. Выпишем последовательно все натуральные числа от 2 до n. Вычеркнем из них все кратные 2, затем 3 и т.д. Пользуясь указанным методом, найдите все простые числа, меньшие n.
Указание. Вам предлагается реализовать классический алгоритм нахождения простых чисел, называемый решето Эратосфена.
18*. Задана последовательность из n чисел. Напишите функцию для нахождения самой длинной возрастающей подпоследовательности данной последовательности.
19*. Задана последовательность из n чисел. Напишите функцию для нахождения самой длинной подпоследовательности, обладающей следующим свойством:
A[i]<A[i+1]>A[i+2]<A[i+3]>A[i+4]<...
2. Моделирование векторов (одномерных массивов) на базе ассоциативных списков
1*. Постройте абстрактный тип данных "вектор" на базе ассоциативных списков языка Haskell.3. Моделирование матриц (двухмерных массивов) на базе двухуровневых списков
1. Постройте абстрактный тип данных "матрица", представляющий собой однонаправленный список однонаправленных списков - строк матрицы. Для этого определите следующие операции:
- (1) функцию, вставляющую в матрицу новую строку после строки с номером n;
- (2) функцию, вставляющую в матрицу новый столбец после столбца с номером n;
- (3) функцию, удаляющую из матрицы столбец с номером n;
- (4) функцию, удаляющую из матрицы строку с номером n;
- (5) функцию, обменивающую местами в матрице значения элементов aij и anm;
- (6) функцию, помещающую в матрице элемент aij вместо элемента anm.
2. Реализуйте операции сложения, умножения и транспонирования числовых матриц, представленных с помощью абстрактного типа данных "матрица", а также операцию умножения матрицы на число.
3. Напишите функцию, увеличивающую каждый элемент числовой матрицы на 1.
4. Напишите программу, позволяющую получать сумму значений элементов: (1) в n-ой строке; (2) в n-ом столбце числовой матрицы.
5. Напишите программу, позволяющую определять количество ненулевых элементов: (1) в n-ой строке; (2) в n-ом столбце числовой матрицы.
6. Напишите функцию, производящую вычисление суммы значений элементов числовой матрицы, расположенных в её первой и последней строке, а также - в её первом и последнем столбце:
7. Напишите функцию, производящую вычисление произведения значений элементов числовой матрицы, расположенных по её диагоналям (основной и побочной).
8. Напишите программу, обнуляющую значения элементов:
- (1) n-ой строки матрицы;
- (2) n-го столбца матрицы;
- (3) диагонали матрицы, начиная с элемента, находящегося на пересечении первой строки и первого столбца матрицы.
9. Напишите программу, позволяющую в числовой матрице менять местами: (а) два указанных столбца; (б) две указанные строки.
10. Напишите функцию, заполняющую квадратную матрицу по столбцам последовательностью чисел Фибоначчи:
F1=1, F2=1, Fn=Fn-1+Fn-2, n >=3.
11*. Напишите функцию, заполняющую квадратную матрицу последовательными целыми числами от 1 до n2, расположенными по спирали, начиная с левого верхнего угла и продвигаясь по часовой стрелке.
Указание. Рассмотрите пример для n=6:
1 2 3 4 5 6
20 21 22 23 24 7
19 32 33 34 25 8
18 31 36 35 26 9
17 30 29 28 27 10
16 15 14 13 12 11
На следующем шаге мы рассмотрим генерацию псевдослучайных чисел и списков.
