Главная /
Основы программирования - обучения основам /
Оценить сверху время работы (т.е. количество выполнений тела цикла) алгоритма быстрого возведения в степень: дано: основание a и показатель степени n >= 0 надо: вычислить a в степени n вещ b, p; цел k; b := a; p := 1.0; k := n; цикл пока k > 0 | инв
Оценить сверху время работы (т.е. количество
выполнений тела цикла) алгоритма быстрого возведения в степень:
дано: основание a и показатель степени n >= 0
надо: вычислить a в степени n
вещ b, p; цел k;
b := a; p := 1.0; k := n;
цикл пока k > 0
| инвариант: bk p = an
| если k четное
| | то
| | k := k / 2;
| | b := b * b;
| | иначе
| | k := k - 1;
| | p := p * b;
| конец если
конец цикла
ответ := p;
вопрос
Правильный ответ:
Время работы не больше, чем
C·n,
где C — некоторая константа
(т.е. время пропорционально числу n).
Время работы не больше, чем
C·log2 n,
где C — некоторая константа
(т.е. время пропорционально количеству цифр в двоичной или
десятичной записи числа n).
Время работы не больше, чем
C·r, где C — некоторая константа,
r — квадратный корень из числа n
(т.е. время пропорционально квадратному корню из n).
Сложность вопроса
73
Сложность курса: Основы программирования - обучения основам
50
Оценить вопрос
Комментарии:
Аноним
Если бы не опубликованные решения - я бы не справился c этими тестами intuit.
28 сен 2020
Аноним
Гранд мерси за решебник по интуиту.
21 ноя 2019
Аноним
Спасибо за ответы по интуиту.
09 окт 2016
Другие ответы на вопросы из темы программирование интуит.
- # Выражение содержит числа, переменную x и знаки трех арифметических операций +, -, × (нет операции деления); переменная x может использоваться многократно. Выражение можно преобразовывать, пользуясь известными свойствами арифметических операций. Значение переменной x сообщается только после того, как выражение преобразовано в удобную для вычисления форму. Какой максимальной глубины стека достаточно, чтобы вычислить значение любого такого выражения с помощью стекового калькулятора (записывать промежуточные результаты на бумаге запрещено)?
- # На вход следующей программе передается последовательность целых чисел в диапазоне от 0 до 9, представляющая цифры десятичной записи целого числа n. Программа определяет, делится ли число n на 75 (символом процента '%' обозначается операция нахождения остатка от деления первого числа на второе): цел последовательность p; // Цифры числа n цел s, r, d; . . . s := 0; r := 0; встать в начало последовательности p; цикл пока есть непрочитанные элементы в посл-ти p | прочесть очередной элемент посл-ти p в (вых: d); | s := s + d; // s -- сумма цифр | r := (r % 10) * 10 + d; // r -- число из 2-х конец цикла // последних цифр ответ := ( // n делится на 75, когда s % 3 == 0 и // s делится на 3 и r % 25 == 0 // r делится на 25 ); В ней используются три вспомогательные переменные s, r, d. Можно ли упростить программу, использовав меньшее количество вспомогательных переменных? (Последовательность разрешается читать только один раз.)
- # Выполняется ли инвариант цикла в процессе выполнения тела цикла?
- # Может ли задача использовать объем виртуальной памяти, который превышает объем физической памяти компьютера?
- # Что содержат заголовочные, или h-файлы, в случае языка Си?