階乗サブルーチンまたはプログラムについて、あなたが思いつくさまざまな方法をすべて見たいと思います。誰もがここに来て、新しい言語を学びたいかどうかを確認できることを願っています.
基本的に、アルゴリズムを書くさまざまな方法の例と、それらがさまざまな言語でどのように見えるかを見たいと思っています。
1 エントリにつき 1 つの例に制限してください。特定のスタイル、言語、または 1 つの投稿に適したよく考え抜かれたアイデアを強調しようとしている場合は、回答ごとに複数の例を使用できます。
唯一の実際の要件は、表されるすべての言語で、与えられた引数の階乗を見つけなければならないことです。
# 言語名: オプションのスタイル タイプ
- オプションの箇条書き
コードはここに入る
その他の情報テキストはここに入る
私はときどき、適切な書式設定がない回答を編集します。
それで、私がよく書く 3 つの言語で動作する多言語を書きました。また、この質問に対する他の回答からの 1 つと、今日学んだばかりの 1 つを書きました。これは、非負の整数を含む 1 行を読み取り、階乗を含む 1 行を出力するスタンドアロン プログラムです。Bignum はすべての言語で使用されるため、計算可能な階乗の最大値はコンピューターのリソースにのみ依存します。
perl FILENAMEます。runhugs FILENAMEまたはお好みのコンパイラと同等のもので実行します。g++ -lgmpxx -lgmp -x c++ FILENAMEして適切なライブラリにリンクします。コンパイル後、実行します./a.out。または、お気に入りのコンパイラの同等のものを使用してください。bf < FILENAME > EXECUTABLEます。出力を実行可能にして実行します。または、お気に入りのディストリビューションを使用してください。wspace FILENAMEます。編集： 5番目の言語として空白を追加しました。ちなみに、コードをタグでラップしないでください。<code>ホワイトスペースを壊します。また、コードは固定幅の方が見栄えがよくなります。
char //# b=0+0{- |0*/; #>>>>,----------[>>>>,--------
#define a/*#--]>>>>++<<<<<<<<[>++++++[<----->-]<-<<<
#Perl ><><><> <> <> <<]>>>>[[>>+<<-]>>[<<+>+>-]<->
#C++ --><><> <><><>< > < > < +<[>>>>+<<<-<[-]]>[-]
#Haskell >>]>[-<<<<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]>>]
#ホワイトスペース >>>>[-[>+<-]+>>>>]<<<<[<<<<]<<<<[<<<<
#brainf*ck > < ]>>>>>[>>>[>>>>]>>>>[>>>>]<<<<[[>>>>*/
指数; ;//;#+<<<<-]<<<<]>>>>+<<<<<<<[<<<<][.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 ファクト(int $n){/*<<<[<<<<]<<<[<<
use 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*事実(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 の高速なアルゴリズムの 1 つです。. 170! を超えると不可解に失敗し、小さな階乗では比較的遅くなりますが、80から170の間の階乗では、多くのアルゴリズムと比較して非常に高速です。
curl http://www.google.com/search?q=170!
オンラインインターフェースもありますので、今すぐお試しください！
バグを見つけた場合、または大規模な階乗のより高速な実装を見つけた場合はお知らせください。
このアルゴリズムは少し遅くなりますが、170 を超える結果が得られます。
curl http://www58.wolframalpha.com/input/?i=171!
また、それらをさまざまな他の表現に単純化します。
従来の列挙型ハックを使用します。
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(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)
特徴：
理解しようとすることに興味がある場合は、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+、および * の適切な定義について)。
編集：
（10KBの意味不明なもの、または貼り付けます）。たとえば、Unix プロンプトで次のように入力します。
$ エコー "4" | ./lazy facdec.lazy
24
$ エコー "5" | ./lazy facdec.lazy
120
それ以上の数値、たとえば 5 の場合はかなり遅くなります。
独自のすべてのプリミティブ( Hazyで記述されたコード、ラムダ計算インタープリター、および Haskell で記述された LC-to-Lazy K コンパイラー)のライブラリ コードを含める必要があるため、コードは一種の肥大化しています。
入力ファイル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を開きます。
factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)
ノート：
print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000
×/⍳X
または、組み込みの演算子を使用します。
!X
出典：http ：//www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt
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!;
これは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
(テキストの冒険を書くための COBOL を思い起こさせます。プロポーショナル フォントは意図的なものです):
(n - a number) の階乗が何の数かを決定するには:
n が 0 の場合、1 を決定します。
それ以外の場合は、(n マイナス 1) 倍 n の階乗を決定します。
この関数 (「句」) をゲームから実際に呼び出したい場合は、アクションと文法規則を定義する必要があります。
「階乗ゲーム」 [これはソースの最初の行に違いない]
部屋があります。[少なくとも 1 つある必要があります!]
因数分解は、数値に適用されるアクションです。
「factorial [a number]」を階乗として理解します。
階乗
を実行します。 n を理解した数の階乗とします。
「[ん]です」と言ってください。
public static int factorial(int n)
{
return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
}
ハスケル:
ones = 1 : ones
integers = head ones : zipWith (+) integers (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)
fac(0) -> 1;
fac(N) when N > 0 -> fac(N, 1).
fac(1, R) -> R;
fac(N, R) -> fac(N - 1, R * N).
+++++
>+<[[->>>>+<<<<]>>>>[-<<<<+>>+>>]<<<<>[->>+<<]<>>>[-<[->>+<<]>>[-<<+<+>>>]<]<[-]><<<-]
マイケル・ライツェンシュタイン著。
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
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
バッチ (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
(factorial=Hash.new{|h,k|k*h[k-1]})[1]=1
利用方法：
factorial[5]
=> 120
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).
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)
図式
以下は単純な再帰的定義です。
(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)!。
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 プログラマー (ペアノ初心者)
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 プログラマー (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 プログラマーのメモ化 (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 プログラマー (彼はクラスでそれを行います。彼はそのファンデップ ジョーンズを持っています! 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 プログラマー (常に「基本的な Bird フォールド」から始めます)
-- (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
ポスドク Haskell プログラマー (Uustalu、Vene、および Pardo の「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]
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;
}
bash および再帰的ですが、新しいプロセスで各反復を処理するという追加の利点があります。オーバーフローする前に計算できる最大値は !20 ですが、答えを気にせず、システムを崩壊させたい場合は、大きな数に対しても実行できます;)
#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));
パワーシェル
function factorial( [int] $n )
{
$result = 1;
if ( $n -gt 1 )
{
$result = $n * ( factorial ( $n - 1 ) )
}
$result
}
ここにワンライナーがあります：
$n..1 | % {$result = 1}{$result *= $_}{$result}
上記のほとんどの問題は、約 25 で精度がなくなることです! (12! with 32 bit ints) または単にオーバーフローします。これらの制限を打ち破るための 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 文字を超えています。
スキズ
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 : 関数の戻り値の型を指定しませんでした
入力と出力はチャーチ数字です (つまり、自然数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)))
以下のコードは冗談ですが、uint で戻り値のスペースがなくなる前に、戻り値が uint32 の n < 34、<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");
}
}
(defn fact
([n] (fact n 1))
([n acc] (if (= n 0)
acc
(recur (- n 1) (* acc n)))))
(defn fact [n] (apply * (range 1 (+ n 1))))
Ruby: 機能的
def factorial(n)
return 1 if n == 1
n * factorial(n -1)
end
procedure factorial(n)
return (0<n) * factorial(n-1) | 1
end
負の値が 1 を返すように少しごまかしました。負の引数を指定して失敗させたい場合は、少し簡潔です。
return (0<n) * factorial(n-1) | (n=0 & 1)
それで
write(factorial(3))
write(factorial(-1))
write(factorial(20))
版画
6
2432902008176640000
procedure factorials()
local f,n
f := 1; n := 0
repeat suspend f *:= (n +:= 1)
end
それで
every write(factorials() \ 5)
版画
1
2
6
24
120
これを理解するには: 評価は目標指向であり、失敗すると後戻りします。ブール型は存在せず、他の言語でブール値を返す二項演算子は、失敗するか、2 番目の引数を返します。ただし、| は例外です。単一値のコンテキストでは、成功した場合は最初の引数を返し、それ以外の場合はその引数を試みます。 2 番目の引数。(複数値のコンテキストでは、最初の引数を返し、次に2 番目の引数を返します)
suspend他の言語と似yieldていますが、結果を返すためにジェネレーターが明示的に複数回呼び出されない点が異なります。代わりに、
every引数にすべての値を要求しますが、デフォルトでは何も返しません。副作用 (この場合は I/O) に役立ちます。
\ジェネレーターによって返される値の数を制限します。 の場合はfactorials無限になります。
factorial n = product [1..n]
bash & bcほど高速なものはありません:
function fac { seq $1 | paste -sd* | bc; }
$ fac 42
1405006117752879898543142606244511569936384000000000
$
#Language: T-SQL
#Style: Recursive, divide and conquer
楽しみのために - T-SQL で、分割統治再帰法を使用します。はい、再帰的 - スタック オーバーフローのない SQL で。
create function factorial(@b int=1, @e int) returns float as begin
return case when @b>=@e then @e else
convert(float,dbo.factorial(@b,convert(int,@b+(@e-@b)/2)))
* convert(float,dbo.factorial(convert(int,@b+1+(@e-@b)/2),@e)) end
end
次のように呼び出します。
print dbo.factorial(1,170) -- the 1 being the starting number
これは Agda2 であり、非常に優れた Agda2 構文を使用しています。
module fac where
data Nat : Set where -- Peano numbers
zero : Nat
suc : Nat -> Nat
{-# BUILTIN NATURAL Nat #-}
{-# BUILTIN SUC suc #-}
{-# BUILTIN ZERO zero #-}
infixl 10 _+_ -- Addition over Peano numbers
_+_ : Nat -> Nat -> Nat
zero + n = n
(suc n) + m = suc (n + m)
infixl 20 _*_ -- Multiplication over Peano numbers
_*_ : Nat -> Nat -> Nat
zero * n = zero
n * zero = zero
(suc n) * (suc m) = suc n + (suc n * m)
_! : Nat -> Nat -- Factorial function, syntax: "x !"
zero ! = suc zero
(suc n) ! = (suc n) * (n !)
Agda 2: 関数型、依存型。
data Nat = zero | suc (m::Nat)
add (m::Nat) (n::Nat) :: Nat
= case m of
(zero ) -> n
(suc p) -> suc (add p n)
mul (m::Nat) (n::Nat)::Nat
= case m of
(zero ) -> zero
(suc p) -> add n (mul p n)
factorial (n::Nat)::Nat
= case n of
(zero ) -> suc zero
(suc p) -> mul n (factorial p)
function factorial (n)
if (n <= 1) then return 1 end
return n*factorial(n-1)
end
そして、これが実際にキャッチされたスタック オーバーフローです。
> print (factorial(234132))
stdin:3: stack overflow
stack traceback:
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
...
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:3: in function 'factorial'
stdin:1: in main chunk
[C]: ?
Mathematica : 純粋な再帰関数の使用
(If[#>1,# #0[#-1],1])&
階乗は関数的に次のように定義できます。
def fact(n: Int): BigInt = 1 to n reduceLeft(_*_)
またはより伝統的に
def fact(n: Int): BigInt = if (n == 0) 1 else fact(n-1) * n
そして、私たちは作ることができます! Ints の有効なメソッド:
object extendBuiltins extends Application {
class Factorizer(n: Int) {
def ! = 1 to n reduceLeft(_*_)
}
implicit def int2fact(n: Int) = new Factorizer(n)
println("10! = " + (10!))
}
C++ でのコンパイル時間
template<unsigned i>
struct factorial
{ static const unsigned value = i * factorial<i-1>::value; };
template<>
struct factorial<0>
{ static const unsigned value = 1; };
コードで次のように使用します。
Factorial<5>::value
facts: array[2..12] of integer;
function TForm1.calculate(f: integer): integer;
begin
if f = 1 then
Result := f
else if f > High(facts) then
Result := High(Integer)
else if (facts[f] > 0) then
Result := facts[f]
else begin
facts[f] := f * Calculate(f-1);
Result := facts[f];
end;
end;
initialize
for i := Low(facts) to High(facts) do
facts[i] := 0;
目的の値以上の階乗が最初に計算された後、このアルゴリズムは定数時間 O(1) で階乗を返すだけです。
int32 は 12 までしか保持できないことを考慮に入れます!
Nemerle: 機能的
def fact(n) {
| 0 => 1
| x => x * fact(x-1)
}
Python: 短絡ブール評価を使用した機能的で再帰的なワンライナー。
factorial = lambda n: ((n <= 1) and 1) or factorial(n-1) * n
改行が続く負でない整数を入力として受け入れ、改行が続く対応する階乗を出力します。
>>>>,----------[>>>>,----------]>>>>++<<<<<<<<[>++++++[<----
-->-]<-<<<<]>>>>[[>>+<<-]>>[<<+>+>-]<->+<[>>>>+<<<-<[-]]>[-]
>>]>[-<<<<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]>>]>>>>[-[>+<-]+>>>
>]<<<<[<<<<]<<<<[<<<<]>>>>>[>>>[>>>>]>>>>[>>>>]<<<<[[>>>>+<<
<<-]<<<<]>>>>+<<<<<<<[<<<<]>>>>-[>>>[>>>>]>>>>[>>>>]<<<<[>>>
+<<<-]>>>[<<<+>>+>-]<-[>>+<<[-]]<<[<<<<]>>>>[>[>+<-]>[<<+>+>
-]<<[>>>+<<<-]>>>[<<<+>>+>-]<->+++++++++[-<[-[>>>>+<<<<-]]>>
>>[<<<<+>>>>-]<<<]<[>>+<<<<[-]>>[<<+>>-]]>>]<<<<[<<<<]<<<[<<
<<]>>>>-]>>>>]>>>[>[-]>>>]<<<<[>>+<<-]>>[<<+>+>-]<->+<[>-<[-
]]>[-<<-<<<<[>>+<<-]>>[<<+>+>-]<->+<[>-<[-]]>]<<[<<<<]<<<<-[
>>+<<-]>>[<<+>+>-]+<[>-<[-]]>[-<<++++++++++<<<<-[>>+<<-]>>[<
<+>+>-]+<[>-<[-]]>]<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]<->+<[>>>
>+<<<-<[-]]>[-]>>]>]>>>[>>>>]<<<<[>+++++++[<+++++++>-]<--.<<
<<]++++++++++.
以前に投稿されたbrainf * ckの回答とは異なり、これはメモリの場所をオーバーフローしません. (その実装は n! を単一のメモリ位置に配置し、標準の bf ルールの下で事実上 n を 6 未満に制限します。) このプログラムは n! を出力します。n の任意の値に対して、時間とメモリ (または bf 実装) によってのみ制限されます。たとえば、私のマシンで Urban Muller のコンパイラを使用すると、1000 を計算するのに 12 秒かかります! プログラムが左/右にしか移動できず、1 ずつインクリメント/デクリメントできないことを考えると、これはかなり良いことだと思います。
信じられないかもしれませんが、これは私が書いた最初の bf プログラムです。約 10 時間かかりましたが、そのほとんどがデバッグに費やされました。残念なことに、Daniel B. Cristofani がfactorial generatorを書いたことを後で知りました。
>++++++++++>>>+>+[>>>+[-[<<<<<[+<<<<<]>>[[-]>[<<+>+>-]<[>+<-
]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>>>>+>+<
<<<<<-[>+<-]]]]]]]]]]]>[<+>-]+>>>>>]<<<<<[<<<<<]>>>>>>>[>>>>
>]++[-<<<<<]>>>>>>-]+>>>>>]<[>++<-]<<<<[<[>+<-]<<<<]>>[->[-]
++++++[<++++++++>-]>>>>]<<<<<[<[>+>+<<-]>.<<<<<]>.>>>>]
彼のプログラムははるかに短いですが、彼は事実上プロの BF ゴルファーです。
/fact0 { dup 2 lt { pop } { 2 copy mul 3 1 roll 1 sub exch pop fact0 } ifelse } def
/fact { 1 exch fact0 } def
Forth (再帰):
: 階乗 ( n -- n )
重複 1 > 場合
dup 1 - 再帰 *
そうしないと
ドロップ1
それから
;
Java Script: ビット fnc をカウントする「インタビューの質問」を使用したクリエイティブな方法。
function nu(x)
{
var r=0
while( x ) {
x &= x-1
r++
}
return r
}
function fac(n)
{
var r= Math.pow(2,n-nu(n))
for ( var i=3 ; i <= n ; i+= 2 )
r *= Math.pow(i,Math.floor(Math.log(n/i)/Math.LN2)+1)
return r
}
21まで使えます！その後、Chrome は科学表記法に切り替えます。インスピレーションは、睡眠不足とクヌースらの「具体的な数学」に感謝します。
? to factorial :n
> ifelse :n = 0 [output 1] [output :n * factorial :n - 1]
> end
そして呼び出すには：
? print factorial 5
120
これは、ロゴのUCBLogo方言を使用しています。
Moog moog => dac;
4.0 => moog.gain;
for (0 => int i; i < 8; i++) {
<<< factorial(i) >>>;
}
fun int factorial(int n) {
1 => int result;
if (n != 0) {
n * factorial(n - 1) => result;
}
Std.mtof(result % 128) => moog.freq;
0.25::second => now;
return result;
}
そして、それはこのように聞こえます。それほど面白くはありませんが、ねえ、それは単なる階乗関数です！
*NIXシェル
Linuxバージョン：
seq -s'*' 42 | bc
BSDバージョン：
jot -s'*' 42 | bc
Haskell：
factorial n = product [1..n]
Python：
再帰的
def fact(x):
return (1 if x==0 else x * fact(x-1))
イテレータの使用
import operator
def fact(x):
return reduce(operator.mul, xrange(1, x+1))
class
APPLICATION
inherit
ARGUMENTS
create
make
feature -- Initialization
make is
-- Run application.
local
l_fact: NATURAL_64
do
l_fact := factorial(argument(1).to_natural_64)
print("Result is: " + l_fact.out)
end
factorial(n: NATURAL_64): NATURAL_64 is
--
require
positive_n: n >= 0
do
if n = 0 then
Result := 1
else
Result := n * factorial(n-1)
end
end
end -- class APPLICATION
多くのMathematicaソリューションのうちの2つ（ただし、！は組み込みで効率的です）：
(* returns pure function *)
(FixedPoint[(If[#[[2]]>1,{#[[1]]*#[[2]],#[[2]]-1},#])&,{1,n}][[1]])&
(* not using built-in, returns pure function, don't use: might build 1..n list *)
(Times @@ Range[#])&
Perl、ペシマル:
# Because there are just so many other ways to get programs wrong...
use strict;
use warnings;
sub factorial {
my ($x)=@_;
for(my $f=1;;$f++) {
my $tmp=$f;
foreach my $g (1..$x) {
$tmp/=$g;
}
return $f if $tmp == 1;
}
}
「*」演算子を使用しないことで余分なポイントが得られると信じています...
わかりましたので、自分で試してみます。
(defun format-fact (stream arg colonp atsignp &rest args)
(destructuring-bind (n acc) arg
(format stream
"~[~A~:;~*~/format-fact/~]"
(1- n)
acc
(list (1- n) (* acc n)))))
(defun fact (n)
(parse-integer (format nil "~/format-fact/" (list n 1))))
より優れた、さらにあいまいな FORMAT ベースの実装が必要です。これは非常に簡単で退屈で、単純に FORMAT を IF の代わりに使用しています。明らかに、私は FORMAT の専門家ではありません。
FORTH、反復 1 ライナー
: FACT 1 SWAP 1 + 1 DO I * LOOP ;
v
>v"Please enter a number (1-16) : "0<
,: >$*99g1-:99p#v_.25*,@
^_&:1-99p>:1-:!|10 <
^ <
Cat's Eye Technologies のChris Pressey による難解な言語。
multi factorial ( Int $n where { $n <= 0 } ){
return 1;
}
multi factorial ( Int $n ){
return $n * factorial( $n-1 );
}
これも機能します：
multi factorial(0) { 1 }
multi factorial(Int $n) { $n * factorial($n - 1) }
最後の例の詳細については、use.perl.orgの Jonathan Worthington のジャーナルを確認してください。
sub factorial ( int $n ){
my $result = 1;
loop ( ; $n > 0; $n-- ){
$result *= $n;
}
return $result;
}
子：
編集: for ループ内の変数宣言のため、実際には C++ だと思います。
int factorial(int x) {
int product = 1;
for (int i = x; i > 0; i--) {
product *= i;
}
return product;
}
シンプルなソリューションが最適です。
#include <stdexcept>;
long fact(long f)
{
static long fact [] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 1932053504, 1278945280, 2004310016, 2004189184 };
static long max = sizeof(fact)/sizeof(long);
if ((f < 0) || (f >= max))
{ throw std::range_error("Factorial Range Error");
}
return fact[f];
}
(defun fact (n)
(loop for i from 1 to n
for acc = 1 then (* acc i)
finally (return acc)))
さて、誰かが FORMAT に基づいたバージョンを考え出すことができれば...
factorial = function( n )
{
return n > 0 ? n * factorial( n - 1 ) : 1;
}
Factorial が何であるかはわかりませんが、他のプログラムが JavaScript で行うことと同じです。
fact[n_] := Times @@ Range[n]
これは のシンタックス シュガーですApply[Times, Range[n]]。もちろん、ビルトインを数えないで、それが最善の方法だと思いますn!。自動的にbignumを使用することに注意してください。
(define (factorial n)
(define (fac-times n acc)
(if (= n 0)
acc
(fac-times (- n 1) (* acc n))))
(if (< n 0)
(display "Wrong argument!")
(fac-times n 1)))
(define factorial
(lambda (n)
(if (= n 0)
1
(* n (factorial (- n 1))))))
動作するはずですが、この関数を大量に呼び出すと、再帰ごとにスタックが拡張されることに注意してください。これは、C や Java などの言語では不適切です。
(define factorial
(lambda (n)
(factorial_cps n (lambda (k) k))))
(define factorial_cps
(lambda (n k)
(if (zero? n)
(k 1)
(factorial (- n 1) (lambda (v)
(k (* n v)))))))
ああ、この方法では、代わりに継続を拡張できるため、再帰ごとにスタックを大きくする必要はありません。ただし、C には継続がありません。
(define factorial
(lambda (n)
(factorial_cps n (k_))))
(define factorial_cps
(lambda (n k)
(if (zero? n)
(apply_k 1)
(factorial (- n 1) (k_extend n k))))
(define apply_k
(lambda (ko v)
(ko v)))
(define kt_empty
(lambda ()
(lambda (v) v)))
(define kt_extend
(lambda ()
(lambda (v)
(apply_k k (* n v)))))
元の CPS プログラムで使用されていた継続の表現の責任は、kt_ヘルパー プロシージャに移されたことに注意してください。
継続の表現はヘルパー プロシージャにあるため、型指示子として代わりにParentheCを使用するように切り替えることができます。kt_
(define factorial
(lambda (n)
(factorial_cps n (kt_empty))))
(define factorial_cps
(lambda (n k)
(if (zero? n)
(apply_k 1)
(factorial (- n 1) (kt_extend n k))))
(define-union kt
(empty)
(extend n k))
(define apply_k
(lambda ()
(union-case kh kt
[(empty) v]
[(extend n k) (begin
(set! kh k)
(set! v (* n v))
(apply_k))])))
それでは十分じゃない。グローバル変数とプログラムカウンターを設定する代わりに、すべての関数呼び出しを置き換えます。プロシージャーは、GOTO ステートメントに適したラベルになりました。
(define-registers n k kh v)
(define-program-counter pc)
(define-label main
(begin
(set! n 5) ; what is the factorial of 5??
(set! pc factorial_cps)
(mount-trampoline kt_empty k pc)
(printf "Factorial of 5: ~d\n" v)))
(define-label factorial_cps
(if (zero? n)
(begin
(set! kh k)
(set! v 1)
(set! pc apply_k))
(begin
(set! k (kt_extend n k))
(set! n (- n 1))
(set! pc factorial_cps))))
(define-union kt
(empty dismount) ; get off the trampoline!
(extend n k))
(define-label apply_k
(union-case kh kt
[(empty dismount) (dismount-trampoline dismount)]
[(extend n k) (begin
(set! kh k)
(set! v (* n v))
(set! pc apply_k))]))
ほら、私たちもmain今手続きをしています。あとは、このファイルを名前を付けて保存しfact5.pc、ParentheC の pc2c で実行するだけです。
> (load "pc2c.ss")
> (pc2c "fact5.pc" "fact5.c" "fact5.h")
それは可能性が？と を取得fact5.cしfact5.hました。どれどれ...
$ gcc fact5.c -o fact5
$ ./fact5
Factorial of 5: 120
成功！再帰的な Scheme プログラムを非再帰的な C プログラムに変換しました! そして、それを行うのに数時間しかかからず、壁に額の形をした多くの印象がありました！便宜上、fact5.cおよびfact5.hです。
Perl (Y-コンビネータ/機能)
print sub {
my $f = shift;
sub {
my $f1 = shift;
$f->( sub { $f1->( $f1 )->( @_ ) } )
}->( sub {
my $f2 = shift;
$f->( sub { $f2->( $f2 )->( @_ ) } )
} )
}->( sub {
my $h = shift;
sub {
my $n = shift;
return 1 if $n <=1;
return $n * $h->($n-1);
}
})->(5);
'print' の後と '->(5)' の前のすべてがサブルーチンを表します。階乗部分は最後の「sub {...}」にあります。他のすべては、Y コンビネーターを実装することです。
AWK
#!/usr/bin/awk -f
{
result=1;
for(i=$1;i>0;i--){
result=result*i;
}
print result;
}
def factorial(n)
(1 .. n).inject{|a, b| a*b}
end
def factorial(n)
n == 1 ? 1 : n * factorial(n-1)
end
fact=. verb define
*/ >:@i. y
)
<Extension()> _
Public Function Product(ByVal xs As IEnumerable(Of Integer)) As Integer
Return xs.Aggregate(1, Function(a, b) a * b)
End Function
Public Function Fact(ByVal n As Integer) As Integer
Return Aggregate x In Enumerable.Range(1, n) Into Product()
End Function
これはAggregate、VB でキーワードを使用する方法を示しています。C# はこれを行うことができません(ただし、C# はもちろん拡張メソッドを直接呼び出すことができます)。
#Language: T-SQL
#Style: Big Numbers
別の T-SQL ソリューションを次に示します。最もルーブ ゴールドバーグ的な方法で大きな数をサポートします。セットベースの操作がたくさん。一意に SQL を保持しようとしました。恐ろしいパフォーマンス (Dell Latitude D830 で 400! に 33 秒かかりました)
create function bigfact(@x varchar(max)) returns varchar(max) as begin
declare @c int
declare @n table(n int,e int)
declare @f table(n int,e int)
set @c=0
while @c<len(@x) begin
set @c=@c+1
insert @n(n,e) values(convert(int,substring(@x,@c,1)),len(@x)-@c)
end
-- our current factorial
insert @f(n,e) select 1,0
while 1=1 begin
declare @p table(n int,e int)
delete @p
-- product
insert @p(n,e) select sum(f.n*n.n), f.e+n.e from @f f cross join @n n group by f.e+n.e
-- normalize
while 1=1 begin
delete @f
insert @f(n,e) select sum(n),e from (
select (n % 10) as n,e from @p union all
select (n/10) % 10,e+1 from @p union all
select (n/100) %10,e+2 from @p union all
select (n/1000)%10,e+3 from @p union all
select (n/10000) % 10,e+4 from @p union all
select (n/100000)% 10,e+5 from @p union all
select (n/1000000)%10,e+6 from @p union all
select (n/10000000) % 10,e+7 from @p union all
select (n/100000000)% 10,e+8 from @p union all
select (n/1000000000)%10,e+9 from @p
) f group by e having sum(n)>0
set @c=0
select @c=count(*) from @f where n>9
if @c=0 break
delete @p
insert @p(n,e) select n,e from @f
end
-- decrement
update @n set n=n-1 where e=0
-- normalize
while 1=1 begin
declare @e table(e int)
delete @e
insert @e(e) select e from @n where n<0
if @@rowcount=0 break
update @n set n=n+10 where e in (select e from @e)
update @n set n=n-1 where e in (select e+1 from @e)
end
set @c=0
select @c=count(*) from @n where n>0
if @c=0 break
end
select @c=max(e) from @f
set @x=''
declare @l varchar(max)
while @c>=0 begin
set @l='0'
select @l=convert(varchar(max),n) from @f where e=@c
set @x=@x+@l
set @c=@c-1
end
return @x
end
例：
print dbo.bigfact('69')
戻り値：
171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000
#Language: T-SQL, C#
#Style: Custom Aggregate
別のクレイジーな方法は、カスタム集計を作成し、それを整数 1..n の一時テーブルに適用することです。
/* ProductAggregate.cs */
using System;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;
[Serializable]
[SqlUserDefinedAggregate(Format.Native)]
public struct product {
private SqlDouble accum;
public void Init() { accum = 1; }
public void Accumulate(SqlDouble value) { accum *= value; }
public void Merge(product value) { Accumulate(value.Terminate()); }
public SqlDouble Terminate() { return accum; }
}
これをSQLに追加します
create assembly ProductAggregate from 'ProductAggregate.dll' with permission_set=safe -- mod path to point to actual dll location on disk.
create aggregate product(@a float) returns float external name ProductAggregate.product
テーブルを作成します（SQLでこれを行う組み込みの方法があるはずです-うーん、SOの質問ですか？）
select 1 as n into #n union select 2 union select 3 union select 4 union select 5
そして最後に
select dbo.product(n) from #n
Common Lisp バージョン:
(defun ! (n) (reduce #'* (loop for i from 2 below (+ n 1) collect i)))
かなり速いようです。
* (! 42)
1405006117752879898543142606244511569936384000000000
fac := [ :x | x = 0 ifTrue: [ 1 ] ifFalse: [ x * (fac value: x -1) ]].
Transcript show: (fac value: 24) "-> 620448401733239439360000"
NB は Squeak では機能せず、完全な閉鎖が必要です。
Dictionary でメソッドを定義する
Dictionary >> fac: x
^self at: x ifAbsentPut: [ x * (self fac: x - 1) ]
利用方法
d := Dictionary new.
d at: 0 put: 1.
d fac: 24
(1 to: 24) inject: 1 into: [ :a :b | a * b ]
再帰共通テーブル式を使用したインラインテーブル関数。SQLServer2005以降。
CREATE FUNCTION dbo.Factorial(@n int) RETURNS TABLE
AS
RETURN
WITH RecursiveCTE (N, Value) AS
(
SELECT 1, CAST(1 AS decimal(38,0))
UNION ALL
SELECT N+1, CAST(Value*(N+1) AS decimal(38,0))
FROM RecursiveCTE
)
SELECT TOP 1 Value
FROM RecursiveCTE
WHERE N = @n
Occam-pi
PROC subprocess(MOBILE CHAN INT parent.out!,parent.in?)
INT value:
SEQ
parent.in ? value
IF
value = 1
SEQ
parent.out ! value
OTHERWISE
INITIAL MOBILE CHAN INT child.in IS MOBILE CHAN INT:
INITIAL MOBILE CHAN INT child.out IS MOBILE CHAN INT:
FORKING
INT newvalue:
SEQ
FORK subprocess(child.in!,child.out?)
child.out ! (value-1)
child.in ? newvalue
parent.out ! (newalue*value)
:
PROC main(CHAN BYTE in?,src!,kyb?)
INITIAL INT value IS 0:
INITIAL MOBILE CHAN INT child.out is MOBILE CHAN INT
INITIAL MOBILE CHAN INT child.in is MOBILE CHAN INT
SEQ
WHILE TRUE
SEQ
subprocess(child.in!,child.out?)
child.out ! value
child.in ? value
src ! value:
value := value + 1
:
うーん...TCLなし
proc factorial {n} {
if { $n == 0 } { return 1 }
return [expr {$n*[factorial [expr {$n-1}]]}]
}
puts [factorial 6]
しかしもちろん、それはnの値が大きい場合には機能しません。tcllibを使用するとさらにうまくいくことができます。
package require math::bignum
proc factorial {n} {
if { $n == 0 } { return 1 }
return [ ::math::bignum::tostr [ ::math::bignum::mul [
::math::bignum::fromstr $n] [ ::math::bignum::fromstr [
factorial [expr {$n-1} ]
]]]]
}
puts [factorial 60]
最後にあるすべての]を見てください。これは実質的にLISPです！
読者のためのエクササイズとして、n> 2^32の値のバージョンを残します
fact 0 = 1
fact n = n * fact (n-1)
これはn！を計算するだけでなく、O（n！）でもあります。ただし、「大きな」ものを計算したい場合は、問題が発生する可能性があります。
long f(long n)
{
long r=1;
for (long i=1; i<n; i++)
r=r*i;
return r;
}
long factorial(long n)
{
// iterative implementation should be efficient
long result;
for (long i=0; i<f(n); i++)
result=result+1;
return result;
}
真に機能的なJava：
public final class Factorial {
public static void main(String[] args) {
final int n = Integer.valueOf(args[0]);
System.out.println("Factorial of " + n + " is " + create(n).apply());
}
private static Function create(final int n) {
return n == 0 ? new ZeroFactorialFunction() : new NFactorialFunction(n);
}
interface Function {
int apply();
}
private static class NFactorialFunction implements Function {
private final int n;
public NFactorialFunction(final int n) {
this.n = n;
}
@Override
public int apply() {
return n * Factorial.create(n - 1).apply();
}
}
private static class ZeroFactorialFunction implements Function {
@Override
public int apply() {
return 1;
}
}
}
おたふく風邪の場合：
fact(N)
N F,I S F=1 F I=2:1:N S F=F*I
QUIT F
または、間接参照のファンの場合：
fact(N)
N F,I S F=1 F I=2:1:N S F=F_"*"_I
QUIT @F
Iswim / Lucid：
factorial = 1 fby factorial * (time+1);
Python、ワンライナー：
他のPythonの答えよりも少しきれいです。これと前の答えは、入力が1未満の場合は失敗します。
def fact（n）：return reduce（int。mul、xrange（2、n））
Java : 機能的
int factorial(int x) {
return x == 0 ? 1 : x * factorial(x-1);
}
Lisp : 末尾再帰
(defun factorial(x)
(labels((f (x acc)
(if (> x 1)
(f (1- x)(* x acc))
acc)))
(f x 1)))
もうひとつのルビー。
class Integer
def fact
return 1 if self.zero?
(1..self).to_a.inject(:*)
end
endこれは、シンボルで to_proc がサポートされている場合に機能します。
ActionScript: 手続き型/OOP
function f(n) {
var result = n>1 ? arguments.callee(n-1)*n : 1;
return result;
}
// function call
f(3);
~),1>{*}*
~入力文字列を (整数に) 評価します)数を増やします,範囲です（4、[0 1 2 3]になります）1>インデックスが 1 以上の値を選択します{*}*リスト上で乗算をたたみます走る：
echo 5 | ruby gs.rb fact.gs
function f($n){return array_reduce(range(1,$n),'bcmul',1);}
array_product(range(1,$n));
Bourne シェル: 機能的
factorial() {
if [ $1 -eq 0 ]
then
echo 1
return
fi
a=`expr $1 - 1`
expr $1 \* `factorial $a`
}
Korn Shell と Bourne Again Shell にも使用できます。:-)
パイソン:
def factorial(n):
return reduce(lambda x, y: x * y,range(1, n + 1))
OCaml とオッドボールが密接に関係していると誰も信じないように、階乗の適切な実装を提供しようと思いました。
# let rec factorial n =
if n=0 then 1 else n * factorial(n - 1);;
私は自分の主張をあまりうまくやったとは思わない...
.
def factorial( value: BigInt ): BigInt = value match {
case 0 => 1
case _ => value * factorial( value - 1 )
}
これは興味深い Ruby バージョンです。私のラップトップでは、30000が見つかります！1秒以内に。(Ruby では、計算よりも印刷用にフォーマットする方が時間がかかります。) これは、数字を順番に乗算する単純なソリューションよりも大幅に高速です。
def factorial (n)
return multiply_range(1, n)
end
def multiply_range(n, m)
if (m < n)
return 1
elsif (n == m)
return m
else
i = (n + m) / 2
return multiply_range(n, i) * multiply_range(i+1, m)
end
end
int f(int n) { for (int i = n - 1; i > 0; n *= i, i--); return n ? n : 1; }
簡潔にするために int を使用しました。より大きな数をサポートするには、他の型を使用してください。
単一行で再帰を使用する C# 階乗
private static int factorial(int n){ if (n == 0)return 1;else return n * factorial(n - 1); }
4 つの実装:
コード：
#!/usr/bin/env python
""" weave_factorial.py
"""
# [weave] factorial() as extension module in C++
from scipy.weave import ext_tools
def build_factorial_ext():
func = ext_tools.ext_function(
'factorial',
r"""
unsigned long long i = 1;
for ( ; n > 1; --n)
i *= n;
PyObject *o = PyLong_FromUnsignedLongLong(i);
return_val = o;
Py_XDECREF(o);
""",
['n'],
{'n': 1}, # effective type declaration
{})
mod = ext_tools.ext_module('factorial_ext')
mod.add_function(func)
mod.compile()
try: from factorial_ext import factorial as factorial_weave
except ImportError:
build_factorial_ext()
from factorial_ext import factorial as factorial_weave
# [python] pure python procedural factorial()
def factorial_python(n):
i = 1
while n > 1:
i *= n
n -= 1
return i
# [psyco] factorial() psyco-optimized
try:
import psyco
factorial_psyco = psyco.proxy(factorial_python)
except ImportError:
pass
# [list] list-lookup factorial()
factorials = map(factorial_python, range(21))
factorial_list = lambda n: factorials[n]
相対的なパフォーマンスを測定します。
$ python -mtimeit \
-s "from weave_factorial import factorial_$label as f" "f($n)"
n = 12
n = 20
µsecはマイクロ秒を表します。
これが私の提案です。Mathematica で実行され、正常に動作します。
gen[f_, n_] := Module[{id = -1, val = Table[Null, {n}], visit},
visit[k_] := Module[{t},
id++; If[k != 0, val[[k]] = id];
If[id == n, f[val]];
Do[If[val[[t]] == Null, visit[t]], {t, 1, n}];
id--; val[[k]] = Null;];
visit[0];
]
Factorial[n_] := Module[{res=0}, gen[res++&, n]; res]
更新 OK、これがどのように機能するかです: 訪問関数は Sedgewick のアルゴリズムの本からのもので、長さ n のすべての順列を「訪問」します。訪問時に、順列を引数として関数 f を呼び出します。
したがって、Factorial は長さ n のすべての順列を列挙し、順列ごとにカウンター res を増やして n! を計算します。O（n + 1）で！時間。
C++
factorial(int n)
{
for(int i=1, f = 1; i<=n; i++)
f *= i;
return f;
}
!(defun ! (n)
「階乗」
(ラベル ((fac (n prod)
(if (zerop n)
製品
(fac (- n 1) (* prod n)))))
(fac n 1)))
edit : またはオプションのパラメーターとしてアキュムレータを使用:
(defun ! (n &optional prod)
「階乗」
(if (zerop n)
製品
(! (- n 1) (* 製品 n))))
または、削減として、より大きなメモリフットプリントとより多くのconsingを犠牲にして：
(defun range (start end &optional acc)
"包括的開始から排他的終了までの範囲、開始 = 開始終了)
(nreverse acc)
(range (+ start 1) end (cons start acc))))
(defun ! (n)
「階乗」
(reduce #'* (range 1 (+ n 1))))
Lisp再帰:
(defun factorial (x)
(if (<= x 1)
1
(* x (factorial (- x 1)))))
USE: math.ranges
: 階乗 ( n -- n! ) 1 [a,b] 積 ;
これにより、マルチコア CPU を利用できますが、おそらく最も効果的な方法ではありません。openステートメントはfork でプロセスを複製し、子プロセスから親プロセスへのパイプを開きます。一度に 2 を乗算する作業は、非常に短時間のプロセスのツリーに分割されます。もちろん、この例は少しばかげています。要点は、実際にはもっと難しい計算があった場合、この例は作業を並列に分割する 1 つの方法を示しているということです。
#!/usr/bin/perl -w
use strict;
use bigint;
print STDOUT &main::rangeProduct(1,$ARGV[0])."\n";
sub main::rangeProduct {
my($l, $h) = @_;
return $l if ($l==$h);
return $l*$h if ($l==($h-1));
# arghhh - multiplying more than 2 numbers at a time is too much work
# find the midpoint and split the work up :-)
my $m = int(($h+$l)/2);
my $pid = open(my $KID, "-|");
if ($pid){ # parent
my $X = &main::rangeProduct($l,$m);
my $Y = <$KID>;
chomp($Y);
close($KID);
die "kid failed" unless defined $Y;
return $X*$Y;
} else {
# kid
print STDOUT &main::rangeProduct($m+1,$h)."\n";
exit(0);
}
}
JavaScript 匿名関数の使用:
var f = function(n){
if(n>1){
return arguments.callee(n-1)*n;
}
return 1;
}
注: を上書きし、以下eをf登録します。
[2++d]se[d1-d_1<fd0>e*]sf
使用するには、階乗を取得する値をスタックの一番上に置き、実行lfx(レジスタをロードしてf実行) します。これにより、スタックの一番上がポップされ、その値の階乗がプッシュされます。
説明: スタックのトップが の場合x、最初の部分はスタックのトップを のように見せます(x, x-1)。(x, (x-1)!)新しいスタックの最上位が負でない場合、再帰的に factorial を呼び出すため、スタックはx>= 1 または= 0 の場合(0, -1)ですx。次に、新しいスタックの最上位が負の場合、 を実行します2++d。(0, -1)をに置き換えます(1, 1)。最後に、スタックの上位 2 つの値を乗算します。
再帰、LOOP、さらには FORMAT を悪用する Common Lisp ソリューションを目にします。誰かが CLOS を悪用する解決策を書く時が来たと思います!
(defgeneric factorial (n))
(defmethod factorial ((n (eql 0))) 1)
(defmethod factorial ((n integer)) (* n (factorial (1- n))))
(あなたのお気に入りの言語のオブジェクト システム ディスパッチャーはそれを行うことができますか?)
... Haskell と Python がリスト内包表記を借用した場所。
proc factorial(n);
return 1 */ {1..n};
end factorial;
また、組み込みINTEGER型は任意精度であるため、これは任意の正の に対して機能しますn。
setGeneric( 'fct', function( x ) { standardGeneric( 'fct' ) } )
setMethod( 'fct', 'numeric', function( x ) {
lapply( x, function(a) {
if( a == 0 ) 1 else a * fact( a - 1 )
} )
} )
数値の配列を渡すことができるという利点があり、それらはすべてうまくいきます...
例えば：
> fct( c( 3, 5, 6 ) )
[[1]]
[1] 6
[[2]]
[1] 120
[[3]]
[1] 720
私はこれがより効率的なものになる可能性があるとかなり確信しています。これは、「hello、world」と第3章のサンプルコードの入力以外の私の最初のlisp関数です。PracticalCommonLispは素晴らしいテキストです。この関数は、大きな階乗をうまく処理するようです。
(defun factorial (x)
(if (< x 2) (return-from factorial (print 1)))
(let ((tempx 1) (ans 1))
(loop until (equalp x tempx) do
(incf tempx)
(setf ans (* tempx ans)))
(list ans)))
C++ の constexpr
constexpr uint64_t fact(uint32_t n)
{
return (n==0) ? 1:n*fact(n-1);
}
フォックスプロ:
function factorial
parameters n
return iif( n>0, n*factorial(n-1), 1)
Common Lisp、まだ誰もコミットしていないので:
(defun factorial (n)
(if (<= n 1)
1
(* n (factorial (1- n)))))
Vb6 :
Private Function factCalculation(ByVal Number%)
Dim intNum%
intNum = 1
For i = 2 To Number
intNum = intNum * Number
Next i
return intNum
End Function
Private Sub Form_Load()
Dim FactResult% : FactResult = factCalculation(3) 'e.g
Print FactResult
End Sub
factorial n = factorial' n 1
factorial' 0 a = a
factorial' n a = factorial' (n-1) (n*a)
イオでは：
factorial := method(n,
if (list(0, 1) contains(n),
1,
n * factorial(n - 1)
)
)