不同语言的因子算法

Question

对于阶乘子程序或程序,我希望看到所有不同的方法.希望是任何人都可以来这里看看他们是否想学习一门新语言.

思路:

• 程序
• 实用
• 面向对象
• 一个衬里
• 混淆
• 古怪
• 糟糕的代码
• 多语种

基本上我想看一个例子,编写算法的不同方式,以及它们在不同语言中的样子.

请将其限制为每个条目一个示例.如果你试图突出一个特定的风格,语言,或者仅仅是一个经过深思熟虑的想法,我会允许你在每个答案中有不止一个例子.

唯一真正的要求是它必须在所有代表的语言中找到给定参数的阶乘.

有创意!

推荐指南:

# Language Name: Optional Style type

   - Optional bullet points

    Code Goes Here

Other informational text goes here

我会偶尔编辑任何没有正确格式的答案.

Answer 1

Polyglot:5种语言,均使用bignums

所以,我写了一个多语言,它使用我经常写的三种语言,以及我对这个问题的另一个答案和我今天刚刚学到的一种语言.它是一个独立程序,它读取包含非负整数的单行并打印包含其阶乘的单行.Bignums用于所有语言,因此最大可计算因子仅取决于您的计算机资源.

• Perl:使用内置的bignum包.运行perl FILENAME.
• Haskell:使用内置bignums.运行runhugs FILENAME或与您最喜欢的编译器等效.
• C++:要求GMP支持bignum.要使用g ++进行编译,请使用g++ -lgmpxx -lgmp -x c++ FILENAME链接到正确的库.编译完成后,运行./a.out.或者使用您最喜欢的编译器等效.
• brainf*ck:我在这篇文章中写了一些bignum支持.使用Muller的经典发行版,编译bf < FILENAME > EXECUTABLE.使输出可执行并运行它.或者使用您喜欢的发行版.
• 空白:使用内置的bignum支持.运行wspace FILENAME.

编辑:将Whitespace添加为第五种语言.顺便说一句,你不换行的代码<code>标签; 它打破了空白.此外,代码看起来固定宽度更好.

char //# b=0+0{- |0*/; #>>>>,----------[>>>>,--------
#define	a/*#--]>>>>++<<<<<<<<[>++++++[<------>-]<-<<<
#Perl	><><><>	 <> <> <<]>>>>[[>>+<<-]>>[<<+>+>-]<->
#C++	--><><>	<><><><	> < > <	+<[>>>>+<<<-<[-]]>[-]
#Haskell >>]>[-<<<<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]>>]
#Whitespace	>>>>[-[>+<-]+>>>>]<<<<[<<<<]<<<<[<<<<
#brainf*ck > < ]>>>>>[>>>[>>>>]>>>>[>>>>]<<<<[[>>>>*/
exp; ;//;#+<<<<-]<<<<]>>>>+<<<<<<<[<<<<][.POLYGLOT^5.
#include <gmpxx.h>//]>>>>-[>>>[>>>>]>>>>[>>>>]<<<<[>>
#define	eval int	main()//>+<<<-]>>>[<<<+>>+>->
#include <iostream>//<]<-[>>+<<[-]]<<[<<<<]>>>>[>[>>>
#define	print std::cout	<< // >	<+<-]>[<<+>+>-]<<[>>>
#define	z std::cin>>//<< +<<<-]>>>[<<<+>>+>-]<->+++++
#define c/*++++[-<[-[>>>>+<<<<-]]>>>>[<<<<+>>>>-]<<*/
#define	abs int $n //><	<]<[>>+<<<<[-]>>[<<+>>-]]>>]<
#define	uc mpz_class fact(int	$n){/*<<<[<<<<]<<<[<<
use bignum;sub#<<]>>>>-]>>>>]>>>[>[-]>>>]<<<<[>>+<<-]
z{$_[0+0]=readline(*STDIN);}sub fact{my($n)=shift;#>>
#[<<+>+>-]<->+<[>-<[-]]>[-<<-<<<<[>>+<<-]>>[<<+>+>+*/
uc;if($n==0){return 1;}return $n*fact($n-1);	}//;#
eval{abs;z($n);print fact($n);print("\n")/*2;};#-]<->
'+<[>-<[-]]>]<<[<<<<]<<<<-[>>+<<-]>>[<<+>+>-]+<[>-+++
-}--	<[-]]>[-<<++++++++++<<<<-[>>+<<-]>>[<<+>+>-++
fact 0	= 1 -- ><><><><	> <><><	]+<[>-<[-]]>]<<[<<+ +
fact	n=n*fact(n-1){-<<]>>>>[[>>+<<-]>>[<<+>+++>+-}
main=do{n<-readLn;print(fact n)}-- +>-]<->+<[>>>>+<<+
{-x<-<[-]]>[-]>>]>]>>>[>>>>]<<<<[>+++++++[<+++++++>-]
<--.<<<<]+written+by+++A+Rex+++2009+.';#+++x-}--x*/;}

