Comparer deux factorielles sans calculer

Question

Est-il possible de comparer ce qui factorielle du nombre est plus élevé chez les deux nombres sans calcul?
Le scénario est je suis entrain de créer une application console c# qui prend deux factorielle intrants, comme la

123!!!!!!
456!!!  

tout ce que je veux faire, c'est de comparer ce qui factorielle valeur est plus grande que les autres, le morceau de code que j'ai fait est

try
{
    string st = Console.ReadLine();
    Int64 factCount = 0;
    while (st.Contains('!'))
    {
       factCount = st.Where(w => w == '!').Count();
       st = st.Replace('!', ' ');

    };
    decimal result = 1 ;
    for (Int64 j = 0; j < factCount; j++)
    {
        UInt64 num = Convert.ToUInt64(st.Trim());
        for (UInt64 x = num; x > 0; x--)
        {
            result = result * x;
        }
    }
    if (factCount == 0)
    {
        result = Convert.ToUInt64(st.Trim());
    }


    string st2 = Console.ReadLine();
    Int64 factCount2 = 0;
    while (st2.Contains('!'))
    {
        factCount2 = st2.Where(w => w == '!').Count();
        st2 = st2.Replace('!', ' ');
    };
    decimal result2 = 1;
    for (Int64 j = 0; j < factCount2; j++)
    {
        UInt64 num = Convert.ToUInt64(st.Trim());
        for (UInt64 x = num; x > 0; x--)
        {
            result2 = result2 * x;
        }
    }
    if (factCount2 == 0)
    {
        result2 = Convert.ToUInt64(st2.Trim());
    }

    if (result == result2)
    {
        Console.WriteLine("x=y");
    }
    else if (result < result2)
    {
        Console.WriteLine("x<y");
    }
    else if (result > result2)
    {
        Console.WriteLine("x>y");
    }
}
catch (Exception ex)
{
    Console.WriteLine(ex.Message);
    Console.ReadLine();
}

mais l'erreur que j'obtiens est
la valeur est trop grande ou trop petite pour les décimales
J'ai compris l'erreur, mais est-il possible de faire cela

S'il vous plaît suggérer que tout autre type de données qui accueillir valeur supérieure à virgule ou est-il un autre moyen de comparer ces factorielles

Après la mise en œuvre de @Bethsabée suggestion, je change un peu de mon code

    string st = Console.ReadLine();
    int factCount = 0;
    while (st.Contains('!'))
    {
       factCount = st.Where(w => w == '!').Count();
       st = st.Replace('!', ' ');

    };

    string st2 = Console.ReadLine();
    int factCount2 = 0;
    while (st2.Contains('!'))
    {
        factCount2 = st2.Where(w => w == '!').Count();
        st2 = st2.Replace('!', ' ');
    };

    int resultFactCount = factCount - factCount2;
    decimal result = 1;
    decimal result2 = 1;

    if (resultFactCount > 0)
    {

        for (Int64 j = 0; j < resultFactCount; j++)
        {
            UInt64 num = Convert.ToUInt64(st.Trim());
            for (UInt64 x = num; x > 0; x--)
            {
                result = result * x;
            }
        }
        if (factCount == 0)
        {
            result = Convert.ToUInt64(st.Trim());
        }
        UInt64 num1 = Convert.ToUInt64(st.Trim());
        if (result == num1)
        {
            Console.WriteLine("x=y");
        }
        else if (result < num1)
        {
            Console.WriteLine("x<y");
        }
        else if (result > num1)
        {
            Console.WriteLine("x>y");
        }
    }
    else
    {
        int resultFactCount1 = System.Math.Abs(resultFactCount);
        for (Int64 j = 0; j < resultFactCount1; j++)
        {
            UInt64 num = Convert.ToUInt64(st.Trim());
            for (UInt64 x = num; x > 0; x--)
            {
                result2 = result2 * x;
            }
        }
        if (factCount2 == 0)
        {
            result2 = Convert.ToUInt64(st2.Trim());
        }
        UInt64 num1 = Convert.ToUInt64(st.Trim());

        if (result2 == num1)
        {
            Console.WriteLine("x=y");
        }
        else if (result2 < num1)
        {
            Console.WriteLine("x<y");
        }
        else if (result2 > num1)
        {
            Console.WriteLine("x>y");
        }
    }   

