База ответов ИНТУИТ

Программирование

<<- Назад к вопросам

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма быстрого возведения в степень:
int fastPow(double a, int n) {    // дано: основание a и показатель степени n >= 0    // надо: вычислить a в степени n    double b = a, p = 1.0; int k = n;    while (k > 0) {        // Invariant: b^k * p == a^n        if (k%2 == 0) {            // k четное            k /= 2;            b *= b;        } else {            // k нечетное            --k;            p *= b;        }    }    return p;}

(Отметьте один правильный вариант ответа.)

Варианты ответа
Время работы не больше, чем C*r, где C - некоторая константа, r - квадратный корень из числа n (т.е. время пропорционально квадратному корню из n).
Время работы не больше, чем C*log2 n, где C - некоторая константа (т.е. время пропорционально количеству цифр в двоичной или десятичной записи числа n). (Верный ответ)
Время работы не больше, чем C*n, где C - некоторая константа (т.е. время пропорционально числу n).
Похожие вопросы
Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритмаприблизительного вычисления логарифма:
double myLog(double x, double a, double eps) {    // дано: x > 0, a > 1, eps > 0    // надо: вычислить log_a x с точностью eps    double y = 0.0, z = x, t = 1.0;    while (        fabs(t) > eps ||        x <= 1.0/a ||        z >= a    ) {        // Invariant: a^y * z^t == x        if (z >= a) {            z /= a; y += t;        } else if (z <= 1.0/a) {            z *= a; y -= t;        } else {            z *= z; t /= 2.0;        }    }    return y;}
Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма Евклидавычисления наибольшего общего делителя двух целых чисел:
int gcd(int m, int n) {    // дано: целые числа m, n, хотя бы одно отлично от нуля    // надо: вычислить НОД пары (m, n)    int a = m, b = n;    while (b != 0) {        // Invariant: НОД(a, b) == НОД(m, n)        int r := a % b; // находим остаток от деления a на b        a = b; b = r;   // заменяем пару (a, b) на (b, r)    }    return a;           // ответ = a}
Рассмотрим следующую функцию, аргументами которойявляются два целых неотрицательных числа:
int f(int m, int n) {    // дано: m >= 0 и n >= 0    int a = m; int b = n;    int c = 1;    while (a != 0 && b != 0) {        if (a%2 == 0 && b%2 == 0) {            // a и b четные            a /= 2; b /= 2;            c *= 2;        } else if (a%2 == 0) {            // a четное, b нечетное            a /= 2;        } else if (b%2 == 0) {            // a нечетное, b четное            b /= 2;        } else {            // a и b нечетные            if (a > b) {                a -= b;            } else {                b -= a;            }        }    } // end while    return c*(a + b);}
Какое условие является инвариантом цикла?(Через НОД и НОК обозначены наибольший общий делитель инаименьшее общее кратное.)
Функция с прототипом
double root(double a, double b, double eps);
находит корень фиксированной функции
double f(double x);
на отрезке [a, b] методом деления отрезка пополамс точностью eps.Пусть функция f(x) определена следующимобразом:
double f(double x) {    double p = 1.;    double r = 1.;    while (r < 5.5) {        p *= (x - r);        r += 1.;    }    return p;}
Каким будет приблизительное значение переменной xв результате выполнения следующего фрагмента программы:
    double x = root(0., 5.9, 0.000001);
Функция ln(z) (натуральный логарифм z) представляетсяв виде степенного ряда следующим образом:
    ln(1+x) = x - x2/2 + x3/3 - x4/4 + ...
(мы обозначили z=1+x).Рассмотрим реализованную на C/C++ функцию myLog(z),вычисляющую значение логарифма с точностью до одной миллионной:
static const double EPS = 1e-6;double myLog(double z) {    double x = z - 1.;    double s = 0.;    double p = x;    double n = 1.;    double a = x;    while (fabs(a) > EPS) {        s += a;        p = (-p*x);        n += 1.;        a = p/n;    }    return s;}
Для каких значений z ее можно применять так,чтобы функция завершала работу за разумное время иошибка вычисления результата была бы не более 0.0001?Укажите все правильные ответы из числа перечисленных ниже.
Формула Бинома Ньютона дает следующее разложение в ряддля функции "квадратный корень из z":
(1+x)0.5 = sqrt(1+x) =    1 + 0.5 x + 0.5(-0.5)/2! x2 + 0.5(-0.5)(-1.5)/3! x3 + 0.5(-0.5)(-1.5)(-2.5)/4! x4 + ...
(мы обозначили z=1+x). Рассмотрим реализованную на C/C++ функцию mySqrt(z),вычисляющую значение квадратного корня с точностью до одной миллионной:
static const double EPS = 1e-6;double mySqrt(double z) {    double x = z - 1.;    double s = 1;    double k = 0.5;    double n = 1.;    double a = k*x;    while (fabs(a) > eps) {        s += a;        k -= 1.;        n += 1.;        a *= (k/n)*x;    }    return s;}
Для каких значений z ее можно применять так,чтобы функция завершала работу за разумное время иошибка вычисления результата была бы не более 0.0001?Укажите все правильные ответы из числа перечисленных ниже.
Функция с прототипом
double root(double a, double b, double eps);
находит корень фиксированной функции
double f(double x);
на отрезке [a, b] методом деления отрезка пополамс точностью eps.Пусть функция f(x) определена следующимобразом:
double f(double x) {    return sin(x);}
Каким будет приблизительное значение переменной xв результате выполнения следующего фрагмента программы:
    double x = root(-1., 9., 0.000001);
Функция с прототипом
double root(double a, double b, double eps);
находит корень фиксированной функции
double f(double x);
на отрезке [a, b] методом деления отрезка пополамс точностью eps. Сколько примерно раз будет выполненотело цикла при поиске корня, когда используется следующий вызов:
    double x = root(1., 2., 0.001);
Функция arctg(x) раскладываетсяв ряд Тейлора следующим образом:
    arctg(x) = x - x3/3 + x5/5 - x7/7 + ...
Рассмотрим реализованную на C/C++ функцию myAtan(x),вычисляющую значение arctg(x) с точностью до одной миллионной:
static const double EPS = 1e-6;double myAtan(double x) {    double s = 0.;    double p = x;    double n = 1.;    double a = x;    while (fabs(a) > EPS) {        s += a;        p = (-p*x*x);        n += 2.;        a = p/n;    }    return s;}
Для каких значений x ее можно применять?Укажите все правильные ответы из числа перечисленных ниже.
Рассмотрим следующую функцию, аргументами которойявляются два целых неотрицательных числа:
int f(int m, int n) {    int a = m, b = n;    int p = 0;    while (b != 0) {        if (b%2 == 0) { // b четное            b /= 2;            a *= 2;        } else { // b нечетное            --b;            p += a;        }    }    return p;}
Какое условие является инвариантом цикла?