Answer 2

lolcode:

抱歉,我无法抗拒xD

HAI
CAN HAS STDIO?
I HAS A VAR
I HAS A INT
I HAS A CHEEZBURGER
I HAS A FACTORIALNUM
IM IN YR LOOP
    UP VAR!!1
    TIEMZD INT!![CHEEZBURGER]
    UP FACTORIALNUM!!1
    IZ VAR BIGGER THAN FACTORIALNUM? GTFO
IM OUTTA YR LOOP
U SEEZ INT
KTHXBYE    

Answer 3

这是速度更快的算法之一,最高可达170!.它在莫名其妙地超过170!并且对于小因子来说相对较慢,但对于80到170之间的因子,与许多算法相比,它的速度非常快.

curl http://www.google.com/search?q=170!

还有一个在线界面,现在就试试吧!

如果您发现错误或更快地实施大型因子,请告诉我们.

编辑:

此算法稍微慢一些,但结果超出170:

curl http://www58.wolframalpha.com/input/?i=171!

它还将它们简化为各种其他表示形式.

Answer 4

C++:模板元编程

使用经典的枚举黑客.

template<unsigned int n>
struct factorial {
    enum { result = n * factorial<n - 1>::result };
};

template<>
struct factorial<0> {
    enum { result = 1 };
};

用法.

const unsigned int x = factorial<4>::result;

基于模板参数n,在编译时完全计算因子.因此,一旦编译器完成其工作,factorial <4> :: result就是常量.

Answer 5

空白

   	.
 .
 	.
		.
  	.
   	.
			 .
 .
	 	 .
	  .
   	.
 .
  .
 			 .
		  			 .
 .
	.
.
  	 .
 .
.
	.
 	.
.
.
.

很难让它在这里正确显示,但现在我尝试从预览中复制它并且它有效.您需要输入数字并按Enter键.

Answer 6

我发现以下实现只是搞笑:

Haskell程序员的演变

Python程序员的演变

请享用!

Answer 7

C#查找:

没有什么可以计算的,只需查阅即可.要扩展它,将另外8个数字添加到表中,64位整数处于其限制.除此之外,还需要一个BigNum类.

public static int Factorial(int f)
{ 
    if (f<0 || f>12)
    {
        throw new ArgumentException("Out of range for integer factorial");
    }
    int [] fact={1,1,2,6,24,120,720,5040,40320,362880,3628800,
                 39916800,479001600};
    return fact[f];
}

Answer 8

懒惰的 K.

你纯粹的功能编程梦魇成真!

唯一的Esoteric图灵完整编程语言:

• 一个纯粹的功能基础,核心和库 - 事实上,这里是完整的API:SKI
• 甚至没有lambdas!
• 不需要或允许任何数字或列表
• 没有明确的递归但是允许递归
• 一个简单的无限懒惰流的I/O机制

这是所有括号荣耀中的因子代码:

K(SII(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(K(S(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
 (S(S(KS)K)(SII(S(S(KS)K)I))))))))K))))))(S(K(S(K(S(SI(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
 (S(S(KS)K)(SII(S(S(KS)K)I))(S(S(KS)K))(S(SII)I(S(S(KS)K)I))))))))K)))))))
 (S(S(KS)K)(K(S(S(KS)K)))))))))(K(S(K(S(S(KS)K)))K))))(SII))II)

特征:

• 没有减法或条件
• 打印所有阶乘(如果等待足够长的时间)
• 使用第二层教会数字将第N个阶乘转换为N!星号后跟换行符
• 使用Y组合子进行递归

如果您有兴趣尝试理解它,这里是通过Lazier编译器运行的Scheme源代码:

(lazy-def '(fac input)
   '((Y (lambda (f n a) ((lambda (b) ((cons 10) ((b (cons 42)) (f (1+ n) b))))
       (* a n)))) 1 1))

(对于Y,缺点,1,10,42,1 +和*的合适定义).

编辑:

懒惰的K因子在十进制

(10KB的胡言乱语,否则我会粘贴它).例如,在Unix提示符下:

    $ echo "4" | ./lazy facdec.lazy
    24
    $ echo "5" | ./lazy facdec.lazy
    120

