Примеры задач с индуктивными функциями

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

Пусть  = x₁ x₂ … x_n  1 x_n  и p(; t) = x₁ t ^n  1 + x₂ t ^n  2 + ... + x_n  1 t + x_n.

Рассмотрим f() = p(; t), тогда f(*x) = x₁ t ⁿ + x₂ t ^n  1 + ... + x_n  1 t² + x_n t + x =

= f() t + x. (3.1)

Из f(₁) = x₁ = f() t + x₁ следует f() = 0 для всех t.

Эти соотношения лежат в основе следующей программы вычисления значения полинома (t задано). Эту программу естественно назвать схемой Горнера.

Reset(fin); y :=0; {f()=0} while not Eof(fin) do begin Read(fin, x); y := y*t + x end {while} {y = p(; t)}

Простым и показательным примером практического использования данной вычислительной схемы является чтение натурального числа z, представленного в текстовом файле записью в позиционной системе счисления с основанием q (2  q  q_max), т. е. z = <x₁ x₂ ... x_n  1 x_n>_q , где x_i  0..(q  1) для i  1..n  и x₁  0.Очевидно, что z = x₁ q ^n  1 + x₂ q ^n  2 + ... + x_n  1 q + x_n и может быть вычислено по схеме Горнера:

const q = 3; {2  q  10} var x: Char; z: Integer; y: Word; fin: Text; begin Assign(fin, 'Number.dat'); Reset(fin); y :=0; while not Eof(fin) do begin Read(fin, x); z := Ord(x)  48; y := y*q + z end {while}; WriteLn('прочитано число = ', y) end.

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

Можно рассмотреть f₁() = p_t(; t)  как новую ф-цию и попытаться для неё решить задачу заново, а можно поступить иначе  продифференцировать по t уже полученное рекуррентное соотношение (3.1):

[f(*x)]_t = [f()]_t t + f(),

т. е. f₁(*x) = f₁() t + f(). Ф-ция f₁ неиндуктивна, и следует рассмотреть индуктивное расширение F() = (f₁() , f()): F(*x) = ( f₁() t + f(), f() t + x).

Из соотношений f₁(₁) = [x₁]_t = 0 = f₁(₀) t + f(₀) = f₁() t + 0 для всех t  R следует f₁() = 0. Тогда для вычисления F() имеем программу

Reset(fin);

y := 0; {f() = 0} y1 := 0; {f1() = 0}

while not Eof(fin) do

begin

Read(fin, x);

y1:= y1*t + y;

y := y*t + x

end {while} {y = f() & y1= f1()}

Полученную программу можно назвать схемой Горнера для вычисления значения производной многочлена.

Билет№25 Пример вычисл индук ф-ции : задача о равнинах №25

Пример 3. Вычисление максимальной длины равнины (площадки) в заданной последовательности. Пусть задана последовательность  = x₁ x₂ … x_n  1 x_n . Площадкой длины k называется отрезок (связная подпоследовательность) равных элементов, т. е. x_i = x_i + 1 = … = x_{i + k  1} (при этом либо i = 1, либо x_i 1  x_i  , а также либо x_{i + k  1} x_i + k, либо i + k  1 = n). Функция f = «длина самой длинной площадки в » неиндуктивна. Чтобы показать это, воспользуемся критерием индуктивности. Действительно, пусть

 = (1, 1),  = (2, 2),

f() = 2, f() = 2.

При x = 1 получим f(*x) = 3 и f(*x) = 2, т. е. f(*x)  f(*x) , и, следовательно, f  неиндуктивна.

Рассмотрим индуктивное расширение:

F() = ( f(), last(), конкурент()),

где last()  последний элемент последовательности, а конкурент()  длина хвостовой площадки (только площадка, заканчивающаяся последним элементом, может конкурировать с текущим рекордом f()).

Запишем рекуррентные (индуктивные) соотношения:

f(*x) = max(f(), конкурент(*x)),

 конкурент() + 1, если x = last(), конкурент(*x) = 

 1, если x  last(),

last(*x) = x.

Все эти ф-ции на пустой последовательности  можно доопределить согласованно с индуктивными соотношениями: f() = 0, конкурент() = 0, last() = 0.

Тогда получаем программу

Reset(fin);

y := 0; {f() = 0}

z := 0; {z  конкурент, z() = 0}

last :=0; {last()  любой}

while not Eof(fin) do

begin

Read(fin, x);

if   x = last  then z := z + 1

else  z := 1;

if z > y then y := z;

last := x

end {while}

Билет№26 Пример вычисл индуктив ф-ции:задача об отрезке с максимальной суммой №26

Пример 4. Вычисление максимальной суммы Эл-тов среди всех отрезков последовательности. Пусть задана последовательность  = x₁ x₂ … x_n  1 x_n . Требуется вычислить f() = «сумма элементов отрезка с максимальной суммой», где отрезок  связная подпоследовательность последовательности .

Пусть S(k, m) =  _ik..m x_i, где 1  k  m  n. Тогда f() = max(S(k, m): 1  k  m  n).Функция f – неиндуктивна. Действительно, по критерию индуктивности: пусть  = (5, 1),  = (1, 5), f() = 5, f() = 5, но при x = 1 получим f(*x) = 5 и f(*x) = 6, т. е. f(*x)  f(*x), и, следовательно, f  неиндуктивна.

Рассмотрим индуктивное расширение F() = ( f(), t()), где роль потенциального конкурента текущему рекорду f() при продолжении последовательности  играет t()  максимальная сумма среди отрезков, прилегающих к правому концу последовательности, т. е. t() = max(S(j, n): 1  j  n).

Вычисление f и t можно проводить следующим образом: f(*x) = max(f(), t(*x)),

t(*x) = max(x, x + t()),

t() = 0, f() =  .

В результате получим программу

const MinInt = 32768; {}

var  x,{ очередной элемент последовательности }

y, { y = f() }

z:Integer; { z = t() }

fin: Text; { input file}

begin ...

Reset(fin); { L(fin) =  }

y := MinInt; z := 0; { y = f(), z = t() }

{ inv: y = f(L(fin)) & z = t(L(fin)) }

{ bound: length(R(fin)) }

while not Eof(fin) do

begin

Read( fin, x );

if z > 0 then z := z + x  else z := x;

if z > y then { обновить рекорд } y := z;

end { while }…

end.

Билет№27 Кванторы существования.всеобщности и счёта,их использование при записи утверждение о массивах №27