Désolé de le dire mais encore 123!!! c'est tellement énorme que j'obtiens le même message d'erreur

---

Traditionnellement m!!...! avec n !s signifie m(m-n)(m-2n).... cependant, ici, est pris comme (...((m!)!)!...)!
Note de l'Alec, oui, je sais, c'est un malheureux la notation, mais vous voyez la définition conventionnelle est beaucoup plus utile (dans le domaine de la combinatoire, l'endroit où les factorielles venir) que celui que l'OP veut.
Je mettrais cela dans un commentaire, mais ce serait éclipsé par les autres et c'est tout à fait important.

Answer 1

Ici, a!! est défini comme (a!)!.

123!!!!!! est absolument gigantesque. Je pense que vous auriez besoin de plus de particules qu'il y a dans l'univers, si vous aviez à écrire à l'encre.

Vous ne pouvez donc comparer les numéros directement. Je conject qu'il n'y a pas un nombre de classe qui peut faire cela.

Ce que vous pouvez faire, c'est de considérer le quotient 123!!!!!! / 456!!!. Beaucoup de multiples doivent être similaires, de sorte que vous pouvez les annuler. Notez également que les ! annuler. C'est parce que x > y implique, et qui est impliqué par x! > y! où x et y sont des entiers positifs.

Finalement, vous atteignez un point où vous pouvez les évaluer comme étant inférieur ou supérieur à 1, le rendement de votre réponse.

Je peux vous dire sur l'inspection qu' 123!!!!!! est plus importante depuis 123!!! est plus grand que 456.

Answer 2

Contrairement aux autres réponses, vous pouvez le faire sans aucune approximation.

C'est ici :

 123 !!!!!! > 456 !!! 
 

signifie réellement

 123 !!!!! > 456 !!
123 !!!! > 456 ! 
 

et aussi

 123 !!! > 456  
 

Il suffit donc de prouver ce qui précède. C’est simple, car vous avez au moins un opérande qui peut tenir dans un UInt64

Donc, cela devrait vous donner quelque chose comme ça:

 public class Program
{
    static bool LeftIsGreaterThanRightSide(UInt64 leftSide, int leftSidefactCount, UInt64 rightSide)
    {
        try
        {
            checked // for the OverflowException
            {
                UInt64 input2 = leftSide;
                int factCount = leftSidefactCount;
                UInt64 result = 1;

                for (Int64 j = 0; j < factCount; j++)
                {
                    UInt64 num = input2;
                    for (UInt64 x = num; x > 0; x--)
                    {
                        result = result * x;
                    }
                }

                // None of the operand are great or equal than UInt64.MaxValue
                // So let's compare the result normaly
                return result > rightSide; 
            }
        }
        catch (OverflowException)
        {
            // leftSide overflowed, rightSide is a representable UInt64 so leftSide > rightSide ; 
            return true; 
        }
    }


    static void Main()
    {
        String input1 = Console.ReadLine();
        String input2 = Console.ReadLine();

        int fact1Count = input1.Count(c => c == '!');
        int fact2Count = input2.Count(c => c == '!');

        UInt64 x = Convert.ToUInt64(input1.Replace("!", String.Empty).Trim());
        UInt64 y = Convert.ToUInt64(input2.Replace("!", String.Empty).Trim());

        x = x == 0 ? 1 : x ; // Handling 0 !
        y = y == 0 ? 1 : y; 

        if (fact1Count > fact2Count)
        {
            fact1Count = fact1Count - fact2Count;
            Console.WriteLine(LeftIsGreaterThanRightSide(x, fact1Count, y) ? "x > y" : "x <= y");
        }
        else
        {
            fact2Count = fact2Count - fact1Count;
            Console.WriteLine(LeftIsGreaterThanRightSide(y, fact2Count, x) ? "y > x" : "y <= x");
        }

        Console.ReadLine();
    }


}
 

Answer 3

Pour les chiffres donnés, en supposant qu' 456!!! moyen ((456!)!)! nous avons

  123!!!!!! == (123!!!)!!!

et

  123!!! >>> 456 // >>> stands for "much, much...much larger", ">>" is not enough 

même 123! (ce qui est 1.2e205) beaucoup plus que juste 456

Pour estimer les factorielles réelle de ces valeurs, nous allons utiliser l'approximation de Stirling

https://en.wikipedia.org/wiki/Stirling%27s_approximation

c'est à dire

  ln(n!) == n * ln(n) - n
  lg(n!) == ln(n!)/ln(10) == n * ln(n) / ln(10) - n / ln(10) == n * lg(n) - n / ln(10)
      n! == n ** n / exp(n)

Donc, ((456!)!)! est d'environ

  lg(456!)       == 1014
  lg((456!)!)    == 1e1014 * 1014- 1e1014/ln(10) == 1e1017
  lg(((456!)!)!) == 1e(1e1017) 
     ((456!)!)!  == 1e(1e(1e1017))

ce qui est extrêmement grand nombre (note triple élévation à la puissance) et c'est pourquoi on ne peut pas être représenté comme naïf BigInteger de la valeur.

Answer 4

Ce devrait être facile:

Comme d'autres l'ont dit, vous pouvez supprimer tous les "!", car x > y <==> x! > y!

Votre programme aura essentiellement pour prouver qu'une factorielle (123!!!) est plus grand qu'un numéro ordinaire. Vous pouvez résoudre ce problème avec une sortie rapide de la boucle. Lors du calcul de la factorielle, vous pouvez revenir dès que le produit est plus grand que la 456, depuis une factorielle grandira toujours avec des itérations supplémentaires.

// While string parsing check if one number equals 0 and has at least
// one "!" - if yes set its value to 1 ( because 0! = 1! = 1 )

int x = 123;
int y = 456;
int numberOfFactorials = 3;

try
{
    for( int i = 0; i < numberOfFactorials; ++i )
    {
        for ( int j = x-1; j > 0; --j )
        {
            x *= j;
            // This quick exit will return after one iteration
            // because 123*122 > 456
            if ( x > y ) return "x is bigger than y";
        }
    }

    return x == y ? "gosh they are the same!"
                  : "x is smaller than y";
}
catch( OverflowException e )
{
   return "x Overflowed so it is bigger than y!";
}

Vous pouvez également utiliser BigInteger avec cette Méthode si vous souhaitez analyser encore plus grand nombres pour l'Entrée des Paramètres.

Answer 5

Comme d'autres ont dit, 123!!!!!! et 456!!! sont tout simplement trop grand pour être représenté par un ordinateur, et une comparaison du type x!! <=> y! réduit de x! <=> y.

Une fois que vous obtenez le nombre minimum d' ! (coupe de la chaînes de caractères), vous pouvez évaluer les opérandes. L'un des numéros sera commune entier (pas factorielle), donc pas de travail ici. Les autres ont au moins une factorielle, sinon la comparaison est trivial.

Supposons que la comparaison est - x! <=> y (un factorielle). Si x >= y, vous avez terminé. Si x < y, évaluer x! et de comparer.

Supposons que la comparaison est - x!! <=> y (deux factorielles). En tabulant les valeurs les plus faibles:

1!! = 1! = 1
2!! = 2! = 2
3!! = 6! = 720
4!! = 24! = 620,448,401,733,239,439,360,000
5!! = 120! = about 6.6895 * 10^198
6!! = 720! = about 2.6012 * 10^1746

Donc, pour sur tout y, x > 4 entraînera x!! > y. Pour x <= 4, évaluer x!! et de comparer.

Pour plus d'factorielles, rappelez-vous que x!!! = (x!)!!, évaluer x!, et l'utilisation de l'étape(s) ci-dessus.