对于上面的数字来说相当慢,比如5.

代码有点臃肿,因为我们必须包含所有自己的原语的库代码(用Hazy编写的代码,lambda演算解释器和用Haskell编写的LC-to-Lazy K编译器).

Answer 9

XSLT 1.0

输入文件factorial.xml:

<?xml version="1.0"?>
<?xml-stylesheet href="factorial.xsl" type="text/xsl" ?>
<n>
  20
</n>

XSLT文件,factorial.xsl:

<?xml version="1.0"?>
<xsl:stylesheet version="1.0"                     
                xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                xmlns:msxsl="urn:schemas-microsoft-com:xslt" >
  <xsl:output method="text"/>
  <!-- 0! = 1 -->
  <xsl:template match="text()[. = 0]">
    1
  </xsl:template>
  <!-- n! = (n-1)! * n-->
  <xsl:template match="text()[. > 0]">
    <xsl:variable name="x">
      <xsl:apply-templates select="msxsl:node-set( . - 1 )/text()"/>
    </xsl:variable>
    <xsl:value-of select="$x * ."/>
  </xsl:template>
  <!-- Calculate n! -->
  <xsl:template match="/n">
    <xsl:apply-templates select="text()"/>
  </xsl:template>
</xsl:stylesheet>

将两个文件保存在同一目录中,然后在IE中打开factorial.xml.

Answer 10

Python:功能性,单行

factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)

注意:

• 它支持大整数.例:

print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000

• 它不适用于n <0.

Answer 11

APL(古怪/单线):

×/?X

1. ⍳X将X扩展为整数1..X的数组
2. ×/乘以数组中的每个元素

或者使用内置运算符:

!X

资料来源:http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt

Answer 12

Perl6

sub factorial ($n) { [*] 1..$n }

我几乎不知道Perl6.但我猜这个[*]算子和Haskell一样product.

这段代码在Pugs上运行,也许是Parrot(我没有检查它.)

编辑

此代码也有效.

sub postfix:<!> ($n) { [*] 1..$n }

# This function(?) call like below ... It looks like mathematical notation.
say 10!;

Answer 13

x86-64汇编:程序

你可以用C调用它(只在linux amd64上用GCC测试过).大会与nasm组装在一起.

section .text
    global factorial
; factorial in x86-64 - n is passed in via RDI register
; takes a 64-bit unsigned integer
; returns a 64-bit unsigned integer in RAX register
; C declaration in GCC:
;   extern unsigned long long factorial(unsigned long long n);
factorial:
    enter 0,0
    ; n is placed in rdi by caller
    mov rax, 1 ; factorial = 1
    mov rcx, 2 ; i = 2
loopstart:
    cmp rcx, rdi
    ja loopend
    mul rcx ; factorial *= i
    inc rcx
    jmp loopstart
loopend:
    leave
    ret

Answer 14

在Inform 7中递归

(它会让你想起COBOL,因为它是用于编写文本冒险;比例字体是故意的):

要确定哪个数是(n - 一个数)的阶乘:
    如果n为零,则决定一个;
    否则决定(n减1)乘以n的阶乘.

如果你想从游戏中实际调用这个函数("短语"),你需要定义一个动作和语法规则:

"阶乘游戏"[这必须是来源的第一行]

有一个房间.[必须至少有一个!]

Factorialing是一个适用于数字的动作.

理解"因子[数字]"作为因子分解.

执行阶乘:
    让n成为理解数的阶乘;
    说"这是[n]".

Answer 15

哈斯克尔:

ones = 1 : ones
integers   = head ones     : zipWith (+) integers   (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)

Answer 16

C#:LINQ

    public static int factorial(int n)
    {
        return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
    }

Answer 17

Erlang:尾递归

fac(0) -> 1;
fac(N) when N > 0 -> fac(N, 1).

fac(1, R) -> R;
fac(N, R) -> fac(N - 1, R * N).

Answer 18

Brainf*CK

+++++
>+<[[->>>>+<<<<]>>>>[-<<<<+>>+>>]<<<<>[->>+<<]<>>>[-<[->>+<<]>>[-<<+<+>>>]<]<[-]><<<-]

由Michael Reitzenstein撰写.

Answer 19

基本:老学校

10 HOME
20 INPUT N
30 LET ANS = 1
40 FOR I = 1 TO N
50   ANS = ANS * I
60 NEXT I
70 PRINT ANS

Answer 20

F#:功能性

