Степень - 2

Прежде чем решать данную задачу и читать ее разбор, рекомендуется решить более простую задачу "A*B" и ознакомиться с ее решением.

При решении данной задачи возникает потребность в написании, так называемой, длинной арифметики. Нетрудно догадаться, что числа, полученные в результате вычислений, не уместятся ни в одном из стандартных целочисленных типов данных.

Для решения проблемы хранения таких чисел можно использовать массив цифр этих чисел, например, пусть у нас есть массив int D [80], в элементе D [0] будем хранить длину нашего числа (количество разрядов), в остальных же D [1] - D [79] будут храниться сами разряды.

Возводить число А в степень В мы будем простым умножением числа А на само себя В раз. При этом, имея в массиве D разряды нашего числа мы как будто представляем его в виде D [1] * 10^n + D [2] * 10^(n - 1) + ... + D [n]; (далее наше "длинное число" будем обозначать просто D). Тогда A * D = A * D [1] * 10^n + A * D [2] * 10^(n - 1) + ... + A * D [n];

Если полученное произведение A * D [i] (i - какой - то произвольный разряд) будет превышать 10, то необходимо осуществить перенос в D [i - 1] разряд. Множитель 10^i используется для канонического разложения числа. Так как мы храним число в виде массива его цифр, то нам просто необходимо умножить все разряды числа D на А и проверить на наличие переполнения разрядов (когда в разряде хранится число, большее 10), если переполнение произшло, то осуществить перенос в старший разряд. Если переполнение происходит в старшем разряде, то аналогично осущесвляется перенос и увеличивается длина числа D.

На первый взгляд все понятно и просто, но имеет место большое количество "подводных камней". Первым таким камнем является, то что наше число будет "расти влево": предположим, было у нас число 823, мы умножили его на 5 и получили 4115, результат состоит уже из четырех разрядов. Если хранить число так, как мы предполагали, то D [1] = 8 (старший разряд). После умножения на 5 в старшем разряде будет число 40 (D [1] = 40). Согласно нашему способу представления "длинных чисел" мы должны произвести перенос в D [0] разряд, но в D [0] хранится длина всего числа, а в область отрицательных значений индексы массива уходить не могут (в отличие от Turbo Pascal), поэтому в случае переноса мы просто потеряем наше число, что приведет к неверному результату.

Решить эту проблему можно, причем очень простым способом: мы будем хранить число задом-наперед! Нет, это не опечатка, именно в обратном порядке! Тогда наше число будет "расти вправо" и перенос будем делать уже в D [i + 1] разряд. Например, исходное число равно 823, запишем его в обратном порядке:

           D [0]|D [1]|D [2]|D [3]|  Разряд
                |     |     |     |
             3  |  3  |  2  |  8  |  значение

После умножения на 5 получим

           D [0]|D [1]|D [2]|D [3]|  Разряд
                |     |     |     |
             3  | 15  | 10  | 40  |  значение

Теперь делаем перенос: из младшего разряда D [1] единицу переносим в D [2], тогда D [1] = 5, D [2] = 11

Двигаемся по массиву дальше: из разряда D [2] единицу переносим в D [3], тогда D [2] = 1, D [3] = 41

Теперь возникло переполнение в старшем разряде, а значит, длина полученного числа будет больше, чем исходного; аналогично делаем перенос: четверку переносим в D [4], тогда D [4] = 4, D [3] = 1, при этом не забываем увеличить длину числа D [0] ++;

В результате получаем:

            D [0]|D [1]|D [2]|D [3]|D [4]|  Разряд
                 |     |     |     |     |
              4  |  5  |  1  |  1  |  4  |  значение

Число 4115 хранится в массиве D в виде цифр в обратном порядке, а значит, можно производить дальнейшее умножение.

Для повышения скорости работы алгоритма можно хранить по несколько цифр в одном элементе массива. Например по 4 (позже будет объяснен наш выбор). Тогда, например, число 454154613 будет представлено в виде:

            D [0]|D [1] |D [2] |D [3]|  Разряд
                 |      |      |     |
              3  | 4631 | 5415 |  4  |  значение

Что значительно сокращает количество элементов массива, а значит, нам придется выполнить намного меньше операций умножения, что также ускоряет процесс вычисления. Сразу же следует рассмотреть число 12240212: разбиваем по 4 цифры: D [1] = 0212 = 212, D [2] = 1224. Проблема заключается в том, что при выводе элементов массива мы получим: 1224212, тем самым мы потеряем нуль, который был на первом месте в элементе D [1].

Так как мы храним по 4 цифры в одном элементе массива, то при печати всех элементов, кроме последнего (старшего разряда), мы должны в случае необходимости (если длина числа в элементе меньше 4) дополнять числа ведущими нулями так, чтобы их длина равнялась 4. Другими словами, мы переходим к представлению чисел в системе счисления по основанию 10000.

[Обсуждение] [Все попытки] [Задача]