Я должен реализовать задачу, которая вычисляет комбинации и мультимножества из m элементов из набора из n элементов. Формулы для них следующие:
Проблема в том, что с факториалом легко переполниться, так что в основном какие решения могут быть для этой проблемы?
Поскольку это подзадача проблемы в TopCoder, у меня есть следующие ограничения:
1) Программа должна быть написана на C++.
2) Я не могу загружать внешние библиотеки.
Вам действительно не нужно вычислять n! напрямую, что может легко привести к переполнению. С
C(n,m) = C(n-1, m-1) + C(n-1,m)
C(n,0) = C(n,n) =1
Вы можете создать таблицу размером (n+1,m+1) и использовать динамическое программирование для построения таблицы снизу вверх.
Алгоритм псевдокода может понравиться следующим:
for i ← 0 to n do // fill out the table row wise
for j = 0 to min(i, m) do
if j==0 or j==i then C[i, j] ← 1
else C[i, j] ← C[i-1, j-1] + C[i-1, j]
return C[n, m]
Если вы объявите c(n,m) длинным двойным, а n не таким большим, этот способ должен работать. В противном случае вам нужно определить свой собственный класс BigInteger, чтобы избежать переполнения, и определить, как оператор + работает с BigInteger, которые обычно представлены в виде массива символов или строки.
←.
- person Peter Wood; 28.03.2013
Факториалы — довольно большие числа (они не помещаются в 64-битное слово). Поэтому вам нужно использовать bignums (арифметика произвольной точности), чтобы вычислить их полностью. Рассмотрите возможность использования для этой цели GMPlib (или кода на языке и реализации, например Common Lisp с SBCL, что дает их изначально)
См. также это и это ответы на вопрос, очень похожий на ваш.
Вместо использования рекурсивного подхода для вычисления факториалов, который может привести к переполнению стека, используйте итеративный подход! Это может спасти вас от переполнения даже для больших чисел.
