Лабораторная работа № 12.

Тема. Указатели на функции.

Требования и общие указания к заданиям.

• Составить функцию, которая по заданной формуле (Симпсона, трапеций, прямоугольников и др.) вычисляет значение определённого интеграла от произвольной функции одной переменной или решает произвольное нелинейное уравнение f(x)=0 с помощью заданного численного метода.

• В качестве одного из параметров этой функции должен быть указатель на подынтегральную функцию или указатель на функцию левой части уравнения f(x)=0.

• Функцию для вычисления определённого интеграла проверить, используя аналитическое выражение для первообразной или с помощью какой-нибудь системы компьютерной математики (Mathcad, Mathematica и др.).

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

• Запрограммировать проверку найденных решений нелинейных уравнений.

Варианты заданий.

В. Задачи второго среднего уровня.

1. Составить функцию, которая вычисляет значение определённого интеграла от произвольной функции одной переменной по формуле правых прямоугольников:

,

где n фиксировано, . Составленную функцию проверить для вычисления интеграла . Значение функции y=sin(t) вычислять с заданной точностью ., используя разложение в ряд Тейлора:

2. Составить функцию, которая вычисляет значение определённого интеграла от произвольной функции одной переменной. по формуле левых прямоугольников

,

где n фиксировано, . Составленную функцию проверить для вычисления интеграла . Значение функции y=cos(t) вычислять с заданной точностью ., используя разложение в ряд Тейлора:

.

3. Составить функцию, которая вычисляет значение определённого интеграла от произвольной функции одной переменной по формуле средних прямоугольников

,

где n фиксировано, Составленную функцию проверить для вычисления интеграла Значение функции y=e^t , где

t= 1/x, вычислять с заданной точностью , используя разложение в ряд Тейлора:

4. Составить функцию, которая вычисляет значение определённого интеграла от произвольной функции одной переменной с помощью составной формулы трапеций:

где n фиксировано, . С помощью составленной функции вычислить значение интеграла для n=3, 6, 9. Для вычисления y = , где t= , составить и использовать функцию, которая реализует следующий итерационный алгоритм: … Вычисления продолжаются до тех пор, пока не выполнится условие . Массив y не формируется, достаточно двух переменных для старого и нового значений y.

5. Составить функцию, которая вычисляет значение определённого интеграла от произвольной функции одной переменной, используя составную формулу трапеций:

где n фиксировано, . С помощью составленной функции вычислить значения интеграла для с = 1, 1.2, 1.4, …, 2.8, 3. Для вычисления y = можно использовать стандартную встроенную функцию или вычислять по итерационной формуле, приведенной в варианте 4.

6. Составить функцию, которая вычисляет значение определённого интеграла от произвольной функции одной переменной, используя составную формулу Симпсона:

где n фиксировано, . С помощью составленной функции вычислить значение интеграла . Значение функции y=e^t , где t= -x², вычислять с заданной точностью , используя разложение в ряд Тейлора:

7. Составить функцию, которая вычисляет значение определённого интеграла от произвольной функции одной переменной, используя составную формулу Симпсона:

где n фиксировано, . С помощью составленной функции вычислить значение интеграла для n=6. Значение функции y=ln(1+t) , где t=x², вычислять с заданной точностью , используя разложение в ряд Тейлора: .

8. Составить функцию для вычисления определённого интеграла от произвольной функции одной переменной по следующей формуле:

I ,

где n фиксировано и кратно трём, , , С помощью составленной функции вычислить значения интегралов для k = 1/4, 1/2, 1, 2, 4.

9. Составить функцию для приближённого решения произвольного нелинейного уравнения f(x)=0 методом деления отрезка пополам с точностью . Используя эту функцию, решить уравнения для a = 0.5+0.1k, k=0,1,2,3,4,5 с точностью ₁=0.1.

10. Составить функцию для приближённого решения произвольного нелинейного уравнения f(x)=0 методом простой итерации с точностью . Используя эту функцию, решить уравнения с точностью ₁=0.0001. Указание. В методе простой итерации исходное уравнение приводится к виду x=(x). Начиная с некоторого заданного начального значения , строим последовательность по правилу . Вычисления прекращаем, если на некотором шаге получим , где — заданная точность решения уравнения.

11. Составить функцию для приближённого решения произвольного нелинейного уравнения f(x)=0 методом Ньютона с точностью . Используя эту функцию, решить уравнения 3x-e^kx = 0 для k = 1, 2, 3, 4, 5 с точностью ₁=10^-5. Значение e^t вычислять с заданной точностью ₂ = 10^-6 с помощью разложения в ряд Тейлора

e^t=1+t+ .

Указание. В методе Ньютона по заданному начальному приближению x_о строим последовательность по правилу

; n=0,1, 2, 3, …

