Комбинаторные алгоритмы решения школьных задач по информатике

В ней отсутствующие  промежуточные 6х+3 заканчиваются суффиксом -иллиард (из нее мы заимствовали миллиард, который еще называется биллион).

Общий список чисел используемых в России представляю ниже:

Таблица1

Произношение чисел, идущих далее, часто различается.

Таблица2

• 10100 - гугол (число придумал 9-летний племянник американского математика Эдварда Каснера) 
• 10123 - квадрагинтиллион (quadraginta, XL)
• 10153 - квинквагинтиллион (quinquaginta, L)
• 10183 - сексагинтиллион (sexaginta, LX)
• 10213 - септуагинтиллион (septuaginta, LXX)
• 10243 - октогинтиллион (octoginta, LXXX)
• 10273 - нонагинтиллион (nonaginta, XC)
• 10303 - центиллион (Centum, C)

Дальнейшие названия могут быть получены либо прямым, либо обратным порядком латинских числительных (как правильно, не известно):

• 10306 - анцентиллион или центуниллион
• 10309 - дуоцентиллион или центдуоллион
• 10312 - трецентиллион или центтриллион
• 10315 - кватторцентиллион или центквадриллион
• 10402 - третригинтацентиллион или центтретригинтиллион

Я считаю, что наиболее правильным будет второй вариант  написания, так как он более соответствует  построению числительных в латинском  языке и позволяет избежать двухсмысленностей (например в числе трецентиллион, которое по первому написанию является и 10903 и 10312). 
Числа далее:

• 10603 - дуцентиллион (ducenti, CC)
• 10903 - трецентиллион (trecenti, CCC)
• 101203 - квадрингентиллион (quadringenti, CD)
• 101503 - квингентиллион (quingenti, D)
• 101803 - сесцентиллион (sescenti, DC)
• 102103 - септингентиллион (septingenti, DCC)
• 102403 - октингентиллион (octingenti, DCCC)
• 102703 - нонгентиллион (nongenti, CM)
• 103003 - миллиллион (или милиаиллион) (mille, M)
• 106003 - дуомилиаллион (duo milia, MM)
• 109003 - тремиллиаллион
• 1015003 - квинквемилиаллион (quinque milia, )
• 10308760 - дуцентдуомилианонгентновемдециллион
• 103000003 - милиамилиаиллион (decies centena milia, )
• 106000003 - дуомилиамилиаиллион
• 1010100 - гуголплекс

3.2. Сравнение больших чисел

Первым делом была выбрана структура класса больших  целых чисел. Так как число может быть как положительным, так и отрицательным было введено символьное поле, отвечающее за знак числа «+» или «–». Само число решено было записывать с помощью очереди с двусторонним доступом (deque) – контейнер из стандартной библиотеки шаблонов (STL). Очередь представляет собой динамический массив с множеством стандартных методов для его обработки. «Цифру» каждого разряда большого числа мы будем помещать в соответствующую ячейку массива. Например, число 12345, записанное с помощью deque<int> mas; будет выгледеть как набор элементов этого массива: mas[0] = 1, mas[1] = 2, mas[2] = 3, mas[3] = 4, mas[4] = 5. Также класс будет содержать некоторое количество методов, для решения поставленных задач. Класс будет иметь название BigInteger. Структура класса изображена на рисунке 3.1.

Рис. 3.1. Схема класса BigInteger

Далее перешли к разработке методов класса. Сначала для непосредственной работы с большими числами были реализованы  методы для чтения числа из консоли  и печати в консоль – chtenie() и vector_print(BigInteger) соответственно.

Метод chtenie() считывает в виде строки данные введенные в консоль. Затем проверяет первый символ строки на наличие знака «–». Потом посимвольно, используя вспомогательную строку, содержащую цифры («0123456789»), заносит каждую цифру в конец очереди-массива. На выходе мы получаем большое число, содержащее знак «», либо «–». Также в методе используется вспомогательный метод dell_null(BigInteger), который возвращает число, удаляя впереди стоящие ничего не значащие нули (т.е. 00123 –> 123).

Метод vector_print(BigInteger) выполняет печать в консоль числа, предварительно задействовав, описанный выше вспомогательный метод dell_null(BigInteger). Сначала происходит печать знака числа, затем, используя цикл, выполняется печать каждого элемента очереди-массива. Результаты работы методов представлены на рисунке 3.2.

Рис. 3.2. Ввод-вывод большого положительного и отрицательного числа в консоль

