Рассмотрим функцию F, которая последовательности коэффициентов многочлена по убыванию степеней ставит в соответствие значение второй производной многочлена в точке t. Какая из приведенных ниже функций на последовательностях является индуктивным расширением функции F?

Правильный ответ:

• # Что можно сказать об условии, указанном в заголовке цикла "пока", после полного завершения цикла?
• # Рассмотрим следующий фрагмент программы: цел m, n; цел a, b, p; . . . a := m; b := n; p := 0; цикл пока b != 0 | если b четное | | то | | b := b / 2; | | a := a * 2; | | иначе | | b := b - 1; | | p := p + a; | конец если конец цикла ответ := p; Какое условие является инвариантом цикла?
• # Оценить сверху время работы (т.е. количество выполнений тела цикла) алгоритма Евклида вычисления НОД двух целых чисел: дано: целые числа m, n, хотя бы одно отлично от нуля надо: вычислить наибольший общий делитель пары (m, n) цел a, b, r; a := m; b := n; цикл пока b != 0 | инвариант: НОД(a, b) == НОД(m, n) | r := a % b; // находим остаток от деления a на b | a := b; b := r; // заменяем пару (a, b) на (b, r) конец цикла ответ := a;
• # Пусть f(x) — целочисленная функция от целочисленного аргумента. Определить, содержит ли следующий фрагмент программы ошибку (т.е. действительно ли тело цикла сохраняет инвариант): // Программа корень функции цел a, b, c; . . . утверждение: a < b и f(a) * f(b) <= 0; // Значения функции на концах отрезка [a,b] разных знаков цикл пока b - a > 1 | инвариант: f(a) * f(b) <= 0 | // Делим отрезок [a, b] пополам | c := (a + b) / 2; // c -- целая часть (a+b)/2 | если f(a) * f(c) < 0 | | то b := c; // выбираем левую половину отрезка | | иначе a := c; // выбираем правую половину отрезка | конец если конец цикла утверждение: a == b - 1 и f(a) * f(b) <= 0;
• # Рассмотрим следующий фрагмент программы на Си: static int *p = 0; . . . p = (int *) malloc(sizeof(int)); *p = 123; Где хранится значение выражения "*p" (т.е. число 123)?