Вычисления продолжаются до тех пор, пока не выполнится условие . Массив x не формируется, достаточно двух переменных для старого и нового значений x.

12. Составить функцию для приближённого решения нелинейного уравнения f(x)=0 с точностью  методом секущих. Используя эту функцию, решить уравнения для = 2(0.1)3 с точностью ₁=10^-5. Указание. В методе секущих по двум начальным приближениям строим последовательность по правилу

; n= 1,2, 3, …

Вычисления продолжаются до тех пор, пока не выполнится условие . Массив x не формируется, достаточно двух переменных для старого и нового значений x.

13. Составить функцию для решения произвольного нелинейного уравнения f(x) модифицированным методом секущих с точностью . Используя эту функцию, решить уравнение для =3(0.5)7 с точностью ₌ . Указание. В модифицированном методе секущих по двум начальным приближениям строим последовательность по правилу

для n=1, 2, …, при . Вычисления прекращаем, если на некотором шаге получим , где — заданная точность решения уравнения.

13. Составить функцию, которая находит приближенно, с точностью до 0,001, минимум произвольной функции от одной переменной на отрезке [u, v]. С помощью составленной функции найти минимум функции y= +sin(x) на отрезке (-0.9, 0.9). Значение функции y= sin (x) вычислять с заданной точностью , используя разложение в ряд Тейлора:

13. Составить функцию, которая выводит таблицу значений произвольной функции от одной переменной на отрезке [u, v] с шагом h. С помощью составленной функции построить таблицу значений функции y=arctg(x) на отрезке [-1, 1] с шагом h=0.1. Значение функции y=arctg(x) вычислять с заданной точностью , используя разложение в ряд:

С. Задачи повышенной сложности.

1— 8. Найти приближённое значение определённого интеграла с заданной точностью , используя соответствующие (см. уровень В) квадратурные формулы. Это означает, что значение интеграла вычисляем не для одного фиксированного количества (n) разбиений отрезка [a, b], а используем двойной пересчёт. Сначала интеграл вычисляем для n разбиений, затем для 2n, 4n и т.д. Вычисления прекращаем, если на некотором шаге получим значение интеграла, полученное на предыдущем шаге, а - значение интеграла, полученное на данном текущем шаге.

Лабораторная работа 13.

Тема: Рекурсивные функции.

Требования и общие указания к заданиям.

Выполнить задания двумя способами: 1) используя механизм рекурсии;

2) разработать нерекурсивный алгоритм и запрограммировать его с помощью обычного цикла. Оба варианта включить в один проект в виде отдельных функций.

B. Задачи второго среднего уровня.

1. Вычислить для заданного натурального n:

.

2.Найти n-й член числовой последовательности, которая определяется рекуррентной формулой

a₁ = 1, a₂ = 2, a₃ = 3, a_n+1 = 3a_n + 2a_n– + a_n–2.

3. Для заданных вещественном x и натуральном n найти значение полинома Чебышева Т_n(x) по рекуррентной формуле:

T₀(x) = 1, T₁(x) = x, T_n+1(x) = 2xT_n(x) – T_n–1(x).

1. Найти значение функции С(m,n), где 0 < m < n, если:

.

3. С помощью признака делимости на 3 проверьте, кратно ли данное натуральное число трём.

4. Найдите n-ю степень (n – натуральное число) числа а, используя рекурсивную функцию.

5. Найдите n-й член арифметической прогрессии с заданными первым членом а и разностью прогрессии d.

6. Найдите n-й член геометрической прогрессии с заданными первым членом b и знаменателем прогрессии q.

7. Методом половинного деления уточните корень уравнения f(х) = 0.

8. Найти максимальный элемент массива а₁, а₂, …, а_n.

9. В одномерном массиве найти i и j такие, что подпоследовательность а_i, а_i+1, …, а_j является перевертышем.

10. В одномерном числовом массиве найдите подпоследовательность подряд идущих элементов, сумма которых максимальна.

11. Рассортировать одномерный массив методом простого выбора.

12. Запрограммировать алгоритм двоичного поиска элемента одномерного массива, равного данному числу.

13. Разработайте рекурсивную функцию нахождения значения функции Аккермана, которая определяется для всех неотрицательных целых аргументов m и n следующим образом:

А(0, n) = n + 1;

A(m, 0) = A(m – 1, 1), если (m > 0);

A(m, n) = A(m – 1, A(m, n – 1)), если (m, n > 0).

С. Задачи повышенной сложности.

1. С помощью рекурсивной функции найдите с заданной точностью квадратный корень , воспользовавшись итерационной формулой Ньютона:

Y₀=1

Вычисления производите пока |Y_i – Y_i-1| не станет меньше заданного EPS..

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

.

