다양한 언어의 계승 알고리즘

StackOverflow https://stackoverflow.com/questions/23930

  •  09-06-2019
  •  | 
  •  

문제

나는 팩토리얼 서브루틴이나 프로그램에 대해 여러분이 생각해 낼 수 있는 다양한 방법을 모두 보고 싶습니다.누구든지 이곳에 와서 새로운 언어를 배우고 싶은지 알아볼 수 있기를 바랍니다.

아이디어:

  • 절차적
  • 기능의
  • 객체지향
  • 하나의 라이너
  • 난독화됨
  • 괴짜
  • 잘못된 코드
  • 다국어

기본적으로 나는 알고리즘을 작성하는 다양한 방법과 그것이 다른 언어에서 어떻게 보이는지에 대한 예를 보고 싶습니다.

항목당 하나의 예시로 제한하세요.특정 스타일, 언어 또는 하나의 게시물에 포함할 수 있는 잘 고안된 아이디어를 강조하려는 경우 답변당 하나 이상의 예를 허용할 것입니다.

유일한 실제 요구 사항은 표현된 모든 언어에서 주어진 인수의 계승을 찾아야 한다는 것입니다.

창의력을 발휘하세요!

권장 지침:

# Language Name: Optional Style type

   - Optional bullet points

    Code Goes Here

Other informational text goes here

나는 때때로 적절한 형식이 없는 답변을 편집할 것입니다.

도움이 되었습니까?

해결책

다국어:5개 언어, 모두 빅넘 사용

그래서 저는 제가 자주 쓰는 세 가지 언어로 작동하는 다중 언어를 썼고, 이 질문에 대한 다른 답변과 오늘 방금 배운 것 중 하나를 썼습니다.이는 음수가 아닌 정수가 포함된 한 줄을 읽고 계승이 포함된 한 줄을 인쇄하는 독립 실행형 프로그램입니다.Bignum은 모든 언어에서 사용되므로 계산 가능한 최대 계승은 컴퓨터 리소스에 따라서만 달라집니다.

  • 펄:내장된 bignum 패키지를 사용합니다.다음으로 실행 perl FILENAME.
  • 하스켈:내장된 빅넘을 사용합니다.다음으로 실행 runhugs FILENAME 또는 귀하가 선호하는 컴파일러와 동등한 것입니다.
  • C++:bignum 지원을 위해서는 GMP가 필요합니다.g++로 컴파일하려면 다음을 사용하세요. g++ -lgmpxx -lgmp -x c++ FILENAME 올바른 라이브러리에 연결합니다.컴파일 후 실행 ./a.out.또는 선호하는 컴파일러와 동등한 것을 사용하십시오.
  • 두뇌 씨발:나는 Bignum 지원을 썼다. 이 게시물.사용 Muller의 고전적 분포, 다음으로 컴파일 bf < FILENAME > EXECUTABLE.출력을 실행 가능하게 만들고 실행하십시오.또는 선호하는 배포판을 사용하세요.
  • 공백:내장된 bignum 지원을 사용합니다.다음으로 실행 wspace FILENAME.

편집하다: 공백을 다섯 번째 언어로 추가했습니다.덧붙여서, ~ 아니다 코드를 감싸다 <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*/;}

다른 팁

롤코드:

미안, 참을 수가 없었어 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

이것은 가장 빠른 알고리즘 중 하나입니다. 170!.그것 실패하다 설명할 수 없을 정도로 170을 넘어섰고 작은 계승의 경우 상대적으로 느리지만 그 사이의 계승의 경우 80 그리고 170 많은 알고리즘에 비해 엄청나게 빠릅니다.

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

온라인 인터페이스도 있습니다. 지금 사용해 보세요!

버그를 발견하거나 대규모 계승에 대한 더 빠른 구현을 발견하면 알려주십시오.

편집하다:

이 알고리즘은 약간 느리지만 170을 넘는 결과를 제공합니다.

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

또한 이를 다양한 다른 표현으로 단순화합니다.

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는 컴파일러가 작업을 완료한 후에는 상수입니다.

공백

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

여기에 제대로 표시되도록 하기가 어려웠는데 이제 미리보기에서 복사해 보았는데 작동됩니다.숫자를 입력하고 Enter를 눌러야 합니다.

나는 다음과 같은 구현이 매우 재미있다고 생각합니다.

하스켈 프로그래머의 진화

Python 프로그래머의 진화

즐기다!

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];
}

게으른 케이

순수 함수형 프로그래밍의 악몽이 실현됩니다!

유일한 난해한 튜링 완전 프로그래밍 언어 그 내용은 다음과 같습니다.

다음은 괄호 안에 있는 모든 팩토리얼 코드입니다.

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, cons, 1, 10, 42, 1+ 및 *의 적절한 정의를 위해).

편집하다:

10진수의 게으른 K 계승

(횡설수설 10KB 그렇지 않으면 붙여넣을 것입니다).예를 들어 Unix 프롬프트에서는 다음과 같습니다.

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

위의 숫자(예: 5)의 경우 다소 느립니다.

코드는 다음을 포함해야 하기 때문에 다소 부풀어 오른다. 우리 자신의 모든 기본 요소에 대한 라이브러리 코드 (코드는 다음과 같이 작성되었습니다. 흐릿한, Haskell로 작성된 람다 미적분학 해석기 및 LC-to-Lazy K 컴파일러).

