Практическая работа № 40
«Инвариант цикла»

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ:

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

Ответ: