[МУЗЫКА] В

качестве примера

использования цикла-до рассмотрим метод половинного деления.

Этот метод применяется,

если нам нужно найти корень уравнения f (x) = 0 на заданном отрезке [a, b].

И наш корень будет находиться с заданной точностью ε.

При этом предполагается, что на данном отрезке существует ровноодин корень.

Для того чтобы корень действительно существовал только один,

необходимо выполнение следующих условий.

Во-первых, функция должна быть монотонна на этом отрезке, то есть монотонно

возрастать либо монотонно убывать, и на этом отрезке она должна быть непрерывна.

Причём кроме этого, знаки функции на концах отрезка должны быть различными.

Что же будет, если мы рассмотрим функцию,

которая не удовлетворяет какому-нибудь из этих условий?

Например, пусть функция не является монотонной на отрезке.

Мы видим, что в данном случае у этой функции на данном отрезке не один корень,

а несколько, то есть метод неприменим.

Если же мы рассмотрим функцию, которая не является на данном отрезке непрерывной,

то тогда может возникать случай, когда корней на этом отрезке нет.

Рассмотрим, как работает данный метод.

Перед нами общая схема.

Выбирается отрезок a, b, на котором функция монотонна в данном случае,

монотонно убывает, непрерывна, и знаки функции на концах отрезка разные.

Разделим данный отрезок пополам точкой c.

Индекс около c показывает, что у нас первый шаг,

то есть мы разделили первый раз наш отрезок, и теперь у нас есть точка c1.

Мы видим, что у нас получилось два отрезка.

На одном из них знаки функции в концах одинаковые, а на другом — разные.

Для дальнейшей работы нам с вами нужен тот отрезок, на котором знаки функции

в концах разные, то есть мы переносим точку b в середину отрезка.

И теперь мы с вами получаем новый отрезок.

Этот новый отрезок мы снова должны разделить пополам.

Получаем точку c2, и теперь мы снова должны выбрать тот отрезок,

на котором знаки функции на концах различны.

В данном случае мы должны взять точку a и перенести её в середину

нашего нового отрезка.

И дальше мы с вами продолжаем делить отрезок пополам и переносить одну из

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

Как только мы увидим, что значение функции в точке a не превышает ε,

мы будем считать, что мы нашли корень с точностью ε.

Теперь рассмотрим постановку задачи.

В постановке задачи, напоминаю,

мы с вами должны указать какие у нас исходные данные.

А исходные данные у нас — это a, b и ε.

Все они вещественного типа.

Результатом будет являться х также вещественного типа — это наш корень.

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

которые в данной задаче следующие.

Во-первых, a должно быть строго меньше b.

Во-вторых, ε обязательно должно быть положительным.

И в-третьих, третье условие показывает, что знаки функции на концах различны, то

есть произведение значений функции в точке a и в точке b будет отрицательным числом.

Связью в данном случае является формула f(х) =

0 с точностью ε, и далее мы говорим, что мы будем считать,

что наш корень располагается в точке a, то есть в левом конце отрезка.

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

То есть алгоритм мы запишем просто для некоторой функции f(х),

а когда станем писать программу, выберем некоторую функцию.

Итак, начинается, как всегда, наш алгоритм со слова «алг»,

которое подчёркивается, и затем следует название алгоритма.

Дальше ключевое слово «нач» — начало,

и название метода — «метод половинного деления».

Затем мы с вами должны ввести исходные данные.

Здесь мы будем вводить исходные данные, проверяя, что эти данные допустимы.

Начнём с того, что введём границы отрезка.

Мы должны ввести границы отрезка и проверить выполнение двух ограничений.

Во-первых, то, что у нас левая граница меньше,

чем правая, а во-вторых, то, что знаки функции в концах различны.

Мы сначала проверяем, если у нас a будет больше или равно b,

то это неправильные данные, мы выводим для пользователя сообщение в чём он ошибся.

Затем мы проверяем условие того, что знаки функции на концах отрезка различны.

Если это не так, то выводим другое сообщение, и наш ввод будет

повторяться до тех пор, пока не выполнятся все ограничения на a и b,

которые мы указали в пункте «при» в постановке задачи.

Затем мы должны ввести точность ε.

ε у нас должно быть положительным, и здесь мы тоже используем цикл с постусловием.

Мы вводим ε, а потом проверяем.

Если наш ε будет числом отрицательным или равным нулю,

то тогда у нас весь ввод, включая вывод сообщения, будет повторяться.