Затем был реализован метод сложения двух больших чисел summa (BigIneger, BigInteger). Сначала метод проверяет знаки переданных ему чисел, если знаки разные, он, немного модифицируя знаки, передает числа методу, вычисляющему разность двух больших чисел, речь о котором пойдет дальше. Если же знаки чисел одинаковые, непосредственно происходит операция их сложения. Принцип основан на сложении «столбиком». Находим «длину» минимального по разрядам числа, затем складываем поразрядно числа в пределах этой «длины», добавляя 1, если сумма на предыдущем шаге была > 9, находим остаток от деления полученного числа на 10 (int % 10) и записываем его в разряд, над которым выполнялась операция. После того, как разряды у одного из чисел закончатся, «добиваем» результирующее число цифрами из оставшихся разрядов большего числа. Естественно, чтобы произвести операцию с первым разрядом, нужно обратиться к последнему элементу нашей очереди массива. Пример сложения представлен на рисунке 3.3.

Рис. 3.3. Операция сложения

Следующей операцией  над большими числами стала операция вычитания, представленная методом rasnost (BigInteger, BigInteger). Вначале метод проверяет знаки переданных ему чисел, если знаки чисел равные (с учетом знака разности), то метод передает числа методу summa (BigInteger, BigInteger). Например, 12 – (-7). Метод передаст 12 и 7 для обработки методу summa (BigInteger, BigInteger). Если знаки чисел разные, то происходит операция вычитания. Принцип основан на вычитании «столбиком». Находим число с меньшим количеством разрядов (меньшей «длиной»), ставим его вторым. И начинаем поразрядно вычитать. При этом, если в разряде первого числа значение больше, чем в разряде второго числа, прибавляем к разности этих чисел 10. Но на следующем шаге вычитаем 1 из следующего полученного результата поразрядного вычитания. Выполняем эти действия, пока не закончатся разряды наименьшего числа, затем «добиваем» результирующее число цифрами из оставшихся нетронутыми разрядов большего числа. Пример вычитания представлен на рисунке 3.4.

Рис. 3.4. Операция вычитания

После того, как были реализованы  операции сложения и вычитания, перешли к написанию операции умножения, которую выполняет метод proisvedenie (BigInteger, BigInteger). Также в его основе лежит принцип умножения «столбиком». Выбираем одно из больших чисел, и поэтапно умножаем числа из каждого разряда этого большого числа, на другое большое число. В результате на каждом шаге у нас получаются «промежуточные» большие числа, суммируя которые с помощью описанного выше метода summa (BigInteger, BigInteger) мы получаем необходимый нам результат. При этом не забываем в зависимости от разряда множителя «добивать» начальные разряды «промежуточных» больших чисел нулями. Как и в предыдущих операциях при поразрядном перемножении в результат мы записываем остаток от деления на 10 и, если результат поразрядного перемножения больше либо равен 10, то на следующем шаге перемножения мы прибавляем число равное целой части от деления предыдущего результата на 10. Также для ускорения процесса перемножения были выделены особые случаи – умножение на 0 и на 1. Пример перемножения двух больших чисел представлен на рисунке 3.5.

Рис. 5.5. Операция умножения

После реализации метода перемножения двух больших чисел  операции возведения числа в степень  и операция взятия факториала числа  не представляют большой трудности, так как могут быть выражены через умножение. Метод stepen (BigInteget, int), представляющий операцию возведения в степень большого числа, принимает в качестве аргументов само большое число и целое число, задающее степень, в которую необходимо возвести большое число. Метод вызывает операцию перемножения числа на само себя в цикле, количество шагов которого равно заданной степени. После выполнения данного цикла получаем нужную нам степень большого числа. Метод factorial(BigInteger), представляющий операцию получения факториала большого числа, мог быть выполнен двумя способами: используя рекурсию или используя итерацию, т.е. цикл. Был выбран второй вариант, так как он более производительный и не требует повторного вызова метода factorial(BigInteger), что замедляло бы работу программы. Для перемножения здесь использовалось вспомогательное большое число, которое изначально приравнивалось к числу, факториал которого нужно было найти. Затем на каждом шаге итерации оно уменьшалось на 1. На каждом шаге это число умножалось на ранее полученный результат, т.е. получалась выражение вида N!=((N*N-1)*N-2*)…*1. После выполнения данного цикла получаем факториал заданного числа.

Рисунок 3.6. Вычисление факториала 1000

Построение проекта  осуществлялось в режиме Release. Технические характеристики компьютера, на котором выполнялись расчеты, представлены на рисунке 7.