Выполняется ли инвариант цикла в процессе выполнениятела цикла?
(Отметьте один правильный вариант ответа.)
Варианты ответа
Не обязательно. (Верный ответ)
Да, выполняется.
утверждение: A(x)цикл пока B(x)| инвариант: A(x)| x := T(x)конец циклаЗдесь через A(x) и B(x)обозначены условия, зависящие от переменной 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;
дано: x > 0, a > 1, ε > 0надо: вычислить loga x с точностью εвещ y, z, t;y := 0.0; z := x; t := 1.0;цикл пока |t| >= ε или z <= 1.0/a или z >= a| инвариант: ay * zt = x| если z >= a| | то| | z := z/a; y := y + t;| иначе если z <= 1.0/a| | то| | z := z*a; y := y - t;| иначе| | z := z*z; t := t/2.0;| конец есликонец циклаответ := y;
дано: основание a и показатель степени n >= 0надо: вычислить a в степени nвещ b, p; цел k;b := a; p := 1.0; k := n;цикл пока k > 0| инвариант: bk p = an| если k четное| | то| | k := k / 2;| | b := b * b;| | иначе| | k := k - 1;| | p := p * b;| конец есликонец циклаответ := p;
// Программа Поискдано: цел n; цел a[n]; // a[0] < a[1] < ... < a[n-1]цел x; // искомый элементцел b, e, c;. . . // рассматриваются исключительные случаиутверждение: a[0] < x и x <= a[n-1]; // общий случайb := 0; e := n - 1;цикл пока e - b > 1| инвариант: a[b] < x и x <= a[e];| c := (b + e) / 2; // c -- целая часть (b+e)/2| если x < a[c]| | то e := c; // выбираем левую половину отрезка| | иначе b := c; // выбираем правую половину отрезка| конец есликонец циклаутверждение: b == e - 1 и a[b] < x и x <= a[e];
дано: целые числа 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;
цел 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;Какое условие является инвариантом цикла?