Метод Золотого Сечения. Детальный разбор Исходного кода программы на Pascal

Скачать pas-файл кода в виде зашифрованного архива. Пароль в рассылке.

По условию требуется:
Вычислить экстремум функции y(x) на заданном интервале с заданной точностью ε.

Функция, как правило, задаются индивидуально по вариантам. Каждый студент-программист должен написать программу для своей функции.

Значение границ интервала, начальное значение шага и точность ввести с клавиатуры в главной программе, т.е. предоставить такую возможность пользователю. Координаты экстремума, конечное значение шага и количество разбиений вывести на экран в главной программе. Здесь стоит поэкспериментировать с разными вариантами вывода.

Решение:
т.е. главное - найти координаты (xe, ye).

Чтобы не отвлекаться в дальнейшем, даю определение:
Компилятор – это компьютерная программа, предназначенная для преобразования исходного кода в машинный код. Другими словами, компилятор из pas-файлов собирает ехе-файлы (или dcu-файлы). При этом если в тексте исходного кода он находит ошибки (участки кода не понятные ему - компилятору), то работа прекращается, а программисту рекомендуется устранить ошибку в такой-то (конкретной) строке…

Давайте посмотрим на модуль…

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

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

Третья строка: после служебного слова uses перечисляются используемые модули. В нашем случае используется всего один модуль crt. Его необходимо включить в программу, т.к. я собираюсь использовать оператор clrscr для очистки экрана. А процедура clrscr описана именно в этом модуле. Это не служебное слово. Если перечитаете список служебных слов, Вы его там не найдете….

Готовые модули – это великая вещь! Как бы ни был широко задуман язык, он все равно имеет границы. Границы языка – это служебные слова, понятные компилятору. Ну, вот не было в языке Pascal задумано команды на очистку экрана… Зато нашелся программист, который эту процедуру написал (и еще несколько других для удобства работы с цветным текстовым экраном) и сохранил их в модуле crt. И сейчас любой желающий может этими командами пользоваться, только перед этим должен подключить данный модуль через uses. И все! Компилятор, не знавший до этого слово clrscr, но, бегло просмотрев подключенный модуль crt, уже не будет возмущаться словом clrscr. Он уже знает, где описан алгоритм действий по этой команде. А больше компилятору ничего и не надо. Он честный труженик. Готов сделать все, только скажите как…

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

Четвертая строка
var norm:boolean; {флаг нормальности данных}
- это описание логической переменной, но переменная эта находится выше всех других функций и процедур в программном модуле. А это значит, что она будет видна (доступна) в них во всех. Про такие переменные говорят – «Переменная уровня модуля» чтобы подчеркнуть их отличие от локальных переменных, которые видны только в одной процедуре или функции.

Далее в модуле поочередно идут описания функции или процедур, которые будут использоваться главной программой или другими процедурами(функциями).

Итак первая из них dannFunc:

function dannFunc(x: real): real;
begin
if x<=0 then
begin
       writeln('недосустимое значение аргумента - ',x);
       norm:=false;
end
else dannFunc:= x+ln(1/x)/ln(10);
end;
 … вычисляющая значение y(x) (будет вызываться из процедуры ExtremGC) и позволяющая в будущем достаточно легко адаптировать код программы под новые функции. Именно в ней студенты забивают функцию своего варианта. Назначение ее примитивно. Получив на входе в качестве параметра значение аргумента х, функция проверяет его на доступность и либо сообщает о недоступности аргумента, либо считает и возвращает значение заданной функции.

Если бы мне требовалось изменить dannFunc для у=х2, то я бы подкорректировал ее так:

function dannFunc(x: real): real;
begin
if false then
begin
       writeln('недосустимое значение аргумента - ',x);
       norm:=false;
end
else dannFunc:= x*x;
end;

Все! Функция будет возвращать квадрат аргумента всегда, т.к. она определена на всей числовой прямой и недоступных значений аргумента для нее нет (false в условии). Но сам блок проверки из функции убирать нецелесообразно. Ведь завтра может понадобиться изменение на функцию у=25/х и тогда этот блок снова станет нужен

