metod1k

и, соответственно, максимальное значения среди нулей всех функций из этого же набора на [0, 1]. Конкретно, вид функции определен в таблице 2.

В этом задании принимается, что функции f1(x) и f2(x) из заданного набора не являются параметрами составной функции F (x). Это означает, что набор функций f1(x), f2(x) для функции F (x) фиксирован, т. е. всегда тот же, что указан в таблице 1, тогда как в других случаях набор функций из этой таблицы считается произвольным, данным просто для примера, чтобы при выполнении задания не пришлось дополнительно подбирать для них еще и выражения.

Пункты задания

1.В рабочей области командного окна сформировать вектор класса CELL, содержащий все функции из таблицы 1 (в виде inline-функций и/или имен соответствующих m-функций), при этом дополнительные параметры 3-ей 4-ой функций из таблицы считать равными 0. При желании этот вектор можно сохранить на жестком диске с помощью команды SAVE, и тогда при необходимости (при входе в систему заново) этот вектор можно будет повторно загружать в рабочую область с помощью команды LOAD.

2.Решить задачу с использованием стандартных функций QUAD и

FZERO в случае, когда значения всех дополнительных параметров у функций из заданного набора отсутствуют. При этом ранее созданный вектор класса CELL с функциями должен использоваться в качестве фактического значения входного параметра разрабатываемой m-функции (т.е. набор этих функций вообще говоря может быть произвольным, а не только тем, который задан таблицей 1).

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

29

4. Доработать программу из предыдущего пункта таким образом, чтобы стало возможным включать в набор исходных функций и функции, зависящие от любого числа дополнительных параметров, как, например, функции 3 и 4 из таблицы 1. Для передачи значений этих параметров в программу следует снабдить ее вторым входным параметром в виде вектора класса CELL с числом элементов равным числу функций, содержащихся в первом входном параметре (также векторе класса CELL). При этом если, скажем, k-ая функция из первого входного параметра не имеет дополнительных параметров, то k-ый элемент второго входного параметра должен быть пустым вектором класса DOUBLE. В противном случае этот вектор должен содержать значения соответствующих параметров k-ой функции. Кроме того, при программировании того или иного, указанного в таблице 2, численного метода использовать стандартный контейнер входных параметров VARARGIN.

Таблица 1.

Заданный примерный набор гладких на [0, 1] функций, имеющих на этом отрезке единственный нечетный нуль

f1(x) = arccos2(2x + 2) − 2x + 0, 99

f2(x) = ln(2x + 1) − 1/(4x2 + 4x + 2)

f3(x) = (tg(x + 0, 2) − 1/(x + 0, 2)) (1 + c1)

f4(x) = x4 − 13x2 + 36 − 1/(x + 0, 01) (1 + c1c2 − c3)

f5(x) = 27x3 − 27x2 + 2 − 2e3x − 1

f6(x) = sin (2x − 1)2 − 12x + 7

f7(x) = cos (2x − 1)2 − 20x + 10

f8(x) = ln2(2x + 1) − 1/(2x + 1)

f9(x) = arctg(0, 8x + 0, 2) + ln(0, 8x + 0, 2) − 1

Продолжение на следующей странице

30

Примерный набор гладких функций (продолжение)

f10(x) = e2x − 3 − cos 2x

Продолжение на следующей странице

31

Варианты заданий (продолжение)

Продолжение на следующей странице

32

Варианты заданий (продолжение)

Примечание 1. Алгоритмы вычисления интегралов должны быть адап-

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

Примечание 2. Для методов Ньютона и секущих за начальное приближение можно принять середину отрезка [0, 1]. При отсутствии быстрой сходимости этих методов (если результат не достигается за некоторое достаточно большое, заранее определенное число шагов, например, за 100 шагов) в качестве результата оставить указанное начальное приближение. В последнем случае на дисплей должно выдаваться соответствую-

щее сообщение.

Примечание 3. Производные вычислять по следующим приближен-

приняв h = 10−8.

ЗАДАНИЕ 8 ОБРАБОТКА ДЕРЕВЬЕВ

Внимательно прочитайте вариант задания, и изобразите графически какое-либо дерево, подходящее для проверки (тестирования) алгоритмов, которые требуется разработать. Сформируйте это дерево средствами языка МАТЛАБ следующими тремя способами:

33

а) в виде линейно-скобочной записи с помощью вектора класса CHAR; б) с помощью вложенных векторов класса CELL;

в) в виде списка векторов из индексов прямых потомков (на базе массива класса CELL).

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

Варианты контрольных заданий по обработке деревьев: Вариант 1

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

2.Удалить из произвольно заданного дерева все поддеревья, в которых число узлов, содержащих более 3-х пустых прямых потомков.

Вариант 2

1.Длина пути к некоторому узлу дерева, по определению, равна значению иерархического уровня данной вершины (длина пути к самому корню считается равной 1). Найти среднюю длину пути к пустым поддеревьям произвольно заданного дерева (для пустого дерева результат должен быть 0, а для дерева без пустых поддеревьев — NaN).

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

