如何编写程序来找到任何自然数的阶乘？
问问题
48247 次
19 回答
38
这将适用于正整数的阶乘（尽管是一个非常小的子集）：
unsigned long factorial(unsigned long f)
{
if ( f == 0 )
return 1;
return(f * factorial(f - 1));
}
printf("%i", factorial(5));
由于您的问题的性质（以及您承认的级别），此解决方案更多地基于解决此问题的概念，而不是将在下一个“置换引擎”中使用的功能。
于 2010-03-10T11:37:29.523 回答
27
这会计算非负整数 [*] 的阶乘，最高可达 ULONG_MAX，它的位数太多，以至于您的机器不太可能存储更多，即使它有时间计算它们。使用需要链接的 GNU 多精度库。
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
void factorial(mpz_t result, unsigned long input) {
mpz_set_ui(result, 1);
while (input > 1) {
mpz_mul_ui(result, result, input--);
}
}
int main() {
mpz_t fact;
unsigned long input = 0;
char *buf;
mpz_init(fact);
scanf("%lu", &input);
factorial(fact, input);
buf = malloc(mpz_sizeinbase(fact, 10) + 1);
assert(buf);
mpz_get_str(buf, 10, fact);
printf("%s\n", buf);
free(buf);
mpz_clear(fact);
}
示例输出：
$ make factorial CFLAGS="-L/bin/ -lcyggmp-3 -pedantic" -B && ./factorial
cc -L/bin/ -lcyggmp-3 -pedantic factorial.c -o factorial
100
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
[*] 如果你用“数字”表示别的意思，那么你必须更具体。我不知道任何其他定义了阶乘的数字，尽管 Pascal 通过使用 Gamma 函数来扩展域做出了英勇的努力。
于 2010-03-10T12:17:15.177 回答
22
当您可以在 Haskell中执行时，为什么要在 C 中执行：
大一 Haskell 程序员
fac n = if n == 0 then 1 else n * fac (n-1)麻省理工学院的二年级 Haskell 程序员（大一时学习了 Scheme）
fac = (\(n) -> (if ((==) n 0) then 1 else ((*) n (fac ((-) n 1)))))初级 Haskell 程序员（Peano 初学者）
fac 0 = 1 fac (n+1) = (n+1) * fac n另一位初级 Haskell 程序员（读到 n+k 模式是“Haskell 的一个令人作呕的部分” 1并加入了“禁止 n+k 模式”运动 [2]）
fac 0 = 1 fac n = n * fac (n-1)高级 Haskell 程序员（投票给尼克松·布坎南·布什——“偏右”）
fac n = foldr (*) 1 [1..n]另一位 Haskell 高级程序员（投票给 McGovern Biafra
Nader——“偏左”）fac n = foldl (*) 1 [1..n]又一位高级 Haskell 程序员（靠得很靠右，他又回到了左边！）
-- using foldr to simulate foldl fac n = foldr (\x g n -> g (x*n)) id [1..n] 1记忆 Haskell 程序员（每天服用银杏叶）
facs = scanl (*) 1 [1..] fac n = facs !! nPointless (ahem) “Points-free” Haskell 程序员（在牛津学习）
fac = foldr (*) 1 . enumFromTo 1迭代 Haskell 程序员（前 Pascal 程序员）
fac n = result (for init next done) where init = (0,1) next (i,m) = (i+1, m * (i+1)) done (i,_) = i==n result (_,m) = m for i n d = until d n i迭代单行 Haskell 程序员（前 APL 和 C 程序员）
fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))积累Haskell程序员（建立一个快速的高潮）
facAcc a 0 = a facAcc a n = facAcc (n*a) (n-1) fac = facAcc 1续传 Haskell 程序员（早年养 RABBITS，后移居新泽西）
facCps k 0 = k 1 facCps k n = facCps (k . (n *)) (n-1) fac = facCps id童子军 Haskell 程序员（喜欢打结；总是“虔诚”，他属于最小定点教会 [8]）
y f = f (y f) fac = y (\f n -> if (n==0) then 1 else n * f (n-1))组合 Haskell 程序员（避开变量，如果不是混淆的话；所有这些柯里化只是一个阶段，尽管它很少阻碍）
s f g x = f x (g x) k x y = x b f g x = f (g x) c f g x = f x g y f = f (y f) cond p f g x = if p x then f x else g x fac = y (b (cond ((==) 0) (k 1)) (b (s (*)) (c b pred)))列表编码 Haskell 程序员（喜欢一元计数）
arb = () -- "undefined" is also a good RHS, as is "arb" :) listenc n = replicate n arb listprj f = length . f . listenc listprod xs ys = [ i (x,y) | x<-xs, y<-ys ] where i _ = arb facl [] = listenc 1 facl n@(_:pred) = listprod n (facl pred) fac = listprj facl解释型 Haskell 程序员（从未“遇到过他不喜欢的语言”）
-- a dynamically-typed term language data Term = Occ Var | Use Prim | Lit Integer | App Term Term | Abs Var Term | Rec Var Term type Var = String type Prim = String -- a domain of values, including functions data Value = Num Integer | Bool Bool | Fun (Value -> Value) instance Show Value where show (Num n) = show n show (Bool b) = show b show (Fun _) = "" prjFun (Fun f) = f prjFun _ = error "bad function value" prjNum (Num n) = n prjNum _ = error "bad numeric value" prjBool (Bool b) = b prjBool _ = error "bad boolean value" binOp inj f = Fun (\i -> (Fun (\j -> inj (f (prjNum i) (prjNum j))))) -- environments mapping variables to values type Env = [(Var, Value)] getval x env = case lookup x env of Just v -> v Nothing -> error ("no value for " ++ x) -- an environment-based evaluation function eval env (Occ x) = getval x env eval env (Use c) = getval c prims eval env (Lit k) = Num k eval env (App m n) = prjFun (eval env m) (eval env n) eval env (Abs x m) = Fun (\v -> eval ((x,v) : env) m) eval env (Rec x m) = f where f = eval ((x,f) : env) m -- a (fixed) "environment" of language primitives times = binOp Num (*) minus = binOp Num (-) equal = binOp Bool (==) cond = Fun (\b -> Fun (\x -> Fun (\y -> if (prjBool b) then x else y))) prims = [ ("*", times), ("-", minus), ("==", equal), ("if", cond) ] -- a term representing factorial and a "wrapper" for evaluation facTerm = Rec "f" (Abs "n" (App (App (App (Use "if") (App (App (Use "==") (Occ "n")) (Lit 0))) (Lit 1)) (App (App (Use "*") (Occ "n")) (App (Occ "f") (App (App (Use "-") (Occ "n")) (Lit 1)))))) fac n = prjNum (eval [] (App facTerm (Lit n)))静态 Haskell 程序员（他在课堂上做，他得到了 Fundep Jones！在 Thomas Hallgren 的“Fun with Functional Dependencies”[7] 之后）
-- static Peano constructors and numerals data Zero data Succ n type One = Succ Zero type Two = Succ One type Three = Succ Two type Four = Succ Three -- dynamic representatives for static Peanos zero = undefined :: Zero one = undefined :: One two = undefined :: Two three = undefined :: Three four = undefined :: Four -- addition, a la Prolog class Add a b c | a b -> c where add :: a -> b -> c instance Add Zero b b instance Add a b c => Add (Succ a) b (Succ c) -- multiplication, a la Prolog class Mul a b c | a b -> c where mul :: a -> b -> c instance Mul Zero b Zero instance (Mul a b c, Add b c d) => Mul (Succ a) b d -- factorial, a la Prolog class Fac a b | a -> b where fac :: a -> b instance Fac Zero One instance (Fac n k, Mul (Succ n) k m) => Fac (Succ n) m -- try, for "instance" (sorry): -- -- :t fac four刚毕业的 Haskell 程序员（研究生教育倾向于让一个人从琐碎的担忧中解放出来，例如，基于硬件的整数的效率）
-- the natural numbers, a la Peano data Nat = Zero | Succ Nat -- iteration and some applications iter z s Zero = z iter z s (Succ n) = s (iter z s n) plus n = iter n Succ mult n = iter Zero (plus n) -- primitive recursion primrec z s Zero = z primrec z s (Succ n) = s n (primrec z s n) -- two versions of factorial fac = snd . iter (one, one) (\(a,b) -> (Succ a, mult a b)) fac' = primrec one (mult . Succ) -- for convenience and testing (try e.g. "fac five") int = iter 0 (1+) instance Show Nat where show = show . int (zero : one : two : three : four : five : _) = iterate Succ Zero Origamist Haskell programmer (always starts out with the “basic Bird fold”) -- (curried, list) fold and an application fold c n [] = n fold c n (x:xs) = c x (fold c n xs) prod = fold (*) 1 -- (curried, boolean-based, list) unfold and an application unfold p f g x = if p x then [] else f x : unfold p f g (g x) downfrom = unfold (==0) id pred -- hylomorphisms, as-is or "unfolded" (ouch! sorry ...) refold c n p f g = fold c n . unfold p f g refold' c n p f g x = if p x then n else c (f x) (refold' c n p f g (g x)) -- several versions of factorial, all (extensionally) equivalent fac = prod . downfrom fac' = refold (*) 1 (==0) id pred fac'' = refold' (*) 1 (==0) id pred笛卡尔倾向的 Haskell 程序员（更喜欢希腊食物，避免辛辣的印度食物；灵感来自 Lex Augusteijn 的“Sorting Morphisms”[3]）
-- (product-based, list) catamorphisms and an application cata (n,c) [] = n cata (n,c) (x:xs) = c (x, cata (n,c) xs) mult = uncurry (*) prod = cata (1, mult) -- (co-product-based, list) anamorphisms and an application ana f = either (const []) (cons . pair (id, ana f)) . f cons = uncurry (:) downfrom = ana uncount uncount 0 = Left () uncount n = Right (n, n-1) -- two variations on list hylomorphisms hylo f g = cata g . ana f hylo' f (n,c) = either (const n) (c . pair (id, hylo' f (c,n))) . f pair (f,g) (x,y) = (f x, g y) -- several versions of factorial, all (extensionally) equivalent fac = prod . downfrom fac' = hylo uncount (1, mult) fac'' = hylo' uncount (1, mult)博士 Haskell 程序员（吃了太多香蕉，眼睛都肿了，现在他需要新镜头！）
-- explicit type recursion based on functors newtype Mu f = Mu (f (Mu f)) deriving Show in x = Mu x out (Mu x) = x -- cata- and ana-morphisms, now for *arbitrary* (regular) base functors cata phi = phi . fmap (cata phi) . out ana psi = in . fmap (ana psi) . psi -- base functor and data type for natural numbers, -- using a curried elimination operator data N b = Zero | Succ b deriving Show instance Functor N where fmap f = nelim Zero (Succ . f) nelim z s Zero = z nelim z s (Succ n) = s n type Nat = Mu N -- conversion to internal numbers, conveniences and applications int = cata (nelim 0 (1+)) instance Show Nat where show = show . int zero = in Zero suck = in . Succ -- pardon my "French" (Prelude conflict) plus n = cata (nelim n suck ) mult n = cata (nelim zero (plus n)) -- base functor and data type for lists data L a b = Nil | Cons a b deriving Show instance Functor (L a) where fmap f = lelim Nil (\a b -> Cons a (f b)) lelim n c Nil = n lelim n c (Cons a b) = c a b type List a = Mu (L a) -- conversion to internal lists, conveniences and applications list = cata (lelim [] (:)) instance Show a => Show (List a) where show = show . list prod = cata (lelim (suck zero) mult) upto = ana (nelim Nil (diag (Cons . suck)) . out) diag f x = f x x fac = prod . upto Post-doc Haskell programmer (from Uustalu, Vene and Pardo’s “Recursion Schemes from Comonads” [4]) -- explicit type recursion with functors and catamorphisms newtype Mu f = In (f (Mu f)) unIn (In x) = x cata phi = phi . fmap (cata phi) . unIn -- base functor and data type for natural numbers, -- using locally-defined "eliminators" data N c = Z | S c instance Functor N where fmap g Z = Z fmap g (S x) = S (g x) type Nat = Mu N zero = In Z suck n = In (S n) add m = cata phi where phi Z = m phi (S f) = suck f mult m = cata phi where phi Z = zero phi (S f) = add m f -- explicit products and their functorial action data Prod e c = Pair c e outl (Pair x y) = x outr (Pair x y) = y fork f g x = Pair (f x) (g x) instance Functor (Prod e) where fmap g = fork (g . outl) outr -- comonads, the categorical "opposite" of monads class Functor n => Comonad n where extr :: n a -> a dupl :: n a -> n (n a) instance Comonad (Prod e) where extr = outl dupl = fork id outr -- generalized catamorphisms, zygomorphisms and paramorphisms gcata :: (Functor f, Comonad n) => (forall a. f (n a) -> n (f a)) -> (f (n c) -> c) -> Mu f -> c gcata dist phi = extr . cata (fmap phi . dist . fmap dupl) zygo chi = gcata (fork (fmap outl) (chi . fmap outr)) para :: Functor f => (f (Prod (Mu f) c) -> c) -> Mu f -> c para = zygo In -- factorial, the *hard* way! fac = para phi where phi Z = suck zero phi (S (Pair f n)) = mult f (suck n) -- for convenience and testing int = cata phi where phi Z = 0 phi (S f) = 1 + f instance Show (Mu N) where show = show . int终身教授（向新生教授 Haskell）
fac n = product [1..n]
- 来自威拉米特大学 Fritz Ruehr的 Haskell 程序员的演变内容- 2001 年 7 月 11 日
于 2010-03-10T23:33:30.300 回答
18
感谢 Christoph，一个适用于很多“数字”的 C99 解决方案：
#include <math.h>
#include <stdio.h>
double fact(double x)
{
return tgamma(x+1.);
}
int main()
{
printf("%f %f\n", fact(3.0), fact(5.0));
return 0;
}
产生 6.000000 120.000000
于 2010-03-10T14:59:09.250 回答
13
For large n you may run into some issues and you may want to use Stirling's approximation:
Which is:
于 2010-03-10T12:08:07.857 回答
9
如果您的主要目标是一个有趣的功能：
int facorial(int a) {
int b = 1, c, d, e;
a--;
for (c = a; c > 0; c--)
for (d = b; d > 0; d--)
for (e = c; e > 0; e--)
b++;
return b;
}
（不推荐作为实际使用的算法。）
于 2010-03-10T12:15:19.597 回答
7
a tail-recursive version:
long factorial(long n)
{
return tr_fact(n, 1);
}
static long tr_fact(long n, long result)
{
if(n==1)
return result;
else
return tr_fact(n-1, n*result);
}
于 2010-03-10T12:02:11.193 回答
7
在 C99（或 Java）中，我会像这样迭代地编写阶乘函数：
int factorial(int n)
{
int result = 1;
for (int i = 2; i <= n; i++)
{
result *= i;
}
return result;
}
C 不是函数式语言，您不能依赖尾调用优化。因此，除非需要，否则不要在 C（或 Java）中使用递归。
仅仅因为阶乘经常用作递归的第一个示例，并不意味着您需要递归来计算它。
如果 n 太大，这将静默溢出，就像 C（和 Java）中的自定义一样。
如果 int 可以表示的数字对于您要计算的阶乘而言太小，则选择另一种数字类型。long long 如果它需要稍微大一点，float 或 double 如果 n 不是太大并且你不介意一些不精确，或者如果你想要真正大阶乘的确切值，则使用大整数。
于 2010-03-12T06:46:51.383 回答
5
int factorial(int n){
return n <= 1 ? 1 : n * factorial(n-1);
}
于 2010-03-11T14:06:00.167 回答
5
这是一个使用 OPENSSL 的 BIGNUM 实现的 C 程序，因此对学生来说不是特别有用。（当然接受 BIGNUM 作为输入参数很疯狂，但有助于演示 BIGNUM 之间的交互）。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <openssl/crypto.h>
#include <openssl/bn.h>
BIGNUM *factorial(const BIGNUM *num)
{
BIGNUM *count = BN_new();
BIGNUM *fact = NULL;
BN_CTX *ctx = NULL;
BN_one(count);
if( BN_cmp(num, BN_value_one()) <= 0 )
{
return count;
}
ctx = BN_CTX_new();
fact = BN_dup(num);
BN_sub(count, fact, BN_value_one());
while( BN_cmp(count, BN_value_one()) > 0 )
{
BN_mul(fact, count, fact, ctx);
BN_sub(count, count, BN_value_one());
}
BN_CTX_free(ctx);
BN_free(count);
return fact;
}
这个测试程序展示了如何为输入创建一个数字以及如何处理返回值：
int main(int argc, char *argv[])
{
const char *test_cases[] =
{
"0", "1",
"1", "1",
"4", "24",
"15", "1307674368000",
"30", "265252859812191058636308480000000",
"56", "710998587804863451854045647463724949736497978881168458687447040000000000000",
NULL, NULL
};
int index = 0;
BIGNUM *bn = NULL;
BIGNUM *fact = NULL;
char *result_str = NULL;
for( index = 0; test_cases[index] != NULL; index += 2 )
{
BN_dec2bn(&bn, test_cases[index]);
fact = factorial(bn);
result_str = BN_bn2dec(fact);
printf("%3s: %s\n", test_cases[index], result_str);
assert(strcmp(result_str, test_cases[index + 1]) == 0);
OPENSSL_free(result_str);
BN_free(fact);
BN_free(bn);
bn = NULL;
}
return 0;
}
用 gcc 编译：
gcc factorial.c -o factorial -g -lcrypto
于 2010-03-10T18:02:29.327 回答
3
对于大数，您可能可以使用一个近似解，tgamma从 math.h 中得到 (n! = Gamma(n+1))。如果您想要更大的数字，它们将不适合双精度数，因此您应该改用lgamma（伽玛函数的自然对数）。
如果您在没有完整 C99 math.h 的地方工作，您可以轻松地自己做这种事情：
double logfactorial(int n) {
double fac = 0.0;
for ( ; n>1 ; n--) fac += log(fac);
return fac;
}
于 2010-03-10T21:53:05.397 回答
3
我认为在大多数情况下我不会使用它，但是一种越来越不广泛使用的众所周知的做法是使用查找表。如果我们只使用内置类型，那么内存命中很小。
只是另一种方法，让海报意识到不同的技术。许多递归解决方案也可以被记忆，在算法运行时填充查找表，从而大大降低未来调用的成本（我猜有点像 .NET JIT 编译背后的原理）。
于 2010-03-11T09:50:35.717 回答
3
您使用以下代码来执行此操作。
#include <stdio.h>
#include <stdlib.h>
int main()
{
int x, number, fac;
fac = 1;
printf("Enter a number:\n");
scanf("%d",&number);
if(number<0)
{
printf("Factorial not defined for negative numbers.\n");
exit(0);
}
for(x = 1; x <= number; x++)
{
if (number >= 0)
fac = fac * x;
else
fac=1;
}
printf("%d! = %d\n", number, fac);
}
于 2010-03-10T12:11:38.053 回答
2
最简单和最有效的方法是对数求和。如果您使用Log10，您将获得幂和指数。
伪代码
r=0
for i from 1 to n
r= r + log(i)/log(10)
print "result is:", 10^(r-floor(r)) ,"*10^" , floor(r)
您可能需要添加代码，以便整数部分不会增加太多从而降低准确性，但即使是非常大的阶乘，结果也应该没问题。
于 2010-03-11T13:24:02.137 回答
2
C 中使用递归的示例
unsigned long factorial(unsigned long f)
{
if (f) return(f * factorial(f - 1));
return 1;
}
printf("%lu", factorial(5));
于 2010-03-10T11:38:47.337 回答
2
我们必须从1指定的限制开始，比如 .Start nfrom 1*2*3...*n。
在 c 中，我将其编写为一个函数。
main()
{
int n;
scanf("%d",&n);
printf("%ld",fact(n));
}
long int fact(int n)
{
long int facto=1;
int i;
for(i=1;i<=n;i++)
{
facto=facto*i;
}
return facto;
}
于 2010-03-11T11:20:46.357 回答
2
简单的解决方案：
unsigned int factorial(unsigned int n)
{
return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}
于 2015-05-03T16:48:53.200 回答
0
我会按照Boy 先生的建议使用预先计算的查找表来执行此操作。这将比迭代或递归解决方案更快地计算。它取决于n!增长的速度，因为在n!不溢出的情况下您可以计算的unsigned long long最大值（最大值为 18,446,744,073,709,551,615）仅为20!，因此您只需要一个包含 21 个元素的数组。这是它在 c 中的样子：
long long factorial (int n) {
long long f[22] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000, 51090942171709440000};
return f[n];
}
于 2014-05-16T17:34:16.087 回答
0
我将此代码用于阶乘：
#include<stdio.h>
int main(){
int i=1,f=1,n;
printf("\n\nEnter a number: ");
scanf("%d",&n);
while(i<=n){
f=f*i;
i++;
}
printf("Factorial of is: %d",f);
getch();
}
于 2017-08-01T08:28:42.010 回答