Лекции по информатике - Метод инварианта цикла

Метод инварианта цикла является частным случаем метода итераций.

Задается некоторое множество величин М, – подмножество результатов. Надо найти точку . Для этого выделим множества и причем такие, что . Таким образом, наша задача сводится к нахождению точки, которая будет принадлежать пересечению этих множеств. Причем использовать будем только такие преобразования, которые не выходят из I, то есть в нашем случае принадлежность точки множеству Iявляется инвариантом (величиной неизменной).

Пусть – начальная точка.

– преобразование инвариантно относительно принадлежности точки множеству I.

Иллюстрация к вышесказанному:

Под действием преобразования Т точка х₀ переходит в некоторую точку х₁, принадлежащую множеству I. Точка х₁, в свою очередь, переходит в точку х₂, также принадлежащую I. Этот процесс продолжается пока некоторая точка х_nне перейдет в точку принадлежащую некоторому множеству Q, которое выбрано так чтобы его пересечение с Iсодержалось в P. Полученная точка с одной стороны принадлежит Q, а с другой принадлежит I, в силу инвариантности преобразования Т относительно I.

Схема программы:

x:= x0; { x принадлежит I }
while not q(x) do
begin
{ x принадлежит I\Q }
  x:= T(x);
{ x принадлежит I }
end;
{ x принадлежит пересечению I и Q }

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

type
  _Real = single;
  _Unsign = word;


function power(x: _Real; n: _Unsign):Real;
{ х - основание, n – показатель.
  Подпрограмма обеспечивает возведение в степень }
var
  z: _Real;
begin
  z:= 1.0;
  while n > 0 do { z*x^n - инвариант }
  begin
    if odd(n) then { проверка нечетности }
    begin
      dec(n); { n:=n-1 }
      z:= z*x;
    end else
    begin
      n:= n chr 1; { n:= n div 2 }
      x:= sqr(x);
    end;
  end;
  power:= z;
end;

Докажем, что данная программа завершится за конечное число шагов. Подпрограмма завершает свою работу когда z = xⁿ, т.е. предназначена для возведения х в n–ую степень. Число повторений равно количество "нулей" + 2*количество "единиц" – 1 в двоичной записи числа n <= 2*количество значащих цифр – 1 в двоичной записи = 2*log₂n - 1. При этом данная программа будет очень эффективна.

Слава Антонов © 2002 — August 13, 2008

197-577-902