function dannFunc(x: real): real;
begin
if х=0 then
begin
       writeln('недосустимое значение аргумента - ',x);
       norm:=false;
end
else dannFunc:= 25/x;
end;

Следующие две процедуры

procedure a_change(zc:real; var a, b, x1, x2, y1, y2: real); {Сдвиг точки а в точку х1}
begin
a:=x1; x1:=x2; y1:=y2;
x2:=a+((b-a)/zc);
y2:=dannFunc(x2);
end;

procedure b_change(zc:real; var a, b, x1, x2, y1, y2: real); {Сдвиг точки b в точку х2}
begin
b:=x2; x2:=x1; y2:=y1;
x1:=b-((b-a)/zc);
y1:=dannFunc(x1);
end;
 ... характерны для алгоритма «Золотого сечения». Его суть: первоначально заданный интервал [a,b] делится точками х1 и х2, а затем сужается одним их двух способов: либо точка а (начало интервала) перемещается в точку х1; либо точка b (конец интервала) перемещается в точку х2. После ряда таких шагов интервал уменьшится до величины <= ε и программа остановится, т.к. заданная точность достигнута. Правда программа может остановиться и в случае обнаружения недопустимого аргумента…

Следующая процедура является ключевой для программы (не путайте с главной программой)

procedure ExtremGC(a, b, eps: real; var xe, ye, dx1: real; var nn: longint);
   {Нахождение экстремума функции на отрезке. Метод золотого сечения}
var x1,x2,zc,y1,y2 :real;
begin

nn:= 0;
zc:=(1+sqrt(5))/2; {~1.618 -константа золотого сечения}
{ writeln;writeln(zc); }{можно убрать знак комментария для проверки}


x1:=b-((b-a)/zc); x2:=a+((b-a)/zc);
y1:=dannFunc(x1); y2:=dannFunc(x2);

