Задача на работу с большими числами: их запись, хранение, умножение и сравнение.
Условия задачи
Рассмотрим все целочисленные комбинации a^b для 2 ≤ a ≤ 5 и 2 ≤ b ≤ 5:
22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125
Если их расположить в порядке возрастания, исключив повторения, мы получим следующую последовательность из 15 различных членов:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
Сколько различных членов имеет последовательность a^b для 2 ≤ a ≤ 100 и 2 ≤ b ≤ 100?
Описание работы программы
Для начала определимся с максимальными порядками значений, которые будут использоваться в программе.
100 в степени 100 будет представлять число с двумя сотнями нулей, поэтому вычисленные значения будем раскладывать на отдельные цифры и хранить в массивах соответствующей длины.
Далее, сколько будет значений? От 2 до 100 будет 99 чисел, таким образом 99 оснований в 99 степенях дадут 9801 значений.
Таким образом для хранения вычисленных значений решил использовать двумерный массив:
static unsigned char arr [1000][255] = {0};
static - нужен чтобы массив размещался не в стеке функции main (и не переполнял его), а непосредственно в памяти программы.
unsigned char - чтобы в ячейки массива можно было записывать значения от 0 до 255.
arr[0] - будет хранить длину массива.
Для промежуточных вычислений служит массив num1_arr.
Далее в программе вычисляются значения выражений от 2^2 до 100^100 и заносятся в массив arr, только если такого значения в нем нет.
Количество занесённых значений в массив подсчитывает счётчик cnt.
Работа функции, раскладывающей число на отдельные цифры
В ячейки массива последовательно заносятся остатки от деления числа на 10, после чего число делится на десять - уменьшается на порядок.
В нулевую ячейку массива заносится длина массива.
Работа функции перемножающей числа
Первое число передаётся в функцию уже в виде ссылки на массив, второе - в виде числа и его перед умножением необходимо также представить в виде массива.
Далее умножаем столбиком цифры из первого числа на цифры второго. Результаты заносим в промежуточный массив, цифры в нем после поразрядно складываем.
Последним пунктом определяем индекс последней цифры в массиве и заносим уточнённую длину массива в первую ячейку.
Описание прочих функций
compare_nums() - сравнивает поэлементно два массива. Поскольку в первой ячейке записана длина массива, то сразу отсекаются массивы разной длины.
copy_arr() - копирует элементы массива из одного в другой.
nullyfy_arr() - обнуляет массив - заполняет его нулями.
Ответ на задачу:
В коде есть подробные комментарии, если что непонятно - спрашивайте.
P.S. Изначальная цель блога - получить "фидбек" в комментариях, чтобы более опытные "кодеры" указывали мне на ошибки, советовали и всячески помогали в саморазвитии.
Также приглашаю всех на мой сайт)
На нем Вы можете посмотреть ответ на задачу Эйлера 29 (когда необходима лишь небольшая подсказка) и последний, самый быстрый вариант решения.
В общем, добро пожаловать на канал))