Программирование - тест 74

Упражнение 1:

---

Номер 1

В массиве, содержащем 1000 элементов,
выполняется последовательный поиск элемента x.
При этом x содержится
в массиве с вероятностью 0.25. Сколько в среднем операций сравнения
будет выполнено?

Ответ:

---

Номер 2

В массиве, содержащем 1000 элементов,
выполняется последовательный поиск элемента x.
При этом x содержится
в массиве с вероятностью 0.75. Сколько в среднем операций сравнения
будет выполнено?

Ответ:

---

Упражнение 2:

---

Номер 1

В массиве, содержащем 1000 элементов,
выполняется последовательный поиск элемента x.
При x содержится
в массиве с вероятностью равна 0.1.
Сколько в среднем операций сравнения
будет выполнено?

Ответ:

---

Номер 2

Пусть дан массив 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?

Ответ:

---

Упражнение 3:

---

Номер 1

Пусть дан массив 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;
            }
        }
        if (a[beg] == x) {
            *idx = beg;
        } else  {
            *idx = end;
        }
        . . .

Пусть значение x содержится в массиве
в нескольких экземплярах. Индекс какого элемента
массива a будет записан в переменную *idx?

Ответ:

---

Номер 2

Пусть дан массив 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?

Ответ:

---

Упражнение 4:

---

Номер 1

Пусть элементы массива a
нестрого возрастают (соседние элементы могут быть равными).
Дано произвольное значение x, требуется
найти максимальный индекс i такой, что
a[i] <= x. Используется идея алгоритма
бинарного поиска. Каким должен быть инвариант цикла,
в котором рассматривается основной случай после отбрасывания
исключительных ситуаций?
(Условие завершения цикла
end == beg+1.)

Ответ:

---

Номер 2

Пусть элементы массива a
нестрого возрастают (соседние элементы могут быть равными).
Дано произвольное значение x, требуется
найти минимальный индекс i такой, что
a[i] >= x. Используется идея алгоритма
бинарного поиска. Каким должен быть инвариант цикла,
в котором рассматривается основной случай после отбрасывания
исключительных ситуаций?
(Условие завершения цикла
end == beg+1.)

Ответ:

---

Упражнение 5:

---

Номер 1

Пусть элементы массива a
нестрого возрастают (соседние элементы могут быть равными).
Дано произвольное значение x, требуется
найти максимальный индекс i такой, что
a[i] <= x. Используется идея алгоритма
бинарного поиска. В приведенном ниже цикле
рассматривается основной случай после отбрасывания
исключительных ситуаций:

    while (end-beg > 1) {
        int c = (beg+end)/2;
        if (a[c] <= x)
            beg = c;
        else
            end = c;
    }
    // ответ в переменной beg

Какое утверждение является
инвариантом этого цикла?

Ответ:

---

Номер 2

Программа, использующая бинарный поиск, ищет
элемент в массиве длины миллион в среднем за
одну тысячную секунды. Сколько примерно времени
потребуется на поиск, если мы заменим алгоритм поиска
с бинарного на последовательный?

Ответ:

---

Упражнение 6:

---

Номер 1

Программа, использующая последовательный поиск, ищет
элемент в массиве длины миллион в среднем за
одну секунду. Сколько примерно времени
потребуется на поиск, если мы заменим алгоритм поиска
с последовательного на бинарный?

Ответ:

---

Номер 2

Оцените примерно, во сколько раз алгоритм бинарного поиска
работает быстрее алгоритма последовательного поиска
для массива из 64 миллионов элементов.

Ответ:

---