while ((b-a>eps) and norm) do {оптимизирован}
    begin

       if y1>=y2
       then a_change(zc, a, b, x1, x2, y1, y2)
       else b_change(zc, a, b, x1, x2, y1, y2); {поиск минимума}

       {if y1<=y2
       then a_change(zc, a, b, x1, x2, y1, y2)
       else b_change(zc, a, b, x1, x2, y1, y2); {поиск максимума для другого случая}

       inc(nn);
    end;

dx1:= abs(b-a);
xe:=(a+b)/2; ye:=dannFunc(xe);

end;

Процедура ExtremGC, вычисляющая экстремум с заданной точностью (будет вызываться из главной программы)
Параметры по значению:

  • границы интервала [a, b]
  • точность ε

Параметры по ссылке:
  • координаты (xe, ye) экстремума
  • конечное значение шага dx
  • количество разбиений n

Данная процедура получает семь параметров. Первые три параметра передаются по значению, а следующие четыре - по ссылке. Кто не знает, что это такое (по ссылке и по значению) рекомендую отыскать в интернете и изучить информацию, т.к. это одно из основных понятий программирования. Без него не куда!!!

Цикл while ((b-a>eps) and norm) do будет выполняться до тех пор, пока интервал не уменьшится до величины меньше или равной эпсилон. Уменьшение интервала (сдвиги границ) происходят в ранее рассмотренных процедурах a_change и b_change, которые вызываются из данной процедуры. Или выход из цикла произойдет, когда переменной-флагу norm будет присвоено значение false в функции dannFunc. Какое из событий наступит ранее (а второе может и не наступить), то и прервет цикл…

Суть метода (цикла): имеющийся отрезок [a,b] делится точками х1 и х2 где a<x1<x2<b в пропорциях золотого сечения. В этих точках определяется значение функции. После этого не интересующий программу отрезок отбрасывается, а оставшийся (если не достигнута заданная точность) подвергается той же обработке на следующем шаге цикла. Цикл закончится только тогда, когда рассматриваемый отрезок сузится до размеров ε. За ответ будет принята середина этого крохотного отрезка.

Если входные параметры для данного примера   a=0.1,    b=1, то
при первой итерации х1=0.4438(z2),    х2=0.6562(z3)
при второй итерации a=0.1,    b=0.6562(z3),    х1=0.3124(z1),    х2=0.4438(z2)
при третьей итерации a=0.3124(z1),    b=0.6562(z3),    х1=0.4438(z2),    х2=0.5249
…и так попеременно отбрасывая правые или левые части алгоритм неминуемо достигнет точки экстремума.
Метод золотого сечения

По окончанию цикла, остается инициализировать три параметра (переменные) по ссылке (т.к. параметр nn уже инициализирован в ходе цикла).

Все. Остается рассмотреть главную программу, которая располагается между последними в программном модуле операторами begin и end. Правда, перед этим есть еще блок описания переменных:

var
a, b, dx0, eps: real;
xe, ye, dx1: real;
n: longint;
 видимость этих переменных распространяется только на блок главной программы!
Но ведь нам надо будет, чтобы с этими данными работали другие процедуры и функции???
А выход простой – послать эти переменные как параметры в нужную функцию (процедуру).
Причем, если процедура принимает параметр по значению, то она им пользуется, но наша переменная останется неизменной.
А вот если процедура принимает параметр по ссылке, то она может вносить изменения в данную переменную.
Посмотрите еще раз процедуру ExtremGC: первые три параметра по значению, поэтому даже если внутри процедуры параметры a, b неоднократно изменялись, то на самих переменных это никак не скажется. Другое дело переменные xe, ye, dx1, n … Отправляясь в процедуру они вообще не были инициализированы (им не было присвоено значение), а после окончания ExtremGC они имеют четкие значения, которые им были присвоены в процессе отработки алгоритма.

И так, описываю строки главной программы:

begin
clrscr;        очистка экрана
norm:=true;        начальная инициализация флага, считаем, что данные нормальные
write('Ведите a, b, eps ');        приглашение пользователю, чтобы знал, что вводить
readln(a, b, eps);        чтение введенных пользователем значений в переменные
ExtremGC(a, b, eps, xe, ye, dx1, n);        вызов ключевой процедуры с отправкой в нее семи переменных

if norm then        условие для вывода результата (если интервал задан не корректно и флаг получил значение false, то вывода не будет)
writeln('Экстремум : E(',xe:6:4,', ',ye:6:4,') шаг = ', dx1:6:4, ' количество разбиений = ', n:3);
readkey        очень важная строка, заставляет окно программы ожидать нажатия любой клавиши, а не закрываться после печати результата (удалите или закомментируйте ее и будете неприятно удивлены работой программы)
end.

Давайте, поэкспериментируем с выводом…

Если вы хотите осуществить вывод в несколько строк, то можно использовать несколько операторов writeln.

if norm then
begin
       writeln('Координаты экстремума: х = ',xe:6:4,', у = ',ye:6:4);
       writeln('шаг = ',dx1:6:4);
       writeln('количество разбиений = ',n:3);
end;

Или в одном операторе использовать символы перевода строки и возврата каретки (#10,#13):

if norm then
writeln('Координаты экстремума: х = ',xe:6:4,', у = ',ye:6:4,#10,#13,
'шаг = ',dx1:6:4,#10,#13,'количество разбиений = ',n:3);

Если в вашей функции требуется найти максимум, а не минимум, то достаточно закомментировать (закрыть) блок поиска минимума и раскомментировать (открыть) блок поиска максимума. Вот так:

while ((b-a>eps) and norm) do {оптимизирован}
begin

       {if y1>=y2
       then a_change(zc, a, b, x1, x2, y1, y2)
       else b_change(zc, a, b, x1, x2, y1, y2); {поиск минимума}

       if y1<=y2
       then a_change(zc, a, b, x1, x2, y1, y2)
       else b_change(zc, a, b, x1, x2, y1, y2); {поиск максимума}
.......

Скачать pas-файл кода в виде зашифрованного архива. Пароль в рассылке.

Другие примеры на языке «Delphi»

Другие примеры на языках «Pascal», «PascalABC»


Поделиться в соц сетях:




Если на этой странице не нашлось того, что Вы так искали...

         Не расстраивайтесь, не все потеряно... Смело щелкайте...

Сайт помощи студентам по программированию и информатике

Program code