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

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

В массиве, содержащем 1000 элементов,выполняется последовательный поиск элемента x.При x содержитсяв массиве с вероятностью равна 0.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;            }        }        *idx = end;        . . .

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

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

Рассмотрим реализацию матрицы вещественных чиселразмера m строк на n столбцовпри помощи линейного массива,в котором хранятся сначала элементы нулевой строки матрицы,затем первой и т.д., в конце - элементы (m-1)-й строки:

    int m, n; // Размеры матрицы: число строк, столбцов    . . .    double* a = new double[m*n];    // a[i*n + j] -- элемент i-й строки и j-го столбца

Пусть функция с прототипом

void transp(double* a, int m, int n);

реализует транспонированиематрицы, при выполнении которого строки матрицы становятсястолбцами, столбцы - строками, а матрица размераm на nпревращается в матрицу размераn на mПусть эта функция применяется к прямоугольной матрице,содержащей 3 строки и 5 столбцов, элементы которой хранятсяв линейном массиве a. Сколько элементов массиваa при этом останутся на своем месте?

Рассмотрим реализацию матрицы вещественных чиселразмера m строк на n столбцовпри помощи линейного массива,в котором хранятся сначала элементы нулевой строки матрицы,затем первой, второй и т.д., в конце - элементы (m-1)-й строки:

    int m, n; // Размеры матрицы: число строк, столбцов    . . .    double* a = new double[m*n];    // a[i*n + j] -- элемент i-й строки и j-го столбца

Пусть функция с прототипом

void transp(double* a, int m, int n);

реализует транспонированиематрицы, при выполнении которого строки матрицы становятсястолбцами, столбцы - строками, а матрица размераm на nпревращается в матрицу размераn на mПусть эта функция применяется к прямоугольной матрице,содержащей 2 строки и 4 столбца, элементы которой хранятсяв линейном массиве a Сколько элементов массиваa при этом останутся на своем месте?

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

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

Левым нейтральным элементом (левой единицей) для бинарной операции называется элемент e такой, что для всякогодругого элемента x "произведение" e наx равно x:e x = x. Какие элементы будут нейтральнымидля операций суммы и максимума чисел соответственно?

Левым нейтральным элементом (левой единицей) для бинарной операции называется элемент e такой, что для всякогодругого элемента x "произведение" e наx равно x:e x = x. Какие элементы будут нейтральнымидля операций произведения и минимума чисел соответственно?