алгоритм — C ++: комбинированные / мультимножественные функции (факториальное переполнение)
Я должен реализовать задачу, которая вычисляет комбинации и мультимножества из 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, чтобы избежать переполнения и определить, как + Оператор работает для BigIntegers, которые обычно представлены в виде массива символов или строки.
Другие решения
Факториалы — это довольно большие числа (они не вписываются в 64-битное слово). Так что вам нужно использовать bignums (произвольная точность арифметики), чтобы вычислить их в полном объеме. Рассмотреть возможность использования GMPlib для этой цели (или кода на языке и реализации, например Common Lisp с SBCL, что дает их изначально)
Смотрите также этот а также тот ответы на вопрос, очень похожий на ваш.
Вместо использования рекурсивного подхода для вычисления факториалов, которые могут привести к переполнению стека, используйте итеративный подход! Это может спасти вас от переполнения даже для больших чисел.