1. Какие преимущества и недостатки имеет алгоритм «решето Эратосфена» по сравнению с проверкой каждого числа на простоту?
Преимущества алгоритма «решето Эратосфена» включают его высокую эффективность для нахождения всех простых чисел до определённого предела, так как его сложность составляет O(n log log n). Алгоритм проходит по каждому числу только один раз, что упрощает его реализацию. Однако алгоритм требует значительного объёма памяти, равного O(n), что делает его неподходящим для больших пределов. Проверка каждого числа на простоту путём деления на предыдущие числа менее эффективна (O(n√n)), но она требует гораздо меньше памяти и подходит для проверки отдельных чисел.
2. В каких случаях необходимо применять «длинную арифметику»?
Длинная арифметика применяется, когда нужно работать с числами, превышающими диапазон стандартных типов данных. Это необходимо в задачах криптографии, научных расчётах с большими точностями, вычислении факториалов больших чисел или моделировании физических процессов.
3. Какое максимальное число можно записать в ячейку размером 64 бита? Рассмотрите варианты хранения чисел со знаком и без знака.
Для числа без знака (unsigned): Максимальное значение равно 2 в степени 64 минус 1, то есть 18446744073709551615.
Для числа со знаком (signed): Максимальное положительное значение равно 2 в степени 63 минус 1, то есть 9223372036854775807. Минимальное отрицательное значение равно минус 2 в степени 63, то есть минус 9223372036854775808.
4. Можно ли использовать для хранения «длинного» числа символьную строку? Оцените достоинства и недостатки такого подхода.
Да, можно. Достоинства такого подхода включают простоту реализации и отсутствие ограничений на длину числа. Однако это увеличивает объём памяти, так как каждая цифра занимает больше места, чем в числовом представлении, и усложняет выполнение операций.
5. Почему неудобно хранить «длинное» число, записывая первую значащую цифру в начало массива?
Такой подход требует постоянного сдвига всех элементов массива при выполнении арифметических операций, что снижает их скорость. Удобнее хранить младшие разряды в начале массива, чтобы избежать частых сдвигов.
6. Сколько разрядов десятичной записи числа можно хранить в одной 16-битной ячейке?
Максимальное число, которое можно записать в 16 бит, равно 2 в степени 16 минус 1, то есть 65535.
Чтобы найти количество десятичных разрядов, нужно взять десятичный логарифм. Берём целую часть логарифма 10 от 65535 и добавляем 1. Получается 5.
Таким образом, в 16-битной ячейке можно хранить до 5 десятичных разрядов.
7. Объясните, какие проблемы возникают при выводе длинного числа. Как их можно решать?
Проблемы включают необходимость преобразования разрядов в строку и корректного вывода, а также возможное переполнение буфера. Решение состоит в последовательном объединении разрядов в строку и корректной обработке ведущих нулей.
*8. Предложите способ вывода «длинного» числа без использования возможностей функции format.
Для вывода длинного числа можно пройти по массиву, содержащему его разряды, начиная с самого старшего, и последовательно формировать строку, исключая ведущие нули. Например: Копировать код def print_long_number(digits): result = "" for digit in reversed(digits): result += str(digit) print(result.lstrip("0"))
*9. Предложите алгоритм поиска целого кубического корня из целого числа.
Если x больше или равно нулю, установить low равным 0, а high равным x. Если x меньше нуля, установить low равным x, а high равным 0.
Пока low меньше или равно high: a) Вычислить середину: mid равно (low плюс high) делённое на 2. b) Посчитать куб числа mid: cube равно mid умножить на mid умножить на mid. c) Сравнить cube с x:
Если cube равно x, вернуть mid. Если cube меньше x, установить low равным mid плюс 1. Если cube больше x, установить high равным mid минус 1. Когда цикл завершён, вернуть high.
def integer_cube_root(x): low, high = (0, x) if x >= 0 else (x, 0) while low <= high: mid = (low + high) // 2 cube = mid ** 3 if cube == x: return mid elif cube < x: low = mid + 1 else: high = mid - 1 return high
Пример: Для x = 27 алгоритм возвращает 3. Для x = -64 алгоритм возвращает -4.