直截了当:

let rec fact x = 
    if   x < 0 then failwith "Invalid value."
    elif x = 0 then 1
    else x * fact (x - 1)

获得幻想:

let fact x = [1 .. x] |> List.fold_left ( * ) 1

Answer 21

批量(NT):

@echo off

set n=%1
set result=1

for /l %%i in (%n%, -1, 1) do (
    set /a result=result * %%i
)

echo %result%

用法:C:> factorial.bat 15

Answer 22

递归Prolog

fac(0,1).
fac(N,X) :- N1 is N -1, fac(N1, T), X is N * T.

Tail Recursive Prolog

fac(0,N,N).
fac(X,N,T) :- A is N * X, X1 is X - 1, fac(X1,A,T).
fac(N,T) :- fac(N,1,T).

Answer 23

红宝石递归

(factorial=Hash.new{|h,k|k*h[k-1]})[1]=1

用法:

factorial[5]
 => 120

Answer 24

方案

这是一个简单的递归定义:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

在Scheme中,tail-recursive函数使用常量堆栈空间.这是一个尾递归的factorial版本:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

Answer 25

D模板:功能性

template factorial(int n : 1)
{
  const factorial = 1;
}

template factorial(int n)
{
  const factorial =
     n * factorial!(n-1);
}

要么

template factorial(int n)
{
  static if(n == 1)
    const factorial = 1;
  else 
    const factorial =
       n * factorial!(n-1);
}

像这样使用:

factorial!(5)

Answer 26

奇怪的例子？怎么样使用伽玛功能!自从,Gamma n = (n-1)!.

OCaml:使用Gamma

let rec gamma z =
    let pi = 4.0 *. atan 1.0 in
    if z < 0.5 then
        pi /. ((sin (pi*.z)) *. (gamma (1.0 -. z)))
    else
        let consts = [| 0.99999999999980993; 676.5203681218851; -1259.1392167224028;
                        771.32342877765313; -176.61502916214059; 12.507343278686905;
                 -0.13857109526572012; 9.9843695780195716e-6; 1.5056327351493116e-7;
                     |] 
        in
        let z = z -. 1.0 in
        let results = Array.fold_right 
                          (fun x y -> x +. y)
                          (Array.mapi 
                              (fun i x -> if i = 0 then x else x /. (z+.(float i)))
                              consts
                          )
                          0.0
        in
        let x = z +. (float (Array.length consts)) -. 1.5 in
        let final = (sqrt (2.0*.pi)) *. 
                    (x ** (z+.0.5)) *.
                    (exp (-.x)) *. result
        in
        final

let factorial_gamma n = int_of_float (gamma (float (n+1)))

Answer 27

新生Haskell程序员

fac n = if n == 0 
           then 1
           else n * fac (n-1)

麻省理工学院的二年级学生Haskell程序员(作为新生学习计划)

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]并加入了"Ban 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程序员(每天服用Ginkgo Biloba)

facs = scanl (*) 1 [1..]

fac n = facs !! n

