1.3. Индуктивные функции (по А.Г.Кушниренко)

  •  
    •  
      •  
        • (а) среднее арифметическое последовательности вещественных чисел;
        • (б) число элементов последовательности целых чисел, равных ее максимальному элементу;
        • (в) второй по величине элемент последовательности целых чисел (тот, который будет вторым, если переставить члены в неубывающем порядке);
        • (г) максимальное число идущих подряд одинаковых элементов;
        • (д) максимальная длина монотонного (неубывающего или невозрастающего) участка из идущих подряд элементов в последовательности целых чисел;
        • (е) число групп из единиц, разделенных нулями (в последовательности нулей и единиц).
      •  
        • (а) <сумма всех членов последовательности; длина>;
        • (б) <число элементов, равных максимальному; значение максимального>;
        • (в) <наибольший элемент последовательности; второй по величине элемент>;
        • (г) <максимальное число идущих подряд одинаковых элементов; число идущих подряд одинаковых элементов в конце последовательности; последний элемент последовательности>;
        • (д) <максимальная длина монотонного участка; максимальная длина неубывающего участка в конце последовательности; максимальная длина невозрастающего участка в конце последовательности; последний член последовательности>;
        • (е) <число групп из единиц, последний член>.
    • Пусть 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 определена только на непустых последовательностях, то первая строка заменяется на "<x[1]>k := 1; f := f ();"<x[1]...x[n]><x[1]...x[n]><x[1]...x[n]>

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

      1.3.1. Указать индуктивные расширения для следующих функций:

      Решение. 1.3.2. (Сообщил Д.Варсонофьев.) Даны две последовательности x[1]..x[n] и y[1]..y[k] целых чисел. Выяснить, является ли вторая последовательность подпоследовательностью первой, т. е. можно ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. Число действий порядка n+k.

      Решение. (вариант 1) Будем сводить задачу к задаче меньшего размера.
      n1:=n;
      k1:=k;
      {инвариант: искомый ответ <=> возможность из x[1]..x[n1] получить
      y[1]..y[k1] }
      while (n1 > 0) and (k1 > 0) do begin
      | if x[n1] = y[k1] then begin
      | | n1 := n1 - 1;
      | | k1 := k1 - 1;
      | end else begin
      | | n1 := n1 - 1;
      | end;
      end;
      {n1 = 0 или k1 = 0; если k1 = 0, то ответ - да, если k1<>0
      (и n1 = 0), то ответ - нет}
      answer := (k1 = 0);

      Мы использовали то, что если x[n1] = y[k1] и y[1]..y[k1] - подпоследовательность x[1]..x[n1], то y[1]..y[k1-1] - подпоследовательность x[1]..x[n1-1].

      (вариант 2) Функция x[1]..x[n1] |-> (максимальное k1, для которого y[1]..y[k1] есть подпоследовательность x[1]..x[n1]) индуктивна.

      1.3.3. Даны две последовательности x[1]..x[n] и y[1]..y[k] целых чисел. Найти максимальную длину последовательности, являющейся подпоследовательностью обеих последовательностей. Количество операций порядка n*k.

      Решение (сообщено М.Н.Вайнцвайгом, А.М.Диментманом). Обозначим через f(n1,k1) максимальную длину общей подпоследовательности последовательностей x[1]..x[n1] и y[1]..y[k1]. Тогда
      x[n1] <> y[k1] => f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1));
      x[n1] = y[k1] => f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1),
      f(n1-1,k1-1)+1 );

      (Поскольку f(n1-1,k1-1)+1 ><f(n1,0), ..., f(n1,k)>= f(n1,k1-1), f(n1-1,k1), во втором случае максимум трех чисел можно заменить на третье из них.)

      Поэтому можно заполнять таблицу значений функции f, имеющую размер n*k. Можно обойтись и памятью порядка k (или n), если индуктивно (по n1) выписать (как функция от n1 этот набор индуктивен).

      1.3.4. (из книги Д.Гриса) Дана последовательность целых чисел x[1],..., x[n]. Найти максимальную длину ее возрастающей подпоследовательности (число действий порядка n*log(n)).

      Решение. Искомая функция не индуктивна, но имеет следующее индуктивное расширение: в него входят помимо максимальной длины возрастающей подпоследовательности (обозначим ее k) также и числа u[1],...,u[k], где u[i] = (минимальный из последних членов возрастающих подпоследовательностей длины i). Очевидно, u[1] <= ... <= u[k]. При добавлении нового члена x значения u и k корректируются.
      n1 := 1; k := 1; u[1] := x[1];
      {инвариант: k и u соответствуют данному выше описанию}
      while n1 <> n do begin
      | n1 := n1 + 1;
      | ...
      | {i - наибольшее из тех чисел отрезка 1..k, для кото|
      рых u[i] < x[n1]; если таких нет, то i=0 }
      | if i = k then begin
      | | k := k + 1;
      | | u[k+1] := x[n1];
      | end else begin {i < k, u[i] < x[n1] <= u[i+1] }
      | | u[i+1] := x[n1];
      | end;
      end;

      Фрагмент ... использует идею двоичного поиска; в инварианте условно полагаем u[0] равным минус бесконечности, а u[k+1] - плюс бесконечности; наша цель: u[i] < x[n1] <= u[i+1].
      i:=0; j:=k+1;
      {u[i] < x[n1] <= u[j], j > i}
      while (j - i) <> 1 do begin
      | s := i + (j-i) div 2; {i < s < j}
      | if x[n1] <= u[s] then begin
      | | j := s;
      | end else begin {u[s] < x[n1]}
      | | i := s;
      | end;
      end;
      {u[i] < x[n1] <= u[j], j-i = 1}

      Замечание. Более простое (но не минимальное) индуктивное расширение получится, если для каждого i хранить максимальную длину возрастающей подпоследовательности, оканчивающейся на x[i]. Это расширение приводит к алгоритму с числом действий порядка n*n.

      1.3.5. Какие изменения нужно внести в решение предыдущей задачи, если надо искать максимальную неубывающую последовательность?

Другие записи

10.06.2016. 1.1.Задачи без массивов
1.1.1. Даны две целые переменные a, b. Составить фрагмент программы, после исполнения которого значения переменных поменялись бы местами (новое значение a равно старому значению b и наоборот).  …