Задача 26: 2^n
Вывести в файл output.txt число 2^n, n<=10000, n - натуральное.
Входной файл input.txt в единственной строке содержит число n
Решение:
Наконец-то мы дошли до длинной арифметики! 2^10000 имеет порядка
3000 десятичных знаков, так что ни о каких extended'ах, а тем более
longint'ах речи быть не может.
Существует такое понятие - длинная арифметика - выполнение
арифметических операций в массиве (естественно, с потерями в
скорости, но что же делать). В нашем случае нам нужно реализовать
одно из простейших действий над длинными числами - умножение на 2.
Для надежности заведем массив длиной 4000, состоящий из элементов
типа byte. Их будет достаточно для хранения одной десятичной
цифры(можно хранить 2 и даже чуть больше десятичных цифр, но это
сопряжено с извращениями и усложнениями, так что не будем экономить
память, а будем экономить время и нервы). Обнулим массив и присвоим
4000 элементу значение 1 = 2^0. Затем в цикле от 1 до n будем
запускать процедуру умножения на 2.
Вы наверняка хорошо представляете процедуру умножения на 2 в
столбик. Здесь все точно также! Двигаясь от последнего элемента к
первому(он будет определяться динамически и в начальный момент
времени равен 4000), мы будем умножать его на 2 и, в случае если он
превысил 9, будем брать остаток от деления на 10, а результат
деления заносить в специальную переменную - так называемый флаг
переноса. Это можно ассоциировать с умножением в столбик, например
8*2 - 6 пишем, 1 в уме. Главное, не забыть прибавить значение
счетчика к следующему разряду.
Если цикл закончился, а флаг переноса не равен 0, то следует
уменьшить счетчик, указывающий на первую цифру числа(сначала он был
равен 4000), и присвоить элементу с номером счетчика значение флага
переноса. В принципе, можно было проходить весь массив от конца к
началу, но многократное бесполезное умножение 2 на 0 заметно снижает
скорость, что немаловажно.
Стоит заметить, что некоторые предпочитают записывать младшие
разряды числа в начале массива, но это непринципиально ни по размеру
памяти, ни по времени работы. Кому как удобнее.
Далее
ð