Вариант 3

1.Степенью узла будем называть число исходящих из него стрелок (не пустых поддеревьев). Найти число всех узлов произвольно заданного дерева, степень которых больше заданной (для пустого дерева результат должен быть равен 0).

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

Вариант 4

1.Длина пути к некоторому узлу дерева, по определению, равна зна-

34

чению иерархического уровня данной вершины (длина пути к самому корню считается равной 1). Найти среднюю длину пути к листьям произвольно заданного дерева (для пустого дерева результат должен быть равен NaN).

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

Вариант 5

1.Длина пути к некоторому узлу дерева, по определению, равна значению иерархического уровня данной вершины (длина пути к самому корню считается равной 1). Найти среднюю длину пути к внутренним узлам произвольно заданного дерева (для пустого дерева результат должен быть равен NaN).

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

Вариант 6

1.Найти число узлов произвольно заданного дерева с заданным значением информационного поля (для пустого дерева результат должен быть равен 0).

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

Вариант 7

1.Найти число узлов произвольно заданного дерева, находящихся на заданном иерархическом уровне (для пустого дерева результат должен быть равен 0).

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

Вариант 8

1.Найти число узлов произвольно заданного дерева, среди прямых потомков которых есть листья (для пустого дерева результат должен быть равен 0).

2.Удалить из произвольно заданного дерева все поддеревья, в кото-

35

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

Вариант 9

1.Найти число узлов произвольно заданного дерева, среди прямых потомков которых не более одного листа (для пустого дерева результат должен быть равен 0).

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

Вариант 10

1.Найти число узлов произвольно заданного дерева, все прямые потомки которых суть листья (для пустого дерева результат должен быть равен 0).

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

Вариант 11

1.Найти число узлов произвольно заданного дерева, среди прямых потомков которых не менее, чем 3 листа (для пустого дерева результат должен быть равен 0).

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

Вариант 12

1.Найти число узлов произвольно заданного дерева, среди прямых потомков которых не все суть листья (для пустого дерева результат должен быть равен 0).

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

Вариант 13

1.Найти число узлов произвольно заданного дерева, среди прямых потомков которых не более одного не являющегося листом (для пустого дерева результат должен быть равен 0).

36

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

Вариант 14

1.Найти число узлов произвольно заданного дерева, среди прямых потомков которых нет листьев (для пустого дерева результат должен быть равен 0).

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

Вариант 15

1.Найти число узлов произвольно заданного дерева, среди прямых потомков которых не менее трех не являются листьями (для пустого дерева результат должен быть равен 0).

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

Вариант 16

1.Длина пути к некоторому узлу дерева, по определению, равна значению иерархического уровня данной вершины (длина пути к самому корню считается равной 1). Найти среднюю длину пути к узлам произвольно заданного дерева, среди прямых потомков которых не менее, чем три листа (для пустого дерева результат должен быть равен NaN).

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

Вариант 17

1.Длина пути к некоторому узлу дерева, по определению, равна значению иерархического уровня данной вершины (длина пути к самому корню считается равной 1). Найти среднюю длину пути к узлам произвольно заданного дерева, среди прямых потомков которых не все суть листья (для пустого дерева результат должен быть равен NaN).

37

2. Удалить из произвольно заданного дерева все поддеревья, в которых средняя длина пути к узлам, имеющим прямыми потомками узлы, не являющиеся листьями, меньше n.

Вариант 18

1.Длина пути к некоторому узлу дерева, по определению, равна значению иерархического уровня данной вершины (длина пути к самому корню считается равной 1). Найти среднюю длину пути к узлам произвольно заданного дерева, среди прямых потомков которых не более одного не являющегося листом (для пустого дерева результат должен быть равен NaN).

2.Удалить из произвольно заданного дерева все поддеревья, в которых средняя длина пути к узлам, имеющим среди прямых потомков не более одного не являющегося листом, меньше n.

Вариант 19

1.Длина пути к некоторому узлу дерева, по определению, равна значению иерархического уровня данной вершины (длина пути к самому корню считается равной 1). Найти среднюю длину пути к узлам произвольно заданного дерева, среди прямых потомков которых нет листьев (для пустого дерева результат должен быть равен NaN).

2.Удалить из произвольно заданного дерева все поддеревья, в которых средняя длина пути к узлам, не имеющим листьев, меньше n.

Вариант 20

1.Длина пути к некоторому узлу дерева, по определению, равна значению иерархического уровня данной вершины (длина пути к самому корню считается равной 1). Найти среднюю длину пути к узлам произвольно заданного дерева, среди прямых потомков которых не менее, чем три не являющихся листьями (для пустого дерева результат должен быть равен NaN).

2.Удалить из произвольно заданного дерева все поддеревья, в которых средняя длина пути к тем узлам, среди прямых потомков которых, по крайней мере, 3 не являются листьями, меньше n.

38