Билет №17 Теорема о цикле repeat- until ,его инварианте и ограничивающей его ф-ции. Аннотирование цикла и понимание аннотации №17
Repeat S until B = begin S;
While not B do S end.
{Q & not B } S {Q }
{Q}while not B do S [Q &]B
{P} S {Q}, {Q & not B} S {Q}
при первом при послед.
{P} repeat S until B {Q & B}
На всех шагах .кроме 1, Q-инвариантно! Тело цикла выполняется хотя бы 1 раз
If B then S1 else S2
While B do S
B - сохраняет усл, кот в repeat-until нет
Правило: Если предполож , что из Q & not BP .{p} S {Q}
{P} repeat S until B {Q & B треб для огранич ф-ции
1)P (t>0)
2){P & (t0-t > 0) } S {0 t t0}
Вопрос№18 Алгоритм анализа двоичной записи натурального числа в двоичной сист счисления №18
Рассматривается следующая задача: для заданного a (например, aR) и заданного n вычислить степень an.
Для примера рассмотрим вычисление a11. Действуя «в лоб» последовательным умножением aaaaaaaaaaa, затратим 10 умножений. Действуя более изобретательно, можно получить результат всего за 5 умножений, а именно: 1) aa=a2; 2) (a2) (a2)=a4; 3) a4a=a5; 4) (a5) (a5) = a10; 5) a10a = a11. Чтобы понять этот способ действий, рассмотрим естественное (рекурсивное) определение
(2.10) и
будем применять его последовательно.
Например, 1) a11 = (a5)2
a, 2) a5 = (a2)2
a, 3) a2 = a
a.
Вычисления следует выполнять в обратном порядке: сначала вычислить a2, затем a5 и, наконец, a11.(индийский способ вычисления степени)
Оказывается, что можно описать эти вычисления без ссылок на рекурсивное определение (2.10). Основную роль здесь будет играть двоичная система счисления. Рассмотрим двоичную запись показателя степени n, например: 1110 = 10112. В этой последовательности нулей и единиц заменим каждый символ «0» на символ «К», а каждый символ «1» на пару символов «КУ». Для n = 10112 получим «КУККУКУ». Вычеркнем два первых слева символа «КУ» (они соответствуют первому слева символу «1» в двоичной записи). Для n = 10112 получим «ККУКУ». Установим текущий результат равным a. Далее читаем полученную последовательность слева направо и выполняем следующие действия: если встретился символ «У», то умножаем текущее значение на a, если же очередной символ есть «К», то возводим текущее значение в квадрат. Для нашего примера при n = 10112 получим:
0. b := a; { b = a}
1. {К} b := sqr(b); { b = a2}
2. {КУ} b := sqr(b); b := b*a; { b = a5}
3. {КУ} b := sqr(b); b := b*a; { b = a11}.
В общем случае обосновать эти действия можно следующим образом. Пусть вычислено b = am. Рассмотрим число M = 2m + , где = 0 или 1. Переход от числа m к числу M соответствует приписыванию справа к двоичной записи числа m одного бита . Тогда имеем aM = a2m + = (am)2a. При = 0 получаем aM = (am)2, что соответствует операции «К», а при = 1 получаем aM = (am)2a, что соответствует операции «КУ». Вся последовательность действий получается в результате чтения двоичной записи показателя степени n слева направо и обработки очередного бита указанным ранее способом. Подсчитаем общее количество умножений, выполняемых при «индийском» способе. Длина двоичной записи числа n равна log2 n + 1. Пусть N1(n) есть число единиц в двоичной записи числа n. Тогда общее количество операций умножения и возведения в квадрат (с учётом отбрасывания первых символов «КУ») будет log2 n + 1 + N1(n) 2 или log2 n + N1(n) 1.
Рассмотренный алгоритм можно назвать бинарным методом «слева направо». Для компьютерной реализации более эффективным оказывается аналогичный бинарный алгоритм, основанный на анализе двоичной записи показателя степени справа налево. Опишем процесс разработки этого алгоритма, основанный на конструктивном использовании понятия инварианта цикла.
Для начала рассмотрим более простую вспомогательную задачу вычисления по заданному n функции N1(n) числа единиц в двоичной записи числа n. Приведём примеры: N1(1110) = N1(10112) = 3, N1(3210) = N1(1000002) = 1, N1(3110) = N1(111112) = 5.
Анализ двоичной записи числа n справа налево выполним, используя булевскую функцию Odd(n): если справедливо Odd(n), т. е. n нечётно, то последний (крайний справа) бит в двоичной записи n есть 1; если же справедливо not Odd(n), т. е. n чётно, то последний бит в двоичной записи n есть 0. Переход к следующему слева биту осуществляется операцией n div 2. Пусть выполнено i таких шагов (0 < i < log2 n + 1). Для анализируемой части двоичной записи значения переменной n введем переменную m, сохраняя n неизменной. Состояние после i-го шага схематически изображено на рис. 2.1.
--------------------------------------------------------------------------------------------------
i ! i 1 … 2 1 0 -показат степени 2
… ! … -2ичная запись n
i +1 i ! i 1 … 3 2 1 -Номера шагов
Двоичная запись m Двоичная запись p
--------------------------------------------------------------------------
Здесь p – число, двоичную запись которого составляют правые i бит двоичной записи числа n. Очевидно, что N1(n) = N1(m) + N1(p). Например, при n = 8610 = 10101102 и i = 4 имеем m = 1012 = 510 и N1(m) = 2, а также p = 1102 = 610 и N1(p) = 2. Поскольку N1(n) = 4, то действительно N1(n) = N1(m) + N1(p) = 2 + 2 = 4. Рис. 2.2 иллюстрирует этот факт.
|
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
|
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
|
|
| ||||||
|
Двоичная запись m |
Двоичная запись p | ||||||
Рис. 2.2. Иллюстрация соотношения N1(n) = N1(m) + N1(p)
Пусть в цикле просмотра двоичной записи справа налево вычисляется y = N1(p), тогда в качестве инварианта цикла рассмотрим соотношение N1(n) = N1(m) + y, и вместе с условием окончания цикла m = 0 оно даст требуемое постусловие N1(n) = y. Программа, вычисляющая функцию N1(n) , имеет следующий вид:
{n0}
m := n; y :=0;
{Инвариант: (N1(n) = N1(m) + y) & (0 m n) }
while m > 0 do
begin
if Odd(m) then y := y + 1;
m := m div 2;
end;
{y=N1(n)}
Билет №19 Алгоритм возведения в степень(прим проектирования цикла с помощью иварианта) №19
Основной цикл в задаче вычисления степени будет соответствовать просмотру двоичной записи n справа налево. Представляет интерес инвариантное утверждение, описывающее состояние программы (связь между переменными программы) на произвольном шаге этого цикла. Из рис. 2.1 ясно, что после i-го шага n = m 2i + p. Для примера с n = 8610 = 10101102 и i = 4 (рис. 2.2) действительно имеем 8610 = 5 24 + 6. Тогда для степени an после i-го шага имеем представление
(2.11)
Предположим, что
в цикле кроме m
вычисляются ещё две величины
Тогда
из (2.11) получимan = bm c.
Это и будет инвариант
цикла. Более
точно инвариантом будет
(an = bm c) & (0 m n).
Если перед началом цикла положить m = n,
c = 1
и b = a,
то инвариант перед циклом будет выполнен.
Таким образом, можно записать набросок
цикла:
{Предусловие: n>0}
m := n; c := 1; b := a;
{Инвариант: (an = bm c) & (0 m n)}
while m > 0 do
begin
,,,,,,,,,,,,ТЕЛО ЦИКЛА ,,,,,,,,,,,,
end;
{Постусловие: ?}
Уже известно (см. задачу вычисления N1(n)), как изменяется переменная m в теле цикла: переход к следующему биту двоичного представления реализуется операцией m div 2. Тогда после завершения цикла получим m = 0 и из инварианта будет следовать an = bm c = b0 c = с. Таким образом, постусловием этого цикла является с = an, т. е. требуемый результат сформируется в переменной c.
Используя инвариант цикла, определим остальные операции в теле цикла. Пусть
ТЕЛО ЦИКЛА:
{(an = bm c) & (0 < m n)} Операторы изменения переменных b и c;
m := m div 2; {(an = bm c) & (0 m n)}
По правилу вывода для оператора присваивания (2.3) имеем следующее свойство оператора m := m div 2 :
{(an = bm div 2 c) & (0 (m div 2) n)} m := m div 2 {(an = bm c) & (0 m n)}
или с учётом следования (0 < m n) (0 (m div 2) n) получаем{(an = bm div 2 c) & (0 < m n)} m := m div 2 {(an = bm c) & (0 m n)}.
Тогда для того чтобы тело цикла обладало сформулированным ранее свойством, первая часть тела цикла «Операторы изменения переменных b и c» должна обладать свойством {(an = bm c) & (0 < m n)}
Операторы изменения переменных b и c; {(an = bm div 2 c) & (0 < m n)}.
Рассмотрим отдельно случаи чётного и нечётного значения m. Пусть not Odd(m), тогда m = (m div 2) 2 и требуемое свойство {an = b(m div 2) 2 c}
Операторы изменения переменных b и c;
{an = bm div 2 c}
можно обеспечить, используя оператор b := sqr(b). Действительно, слабейшее предусловие для оператора присваивания b := sqr(b) относительно постусловия an = bm div 2 c есть an = (b2)m div 2 c = b(m div 2) 2 c, что совпадает с требуемым предусловием тела цикла.
Пусть теперь Odd(m), тогда m = (m div 2) 2 + 1 и требуемое свойство
{an = b(m div 2) 2 +1 c}
Операторы изменения переменных b и c;
{an = bm div 2 c}
можно обеспечить, используя кроме оператора b := sqr(b) ещё и добавленный перед ним оператор c := c*b. Действительно, слабейшее предусловие для пары операторов c := c*b и b := sqr(b) относительно постусловия an = bm div 2 c есть an = (b2)m div 2 (c*b) = b(m div 2) 2 +1 c, что совпадает с требуемым предусловием тела цикла.
Таким образом, программа вычисления степени принимает законченный вид
{Предусловие: n>0}
m := n; c := 1; b := a;
{Инвариант: (an = bm c) & (0 m n)}
while m > 0 do
begin
if Odd(m) then c := c*b;
b := sqr(b);
m := m div 2;
end;
{Постусловие: c = an}
Ещё раз обратимся к телу цикла и его предполагаемому свойству. Оказывается, что прежняя конструкция тела цикла не единственна. Рассмотрим отдельно случай чётного и нечётного значений m. При чётных m, как было установлено ранее, операции m := m div 2 и b := sqr(b) сохраняют инвариант. Заметим, что новое значение m может быть как чётным, так и нечётным. Пусть m – нечётное, тогда инвариант цикла можно сохранить, используя операции m := m 1 и c := c*b. При этом новое значение m заведомо чётно. Данные соображения наводят на мысль о выделении внутреннего цикла (после выполнения которого сохранён инвариант объемлющего цикла):
{ not Odd(m), возможно, кроме первого входа}
while not Odd(m) do begin m := m div 2; b := sqr(b) end;
{Odd(m)}
На выходе из цикла будет Odd(m), поэтому можно выполнить рассмотренные ранее для этого случая действия m := m 1 и c := c*b, сохраняющие инвариант. Комбинируя эти два фрагмента, получим новое тело цикла и, соответственно, новый вариант алгоритма:
{Предусловие: n > 0}
m := n; c := 1; b := a;
{Инвариант:(an = bm c) & (0 m n)}
while m > 0 do
begin
{ not Odd(m), возможно, кроме первого входа}
while not Odd(m) do begin m := m div 2; b := sqr(b) end;
{Odd(m)}
m := m 1; c := c*b { not Odd(m) }
end;
{Постусловие: c = an}
Билет №20 Послед как способ организ данных, №20
Базавые операции и типовые действия с файлами