计算阶乘|集2中的数字-yiteyi-C++库

给定一个整数n（可以非常大），求其阶乘中出现的位数，其中阶乘定义为，阶乘（n）=1*2*3*4*n和阶乘（0）=1 例如：

null

Input :  n = 1Output : 11! = 1, hence number of digits is 1Input :  5Output : 35! = 120, i.e., 3 digitsInput : 10Output : 710! = 3628800, i.e., 7 digitsInput : 50000000Output : 363233781Input : 1000000000Output : 8565705523

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们已经讨论了在 计算阶乘|集1中的数字 。但是，该解决方案无法处理n>10^6的情况那么，我们能改进我们的解决方案吗？对我们可以。我们可以用Kamenesky的公式来找到答案！

It approximates the number of digits in a factorial by :f(x) =    log10( ((n/e)^n) * sqrt(2*pi*n))Thus, we can pretty easily use the property of logarithms to,f(x) = n* log10(( n/ e)) + log10(2*pi*n)/2

就这样！我们的解决方案可以处理可以容纳在32位整数中的非常大的输入，除此之外。以下是上述理念的实施：

C++

                         // A optimised program to find the                       
                         // number of digits in a factorial                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns the number of digits present                       
                         // in n! Since the result can be large                       
                         // long long is used as return type                       
                         long                                     long                                     findDigits(                                     int                                     n)                       
                         {                       
                                                 // factorial of -ve number                       
                                                 // doesn't exists                       
                                                 if                                     (n < 0)                       
                                                 return                                     0;                       
           
                                                 // base case                       
                                                 if                                     (n <= 1)                       
                                                 return                                     1;                       
           
                                                 // Use Kamenetsky formula to calculate                       
                                                 // the number of digits                       
                                                 double                                     x = ((n *                                     log10                                     (n / M_E) +                       
                                                 log10                                     (2 * M_PI * n) /                       
                                                 2.0));                       
           
                                                 return                                     floor                                     (x) + 1;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 cout << findDigits(1) << endl;                       
                                                 cout << findDigits(50000000) << endl;                       
                                                 cout << findDigits(1000000000) << endl;                       
                                                 cout << findDigits(120) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // An optimised java program to find the                       
                         // number of digits in a factorial                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
                                                 public                                     static                                     double                                     M_E =                                     2.71828182845904523536                                     ;                       
                                                 public                                     static                                     double                                     M_PI =                                     3.141592654                                     ;                       
           
                                                 // Function returns the number of                       
                                                 // digits present in n! since the                       
                                                 // result can be large, long long                       
                                                 // is used as return type                       
                                                 static                                     long                                     findDigits(                                     int                                     n)                       
                                                 {                       
                                                 // factorial of -ve number doesn't exists                       
                                                 if                                     (n <                                     0                                     )                       
                                                 return                                     0                                     ;                       
           
                                                 // base case                       
                                                 if                                     (n <=                                     1                                     )                       
                                                 return                                     1                                     ;                       
           
                                                 // Use Kamenetsky formula to calculate                       
                                                 // the number of digits                       
                                                 double                                     x = (n * Math.log10(n / M_E) +                       
                                                 Math.log10(                                     2                                     * M_PI * n) /                       
                                                 2.0                                     );                       
           
                                                 return                                     (                                     long                                     )Math.floor(x) +                                     1                                     ;                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 System.out.println(findDigits(                                     1                                     ));                       
                                                 System.out.println(findDigits(                                     50000000                                     ));                       
                                                 System.out.println(findDigits(                                     1000000000                                     ));                       
                                                 System.out.println(findDigits(                                     120                                     ));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Pramod Kumar.                       

Python3

                         # A optimised Python3 program to find                       
                         # the number of digits in a factorial                       
                         import                                     math                       
           
                         # Returns the number of digits present                       
                         # in n! Since the result can be large                       
                         # long long is used as return type                       
                         def                                     findDigits(n):                       
                                   
                                                 # factorial of -ve number                       
                                                 # doesn't exists                       
                                                 if                                     (n <                                     0                                     ):                       
                                                 return                                     0                                     ;                       
           
                                                 # base case                       
                                                 if                                     (n <                                     =                                     1                                     ):                       
                                                 return                                     1                                     ;                       
           
                                                 # Use Kamenetsky formula to                       
                                                 # calculate the number of digits                       
                                                 x                                     =                                     ((n                                     *                                     math.log10(n                                     /                                     math.e)                                     +                       
                                                 math.log10(                                     2                                     *                                     math.pi                                     *                                     n)                                     /                                     2.0                                     ));                       
           
                                                 return                                     math.floor(x)                                     +                                     1                                     ;                       
           
                         # Driver Code                       
                         print                                     (findDigits(                                     1                                     ));                       
                         print                                     (findDigits(                                     50000000                                     ));                       
                         print                                     (findDigits(                                     1000000000                                     ));                       
                         print                                     (findDigits(                                     120                                     ));                       
                                   
                         # This code is contributed by mits                       

C#

                         // An optimised C# program to find the                       
                         // number of digits in a factorial.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                                 public                                     static                                     double                                     M_E = 2.71828182845904523536;                       
                                                 public                                     static                                     double                                     M_PI = 3.141592654;                       
           
                                                 // Function returns the number of                       
                                                 // digits present in n! since the                       
                                                 // result can be large, long long                       
                                                 // is used as return type                       
                                                 static                                     long                                     findDigits(                                     int                                     n)                       
                                                 {                       
                                                 // factorial of -ve number                       
                                                 // doesn't exists                       
                                                 if                                     (n < 0)                       
                                                 return                                     0;                       
           
                                                 // base case                       
                                                 if                                     (n <= 1)                       
                                                 return                                     1;                       
           
                                                 // Use Kamenetsky formula to calculate                       
                                                 // the number of digits                       
                                                 double                                     x = (n * Math.Log10(n / M_E) +                       
                                                 Math.Log10(2 * M_PI * n) /                       
                                                 2.0);                       
           
                                                 return                                     (                                     long                                     )Math.Floor(x) + 1;                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 Console.WriteLine(findDigits(1));                       
                                                 Console.WriteLine(findDigits(50000000));                       
                                                 Console.WriteLine(findDigits(1000000000));                       
                                                 Console.Write(findDigits(120));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal                       

PHP

                         <?php                       
                         // A optimised PHP program to find the                       
                         // number of digits in a factorial                       
           
                         // Returns the number of digits present                       
                         // in n! Since the result can be large                       
                         // long long is used as return type                       
                         function                                     findDigits(                                     $n                                     )                       
                         {                       
                                   
                                                 // factorial of -ve number                       
                                                 // doesn't exists                       
                                                 if                                     (                                     $n                                     < 0)                       
                                                 return                                     0;                       
           
                                                 // base case                       
                                                 if                                     (                                     $n                                     <= 1)                       
                                                 return                                     1;                       
           
                                                 // Use Kamenetsky formula to                       
                                                 // calculate the number of digits                       
                                                 $x                                     = ((                                     $n                                     * log10(                                     $n                                     / M_E) +                       
                                                 log10(2 * M_PI *                                     $n                                     ) /                       
                                                 2.0));                       
           
                                                 return                                     floor                                     (                                     $x                                     ) + 1;                       
                         }                       
           
                                                 // Driver Code                       
                                                 echo                                     findDigits(1).                                     ""                                     ;                       
                                                 echo                                     findDigits(50000000).                                     ""                                     ;                       
                                                 echo                                     findDigits(1000000000).                                     ""                                     ;                       
                                                 echo                                     findDigits(120) ;                       
                                   
                         // This code is contributed by nitin mittal                       
                         ?>                       

Javascript

                         <script>                       
           
                         // A optimised Javascript program to find the                       
                         // number of digits in a factorial                       
           
                         // Returns the number of digits present                       
                         // in n! Since the result can be large                       
                         // long long is used as return type                       
                         function                                     findDigits(n)                       
                         {                       
                                                 // factorial of -ve number                       
                                                 // doesn't exists                       
                                                 if                                     (n < 0)                       
                                                 return                                     0;                       
           
                                                 // base case                       
                                                 if                                     (n <= 1)                       
                                                 return                                     1;                       
           
                                                 // Use Kamenetsky formula to calculate                       
                                                 // the number of digits                       
                                                 let x = ((n * Math.log10(n / Math.E) +                       
                                                 Math.log10(2 * Math.PI * n) /                       
                                                 2.0));                       
           
                                                 return                                     Math.floor(x) + 1;                       
                         }                       
           
                         // Driver Code                       
                                   
                                                 document.write(findDigits(1) +                                     "<br>"                                     );                       
                                                 document.write(findDigits(50000000) +                                     "<br>"                                     );                       
                                                 document.write(findDigits(1000000000) +                                     "<br>"                                     );                       
                                                 document.write(findDigits(120) +                                     "<br>"                                     );                       
           
                         // This code is contributed by Mayank Tyagi                       
           
                         </script>                       

输出：

13632337818565705523199

参考资料： oeis。组织本文由 阿什图什·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章