Отправляет email-рассылки с помощью сервиса Sendsay

Всё о работе в Интернет

Подписаться Бесплатная «Серебряная» новостная рассылка Подписчиков 7.350 RSS
←   Ноябрь 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней 1 выпусков (1 раз в 2 месяца)


Сайт рассылки: http://bestinvestblog.com
Открыта: 10-02-2009

Автор
bestinvestblog

Статистика

7.350 подписчиков
0 за неделю
←   Все выпуски   →

Занятие 51. Подпрограмма поиска наименьшего и наибольшего значений функции.


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

Один программист говорит другому:

“Вот представь, что у тебя есть 1000 рублей...”.

А тот возражает: “Нет, лучше для круглого счёта пусть у меня будет 1024...”.

НАИМЕНЬШЕЕ ЗНАЧЕНИЕ ФУНКЦИИ

Пусть на отрезке [a, b] задана непрерывная функция f (x). Если этот отрезок разбить на N  равных участков, шириной h = (b – a) / N каждый, то по оси x образуется N + 1 точка с координатами, равными a, a + h, a + 2  h, a + 2  h, ..., b – h, b. 

Задача составляемого нами алгоритма состоит в том, чтобы среди всех N + 1 значений заданной функции f (x), вычисленных в точках с указанными координатами, выбрать наименьшее и указать для него соответствующее значение координаты x.

Процесс поиска наименьшего значения функции среди имеющихся построен по принципу “предположение + проверка”. Сформулируем этот принцип в общем виде.

Пусть среди определённой совокупности величин требуется отыскать одну, обладающую заданной количественной характеристикой. Тогда поступим следующим образом. Сначала из данной совокупности выберем произвольную величину, и в отношении неё выдвинем предположение, что именно она и является искомой. Далее поочерёдно просматриваем все остальные величины из этой совокупности. При этом для каждой из них выполняем проверку, не является ли её количественная характеристика в большей степени соответствующей условию задачи, нежели у той, которая была зафиксирована при формулировании предположения. По результатам каждой очередной проверки корректируем предыдущее предположение, если в этом возникает необходимость.

Задача C.1.9. “Наименьшее значение функции”. Непрерывная функция f (x) задана на отрезке [a, b], который разбит на N равных частей. Построить подпрограмму определения значения аргумента x, при котором достигается наименьшее из значений функции, вычисленных в точках разбиения.

Function Minimum_Function(a,b:Real; N:Integer; f:TFunction): Real;
   Var h,min,x,y: Real; i: Integer;
Begin
   h := (b-a)/N; x := a; min := f(a);
   For i:=1 To N Do
      Begin a := a+h; y:=f(a);
            If y<min Then Begin x:=a; min:=y End End;
   Minimum_Function := x
End;

В подпрограмме C.1.9 (функция Minimum_Function) принцип “предположение + проверка” интерпретируется следующим образом.

Вычисляем шаг изменения аргумента h = (b – a) / N.

Предполагаем, что наименьшее значение функции достигается в самой первой точке отрезка [a, b]. Фиксируем это предположение с помощью вспомогательных переменных min и x, которые должны быть равны соответственно наименьшему значению функции и аргументу, при котором оно достигается. Таким образом, x = a, min = f (a).

Проверяем это предположение для следующего значения функции. Для этого вычисляем новое значение аргумента a, увеличив предыдущее на величину шага h. Вычисляем также соответствующее значение функции y = f (a). Сравниваем значение переменной y со значением min и, если значение y оказалось меньшим значения min, то корректируем предыдущее предположение, положив x равным новому значению аргумента, а min – новому наименьшему значению функции.

Поскольку общее количество точек N + 1, и первая из них была использована в первоначальном предположении, то вышеупомянутую проверку выполняем N раз для всех остальных точек. Для этого в подпрограмме C.1.9 применяем оператор цикла с параметром i, изменяющимся от 1 до N.

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

После завершения цикла, когда оказываются проверенными все точки, значение функции Minimum_Function полагаем равным значению аргумента x, для которого достигается наименьшее из значений функции, вычисленных в точках разбиения отрезка [a, b].

Таким образом, на любом шаге цикла переменные x и min всегда соответствуют наименьшему значению функции из числа уже просмотренных. Следовательно, после просмотра и проверки всех значений мы получаем окончательное решение задачи.

Другие особенности подпрограммы C.1.9 таковы.

-       Значения, наименьшее из которых отыскивается, вычисляются посредством обращение к некоторой функции f (x), указанной в качестве формального параметра подпрограммы. Эта функция имеет нестандартный процедурный тип TFunction, который предварительно должен быть определён в разделе типов программы следующим образом: Type TFunction = Function ( x: Real ): Real.

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

-       Значение аргумента, при котором достигается наибольшее значение функции, может быть найдено при помощи аналогичной подпрограммы, в которой символ “ < ” заменён символом “ > ”. 

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

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

