Разделение двух целых чисел Ulong дает неправильный результат

Я пишу программу для каталонского номера. Итак, вот формула для этого:

Это формула

Я решил использовать среднюю часть формулы, потому что остальные части слишком абстрактны для моих знаний (может быть, я слишком много спал на уроках математики). На самом деле моя программа отлично работает для n = 0;,n = 5;, n = 10; Но если я ввожу n = 15; - вот бум - выводится 2, когда должно быть 9694845. Итак, мой ребенок:

using System;
namespace _8_Numbers_of_Catalan
{
    class CatalanNumbers
    {
        static void Main()
        {
            Console.Write("n: ");
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine("Catalan({0})", n);
            //calculating the Catan number from the formula 
            // Catan(n) = [(2*n)!]/[(n+1)! * n!]
            Console.WriteLine((factorial(2 * n)) / (factorial(n + 1) * factorial(n)));
        }//finding the factorial
        private static ulong factorial(int n)
        {
            ulong fact = 1;
            for (int i = 1; i <= n; i++)
            {
                fact *= (ulong)i;
            }
            return fact;
        }
    }
}

Заранее спасибо за понимание, если что-то явно не так. Я новичок в программировании.


c# math factorial catalan
person Kadiyski    schedule 21.04.2015    source источник
comment
Используйте третью формулу, которая позволяет избежать переполнения, которое происходит со второй формулой. Поищите в википедии, число PI похоже на SIGMA, но только с умножением. Переводит 1:1 в код.   -  person Peter - Reinstate Monica    schedule 21.04.2015
comment
Это наивная реализация факториала. Это будет неточно и неэффективно. Лучше пойти с функцией lngamma и мемоизацией. Интересно, существует ли рекурсивное отношение C(n) и C(n-1)   -  person duffymo    schedule 21.04.2015

Ответы (2)


arrow_upward
4
arrow_downward

Это потому, что вы выполняете их вычисление, используя целочисленные переменные, которые могут содержать не более 64 бит.

Ваш вызов factorial(15 * 2) равен 30!, что приведет к значению

265,252,859,812,191,058,636,308,480,000,000

Гораздо больше, чем умещается в 64-битной целочисленной переменной:

18,446,744,073,709,551,615 (0xFFFFFFFFFFFFFFFF).

Возможные варианты: использовать тип System.Numerics.BigInteger ( медленно) или double (до максимального значения 1.7976931348623157E+308). Это означает, что вы потеряете некоторую точность, которая может иметь значение, а может и не иметь.

Другой вариант, который у вас есть, — использовать алгоритм для аппроксимации значения больших факториалов с помощью асимптотической аппроксимации, такой как алгоритм Шёнхаге-Штрассена, используемый Mathematica.

Вы также можете проверить некоторые существующие онлайн-ресурсы для расчета больших факториалов в .NET.

В качестве последнего, но не менее важного варианта (и я не проверял его полностью), мне кажется вероятным, что существуют определенные алгоритмы, которые позволяют вам вычислить (или приблизить с достаточной точностью) Catalan number.

person Alex    schedule 21.04.2015
comment
Было бы неплохо, если бы голосующий мог прокомментировать, что, по его/ее мнению, не так с этим ответом, чтобы у меня была возможность соответствующим образом его улучшить. - person Alex; 21.04.2015

arrow_upward
3
arrow_downward

для этого вы должны использовать System.Numerics.BigInteger. (добавьте System.Numerics в качестве ссылки в свой проект).

private static BigInteger factorial(int n)
{
     BigInteger fact = 1;
     for (int i = 1; i <= n; i++)
     {
        fact *= i;
     }
     return fact;
 }

 // output: 9694845
person stefankmitph    schedule 21.04.2015