Книга "Программирование в теоремах и задачах"

Краткое описание/вступление:

ниренко).

     Пусть M - некоторое множество. Функция f, аргументами кото-
рой являются последовательности элементов множества M, а  значе-
ниями - элементы некоторого множества N, называется индуктивной,
если  ее значение на последовательности x[1]..x[n] можно восста-
новить по ее значению на последовательности  x[1]..x[n-1]  и  по
x[n],  т.  е.  если  существует  функция F из N*M (множество пар
, где n - элемент множества N, а m - элемент множества M) в
N, для которой

      f() = F (f (), x[n]).

     Схема алгоритма вычисления индуктивной функции:

  k := 0; f := f0;
  {инвариант: f - значение функции на }
  while  k<> n do begin
  | k := k + 1;
  | f := F (f, x[k]);
  end;

     Здесь f0 - значение функции  на  пустой  последовательности
(последовательности  длины  0). Если функция f определена только
на непустых последовательностях, то первая строка заменяется  на
"k := 1; f := f ();".

     Индуктивные расширения.

     Если функция f не является индуктивной, полезно  искать  ее
индуктивное  расширение  - такую индуктивную функцию g, значения
которой определяют значения f (это значит, что существует  такая
функция  t,  что  f  () = t (g ()) при
всех ). Можно доказать, что среди всех  индуктивных
расширений  существует  минимальное  расширение F (минимальность
означает, что для любого индуктивного расширения  g  значения  F
определяются значениями g).

     1.3.1.  Указать  индуктивные  расширения   для   следующих
функций:
   а)  среднее  арифметическое  последовательности вещественных
чисел;
   б) число элементов последовательности целых чисел, равных ее
максимальному элементу;
   в)  второй по величине элемент последовательности целых чисел
(тот, который будет вторым, если переставить члены в неубывающем
порядке);
   г) максимальное число идущих подряд одинаковых элементов;
   д) максимальная длина монотонного (не