Главная /
Основы программирования - обучения основам /
Оценить сверху время работы (т.е. количество выполнений тела цикла) алгоритма приблизительного вычисления логарифма: дано: x > 0, a > 1, ε > 0 надо: вычислить loga x с точностью ε вещ y, z, t; y := 0.0; z := x; t := 1.0; цикл пока |t| >= ε или
Оценить сверху время работы (т.е. количество
выполнений тела цикла) алгоритма
приблизительного вычисления логарифма:
дано: x > 0, a > 1, ε > 0
надо: вычислить loga x с точностью ε
вещ y, z, t;
y := 0.0; z := x; t := 1.0;
цикл пока |t| >= ε или z <= 1.0/a или z >= a
| инвариант: ay * zt = x
| если z >= a
| | то
| | z := z/a; y := y + t;
| иначе если z <= 1.0/a
| | то
| | z := z*a; y := y - t;
| иначе
| | z := z*z; t := t/2.0;
| конец если
конец цикла
ответ := y;
вопрос
Правильный ответ:
Время работы не больше, чем
C·log2 [x+1],
где C — некоторая константа,
[x+1] — целая часть числа x+1
(т.е. время пропорционально количеству цифр
в двоичной или десятичной записи
целой части числа x).
Время работы не больше, чем
C·log2 [x+1]·log2 (1/ε),
где C — некоторая константа, а квадратные скобки
обозначают целую часть.
Иначе говоря, время пропорционально количеству цифр
в двоичной или десятичной записи
целой части x, умноженному на требуемое количество значащих
цифр в дробной части результата.
Время работы не больше, чем
C·log2 [x+1] + log2 (1/ε),
где C — некоторая константа, а квадратные скобки
обозначают целую часть. Иначе говоря,
время пропорционально сумме количества цифр
в двоичной или десятичной записи
целой части x и требуемого количества значащих
цифр в дробной части результата.
Сложность вопроса
89
Сложность курса: Основы программирования - обучения основам
50
Оценить вопрос
Комментарии:
Аноним
Зачёт всё. Лечу отмечать отмечать халяву с тестами интуит
16 июн 2020
Другие ответы на вопросы из темы программирование интуит.
- # В операционной системе MS Windows файл "tmp.dat" создается в результате выполнения следующего фрагмента программы: int a[3]; int i; FILE *f = fopen("tmp.dat", "wt"); a[0] = 1; a[1] = 10; a[2] = 100; for (i = 0; i < 3; ++i) { fprintf(f, "%d\n", a[i]); } fclose(f); Чему равен размер файла "tmp.dat" в байтах?
- # Даны очередь и стек элементов одного и того же типа. Можно ли написать программу, которая удаляет из очереди предпоследний элемент и не меняет порядка остальных элементов? При этом разрешается использовать стек как вспомогательную структуру данных; другими структурами (за исключением простых переменных) пользоваться запрещено.
- # Чему равен минимум пустой последовательности целых чисел?
- # Диаметром множества вещественных чисел называется максимум из абсолютных величин попарных разностей его элементов. Рассмотрим функцию F, которая последовательности вещественных чисел ставит в соответствие диаметр множества ее элементов. Какая из приведенных ниже функций на последовательностях является индуктивным расширением функции F?
- # Указать, чему будет равно значение переменной n в результате выполнения следующего фрагмента программы: int n = 33; switch (n % 4) { case 1: n += 3; case 2: n += 2; case 3: ++n; break; default: ++n; }