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

Практическая работа № 39.      
Инвариант цикла

1.  Определите инвариант цикла для следующего алгоритма двоичного поиска (предполагается, что элементы массива A отсортированы по неубыванию):

 L:= 1; R:= n + 1

 нц пока L < R - 1

   c:= div(L + R, 2)

   если X < A[c] то

     R:= c

   иначе

     L:= c

   все

 кц

Ответ:

Используя найденный инвариант, определите, какой именно элемент массива будет найден, если в массиве есть несколько элементов, равных X.

Ответ:

Как нужно изменить инвариант (и цикл!), чтобы найти первый элемент, равный X?

Ответ:

2.       Определите инвариант для следующего цикла.

 k := 0; b := 1

 нц пока k < n 

   k := k + 1

   b := b * a

 кц

Ответ:

Что будет вычислено в переменной b?

Ответ:

3.       Определите инвариант для следующего цикла.

 k := n; b := 1

 нц пока k > 0 

   k := k - 1 

   b := b * a

 кц

Ответ:

Что будет вычислено в переменной b?

Ответ:

4.       Запишите предусловие и постусловие для алгоритма вычисления сумму всех делителей числа.

Ответ:

5.       Запишите предусловие и постусловие для алгоритма проверки числа на простоту.

Ответ:

6.       Запишите предусловие и постусловие для алгоритма определения количества слов в символьной строке.

Ответ:

7.       Запишите предусловие и постусловие для алгоритма двоичного поиска в отсортированном массиве.

Ответ:

8.       Запишите предусловие и постусловие для алгоритма перестановки элементов массива в обратном порядке.

Ответ:

9.       Запишите предусловие и постусловие для алгоритма преобразования числа из символьной записи в значение целого типа.

Ответ:

10.   Предложите другие начальные значения переменных ,  и  в алгоритме быстрого возведения в степень (см. Пример 4 в §37 учебника). Инвариант цикла должен сохраниться.

Ответ:

11.   Оцените сложность алгоритма быстрого возведения в степень при , где m – натуральное число.

Ответ: