алгоритм — C ++: комбинированные / мультимножественные функции (факториальное переполнение)

Я должен реализовать задачу, которая вычисляет комбинации и мультимножества из m элементов из набора из n элементов.
Формулы для них следующие:

введите описание изображения здесь

введите описание изображения здесь

Проблема в том, что факториал легко переполнить, так что в принципе, какие решения могут быть для этой проблемы?

Поскольку это подзадача проблемы в TopCoder, у меня есть следующие ограничения:

1) Программа должна быть написана на C ++.

2) Я не могу загрузить внешние библиотеки.

1

Решение

Вам не нужно рассчитывать 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, которые обычно представлены в виде массива символов или строки.

5

Другие решения

Факториалы — это довольно большие числа (они не вписываются в 64-битное слово). Так что вам нужно использовать bignums (произвольная точность арифметики), чтобы вычислить их в полном объеме. Рассмотреть возможность использования GMPlib для этой цели (или кода на языке и реализации, например Common Lisp с SBCL, что дает их изначально)

Смотрите также этот а также тот ответы на вопрос, очень похожий на ваш.

0

Вместо использования рекурсивного подхода для вычисления факториалов, которые могут привести к переполнению стека, используйте итеративный подход! Это может спасти вас от переполнения даже для больших чисел.

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector