Н.П. Трифонов, В.Н. Пильщиков - Практикум на ЭВМ

ЗАДАНИЕ 1. ЯЗЫК ПАСКАЛЬ.

ВЫЧИСЛЕНИЕ КОРНЕЙ УРАВНЕНИЙ И ОПРЕДЕЛЕННЫХ ИНТЕГРАЛОВ

ПОСТАНОВКА ЗАДАЧИ

С заданной точностью eps вычислить площадь плоской фигуры, ограниченной тремя кривыми, уравнения которых y=f1(x), y=f2(x) и y=f3(x) определяются вариантом задания.

При решении задачи необходимо:

- с некоторой точностью eps1 вычислить абсциссы точек пересечения кривых, используя предусмотренный вариантом задания метод приближенного решения уравнения F(x)=0; отрезки, где программа будет искать точки пересечения и где применим используемый метод, определить вручную;

- представить площадь заданной фигуры как алгебраическую сумму определенных интегралов и вычислить эти интегралы с некоторой точностью eps2 по квадратурной формуле, предусмотренной вариантом задания.

Величины eps1 и eps2 подобрать вручную так, чтобы гарантировалось вычисле-ние площади фигуры с точностью eps.

ВАРИАНТЫ ЗАДАНИЯ

Во всех вариантах eps=0.001.

А. Уравнения кривых y=f_i(x):

1) f1=2^x+1 f2=x⁵ f3=(1-x)/3

2) f1=3(0.5/(x+1)+1) f2=2.5x-9.5 f3=5/x (x>0)

3) f1=exp(-x)+3 f2=2x-2 f3=1/x

4) f1=exp(x)+2 f2=-1/x f3=-2(x+1)/3

5) f1=0.35x²-0.95x+2.7 f2=3^x+1 f3=1/(x+2)

6) f1=0.6x+3 f2=(x-2)³-1 f3=3/x

7) f1=ln(x) f2=-2x+14 f3=1/(2-x)+6

8) f1=exp(x)+2 f2=-2x+8 f3=-5/x

9) f1=3/((x-1)²+1) f2=sqrt(x+0.5) f3=exp(-x)

10) f1=1+4/(x²+1) f2=x³ f3=2^-x

Б. Методы приближенного решения уравнений:

1) метод деления отрезка пополам;

2) метод хорд (секущих);

3) метод касательных (Ньютона);

4) комбинированный метод (хорд и касательных).

В. Квадратурные формулы:

1) формула прямоугольников;

2) формула трапеций;

3) формула Симпсона (парабол).

ТРЕБОВАНИЯ К ПРОГРАММЕ

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

2. Описать в программе процедуру root(f,g,a,b,eps,x), вычисляющую с точностью eps корень x уравнения f(x)=g(x) на отрезке [a,b]. (Если используется метод касательных или комбинированный метод, то у root должны быть еще параметры f1 и g1 - производные функций f и g.)

3. Описать в программе функцию integral(f,a,b,eps), вычисляющую с точностью eps величину определенного интеграла от функции f(x) на отрезке [a,b].

4. Процедуру root и функцию integral следует предварительно протестировать.

ЛИТЕРАТУРА

1. Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математический анализ. Т. 1 - М.: Наука, 1985.

2. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. - М.: Наука, 1988.

3. Епанешников А.М., Епанешников В.А. Программирование в среде Turbo Pascal 7.0 - М.: "ДИАЛОГ-МИФИ", 2000.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

1. Для корректного применения предложенных методов приближенного решения уравнения F(x)=0 (где F(x)=f(x)-g(x)) необходимо найти отрезок [a,b], на котором уравнение имеет ровно один корень. Достаточное условие для этого таково: на концах отрезка функция F(x) имеет разные знаки и на всем отрезке производная функции не меняет знак. Кроме того, для методов хорд и касательных, а также комбинированного метода обязательно требуется, чтобы на данном отрезке первая и вторая производные функции не меняли свой знак (не обращались в ноль).

2. В методе деления отрезка пополам определяется средняя точка c отрезка [a,b] и из двух отрезков [a,c] и [c,b] выбирается тот, на концах которого функция F(x) имеет разные знаки. К выбранному отрезку применяется та же процедура. Процесс деления отрезков прекращается, когда длина очередного отрезка станет меньше требуемой точности eps; за корень уравнения можно принять любую точку этого отрезка.

В остальных трех методах следует различать два случая:

случай 1 - первая и вторая производные функции F(x) имеют одинаковый знак (F'(x)F"(x)>0);

случай 2 - эти производные имеют разные знаки.

В методе хорд концы (a,F(a)) и (b,F(b)) кривой y=F(x) соединяются прямой линией и определяется точка пересечения этой линии с осью абсцисс:

c = (aF(b) - bF(a)) / (F(b) - F(a)).

Далее выбирается отрезок [c,b] в случае 1 или отрезок [a,c] в случае 2 и к нему применяется та же процедура. Тем самым происходит постепенное приближение к искомому корню слева (в случае 1) или справа (в случае 2).

В методе касательных проводится касательная к кривой y=F(x) в точке (b,F(b)) в случае 1 или в точке (a,F(a)) в случае 2 и определяется точка c пересечения этой касательной с осью абсцисс:

c=d-F(d)/F'(d),

где d=b в случае 1 и d=a в случае 2. Далее проводится касательная к кривой в точке (c,F(c)) и процедура повторяется. Тем самым происходит приближение к искомому корню справа (в случае 1) или слева (в случае 2).

В методах хорд и касательных можно использовать следующий критерий завершения процесса приближения к корню. Если приближение «идет» слева, то на очередном шаге надо сравнить величины F(c) и F(c+eps): если они одного знака, то процесс продолжается, иначе на отрезке [c,c+eps] имеется корень и потому процесс завершается. При приближении справа надо проверять знаки F(c-eps) и F(c).

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

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

- функция возрастает или убывает;

- график функции расположен выше хорды, соединяющей концы графика, или ниже.

Поскольку производные F'(x) и F"(x) на отрезке [a,b] не меняют знак, для проверки первого условия достаточно сравнить F(a) с 0 (при F(a)<0 функция возрастает). Для проверки же второго условия надо сравнить в какой-то внутренней точке отрезка значения функции и хорды; например, если взять среднюю точку (a+b)/2 отрезка, то соотношение F((a+b)/2) > (F(a)+F(b))/2 означает, что график функции расположен выше хорды. Если функция возрастает и ее график расположен ниже хорды или если функция убывает и ее график расположен выше хорды, то имеет место случай 1, иначе – случай 2.

4. Квадратурные формулы для приближенного вычисления интеграла I от функции F(x) на отрезке [a,b] имеют следующий вид (n - число разбиений отрезка [a,b]):

Формула прямоугольников:

I  I_n = h(F₀+F₁+...+F_n-1), где F_i = F(a+(i+0.5)h), h=(b-a)/n

Формула трапеций:

I  I_n = h(0.5F₀+F₁+F₂+...+F_n-1+0.5F_n), где F_i = F(a+ih), h=(b-a)/n

Формула Симпсона (n - четное):

I  I_n = h/3*(F₀+4F₁+2F₂+4F₃+...+4F_n-3+2F_n-2+4F_n-1+F_n), где F_i = F(a+ih), h=(b-a)/n

5. Для обеспечения требуемой точности eps при приближенном вычислении интеграла I по квадратурной формуле нужно подобрать соответствующее число n разбиений отрезка интегрирования. Известны формулы, выражающие n через eps, но в эти формулы входят производные подынтегральной функции, что неудобно на прак-тике. Поэтому для достижения требуемой точности обычно используется следующий метод: берется некоторое начальное число разбиений n₀ (например, 10 или 20) и последовательно вычисляются значения I_n при n, равном 2n₀, 4n₀, 8n₀ и т.д. Известно правило Рунге

| I - I_n |  p | I_n - I_2n |

(для формул прямоугольников и трапеций p=1/3, для формулы Симпсона p=1/15). Согласно этому правилу, когда на очередном шаге величина p|I_n-I_2n| окажется меньше eps, в качестве приближенного значения для I можно взять I_n или, что лучше, I_2n.

6. При реализации функции integral следует учитывать, что в формулах трапеций и Симпсона в сумму I_2n входят значения F_i, вычисленные ранее для суммы I_n, поэтому их не следует перевычислять заново.

7. В процедуре root и функции integral используются параметры-функции (f, g и др.). В языке Турбо Паскаль такие параметры описываются следующим образом.

В разделе типов необходимо описать т.н. функциональный тип:

type TF = function (x:real): real;

(вместо TP и x можно использовать любые другие имена), в который автоматически включаются все описанные в программе вещественные функции от одного веществен-ного аргумента, а затем имя данного типа нужно указать в спецификации формального параметра-функции, например:

procedure root (f, g: TF; a, b, eps1: real; var x: real);

При обращении же к процедуре root или функции integral указываются, как обычно, имена фактических функций (не стандартных!), например:

root(f1, f2, -0.1, 3.5, 0.0001, x12);

Что касается самих фактических функций (f1, f2 и др.), то перед их описанием необходимо разместить директиву {$F+} транслятору:

{$F+}

function f1 (x:real): real; begin f1:=ln(x) end;

function f2 (x:real): real; begin f2:=2*x+14 end;

. . .

ЗАДАНИЕ 2. ЯЗЫК ПАСКАЛЬ.

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ.

ПОСТАНОВКА ЗАДАЧИ

Варианты 1-11

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

Требуется ввести эту последовательность слов в память ЭВМ, преобразовав ее во внутреннее представление (см. ниже), а затем распечатать в алфавитном порядке:

1) все слова последовательности;

2) все слова с указанием для каждого из них его порядкового номера в исходной последовательности;

3) все различные слова с указанием для каждого из них числа его вхождений в исходную последовательность;

4) все различные слова с указанием для каждого из них порядкового номера его первого вхождения в исходную последовательность;

5) сначала все однобуквенные слова, затем все двухбуквенные слова и т.д.;

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

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

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

9) та же задача, что и в варианте 1;

10) та же задача, что и в варианте 3;

11) та же задача, что и в варианте 4.

В качестве внутреннего представления последовательности слов использовать:

в вариантах 1-4 - однонаправленный список из слов, упорядоченных по алфавиту;

в вариантах 5-8 - массив из 6 списков, в k-ом из которых хранятся k-буквенные слова, упорядоченные по алфавиту;

в вариантах 9-11 - двоичное дерево поиска (в нем слева от каждой вершины-слова располагаются только те слова, что предшествуют ему по алфавиту, а справа - следующие за ним по алфавиту).

Варианты 12-18

Дана символьная запись (см. ниже) многочлена (многочленов) от одной переменной X с целыми коэффициентами. Требуется ввести этот многочлен в память ЭВМ, преобразовав во внутреннее представление (см. ниже), выполнить операцию, определяемую вариантом задания, и распечатать полученный результат.

Операции над многочленами:

12) вычислить значение заданного многочлена при заданном целочисленном значении переменной X;

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

14) проверить на равенство два заданных многочлена;

15) получить многочлен, являющийся производной заданного многочлена по переменной X;

16) получить многочлен, являющийся суммой двух заданных многочленов;