반응형
다양한 언어의 팩토리얼 알고리즘
팩토리얼 서브 루틴 또는 프로그램에 대해 생각해 낼 수있는 모든 다른 방법을보고 싶습니다. 희망은 누구나 여기에 와서 그들이 새로운 언어를 배우고 싶어하는지 볼 수 있다는 것입니다.
아이디어 :
- 절차 적
- 기능의
- 객체 지향
- 한 라이너
- 난독 화됨
- 괴짜
- 잘못된 코드
- 다국어
기본적으로 저는 알고리즘을 작성하는 다양한 방법에 대한 예제를보고 싶습니다.
항목 당 하나의 예로 제한하십시오. 특정 스타일, 언어 또는 하나의 게시물에 포함될 수있는 잘 생각한 아이디어를 강조하려는 경우 답변 당 하나 이상의 예제를 제공 할 수 있습니다.
유일한 실제 요구 사항은 표현 된 모든 언어에서 주어진 인수의 계승을 찾아야한다는 것입니다.
창의력을 발휘하십시오!
권장 지침 :
# 언어 이름 : 선택적 스타일 유형
-옵션 글 머리 기호
여기에 코드 입력
기타 정보 텍스트는 여기에 표시됩니다.
나는 가끔씩 적절한 형식이없는 답변을 편집 할 것입니다.
다국어 : 5 개 언어, 모두 bignum 사용
그래서 저는 제가 자주 쓰는 세 가지 언어로 다국어를 썼고,이 질문에 대한 제 다른 답변과 오늘 배운 다른 하나를 썼습니다. 이것은 음이 아닌 정수를 포함하는 단일 행을 읽고 계승을 포함하는 단일 행을 인쇄하는 독립 실행 형 프로그램입니다. Bignums는 모든 언어에서 사용되므로 계산 가능한 최대 계승은 컴퓨터의 리소스에만 의존합니다.
- Perl : 내장 된 bignum 패키지를 사용합니다. 으로 실행합니다
perl FILENAME. - Haskell : 내장 된 bignums를 사용합니다.
runhugs FILENAME또는 좋아하는 컴파일러 와 함께 실행하십시오 . - C ++ : bignum 지원을 위해 GMP가 필요합니다. g ++로 컴파일하려면을 사용
g++ -lgmpxx -lgmp -x c++ FILENAME하여 올바른 라이브러리에 연결하십시오. 컴파일 후./a.out. 또는 좋아하는 컴파일러와 동등한 것을 사용하십시오. - brainf * ck : 나는 이 포스트 에서 큰 지원을 썼다 . 사용 뮬러의 고전적인 분포를 , 컴파일
bf < FILENAME > EXECUTABLE. 출력을 실행 가능하게 만들고 실행하십시오. 또는 좋아하는 배포판을 사용하십시오. - 공백 : 내장 된 bignum 지원을 사용합니다. 으로 실행합니다
wspace FILENAME.
편집 : 다섯 번째 언어로 공백을 추가했습니다. 덧붙여, 할 수 없습니다 와 코드 랩 <code>태그; 공백을 끊습니다. 또한 코드는 고정 너비에서 훨씬 더 멋지게 보입니다.
char // # b = 0 + 0 {-| 0 * /; # >>>>, ---------- [>>>>, --------
#define a / * #-] >>>> ++ <<<<<<<< [> ++++++ [<------>-] <-<<<
#Perl> <> <> <> <> <> <<] >>>> [[>> + <<-] >> [<< +> +>-] <->
# C ++-> <> <> <> <> <> <> <> <+ <[>>>> + <<<-<[-]]> [-]
#Haskell >>]> [-<<<<< [<<<<] >>>> [[>> + <<-] >> [<< +> +>-] >>]
# 공백 >>>> [-[> + <-] + >>>>] <<<< [<<<<] <<<< [<<<<
# 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) {/ * <<< [<<<<] <<< [<<
bignum; sub # <<] >>>>-] >>>>] >>> [> [-] >>>] <<<< [>> + <<-] 사용
z {$ _ [0 + 0] = readline (* STDIN);} 하위 사실 {my ($ n) = shift; # >>
# [<< +> +>-] <-> + <[>-<[-]]> [-<<-<<<< [>> + <<-] >> [<< +> +> + * /
uc; if ($ n == 0) {return 1;} return $ n * fact ($ n-1); } //; #
eval {abs; z ($ n); print fact ($ n); print ( "\ n") / * 2;}; #-] <->
'+ <[>-<[-]]>] << [<<<<] <<<<-[>> + <<-] >> [<< +> +>-] + <[>- +++
-}-<[-]]> [-<< ++++++++++ <<<-[>> + <<-] >> [<< +> +>-++
사실 0 = 1-> <> <> <> <> <> <> <] + <[>-<[-]]>] << [<< + +
사실 n = n * fact (n-1) {-<<] >>>> [[>> + <<-] >> [<< +> +++> +-}
main = do {n <-readLn; print (사실 n)}-+>-] <-> + <[>>>> + << +
{-x <-<[-]]> [-] >>]>] >>> [>>>>] <<<< [> +++++++ [<+++++++ >-]
<-. <<<<] + 작성자 ++++ A + Rex +++ 2009 +. '; # +++ x-}-x * /;}
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
이것은 최대 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 키를 눌러야합니다.
나는 다음 구현이 단지 재밌는 것을 발견합니다.
즐겨!
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
순수한 함수형 프로그래밍의 악몽이 실현됩니다!
다음을 가진 유일한 난해한 Turing-complete 프로그래밍 언어 :
- 순전히 기능적인 기반, 코어 및 라이브러리-사실 완전한 API : SKI
- 람다 도 없습니다 !
- 어떤 번호 또는 목록이 필요하거나 허용
- 명시 적 재귀는 없지만 아직 재귀를 허용합니다.
- 간단한 무한 지연 스트림 기반 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, cons, 1, 10, 42, 1+ 및 *의 적절한 정의를 위해).
편집하다:
Lazy K Factorial in Decimal
( 10KB의 횡설수설 또는 그렇지 않으면 붙여 넣을 것입니다). 예를 들어, Unix 프롬프트에서 :
$ echo "4"| ./lazy facdec.lazy
24
$ echo "5"| ./lazy facdec.lazy
120
위의 숫자는 속도가 느립니다.
코드는 우리 자신의 모든 프리미티브 ( Hazy로 작성된 코드 , 람다 미적분 인터프리터 및 Haskell로 작성된 LC-to-Lazy K 컴파일러)에 대한 라이브러리 코드 를 포함해야하기 때문에 일종의 부풀려 졌습니다.
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 을 엽니 다 .
Python : 기능적, 한 줄짜리
factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)
노트:
- 큰 정수를 지원합니다. 예:
print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000
- n <0 에서는 작동하지 않습니다 .
APL (홀수 / 원 라이너) :
×/⍳X
- ⍳X는 X를 정수 1..X의 배열로 확장합니다.
- × / 배열의 모든 요소를 곱합니다.
또는 내장 연산자를 사용하여 :
!X
출처 : http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt
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!;
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) x n의 계승을 결정합니다.
게임에서이 함수 ( "phrase")를 실제로 호출하려면 동작과 문법 규칙을 정의해야합니다.
"계승 게임"[이것은 소스의 첫 번째 줄이어야 함]
방이 있습니다. [적어도 하나는 있어야합니다!]
팩토리얼 링은 숫자에 적용되는 작업입니다.
팩토리얼 링으로 "계수 [숫자]"를 이해합니다.
팩토리얼 링 수행 :
n을 이해 된 숫자의 팩토리얼이라고합니다.
"[n]"이라고 말합니다.
C # : LINQ
public static int factorial(int n)
{
return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
}
Erlang : 꼬리 재귀
fac(0) -> 1;
fac(N) when N > 0 -> fac(N, 1).
fac(1, R) -> R;
fac(N, R) -> fac(N - 1, R * N).
Haskell :
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
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
재귀 적 프롤로그
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)))
신입생 Haskell 프로그래머
fac n = if n == 0
then 1
else n * fac (n-1)
MIT의 2 학년 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
다른 주니어 하스켈 프로그래머 (n + k 패턴은 "하스켈의 역겨운 부분"[1]을 읽고 "Ban n + k 패턴"-운동 [2]에 합류))
fac 0 = 1
fac n = n * fac (n-1)
수석 Haskell 프로그래머 (Nixon Buchanan Bush에 투표 — "우측으로 기울임")
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 !! n
무의미한 (에헴)“무점”하스켈 프로그래머 (옥스포드에서 공부)
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
Boy Scout 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
대학원 하스켈 프로그래머 초급 (대학원 교육은 하드웨어 기반 정수의 효율성과 같은 사소한 문제에서 벗어나는 경향이 있음)
-- 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 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 프로그래머 (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
종신 교수 (신입생에게 하스켈 교육)
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)
Java 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;
}
PowerShell
function factorial( [int] $n )
{
$result = 1;
if ( $n -gt 1 )
{
$result = $n * ( factorial ( $n - 1 ) )
}
$result
}
다음은 한 줄짜리입니다.
$n..1 | % {$result = 1}{$result *= $_}{$result}
Bash : 재귀
bash 및 재귀 적이지만 새로운 프로세스의 각 반복을 처리한다는 추가 이점이 있습니다. 계산할 수있는 최대 값은 넘치기 전에! 20이지만 대답에 신경 쓰지 않고 시스템이 넘어지기를 원하는 경우 여전히 큰 숫자에 대해 실행할 수 있습니다.)
#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));
참고 URL : https://stackoverflow.com/questions/23930/factorial-algorithms-in-different-languages
반응형
'Programing' 카테고리의 다른 글
| 두 세트의 1000 개 숫자를 서로 어떻게 비교할 수 있습니까? (0) | 2020.11.19 |
|---|---|
| div id에 대한 임의의 문자열 생성 (0) | 2020.11.19 |
| 모든 문자열을 바꾸는 방법은 무엇입니까? (0) | 2020.11.19 |
| 텍스트 및 그룹 노드에 대한 dojox.gfx 경계 상자 (0) | 2020.11.19 |
| 프린터가 조회없이 인쇄 작업을 처리 할 수 있는지 확인 (0) | 2020.11.19 |