XSLT 1.0

입력 파일, 팩토리얼.xml:

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

XSLT 파일, 팩토리얼.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>

두 파일을 모두 같은 디렉터리에 저장하고 엽니다. 팩토리얼.xml IE에서.

파이썬:기능성, 원라이너

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

메모:

  • 큰 정수를 지원합니다.예:
print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000
  • 그것은 작동하지 않습니다 n < 0.

APL (이상한/한 줄짜리):

×/⍳X
  1. ⍳X는 X를 정수 1..X의 배열로 확장합니다.
  2. ×/는 배열의 모든 요소를 ​​곱합니다.

또는 내장 연산자를 사용하면 다음과 같습니다.

!X

원천: http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt

펄6

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

저는 Perl6에 대해 거의 알지 못합니다.하지만 내 생각엔 이건 [*] 연산자는 Haskell과 동일합니다. product.

이 코드는 다음에서 실행됩니다. 퍼그, 그리고 아마도 앵무새 (저는 확인하지 못했습니다.)

편집하다

이 코드도 작동합니다.

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

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

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

Inform 7에서 재귀적으로

(텍스트 모험을 작성하기 위한 것이기 때문에 COBOL을 생각나게 합니다.비례 글꼴은 의도적인 것입니다):

(n - 숫자)의 계승이 무엇인지 결정하려면:
n이 0이면 1을 결정합니다.
그렇지 않으면 (n - 1) 곱하기 n의 계승을 결정합니다.

게임에서 실제로 이 함수("문구")를 호출하려면 동작과 문법 규칙을 정의해야 합니다.

"The Factorial Game" [이것은 소스의 첫 번째 줄임에 틀림없음]

방이 있습니다.[적어도 하나쯤은 있어야 해!]

팩토리얼링은 숫자에 적용되는 작업입니다.

"팩토리얼 [숫자]"를 팩토리얼링으로 이해하세요.

팩토리얼링을 수행합니다:
n을 이해된 숫자의 계승으로 설정합니다.
"[n]이에요"라고 말하세요.

씨#:링크

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

얼랭:꼬리 재귀

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

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

하스켈:

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

Brainf*ck

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

마이클 라이첸슈타인(Michael Reitzenstein)이 각본을 맡은 작품입니다.

기초적인:오래된 학교

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

배치(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

에프#:기능의

간단하게:

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

재귀 프롤로그

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

꼬리 재귀 프롤로그

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).

루비 재귀

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

용법:

factorial[5]
 => 120

계획

다음은 간단한 재귀 정의입니다.

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

Scheme에서 꼬리 재귀 함수는 일정한 스택 공간을 사용합니다.다음은 꼬리 재귀적인 계승 버전입니다.

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

이상한 예?감마 기능을 사용하는 것은 어떻습니까!부터, Gamma n = (n-1)!.

OCaml:감마 사용

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)))

신입생 하스켈 프로그래머

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

MIT의 2 학년 Haskell 프로그래머 (신입생으로서의 계획)

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

주니어 하스켈 프로그래머 (Peano Player 시작)

fac  0    =  1
fac (n+1) = (n+1) * fac n

또 다른 주니어 하스켈 프로그래머 (N+K 패턴은 "Haskell의 역겨운 부분[1]이며 "Ban N+K Patterns"-Movement [2]에 합류했습니다.

fac 0 = 1
fac n = n * fac (n-1)

선임 Haskell 프로그래머 (Nixon Buchanan Bush의 투표 -“린스 오른쪽”)

fac n = foldr (*) 1 [1..n]

또 다른 선임 Haskell 프로그래머 (McGovern Biafra Nader의 투표 -“Leans Left”)

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 Daily)

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

fac n = facs !! n

무의미한 (ahem) "포인트 프리"Haskell 프로그래머 (옥스포드에서 공부)

fac = foldr (*) 1 . enumFromTo 1

반복 Haskell 프로그래머 (전 파스칼 프로그래머)

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

반복적 인 1 라이너 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

연속 통과 하스켈 프로그래머 (초기에 토끼를 키우고 뉴저지로 이사했습니다)

facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)

fac = facCps id

보이 스카우트 하스켈 프로그래머 (매듭을 묶는 것을 좋아합니다.항상“경건한”그는 가장 고정 된 지점의 교회에 속합니다 [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 프로그래머 (Unary에서 계산을 선호)

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)))

STATIC HASKELL 프로그래머 (그는 클래스와 함께, 그는 그 자금을 조달했습니다!Thomas Hallgren의 "Fun with Functional 종속성" [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

종이 접기 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 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

포스트 DOC 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]

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)

자바 1.6:재귀적, 메모됨(후속 호출용)

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;
}

파워셸

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

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

    $result 
}

다음은 한 줄의 내용입니다.

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

세게 때리다:재귀적

Bash 및 재귀적이지만 새로운 프로세스의 각 반복을 처리한다는 추가 이점이 있습니다.계산할 수 있는 최대값은 오버플로되기 전에 !20이지만, 답에 신경 쓰지 않고 시스템이 넘어지기를 원한다면 큰 숫자로 실행할 수 있습니다. ;)

#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top