Главная /
Программирование /
Оценить сверху время работы (т.е. количество выполнений тела цикла) алгоритма приблизительного вычисления логарифма: double myLog(double x, double a, double eps) { // дано: x > 0, a > 1, eps > 0 // надо: вычислить log_a x с точностью eps double y
Оценить сверху время работы (т.е. количество
выполнений тела цикла) алгоритма
приблизительного вычисления логарифма:
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;
}
вопрос
Правильный ответ:
Время работы не больше, чем
C*log2 [x+1],
где C - некоторая константа,
[x+1] - целая часть числа x+1
(т.е. время пропорционально количеству цифр
в двоичной или десятичной записи
целой части числа x).
Время работы не больше, чем
C*log2[x+1]*log2(1/eps),
где C - некоторая константа, а квадратные скобки
обозначают целую часть.
Иначе говоря, время пропорционально количеству цифр
в двоичной или десятичной записи
целой части x, умноженному на требуемое количество значащих
цифр в дробной части результата.
Время работы не больше, чем
C*log2[x+1] + log2(1/eps),
где C - некоторая константа, а квадратные скобки
обозначают целую часть. Иначе говоря,
время пропорционально сумме количества цифр
в двоичной или десятичной записи
целой части x и требуемого количества значащих
цифр в дробной части результата.
Сложность вопроса
56
Сложность курса: Программирование
84
Оценить вопрос
Комментарии:
Аноним
Какой студент находит данные ответы по интуит? Это же элементарно
15 июн 2020
Аноним
Большое спасибо за тесты по intuit.
14 июл 2018
Другие ответы на вопросы из темы программирование интуит.
- # Формула Бинома Ньютона дает следующее разложение в ряд для функции "кубический корень из z" (обозначим ее croot(z)): (1+x)1/3 = croot(1+x) = 1 + (1/3)x + (1/3)(-2/3)/2! x2 + (1/3)(-2/3)(-5/3)/3! x3 + (1/3)(-2/3)(-5/3)(-8/3)/4! x4 + ... (мы сделали замену z=1+x). Этот ряд сходится лишь для значений x, по абсолютной величине не превосходящих 1, а эффективно вычислять его сумму можно только для еще более узкого интервала значений x. Каким свойством функции croot(z)=z1/3 удобнее всего воспользоваться, чтобы свести ее вычисление для положительных значений z к суммированию ряда?
- # Сколько раз в алгоритме Гаусса будет выполнена операция перестановки местами двух строк (с изменением знака одной из них) при приведении к ступенчатому виду следующей матрицы: 1 2 3 4 0 1 2 3 2 7 10 14
- # Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел. Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности. Программа должна содержать функцию, которая получает в качестве параметра имя файла и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл. Задание: найти количество возрастающих участков последовательности.
- # Чему будет равно значение переменной n в результате выполнения следующего фрагмента программы? Процессор имеет 32-разрядную архитектуру. double a[4][3]; int n, m; n = (int)(a+1); m = (int) a; n -= m;
- # Чему будет равно значение переменной n в результате выполнения следующего фрагмента программы? Процессор имеет 32-разрядную архитектуру. double a[10][2]; int n, m; n = (int)(a+1); m = (int) a; n -= m;