Оценить сверху время работы (т.е. количество выполнений тела цикла) алгоритма Евклида вычисления НОД двух целых чисел: дано: целые числа 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;

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

• # Содержимое двухбайтового слова можно интерпретировать либо как неотрицательное целое число в диапазоне 0...65535, либо как число со знаком в диапазоне -32768...32767. Какое число со знаком имеет тот же двоичный код, что и неотрицательное число 65533?
• # Целочисленная переменная x представляет короткое целое число со знаком в диапазоне -128...127 и занимает 1 байт. Чему равно значение x после выполнения приведенного ниже фрагмента программы? x := 120; x := x + 40;
• # Пусть a — целочисленный массив размера n (индекс элементов меняется от 0 до n-1), элементы которого строго возрастают: a[0] < a[1] <... < a[n-1]. Определить, содержит ли следующий фрагмент программы ошибку (т.е. действительно ли тело цикла сохраняет инвариант): // Программа Поиск дано: цел 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];
• # Как располагаются разряды двоичного представления целого числа внутри машинного слова в архитектуре Little Endian (процессоры Intel, Alpha и т.п.)?
• # Чему равна вещественная константа 0.001e+4, записанная в экспоненциальной форме?