Таким образом, мы с вами получаем исходные данные правильные,

то есть удовлетворяющие пункту «при» в постановке задачи.

Затем рассмотрим собственно цикл, который решает задачу.

Это также цикл с постусловием.

Первое присваивание вычисляет координаты точки середины отрезка.

Затем мы проверяем,

какую из половин мы будем использовать для дальнейших вычислений.

Если произведение значений в точке a и в точке c отрицательное,

то тогда, следовательно, мы переносим границу b в середину отрезка.

В противном случае в середину отрезка переносится граница a,

и наши действия будут повторяться до тех пор,

пока у нас с вами в точке a значение функции не превысит ε.

И тогда корнем будет являться как раз вот эта точка a.

Теперь посмотрим, как данный алгоритм кодируется на языке Pascal.

В качестве примера я рассмотрю функцию cosx − х = 0.

Начинаем с того, что объявляем переменные.

Здесь наши переменные a, b — границы отрезка, c — его середина, и ε — точность.

Все они вещественного типа, то есть могут иметь дробную часть.

Затем я вывожу сообщение о том, какую задачу я решаю.

Я применяю метод половинного деления, и далее начинается ввод данных.

Первый цикл вводит границы отрезка, и для них проверяются два условия.

Первое условие — то, что у нас левая граница меньше правой,

а второе условие — то, что знаки функции на концах различны.

Если какое-нибудь из этих условий нарушается, мы выводим соответствующее

сообщение, и наш цикл repeat until будет повторяться ещё раз,

пока не будут выполнены оба ограничения на наши исходные данные.

Затем мы вводим точность ε и проверяем также, что она правильная.

Если точность у нас с вами отрицательная или равна нулю, то будет повторно

выведено сообщение в виде точности ε и заново введены исходные данные.

Теперь начинаем решать задачу.

Здесь снова применяем цикл с постусловием,

который будет выполнять следующие действия.

Сначала вычисляем точку, середину отрезка, координаты этой точки c.

Затем проверяем, какую из границ отрезка нужно переносить в середину.

Если у нас произведение значений в точке a и в точке c отрицательное, значит,

это нужный нам отрезок, и мы переносим точку b.

В противном случае переносим точку a и продолжаем наше действие до тех пор,

пока модуль значения функции в точке a не станет меньше или равным ε.

Как только мы достигли выполнения этого условия,

мы завершаем наш цикл и выводим значение корня.

Обращаю ваше внимание ещё раз,

что здесь мы используем несколько циклов с постусловием,

и в первом цикле и, например, в третьем у нас действий много.

Но поскольку repeat и until точно так же, как Begin и end,

являются операторными скобками, мы с вами,

даже несмотря на то, что много действий внутри циклов, begin и end не используем.

repeat и until — это тоже операторные скобки.

Рассмотрим, как работает программа,

реализующая на языке Pascal метод половинного деления.

В качестве примера у нас выбрана функция cosx − x = 0.

Запустим нашу программу и попробуем ввести исходные данные.

Например, возьмём границы отрезка a, b от 1 до 2.

И мы видим, что для данного отрезка не

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

Попробуем выбрать другой отрезок, допустим, от 0 до 1.

Этот отрезок нам подходит — здесь знаки функции на концах разные.

Теперь попробуем ввести точность ε.

Точность ε у нас должна быть обязательно положительной.

Если я введу отрицательное число, то точность будет спрашиваться заново.

Выберу, допустим, 0,01,

и на нашем отрезке найден корень уравнения.

Итак, на примере этой программы мы с вами видим,

что при вводе недопустимых исходных данных, то есть если у нас

неверные границы отрезка либо неверная точность,

то данные будут переспрашиваться заново.

Посмотрим ещё раз.

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

Допустим, от 7 до 3.

Программа сообщает о том, что у нас неверные данные,

то есть либо нет корня, либо несколько корней.

Если я выбираю отрезок, на котором корня нет,

потому что знаки функции на концах одинаковые,

допустим, от 10 до 20, то появляется сообщение о том,

что нет корня или их, корней, несколько.

Если я выберу правильные границы отрезка, то ввод продолжается.

Далее я задаю точность.

Допустим, я возьму более высокую точность,

чем в первый раз, и получаю корень,

который вычислен с этой повышенной точностью.

[МУЗЫКА]

Пример использования цикла-до: метод половинного деления

Алгоритмизация вычислений (Algorithmic computation)

与讲师见面