Главная /
Программирование /
Пусть a - целочисленный массив размера n (индекс элементов меняется от 0 до n-1), элементы которого строго возрастают: a[0] < a[1] <... < a[n-1]. Определить, содержит ли следующий фрагмент программы ошибку (т.е. действительно ли тело цикла сохран
Пусть a
- целочисленный массив размера n
(индекс элементов меняется от 0 до n-1
),
элементы которого строго возрастают:
a[0] < a[1] <... < a[n-1]
.
Определить, содержит ли следующий фрагмент программы ошибку
(т.е. действительно ли тело цикла сохраняет инвариант):
// Программа Поиск
int n; int *a;
. . .
// дано: целое n;
// целочисленный массив a[n],
// элементы которого строго возрастают
// a[0] < a[1] < ... < a[n-1]
// надо: найти элемент x в массиве
int x; // искомый элемент
. . . // рассматриваются исключительные случаи
// общий случай
// утверждение: a[0] < x && x <= a[n-1];
int b = 0; int e = n - 1;
while (e - b > 1) {
Invariant: a[b] < x && x <= a[e]
int c := (a + b)/2; // c - целая часть (a+b)/2
if (x < a[c]) {
e = c; // выбираем левую половину отрезка
} else {
b = c; // выбираем правую половину
}
}
// утверждение: b == e - 1 &&
// a[b] < x && x <= a[e]
вопрос
Правильный ответ:
Ошибки нет, фрагмент программы корректный.
Фрагмент программы содержит ошибку.
Сложность вопроса
60
Сложность курса: Программирование
84
Оценить вопрос
Комментарии:
Аноним
Если бы не данные ответы - я бы не смог решить c этими тестами интуит.
13 июн 2018
Аноним
Я провалил зачёт, почему я не увидел этот сайт с всеми ответами интуит до того как забрали в армию
17 янв 2016
Другие ответы на вопросы из темы программирование интуит.
- # В алгоритме сортировки слиянием "In Place Merge Sort", не использующем дополнительной памяти, применяется функция mergeBlocks слияния двух упорядоченных блоков, т.е. подмассивов длины m и n, реализованная рекурсивно. Пусть сумма длин блоков m+n=512. При реализации функции mergeBlocks вызывается функция перестановки двух блоков swapBlocks. Какой может быть максимальная суммарная длина блоков переставляемых блоков?
- # Сколько единиц в двоичной записи числа 11?
- # Двоичный код, представляющий число типа double, хранит знак, смещенный порядок и дробную часть двоичного представления мантиссы. Сколько битов отводится под каждый элемент представления?
- # Какую из конструкций цикла в языке C удобнее всего использовать для реализации арифметического цикла, в котором тело цикла последовательно выполняется для всех значений переменной цикла, представляющих арифметическую прогрессию?
- # Алгоритм быстрой сортировки реализован с помощью комбинированной схемы, использующей рекурсию и цикл while, а также вспомогательную функцию partition, которая разделяет текущий отрезок массива на 3 части (элементы, меньшие либо равные медиане, медиана, элементы, большие либо равные медиане): void quickSort(double* a, int n) { if (n <= 1) { return; } else if (n == 2) { if (a[0] > a[1]) swap(&(a[0]), &(a[1])); return; } int beg = 0; int k = n; while (k > 1) { int m = k / 2; partition(a+beg, k, &m); int left = m; int right = k - left - 1; if (left <= right) { // Рекурсивно применяем алг. к левой части quickSort(a+beg, left); beg += left + 1; k -= left + 1; } else { // Рекурсивно применяем алг. к правой части quickSort(a+beg+m+1, right); k -= right + 1; } } } Сколько раз будет вызвана функция partition при выполнении алгоритма быстрой сортировки для массива размера 47? Дайте наиболее точную оценку снизу этого числа.