Текст задания

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

4.1. Дан алгоритм:

алг Последовательность (арг цел М, рез цел Z)
нач цел: X, Y
ввод М;
X := 1
Y := 3
Z := Y
нц пока Z < М
Z := Y - 2 * X
X := Y
Y := Z
кц
вывод Z
кон

Верно ли, что при любом целом М этот алгоритм конечен?

4.2. Рассмотрите следующий алгоритм:

алг Сумма (арг цел М, рез цел N)
нач вещ: S
S := 1
N := 1
вывод "Введите натуральное число М"
ввод М
нц пока S < М
N := N + 1
S := S + 1/N
кц
вывод N
кон

а) Для решения какой задачи предназначен этот алгоритм?

б) Ясно, что при М = 1 тело цикла не выполняется ни разу и, следовательно, алгоритм конечен. При любом ли значении М данный алгоритм конечен?

4.3. Рассмотрите следующий алгоритм, преобразующий натуральные числа.

алг Преобразование (арг цел а, b, n, рез цел m)
нач
ввод n
ввод а
ввод b
m := n
нц пока (m  a) и (m  b)
m : = СКВ(m)
кц (*конец цикла*)
вывод m
кон
алг цел СКВ (арг цел n)
нач
если n < 10
то знач := n * n
иначе знач := СКВ (n div 10) +
(n mod 10)*(n mod 10)
все
кон

При каких a и b этот алгоритм конечен? Перечислите все возможные здесь варианты.

4.4. Рассмотрите следующий алгоритм.

алг Половинчатый (арг цел K, М)
нач
ввод K
ввод М
нц пока (K mod 2 = 0 или M mod 2 = 0)
если K mod 2 = 0
то K := K/2
M := M + K
все
если (M mod 2 = 0)
то М := M/2
M := M + K
все
кц
вывод M * K
кон

Определите, для каких пар натуральных чисел K и М этот алгоритм завершает работу за конечное число шагов.

4.5. Даны два массива К и М с целочисленными элементами, расположенными в каждом из них в порядке возрастания. Рассмотрите следующий алгоритм:

алг Количество (арг цел таб К[1:20], М[1:30], рез цел с)
нач цел: a, b
a := 1
b := 1
c := 1
нц пока (a  20 и b  30)
выбор
при K(a) < M(b)
a := a + 1
при K(a) > M(b)
b := b + 1
при K(a) = M(b)
a := a + 1
b := b + 1
c := c + 1
все
кц
вывод c
кон

а) Для решения какой задачи предназначен этот алгоритм?

б) Найдите подходящий инвариант и докажите гипотезу, выдвинутую вами при выполнении пункта а).

Решение

Решение контрольной работы оформлено в виде документа Word. Для получения решения необходимо оформить заказ и оплатить его.