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

Московский государственныйуниверситет им. М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиТрифонов Н.П., Пильщиков В.Н.Задания практикума на ЭВМ(1 курс)Москва2001УДК 681.325.5ББК 22.18Т67Трифонов Н.П., Пильщиков В.Н.Задания практикума на ЭВМ (1 курс). Учебное пособие, 2-е исправленное издание. —М.: МГУ, 2001. — 32 с.Издательский отдел факультета ВМК (лицензия ЛР №040777 от 23.07.96),Приводятся описания заданий практикума на ЭВМ для студентов 1 курса факультетавычислительной математики и кибернетики МГУ. Эти задания относятся к языку программирования Паскаль и языку ассемблера для персональных компьютеров.В разработке заданий принимали участие И.А Волкова, Е.В.

Зима, В.В. Игнатов,В.Н. Пильщиков, В.И. Родин, Т.В. Руденко, Н.П. Трифонов.В новом издании исправлены замеченные ошибки и неточности первого издания (1992г.), в качестве используемой версии языка Паскаль взят язык Турбо Паскаль 7.0. Приподготовке нового издания большую помощь оказала Е.А. Бордаченкова.Рецензенты:доц. Баула В.Г.доц. Корухова Л.С.Печатается по решению Редакционно-издательского совет факультета вычислительнойматематики и кибернетики МГУ им.

М.В. Ломоносова.ISBN 5-89407-102-Х© Издательский отдел факультетавычислительной математики икибернетики МГУим. М.В.Ломоносова, 2001Замечания по данной электронной версии присылайте на сmсmsu.infо@gmail.cоmМетодическое пособиеЗадание 1. ЯЗЫК ПАСКАЛЬ. ВЫЧИСЛЕНИЕ КОРНЕЙУРАВНЕНИЙ И ОПРЕДЕЛЕННЫХИНТЕГРАЛОВ1.1.

ПОСТАНОВКА ЗАДАЧИС заданной точностью ε вычислить площадь плоской фигуры, ограниченной тремя кривыми, уравнения которых y = f1(x), y = f2(x) и y = f3(x) определяются вариантом задания.При решении задачи необходимо:⎯ с некоторой точностью eps1 вычислить абсциссы точек пересечения кривых, используя предусмотренный вариантом задания метод приближенного решения уравнения F(x)=0; отрезки, где программа будет искатьточки пересечения и где применим используемый метод, определитьвручную;⎯ представить площадь заданной фигуры как алгебраическую сумму определенных интегралов и вычислить эти интегралы с некоторой точностьюeps2 по квадратурной формуле, предусмотренной вариантом задания.Величины ε1 и ε2 подобрать вручную так, чтобы гарантировалось вычисление площадифигуры с точностью ε.1.2. ВАРИАНТЫ ЗАДАНИЯВо всех вариантах ε = 0.001.А.

Уравнения кривыхy = fi(x):1)f1 = 2x + 1f2 = x5f3 = (1 − x)/32)f1 = 3(0.5/(x + 1) + 1)f2 = 2.5x − 9.5f3 = 5/x (x > 0)3)f1 = exp(−x) + 3f2 = 2x − 2f3 = 1/x4)f1 = exp(x) + 2f2 = −1/xf3 = −2(x + 1)/32x5)f1 = 0.35x − 0.95x + 2.7f2 = 3 +1f3 = 1/(x + 2)6)f1 = 0.6x + 3f2 = (x − 2)3 − 1f3 = 3/x7)f1 = ln(x)f2 = −2x + 14f3 = 1/(2 − x)+68)f1 = exp(x) + 2f2 = −2x + 8f3 = −5/x9)f1 = 3/((x − 1)2 + 1)f2 = sqrt (x + 0.5)f3 = exp(−x)10)f1 = 1 + 4/(x2 + 1)f2 = x3f3 = 2−xБ. Методы приближенного решения уравнений:1)метод деления отрезка пополам;2)метод хорд (секущих);3)метод касательных (Ньютона);1Трифонов Н.П., Пильщиков В.Н.

Практикум на ЭВМ4)комбинированный метод (хорд и касательных).В. Квадратурные формулы:1)формула прямоугольников;2)формула трапеций;3)формула Симпсона (парабол).1.3. ТРЕБОВАНИЯ К ПРОГРАММЕ1.В программе предусмотреть печать как площади заданной фигуры, так и абсциссточек пересечения кривых.2.Описать в программе процедуру root (f, g, a, b, eps1, x), вычисляющую с точностью ε1 корень x уравнения f (x) = g (x) на отрезке [a, b].

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

ЛИТЕРАТУРА[1]. Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математический анализ. Т.1 — М.:Наука, 1985.[2]. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. — М.:Наука, 1988.[3]. Епанешников А.М., Епанешников В.А. ПрограммированиеPascal 7.0 — М.: «ДИАЛОГ-МИФИ», 2000.всредеTurbo1.5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ1.Для корректного применения предложенных методов приближенного решенияуравнения F(x) = 0 (где F(x) = f (x) − g (x)) необходимо найти отрезок [a, b], на котором уравнение имеет ровно один корень. Достаточное условие для этого таково:на концах отрезка функция F(x) имеет разные знаки и на всем отрезке производная функции не меняет знак.

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

Процесс деления отрезков прекращается, когда длина очередного отрезка станетменьше требуемой точности ε; за корень уравнения можно принять любую точкуэтого отрезка.3.В остальных трех методах следует различать два случая:случай 1 — первая и вторая производные функции F(x) имеют одинаковый знак(F'(x)F"(x) > 0);случай 2 — эти производные имеют разные знаки.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 + ε): если они одного знака,то процесс продолжается, иначе на отрезке [c, c + ε] имеется корень и потомупроцесс завершается. При приближении справа надо проверять знаки F(c − ε) иF(c).В комбинированном методе одновременно применяется метод хорд и метод касательных, в связи с чем приближение к корню происходит с двух сторон. Критерийокончания — длина очередного отрезка меньше ε.4.При использовании метода хорд, метода касательных или комбинированного метода процедура root должна самостоятельно распознавать, какой из двух случаев,указанных в п.

2, имеет место при текущем обращении к ней. Это можно сделатьпроверкой следующих двух условий:— функция возрастает или убывает;— график функции расположен выше хорды, соединяющей концы графика, илиниже.Поскольку производные F'(x) и F"(x) на отрезке [a, b] не меняют знак, для проверки первого условия достаточно сравнить F(a) с 0 (при F(a) < 0 функция возрастает). Для проверки же второго условия надо сравнить в какой-то внутренней точкеотрезка значения функции и хорды; например, если взять среднюю точку (a + b)/2⎛ a + b ⎞ F (a ) + F (b )отрезка, то соотношение F ⎜означает, что график функции⎟>2⎝ 2 ⎠расположен выше хорды.

Если функция возрастает и ее график расположен нижехорды или если функция убывает и ее график расположен выше хорды, то имеетместо случай 1, иначе — случай 2.5.Квадратурные формулы для приближенного вычисления интеграла I от функцииF(x) на отрезке [a, b] имеют следующий вид (n — число разбиений отрезка [a, b]):Формула прямоугольников:I ≅ In = h(F0 + F1+...+Fn-1),где Fi = F(a + (i + 0.5)h), h = (b – a)/n3Трифонов Н.П., Пильщиков В.Н.

Практикум на ЭВМФормула трапеций:I ≅ In = h (0.5F0 + F1 + F2 + ... + Fn-1 + 0.5Fn),где Fi = F(a + ih), h = (b – a)/nФормула Симпсона (n — чётное):I ≅ In = h/3 (F0 + 4F1 + 2F2 + 4F3 + ... + 4Fn-3 + 2Fn-2 + 4Fn-1 + Fn),где Fi = F(a + ih), h = (b – a)/n6.Для обеспечения требуемой точности ε при приближенном вычислении интегралаI по квадратурной формуле нужно подобрать соответствующее число n разбиенийотрезка интегрирования. Известны формулы, выражающие n через ε, но в этиформулы входят производные подынтегральной функции, что неудобно на практике. Поэтому для достижения требуемой точности обычно используется следующий метод: берется некоторое начальное число разбиений n0 (например, 10или 20) и последовательно вычисляются значения In при n, равном 2n0, 4n0, 8n0 ит.д. Известно правило Рунге| I – In | ≅ p | In – I2n |(для формул прямоугольников и трапеций p = 1/3, для формулы Симпсонаp = 1/15).

Согласно этому правилу, когда на очередном шаге величина p |In − I2n|окажется меньше ε, в качестве приближенного значения для I можно взять In или,что лучше, I2n.7.При реализации функции integral следует учитывать, что в формулах трапеций иСимпсона в сумму I2n входят значения Fi, вычисленные ранее для суммы In, поэтому их не следует перевычислять заново.8.В процедуре 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;...4Методическое пособиеЗадание 2.

ЯЗЫК ПАСКАЛЬ.ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ.2.1. ПОСТАНОВКА ЗАДАЧИВарианты 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 — двоичное дерево поиска (в нем слева от каждой вершиныслова располагаются только те слова, что предшествуют ему по алфавиту, асправа — следующие за ним по алфавиту).5Трифонов Н.П., Пильщиков В.Н.

Практикум на ЭВМВарианты 12-18Дана символьная запись (см. ниже) многочлена (многочленов) от одной переменной X сцелыми коэффициентами. Требуется ввести этот многочлен в память ЭВМ, преобразовав во внутреннее представление (см. ниже), выполнить операцию, определяемую вариантом задания, и распечатать полученный результат.Операции над многочленами:12) вычислить значение заданного многочлена при заданном целочисленномзначении переменной X;13) проверить, имеет ли заданный многочлен хотя бы один целый корень (такими корнями могут быть только положительные и отрицательные делителисвободного члена, а при нулевом свободном члене корнем является 0);14) проверить на равенство два заданных многочлена;15) получить многочлен, являющийся производной заданного многочлена по переменной X;16) получить многочлен, являющийся суммой двух заданных многочленов;17) получить многочлен, являющийся произведением двух заданных многочленов;18) привести подобные члены в заданном многочлене, в котором могут повторяться одночлены с одними и теми же степенями X.Исходный многочлен от переменной X с целыми коэффициентами записывается какалгебраическая сумма одночленов любого из следующих видов (^ — возведение в степень):aX^k,X^k,aX,Xaгде k и a — целые числа (k ≥ 2, a ≥ 1).