2. Разработайте рекурсивную функцию нахождения наибольшего общего делителя двух чисел m и n, используя алгоритм Евклида ( например, НОД(96, 36) : 96 = 2 · 36 + 24; 36 = 1 · 24 +12; 24 = 2 · 12 + 0. Следовательно, НОД(96, 36) = 12). Используя эту функцию, составьте вторую рекурсивную функцию для нахождения наибольшего общего делителя натуральных чисел а₁, а₂, … а_n.одномерного массива.

НОД(n₁, n₂, ... n_m) = НОД (НОД (n₁, n₂, ... n_m–1), n_m)_.

3. Найдите количество n-значных чисел в m-ичной системе счисления, у каждого из которых сумма цифр равна k. При этом в качестве n-значного числа мы допускаем и числа, начинающиеся с одного или нескольких нулей.

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

5. Дана матрица a(m, n), состоящая из нулей и единиц. Найдите в ней прямоугольную подматрицу из одних единиц максимального размера (т.е. с максимальным произведением высоты на длину).

6. Дана матрица a(m, n). Найдите в ней прямоугольную подматрицу, сумма элементов которой максимальна.

7. Дана матрица a(m, n). Найдите в ней путь от элемента a[i1, j1] до элемента a[i2, j2] с максимальной суммой. Ходить можно по горизонталям и вертикалям. Каждый элемент матрицы может входить в путь не более одного раза.

8. Дана матрица a(m, n). Найдите в ней путь от элемента первой строки матрицы до элемента последней строки с максимальной суммой. Ходить можно вниз по вертикали или диагоналям.

9. Вычислите определитель заданной матрицы, пользуясь формулой разложения по первой строке:

где матрица В_k получается из матрицы А вычеркиванием первой строки и k-го столбца.

10. Лабиринт задан матрицей a(m, n), состоящей из нулей и единиц, причем а[1, 1] = 0 и a[m, n] = 0. Разработайте рекурсивную процедуру нахождения пути из клетки а[1, 1] в a[m, n]. Путь должен состоять из элементов, равных нулю. Ходить можно только по вертикалям и горизонталям.

11. Задано число А и два вектора b[1..n] и c[1..n]. Найдите множество I, являющееся подмножеством множества {1, ..., n}, такое, что , а является максимальной из всех возможных.

12. Разработайте рекурсивную функцию, находящую сумму двух натуральных чисел, заданных массивами своих цифр а₁, а₂, …, а_n и b₁, b₂, …, b_m.

13. Разработайте рекурсивную функцию сортировки одномерного массива методом слияния.

14. Дано n различных натуральных чисел. Разработайте рекурсивную функцию формирования всех перестановок этих чисел.

15. Даны два натуральных числа m и n. Найдите НОД(m, n) и натуральные x и y такие, что mx + ny = НОД(m, n).

16. Даны три натуральных числа m, n и k, причем k делится на НОД(m, n). Найдите какое-нибудь целочисленное решение уравнения mx + ny = k.

17. Имеется n населенных пунктов, пронумерованных от 1 до n. Некоторые пары пунктов соединены дорогами. Разработайте рекурсивную процедуру определения, можно ли попасть по этим дорогам из 1-го пункта в n-й.

18. Вводятся три неотрицательных числа d, i, c и две строки X и Y. Найдите преобразование строки X в Y минимальной стоимости. Допустимы следующие три операции:

- удалить любой символ из X (стоимость операции d);

- вставить любой символ в X (стоимость операции i);

- заменить символ в X на произвольный (стоимость операции с).

19. Строка символов состоит из букв А, В и С. Разработайте рекурсивную функцию, преобразующую данную строку по правилам:

а) удаляет четыре подряд идущие буквы А;

б) удаляет из последовательности ВАВА одну пару ВА;

в) удаляет комбинацию АВС.

Преобразования выполняйте до тех пор, пока ни одной из перечисленных комбинаций не останется.

19. Даны две строки x и y. Строка x состоит из нулей и единиц, строка y – из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 – либо в непустую последовательность букв A, либо в непустую последовательность букв B?

20. Задано конечное множество жителей некоего города, причем для каждого из жителей перечислены имена его детей. Жители X и Y считаются родственниками, если:

а) либо Х – ребенок Y,

б) либо Y – ребенок X,

в) либо существует некий Z такой, что Х является родственником Z, а Z является родственником Y.

Перечислите все пары жителей города, которые являются родственниками.

22. На шахматной доске расставьте 8 ферзей так, чтобы они не «били» друг друга.

23. Имеется полоска клетчатой бумаги шириной в одну клетку и длиной в n клеток. На первой клетке установлена шашка. Одним ходом шашку можно передвигать на одну или две клетки. Разработайте рекурсивную функцию, определяющую количество способов продвижения шашки на n-ю клетку.

Г л а в а 8