-       Концы отрезка [a, b] могут быть указаны при обращении к процедуре в любом порядке. При этом изменяется только последовательность просмотра значений функции.

Зная значение аргумента x, при котором достигается наименьшее значение функции, легко получить и само наименьшее значение. Для этого достаточно обратиться к функции f (x), например, следующим образом: f(Minimum_Function(a,b,N,f)).

Завершая обсуждение подпрограммы, хотелось бы предостеречь от типичного недочёта. Желая сэкономить на количестве вспомогательных переменных, часто пишут так:

For i:=1 To N Do
   Begin a := a+h; If f(a)<min Then Begin x:=a; min:=f(a) End End;

Серьёзным недостатком такой записи является то, что в одном и том же операторе ветвления обращение к функции f (x) осуществляется дважды. Это снижает эффективность подпрограммы.

Протестируем нашу подпрограмму с помощью таблицы исполнения.

Дано: N = 4, a = 0, b = 4, f (x) = (x – 2)2 + 1.

Результат: Minimum_Function = 2, наименьшее значение f (x) = 1.

h

a

f (a)

y

y < min

x

min

i

i <= N

1

0

 

 

 

0

 

 

 

 

 

5

 

 

 

5

1

True

 

1

2

2

True

1

2

2

True

 

2

1

1

True

2

1

3

True

 

3

2

2

False

 

 

4

True

 

4

5

5

False

 

 

5

False

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

В заключение приведём полный текст прораммы C.1.9.

{$B+,D+,E+,F+,I+,L+,N+,Q+,R+,X-}
Program C_01_09;
   Type
      TFunction = Function ( x: Real ): Real;
   Function f (x: Real): Real;
   Begin
      f := Sqr(x-2)+1
   End;
   Function Minimum_Function ( a,b: Real; N: Integer; f: TFunction ): Real;
      Var h,min,x,y: Real; i: Integer;
   Begin
      h := (b-a)/N; x := a; min := f(a);
      For i:=1 To N Do
         Begin a := a+h; y:=f(a);
               If y<min Then Begin x:=a; min:=y End End;
      Minimum_Function := x
   End;
   Var a,b: Real; N: Integer;
Begin
   Write('Введите координаты концов отрезка: a,b = ');
   ReadLn(a,b);
   Repeat
      Write('Введите количество участков разбиения: N = ');
      ReadLn(N)
   Until N>0;
   WriteLn('Наименьшее значение достигается при x = ',Minimum_Function(a,b,N,f):0:3);
   ReadLn
End.

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

{$B+,D+,E+,I+,L+,N+,Q+,R+,X–}
Program C_01_09;
   Type
      TFunction = Function (x: Real): Real;
   Function f1 (x: Real): Real; Far;
   Begin
      f1 := Sqr(x–2)–2
   End;
   Function f2 (x: Real): Real; Far;
   Begin
      f2 := –f1(x)

   End;

   Function Minimum_Function ( a,b: Real; N: Integer; f: TFunction ): Real;
      Var h,min,x,y: Real; i: Integer;
   Begin
      h := (b-a)/N; x := a; min := f(a);
      For i:=1 To N Do
         Begin a := a+h; y:=f(a);
               If y<min Then Begin x:=a; min:=y End End;
      Minimum_Function := x
   End;
   Var a, b: Real; N: Integer;
Begin
   Write(’Введите координаты концов отрезка: a, b = ’ );
   ReadLn(a, b);
   Repeat
      Write(’Введите количество участков разбиения: N = ’);
      ReadLn(N)
   Until N > 0;
   WriteLn('Наименьшее значение достигается при x = ',Minimum_Function(a,b,N,f1):0:3);
   WriteLn('Наибольшее значение достигается при x = ',Minimum_Function(a,b,N,f2):0:3);
   ReadLn
End.

В программе представлены описания двух функций f1(x:Real):Real и f2(x:Real):Real, тип которых полностью соответствует типу TFunction. Поэтому обе они могут использовать в качестве фактических параметров обращения к функции Minimum_Function. Для каждой из них с помощью директивы Far установлена дальняя модель памяти.

В качестве значений функции f1 рассматриваются значения выражения (x – 2)2 – 2. Таким образом, функция f1 представляет собой параболу, симметричную относительно вертикали x = 2, и с ветвями, направленными вверх. Нетрудно убедиться, что наименьшее значение этой функции на отрезке [–5, 5] достигается при x = 2 и равно –2. На этом же отрезке наибольшее значение функции достигается при x = –5 и равно 47.

В качестве функции f2 рассматривается функция, противоположная по знаку функции f1. Как указывалось при обсуждении функция Minimum_Function, это позволяет с её помощью найти значение аргумента, при котором достигается наибольшее значение той же функции f1.

Уважаемые подписчики! При необходимости задать вопрос, проконсультироваться, уточнить или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru. При этом настоятельно рекомендую пользоваться браузером Internet Explorer.

С уважением, Александр.

 
В избранное