ncr in c (комбинации)

-1

Я пытаюсь вычислить ncr (комбинации) в c, используя dp. Но он терпит неудачу при n = 70. Может ли кто-нибудь помочь?ncr in c (комбинации)

unsigned long long ncr(int n , int r) 
{ 
unsigned long long c[1001]; 
int i=1; 
c[0]=1; 
for(i=1; i<=r; i++) 
    c[i]= ((unsigned long long) (c[i-1]) * (unsigned long long)(n-i+1))%(unsigned long long) (1000000007)/ (unsigned long long)(i); 
return c[r]; 
}

Основная идея заключается в NCR = ((п-г + 1)/г) * пс (г-1)

источник

2013-02-09 bhavneet

Промежуточный продукт (unsigned long long) (c[i-1]) * (unsigned long long)(n-i+1) очень большое число, и переполнен 64 бит слово.

Возможно, вы захотите использовать bignums. Я настоятельно рекомендую не разрабатывать собственные функции бонуса (например, умножение и деление бигномов), потому что это деликатный алгоритмический субъект (вы все равно можете получить ученого кандидата).

Предлагаю использовать некоторую существующую библиотеку бигума, такую как GMP.

Некоторые языки или реализации (в частности, SBCL для Common Lisp) предлагает собственные бигнемные операции. Но стандартные C или C++ этого не делают.

источник

2013-02-09 11:58:34

Извините, я использовал следующее в действительном коде (взял mod of ans): c [i] = ((unsigned long long) (c [i-1]) * (без знака длинный) (n-i + 1))% (unsigned long long) (1000000007)/(без знака длинный) (i); – bhavneet

Но вам все равно нужно вычислить C (n, p) в бигномах, а затем взять модуль «1000000007», который является большим простым числом (поэтому все цифры или биты C (n, p) необходимы для получения модуля). Вы действительно не можете избежать bignums в вашем случае .... –

@bhavneet Чтобы вычислить 'nCr% p', вы не должны делить на' i', вы должны умножаться с его модульным обратным. Также [здесь] (http://stackoverflow.com/a/10862881/1011995). –

-1

Сделайте деление до умножения. a * b/c = (a/c) * b, где вторая лучше для переполнения, которая кажется вашей проблемой.

источник

2013-02-09 12:08:52 blackmath

, если u означает c [i] = (((unsigned long long) (c [i-1])/(unsigned long long) (i)) * (unsigned long long) (n-i + 1))% (unsigned long long) (1000000007); его все еще не работает – bhavneet

Я не отлаживал его, все же вам нужно сделать это с помощью rec, гораздо лучше и читабельнее, на мой взгляд. она проходит для значений n> = 71? – blackmath

Конечным результатом является целое число, которое не означает, что каждый промежуточный фактор в вашем конкретном порядке построения его является целым числом. – vonbrand

ncr in c (комбинации)

ответ

Смежные вопросы