Примеры решения задач

Задача 7.1. Постройте бесконечную возрастающую последовательность натуральных чисел, состоящую из всех чисел Фибоначчи и степеней двойки. Начальный отрезок такой последовательности будет выглядеть следующим образом:

[1, 2, 3, 4, 5, 8, 13, 16, 21,…

Решение. Легко построить возрастающую последовательность чисел Фибоначчи и отдельно последовательность степеней двойки. Вот соответствующие выражения: power2 = iterate (*2) 1.

fibonacci = 1:2: zipWith (+) fibonacci (tail fibonacci).

Чтобы соединить две бесконечные возрастающие последовательности в одну, воспользуемся алгоритмом слияния списков, модифицированным таким образом, чтобы в результирующую последовательность не попадали одинаковые элементы:

merge: [Integer] -> [Integer] -> [Integer].

merge sl6(xl:tl) s20(x2:t2) | xl < x2 = xl: merge tl s2.

I xl > x2 = x2: merge si t2.

| otherwise = xl: merge tl t2.

Теперь выражение для искомой последовательности будет выглядеть следующим образом:

merge power2 fibonacci.

Текст программы для решения поставленной задачи приведен в листинге 7.2.

Листинг 7.2. Бесконечная последовательность чисел Фибоначчи и степеней двойки.

fibAndPower2: [Integer].

fibAndPower2 = merge power2 fibonacci where power2 = iterate (*2) 1.

fibonacci = l:2:zipWith (+) fibonacci (tail fibonacci).

merge sl@(xl:tl) s20(x2:t2) | xl < x2 = xl: merge tl s2.

I xl > x2 = x2: merge si t2.

I otherwise = xl: merge tl t2.

Заметим, что в результирующей последовательности не так уж много чисел, которые являются одновременно числами Фибоначчи и степенями двойки. Легко находятся первые три таких числа: 1, 2 и 8, однако, попытка найти четвертое приводит к переполнению памяти.

Задача 7.2. Постройте бесконечную числовую матрицу, в которой все натуральные числа расположены «в диагональном» порядке так, как показано ниже:

• 1 2 4 711…
• 3 5 8 12.. .
• 6 9 13 …
• 10 14 …
• 15 …

Решение. Заметим, что каждую следующую строку матрицы можно получить из предыдущей, если отбросить первый элемент строки и прибавить единицу ко всем оставшимся. Таким образом, если обозначить первую строку матрицы идентификатором rowl, то выражение для всей матрицы может быть получено следующим образом: iterate (map (+l).tail) rowl.

Первая строка получается, если взять первое число строки — единицу и последовательно добавлять числа натурального ряда: 1, 2, 3 и т. д. Тогда все выражение для искомой матрицы можно записать следующим образом: diagMatrix: Matrix.

diagMatrix = iterate (map (+ l).tail) rowl where rowl = scanl (+) 1 [1.].

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

" take 4 $ map (take 4) diagMatrix.

[[ 1,2,4,7], [3,5,8,12], [6,9,13,18], [10,14,19,25]].

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

" diagMatrix ! ! 1000 ! ! 1000.

• 2 002 001
• (0.20 secs, 69 431 080 bytes)

Задача 7.3. Напишите функцию для транспонирования матрицы со строками бесконечной длины. Самих строк тоже может быть бесконечно много.

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

Понятно, как получить первую строку искомой матрицы: нужно составить список из первых элементов каждой строки исходной матрицы: firstRow = map head matrix.

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

Листинг 7.3. Транспонирование бесконечной матрицы type Matrix, а = [ [а] ].

transpose: Matrix, а -> Matrix а.

transpose m = map head m: transpose (map tail m).

Если транспонировать матрицу diagMatrix, построенную нами в предыдущей задаче, то точно так же можно вывести первые несколько элементов транспонированной матрицы:

" take 4 $ map (take 4) $ transpose diagMatrix.

[[1,3,6,10], [2,5,9,14], [4,8,13,19], [7,12,18,25]]

Задача 7.4. Напишите функцию, которая по заданному вещественному х строит бесконечный список, элементами которого являются члены разложения функции sin х в ряд Тейлора в окрестности нуля.

Решение. Разложение синуса в ряд Тейлора в окрестности нуля имеет вид.

Для получения членов этого ряда нужно взять первый член этого ряда, а затем каждый следующий член получается, если предыдущий умножить на -х² и поделить на п (п — 1), где число п берется из последовательности нечетных натуральных чисел 3, 5,…

Таким образом, получается следующая функция для генерации бесконечного ряда членов разложения:

rowSin х = scanl (u n -> -u*x*x/(n-1)/n) x [3,5.].

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

>> sin (pi/4).

• 0.7 071 067 811 865 475 «sum $ take 5 $ row (pi/4.0)
• 0.7 071 067 829 368 671

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