无意义(咳咳)"无点"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的"功能依赖的乐趣"之后[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程序员(总是从"基本鸟褶"开始)

-- (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态射"[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

博士后Haskell程序员(来自Uustalu,Vene和Pardo的"来自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]

Answer 28

电源外壳

function factorial( [int] $n ) 
{ 
    $result = 1; 

    if ( $n -gt 1 ) 
    { 
        $result = $n * ( factorial ( $n - 1 ) ) 
    } 

    $result 
}

这是一个单行:

$n..1 | % {$result = 1}{$result *= $_}{$result}

Answer 29

Java 1.6:递归,memoized(后续调用)

private static Map<BigInteger, BigInteger> _results = new HashMap()

public static BigInteger factorial(BigInteger n){
    if (0 >= n.compareTo(BigInteger.ONE))
       return BigInteger.ONE.max(n);
    if (_results.containsKey(n))
       return _results.get(n);
    BigInteger result = factorial(n.subtract(BigInteger.ONE)).multiply(n);
    _results.put(n, result);
    return result;
}

Answer 30

Bash:递归

在bash和递归中,但具有额外的优势,它处理新进程中的每次迭代.在溢出之前它可以计算的最大值是!20,但是如果你不关心答案并希望你的系统能够翻倒,你仍然可以运行大数字;)

#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));

Answer 31

C/C++:程序

unsigned long factorial(int n)
{
    unsigned long factorial = 1;
    int i;

    for (i = 2; i <= n; i++)
        factorial *= i;

    return factorial;
}

PHP:程序

function factorial($n)
{
    for ($factorial = 1, $i = 2; $i <= $n; $i++)
        $factorial *= $i;

    return $factorial;
}

@Niyaz:您没有为函数指定返回类型

Answer 32

上面大部分的问题是它们在大约25时会耗尽精度!(12!有32位整数)或只是溢出.这是ac#实现突破这些限制!

class Number
{
  public Number ()
  {
    m_number = "0";
  }

  public Number (string value)
  {
    m_number = value;
  }

  public int this [int column]
  {
    get
    {
      return column < m_number.Length ? m_number [m_number.Length - column - 1] - '0' : 0;
    }
  }

  public static implicit operator Number (string rhs)
  {
    return new Number (rhs);
  }

  public static bool operator == (Number lhs, Number rhs)
  {
    return lhs.m_number == rhs.m_number;
  }

  public static bool operator != (Number lhs, Number rhs)
  {
    return lhs.m_number != rhs.m_number;
  }

  public override bool Equals (object obj)
  {
     return this == (Number) obj;
  }

  public override int GetHashCode ()
  {
    return m_number.GetHashCode ();
  }

  public static Number operator + (Number lhs, Number rhs)
  {
    StringBuilder
      result = new StringBuilder (new string ('0', lhs.m_number.Length + rhs.m_number.Length));

    int
      carry = 0;

    for (int i = 0 ; i < result.Length ; ++i)
    {
      int
        sum = carry + lhs [i] + rhs [i],
        units = sum % 10;

      carry = sum / 10;

      result [result.Length - i - 1] = (char) ('0' + units);
    }

    return TrimLeadingZeros (result);
  }

  public static Number operator * (Number lhs, Number rhs)
  {
    StringBuilder
      result = new StringBuilder (new string ('0', lhs.m_number.Length + rhs.m_number.Length));

    for (int multiplier_index = rhs.m_number.Length - 1 ; multiplier_index >= 0 ; --multiplier_index)
    {
      int
        multiplier = rhs.m_number [multiplier_index] - '0',
        column = result.Length - rhs.m_number.Length + multiplier_index;

      for (int i = lhs.m_number.Length - 1 ; i >= 0 ; --i, --column)
      {
        int
          product = (lhs.m_number [i] - '0') * multiplier,
          units = product % 10,
          tens = product / 10,
          hundreds = 0,
          unit_sum = result [column] - '0' + units;

        if (unit_sum > 9)
        {
          unit_sum -= 10;
          ++tens;
        }

        result [column] = (char) ('0' + unit_sum);

        int
          tens_sum = result [column - 1] - '0' + tens;

        if (tens_sum > 9)
        {
          tens_sum -= 10;
          ++hundreds;
        }

        result [column - 1] = (char) ('0' + tens_sum);

        if (hundreds > 0)
        {
          int
            hundreds_sum = result [column - 2] - '0' + hundreds;

          result [column - 2] = (char) ('0' + hundreds_sum);
        }
      }
    }

    return TrimLeadingZeros (result);
  }

  public override string ToString ()
  {
    return m_number;
  }

  static string TrimLeadingZeros (StringBuilder number)
  {
    while (number [0] == '0' && number.Length > 1)
    {
      number.Remove (0, 1);
    }

    return number.ToString ();
  }

  string
    m_number;
}

static void Main (string [] args)
{
  Number
    a = new Number ("1"),
    b = new Number (args [0]),
    one = new Number ("1");

  for (Number c = new Number ("1") ; c != b ; )
  {
    c = c + one;
    a = a * c;
  }

  Console.WriteLine (string.Format ("{0}! = {1}", new object [] { b, a }));
}

FWIW:10000!超过35500个字符.

Skizz

Answer 33

Lambda微积分

输入和输出是教会数字(即自然数k是\f n. f^k n;所以3 = \f n. f (f (f n)))

(\x. x x) (\y f. f (y y f)) (\y n. n (\x y z. z) (\x y. x) (\f n. f n) (\f. n (y (\f m. n (\g h. h (g f)) (\x. m) (\x. x)) f)))

Answer 34

下面的代码是诙谐的,但是当你考虑到uint32的返回值被限制为n <34时,在我们用uint返回值的空间用完之前<65 uint64,硬编码33值不是那个疯了 :)

public static int Factorial(int n)
{
    switch (n)
    {
        case 1:
            return 1;
        case 2:
            return 2;
        case 3:
            return 6;
        case 4:
            return 24;
        default:
            throw new Exception("Sorry, I can only count to 4");
    }

}