Вычисление больших факториалов в C++
Я понимаю, что это - классическая проблема программирования, и поэтому я хочу быть ясным, я не ищу код как решение, но ценил бы нажатие в правильном направлении. Я изучаю C++ и как часть процесса обучения, я делаю попытку некоторых проблем программирования. Я пытаюсь записать программу, которая имеет дело с числами до факториала 1 миллиарда. Очевидно, они будут огромным количеством и слишком большой для контакта с использованием нормальных арифметических операций. Любой признак относительно того, какое направление я должен войти в попытку решить этот тип проблемы, ценился бы.
Я попытался бы решить это, не пользуясь дополнительными библиотеками, если это возможно,
Спасибо
PS - проблемой является здесь http://www.codechef.com/problems/FCTRL
Вот метод, я раньше решал проблему, это было достигнуто путем чтения комментариев ниже:
Решение - номер 5 является простым множителем любого числа, заканчивающегося в нуле. Поэтому деля факториальное число на 5, рекурсивно, и добавляя частных, Вы получаете количество конечных нулей в факториальном результате
НАПРИМЕР, - Количество конечных нулей в 126! = 31
126/5 = 25 остатков 1
25/5 = 5 остатков 0
5/5 = 1 остаток 0
25 + 5 + 1 = 31
Это работает на любое значение, просто продолжайте делиться, пока частное не меньше чем 5
8 ответов
Смешал этот вопрос, не уверен, что я действительно понял правильно, но вот дедуктивное предположение:
первый вопрос - как вы получаете ноль на конец числа? Умножение на 10.
Как вы умножаете на 10? Либо умножение на 10 или на 2 х 5 ...
Итак, для X! Сколько у вас 10s и 2x5s ...?
(К счастью, 2 и 5 являются простыми числами)
Редактировать: вот еще один подсказка - я не думаю, что вам нужно сделать любой умножение. Дайте мне знать, если вам нужен еще один намек.
Это не хороший ответ на ваш вопрос, когда вы немного изменили его от того, что я изначально читал. Но я оставлю здесь здесь, чтобы продемонстрировать непрактичность фактически пытаться сделать расчеты основной грубой силой.
Один миллиард факториал будет вне досягаемости любой библиотеки Bignum. Такие цифры потребуют больше места для представления, чем почти кто-либо в памяти. Вам придется начать пейджинг чисел в хранилище, когда вы работаете над ними. Есть способы сделать это. Парень , который недавно рассчитал π до 2700 миллиардов мест , использовал такую библиотеку
Я думаю, что вы должны придумать способ решить проблему в псевдо-коде, прежде чем начать думать о C ++ или любом другом языке для этого значения. Природа вопроса, как некоторые указали некоторые, - это больше проблем с алгоритмом, чем проблема C ++. Те, кто предлагает поиск некоторой неясной библиотеки, указывает вам в направлении скользкого склона, потому что обучение программе изучает, как думать, верно? Найдите хороший текст анализа алгоритма, и он будет вам хорошо служить вам. В нашем отделе мы преподаем из CLRS текста.
Не используйте наивный метод. Если вам нужно рассчитать факториал, используйте быстрый алгоритм: http://www.luschny.de/math/factorial/fastefactorialfunctions.htm
Чтобы решить этот вопрос, как сказал Крис Джонсон, вы должны посмотреть на количество 0.
Факторы 10 будут 1,2,5,10 сама. Итак, вы можете пройти через каждую из N! И напишите их с точки зрения 2 ^ x * 5 ^ y * 10 ^ z. Откажитесь от других факторов чисел.
Теперь ответ будет Greeof (x, y) + z.
Одно интересное, что я учусь из этого вопроса, это всегда лучше хранить факториал числа в терминах простых факторов для легких сравнений.
На самом деле X ^ Y, есть простой способ, используемый в алгоритме RSA, который не помню. Я постараюсь обновить сообщение, если я найду один.
Чтобы начать вас, вы должны хранить номер в какой-то массиве, как std :: вектор (цифра для каждой позиции в массиве), и вам нужно найти определенный алгоритм, который рассчитывает факториал (может быть, в каком-то специализированном классе). ;)
Вам нужен «Большое число» пакет - либо один, который вы используете или один, вы пишете себе.
Я рекомендую сделать некоторые исследования в «Большие алгоритмы числа» . Вы захотите реализовать эквивалент C ++ java Bigdecimal .
Другой способ посмотреть на него использует функцию гамма . Вам не нужно умножать все эти значения, чтобы получить правильный ответ.
Подсказка: вам не может быть не нужно рассчитывать! Для того, чтобы найти количество нулей в конце N!