Какое утверждение является инвариантом для следующего фрагмента программы (т.е. из справедливости утверждения до выполнения фрагмента программы вытекает справедливость утверждения после выполнения)? Предполагается, что n > 0. вещ r, x; цел n; . . . r := -r * x; r := r * n / (n + 1); n := n + 1;

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

• # Рассмотрим следующую реализацию функции onSqrt, которая исполняет команду извлечения квадратного корня в проекте «Стековый калькулятор»: static void onSqrt() { double x; if (st_empty()) { printf("Stack empty.\n"); return; } x = st_pop(); assert(x >= 0.0); // утв: x неотрицательно st_push(sqrt(x)); display(); } Правильно ли здесь используется конструкция «утверждение», которая в Си реализуется функцией assert?
• # Бинарное дерево называется полным, если длины всех путей к внешним (нулевым) вершинам одинаковы. (Это означает, что у каждой нетерминальной вершины ровно два сына, и длины всех путей от корня к терминальным вершинам одинаковы и равны высоте дерева.) Высотой дерева называется число вершин в пути максимальной длины от корня к некоторой терминальной вершине, включая первую и последнюю вершины пути. Сколько вершин в полном бинарном дереве высоты 10?
• # Указать, что вычисляет следующий фрагмент программы: дано: цел n; цел s, k; s := 2; k := 0; цикл пока s <= n | инвариант: s = 2k+1 | s := s * 2; k := k + 1; конец цикла ответ := k;
• # Какой архитектуре соответствует представление целых чисел в протоколах сети Internet?
• # Указать, чему будет равно значение переменной i в результате выполнения следующего фрагмента программы: int i = 10; while (i <= 1000) { i *= 2; }