Инвариант цикла

Инвариант цикла

Цикл с условием продолжения без инициализации

Если

{I and B} S {I}

то

{I} while B do S endwhile {I and not B)

Условие I называют инвариантом цикла.

Численный алгоритм

Программа

a:=x; b:=y; c:=0;

while b ≠ 0 do

{}

{}
b:=b-1; c:=c+a

end

{}

Для данной программы определите, что является аргументом и что является результатом.

Произведите прокрутку алгоритма для значений х=7 и у = 13, заполняя таблицу

Операция	Расчет	Инвариант цикла	Пароль
a:=7; b:=13; c:=0	a=7; b=13; c=0		b≠0
b:=b-1; c:=c+a	a=7; b=12; c=7		b≠0
b:=b-1; c:=c+a	a=7; b=11; c=14		b≠0
			b=0

Запишите выражение для инварианта цикла

Программа – алгоритм 1

a:=x; b:=y; c:=0;

while b ≠ 0 do

{высказывание: a*b+c=x*y}

{ высказывание: b ≠ 0 }
b:=b-1; c:=c+a

end

{ высказывание: a*b+c=x*y и b = 0 дает с = x*y}

Инвариант цикла

I = a*b+c=x*y

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

Усовершенствованный алгоритм перемножения натуральных чисел

Программа – алгоритм 2

a:=x; b:=y; c:=0;

while b ≠ 0 do

{высказывание: a*b+c=x*y}

{ высказывание: b ≠ 0 }
c:=c+a* (b MOD 10);

a:= a*10;

b:=b DIV 10

end

{ высказывание: a*b+c=x*y и b = 0 дает с = x*y}

Операция	Расчет	Инвариант цикла	Пароль
a:=7; b:=13; c:=0	a=7; b=13; c=0	7*13+0=7*13	b≠0
c:=c+a* (b MOD 10); a:= a*10; b:=b DIV 10	c=0+7* (13 MOD 10)= a= 7*10= b=13 DIV 10 =		b≠0
			b=0

Усовершенствованный алгоритм перемножения натуральных чисел

Программа – алгоритм 3

a:=x; b:=y; c:=0;

while b ≠ 0 do

{высказывание: a*b+c=x*y}

{ высказывание: b ≠ 0 }
if Odd (b) then c:=c+a;

a:= a*2;

b:=b DIV 2

end

{ высказывание: a*b+c=x*y и b = 0 дает с = x*y}

Операция	Расчет	Инвариант цикла	Пароль
a:=7; b:=13; c:=0	a=7; b=13; c=0	7*13+0=7*13	b≠0
if Odd (b) then c:=c+a a:= a*2 b:=b DIV 2	c = a= b=		b≠0
			b=0

Нечисленный алгоритм

Поиск слова в тексте

Текст хранится в виде последовательности литер. Необходимо отыскать в нем первое появление определенного «слова», которое можно определить как последовательность литер не длиннее самого текста.

текст: array[0..m-1] of character

слово: array[0..n-1] of character

i:=0; j:=0;

while (i < n) and (j < m – n) do

begin

i:=0;

while (i < n) and (слово[i]= текст[j+i]) do i:=i+1;

if i< n then j:= j+1;

end