Главная /
Программирование /
Пусть дан массив a длины n, элементы которого нестрого возрастают, т.е. соседние элементы могут быть равными. Рассмотрим фрагмент программы бинарного поиска элемента x в массиве a длины n, где после отбрасывания особых ситуаций рассматривается основной сл
Пусть дан массив a
длины n
,
элементы которого нестрого возрастают, т.е. соседние
элементы могут быть равными.
Рассмотрим фрагмент программы бинарного поиска
элемента x
в массиве
a
длины n
, где
после отбрасывания особых ситуаций рассматривается
основной случай:
. . .
// Утверждение: a[0] < x && x <= a[n-1]
int beg = 0; int end = n-1;
while (end-beg > 1) {
// Инвариант: a[beg] < x && x <= a[end]
int c = (beg + end) / 2;
if (a[c] < x) {
beg = c;
} else if (a[c] > x) {
end = c;
} else {
// Утверждение: x == a[c]
*idx = c;
return true;
}
}
*idx = end;
return (x >= a[end]);
. . .
Пусть значение x
содержится в массиве
в нескольких экземплярах. Индекс какого элемента
массива a
будет записан в переменную *idx
?
вопрос
Правильный ответ:
Индекс первого элемента, равного
x
.
Индекс поcледнего элемента, равного
x
.
Может быть записан индекс любого элемента
массива
a
, равного
x
.
Индекс первого элемента, равного
x+1
.
Индекс поcледнего элемента, равного
x-1
.
Сложность вопроса
75
Сложность курса: Программирование
84
Оценить вопрос
Комментарии:
Аноним
Это очень легкий тест интуит.
04 дек 2020
Аноним
Я провалил сессию, почему я не нашёл этот великолепный сайт с всеми ответами по интуит месяц назад
17 сен 2018
Аноним
спасибо
15 янв 2018
Другие ответы на вопросы из темы программирование интуит.
- # Рассмотрим следующий фрагмент программы на C/C++: double x = 1.0; double y = 1e-20; double z = x + y - x; double t = x - x + y; Равны ли значения переменных z и t после его выполнения?
- # Отметьте, какие из перечисленных ниже целочисленных значений помещаются в переменную типа unsigned short
- # Пусть дан массив a длины n, элементы которого нестрого возрастают, т.е. соседние элементы могут быть равными. Рассмотрим фрагмент программы бинарного поиска элемента x в массиве a длины n, где после отбрасывания особых ситуаций рассматривается основной случай: . . . // Утверждение: a[0] < x && x <= a[n-1] int beg = 0; int end = n-1; while (end-beg > 1) { // Инвариант: a[beg] < x && x <= a[end] int c = (beg + end) / 2; if (a[c] < x) { beg = c; } else { end = c; } } *idx = end; . . . Пусть значение x содержится в массиве в нескольких экземплярах. Индекс какого элемента массива a будет записан в переменную *idx?
- # Алгоритм быстрой сортировки реализован с помощью комбинированной схемы, использующей рекурсию и цикл 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? Дайте наиболее точную оценку снизу этого числа.
- # Назовем алгоритм сортировки оптимальным, если он работает за время O(n log2 n) даже при самом плохом входе. Среди перечисленных ниже алгоритмов сортировки отметьте оптимальные.