Факторные алгоритмы на разных языках

Я хочу увидеть все различные способы, которыми вы можете придумать, для подпрограммы факториала или программы. Надежда состоит в том, что любой может прийти сюда и посмотреть, захотят ли они выучить новый язык.

Идеи:

  • процедурный
  • функциональная
  • Объектно-ориентированный
  • Один лайнер
  • Запутанный
  • чудак
  • Плохой код
  • полиглот

По сути, я хочу увидеть пример различных способов написания алгоритма и того, как они будут выглядеть на разных языках.

Пожалуйста, ограничьте это одним примером для каждой записи. Я позволю вам иметь более одного примера для каждого ответа, если вы пытаетесь выделить определенный стиль, язык или просто хорошо продуманную идею, которая подойдет для одного поста.

Единственное реальное требование - это найти факториал данного аргумента во всех представленных языках.

Будь креативным!

Рекомендуемое руководство:

# Название языка: необязательный тип стиля

   - Дополнительные точки пули

    Код идет здесь

Другой информационный текст идет здесь

Иногда я согласен и отредактирую любой ответ, который не имеет достойного форматирования.

23.08.2008 03:46:32
Каждый, кто делает факториалы с использованием рекурсии, находится в состоянии греха! Только рекурсивный Фибоначчи хуже. :-)
stevenvh 18.09.2010 16:33:43
30 ОТВЕТОВ
РЕШЕНИЕ

Полиглот: 5 языков, все с использованием бигнумов

Итак, я написал полиглот, который работает на трех языках, на которых я часто пишу, а также один из моего другого ответа на этот вопрос и один, который я только что выучил сегодня. Это отдельная программа, которая читает одну строку, содержащую неотрицательное целое число, и печатает одну строку, содержащую ее факториал. Bignums используются на всех языках, поэтому максимальный вычисляемый факториал зависит только от ресурсов вашего компьютера.

  • Perl : использует встроенный пакет bignum. Беги с perl FILENAME.
  • Haskell : использует встроенные бигнумы. Запустите с runhugs FILENAMEили ваш любимый эквивалент компилятора.
  • C ++ : требуется GMP для поддержки bignum. Для компиляции с g ++ используйте g++ -lgmpxx -lgmp -x c++ FILENAMEссылки на нужные библиотеки. После компиляции запустите ./a.out. Или используйте эквивалент вашего любимого компилятора.
  • brainf * ck : Я написал некоторую поддержку bignum в этом посте . Используя классический дистрибутив Мюллера , скомпилируйте с bf < FILENAME > EXECUTABLE. Сделайте вывод исполняемым и запустите его. Или используйте ваш любимый дистрибутив.
  • Пробелы : используется встроенная поддержка bignum. Беги с wspace FILENAME.

Редактировать: добавлены пробелы в качестве пятого языка. Кстати, не оборачивайте код <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 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); вывести факт ($ n); напечатать ("\ n") / * 2;}; # -] <->
«+ <[> - <[-]]>] << [<<<<] <<<< - [>> + << -] >> [<< +> +> -] + <[> - +++
-} - <[-]]> [- << ++++++++++ <<<< - [>> + << -] >> [<< +> +> - ++
факт 0 = 1 -> <> <> <> <> <> <> <] + <[> - <[-]]>] << [<< + +
факт n = n * факт (n-1) {- <<] >>>> [[>> + << -] >> [<< +> +++> + -}
main = do {n <-readLn; print (факт n)} - +> -] <-> + <[>>>> + << +
{-X <- <[-]]> [-] >>]>] >>> [>>>>] <<<< [> +++++++ [<+++++++ > -]
<- <<<<] + написанный + по +++ A + Rex +++ 2009 + ';.. # +++ х -} - х * /;}
184
23.05.2017 12:13:33
Наибольшая факториальная вычислимость за одну секунду (не считая вывода) на моем компьютере различными языками в этой реализации: C ++ получает 45000 !, Haskell получает 35000 !, Whitespace получает 11000 !, Perl получает 2000 !, и brainf * ck получает 350! ,
A. Rex 14.01.2009 05:16:45
Вау, у кого-то есть время на руках. Я на самом деле рассматриваю это для принятого ответа.
Brad Gilbert 18.01.2009 01:13:23
Посмотрев на этот код в течение нескольких минут, мои глаза продолжали offensive?
AShelly 30.01.2009 23:29:44
Это удивительно, и этот ответ должен быть принят. Вау. Мой сосед по комнате и я только что попробовали это на всех языках и все еще в восторге. Отличная работа А. Рекс
Justin Bennett 2.02.2009 02:44:31
Это должно быть измерено с WTF в секунду.
Arnis Lapsa 22.07.2009 19:42:50

Perl 6: функциональный

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 , для получения дополнительной информации о последнем примере.

2
1.07.2009 18:38:24

Perl 6: процедурный

sub factorial ( int $n ){

  my $result = 1;

  loop ( ; $n > 0; $n-- ){

    $result *= $n;

  }

  return $result;
}
2
23.08.2008 03:48:58

C:

Редактировать: на самом деле C ++, я думаю, из-за объявления переменной в цикле for.

 int factorial(int x) {
      int product = 1;

      for (int i = x; i > 0; i--) {
           product *= i;
      }

      return product;
 }
2
23.08.2008 03:50:32

Javascript:

factorial = function( n )
{
   return n > 0 ? n * factorial( n - 1 ) : 1;
}

Я не уверен, что такое Factorial, но он делает то же, что и другие программы в javascript.

2
14.10.2008 15:11:34

Haskell:

ones = 1 : ones
integers   = head ones     : zipWith (+) integers   (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)
12
14.01.2009 05:52:35
Я думаю, что вам не хватает скобок, но (после 3: это не нужно.
Jared Updike 29.09.2008 17:34:52
Ваш факториал равен [1, 2, 3, 6, 18, 108, ...] вместо истинного факториала [1, 2, 6, 24, 120, 720, ...].
jfs 19.10.2008 13:33:17
factorials = 1 : (scanl1 (*) . scanl1 (+) . repeat $ 1)
Thomas Eding 24.01.2010 06:07:41

Схема

Вот простое рекурсивное определение:

(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))))
7
23.08.2008 15:24:44

C ++

factorial(int n)
{
    for(int i=1, f = 1; i<=n; i++)
        f *= i;
    return f;
}
1
23.08.2008 04:27:12

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 : Вы не указали тип возврата для функции

5
23.05.2017 12:13:34
Вы действительно должны убедиться, что n и $ n не отрицательны!
jmucchiello 22.12.2008 04:55:13

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    
124
2.09.2008 01:18:50
ЛОЛ. Совершенно неожиданно, понравилось.
Alex Weinstein 22.09.2008 04:17:35
Я принял ответ, потому что это был самый высокий голос. Если кто-то отправит ответ полиглота, я приму его в одно мгновение.
Brad Gilbert 14.10.2008 15:38:24
Здесь есть некоторые проблемы, например, тот факт, что цикл никогда не будет gtfo. Я вставил лучший
Chris Charabaruk 22.11.2008 08:30:58

Шаблоны 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)
7
30.01.2009 18:22:29
Во втором примере удалите «: 1»
Tim Matthews 30.01.2009 11:48:34
Спасибо. Другой пример, где тип выбирается при создании экземпляра шаблона: template factorial (T, T n) {static if (n == 1) const factorial = 1; иначе const factorial = n * factorial! (T, n-1); } factorial! (int, 5));
Tim Matthews 31.01.2009 10:26:36

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))
2
23.02.2009 01:08:37

два из многих решений Mathematica (хотя! является встроенным и эффективным):

(* 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[#])&
2
23.08.2008 20:16:37

Java : функциональный

int factorial(int x) {
    return x == 0 ? 1 : x * factorial(x-1);
}
1
26.08.2008 00:19:49
да, хорошо, забавно, если у вас нет оптимизации хвостового вызова.
Svante 11.01.2009 00:46:27

Mathematica : использование чисто рекурсивных функций

(If[#>1,# #0[#-1],1])&
3
25.08.2008 23:32:45

Рубин: функциональный

def factorial(n)
    return 1 if n == 1
    n * factorial(n -1)
end
4
26.08.2008 00:06:44

Lua

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]: ?
3
26.08.2008 00:17:28

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
9
14.10.2008 15:09:02
Вы также можете получить интереснее с раскрытием: let factorial n = (1,1) |> Seq.unfold (fun (n, p) -> let p '= n * p в Some (p', (n + 1, p) '))) |> Seq.nth (n-1)
namin 14.11.2008 06:55:06
@namim: или для чего-то меньшего излишнего, "позвольте факту x = [2 .. x] |> List.scan_left (*) 1"
Juliet 30.12.2008 14:35:57

Haskell: функциональный

 fact 0 = 1
 fact n = n * fact (n-1)
1
1.09.2008 03:34:45

C ++: шаблон метапрограммирования

Использует классический взлом enum.

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 является константой, как только компилятор выполнил свою работу.

48
3.11.2010 11:19:09
Перечисление не требуется, если вы просто объявляете результат как поле «static const int». Т.е. "static const int result = n * factorial <n - 1> :: result;". «Enum hack» необходим только для компилятора Visual Studio 6 C ++, который не поддерживает шаблоны должным образом.
pauldoo 22.09.2008 10:51:54
Предостережение, связанное с этим решением, заключается в том, что стандарт ANSI C ++ только обязывает компиляторы выполнять такие функции времени компиляции до предела - я считаю, 20 - уровней рекурсии. После этого вы попадаете на неизведанную территорию, оставленную на милость создателей компилятора.
Joe Pineda 27.09.2008 00:25:33
Я думаю, что factorial <20> - это самый большой факториал, который может быть представлен 64-битной длиной со знаком, так что все в порядке
Kip 6.10.2008 16:31:33
@Kip правильно, 20! меньше 2 ^ 64, но 21! больше 2 ^ 64.
Wedge 14.10.2008 21:18:52
pauldoo, но тогда вы также должны определить это статическое целое число const. невыполнение этого требования может привести к ошибке компиляции для некоторого компилятора (стандарт позволяет компиляторам не диагностировать это нарушение - поэтому вы часто не видите его отклоненным)
Johannes Schaub - litb 25.01.2009 01:54:27

Этот не только вычисляет 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;
}
1
1.09.2008 04:41:12

Сборка x86-64: процедурная

Вы можете вызвать это из C (проверено только с GCC на linux amd64). Сборка была собрана с насм.

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
14
6.10.2008 13:26:50

Visual Basic: Linq

<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 #, конечно, может вызывать метод расширения напрямую).

2
1.09.2008 09:16:11

PowerShell

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

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

    $result 
}

Вот одна строка:

$n..1 | % {$result = 1}{$result *= $_}{$result}
6
2.09.2008 03:23:35

Рекурсивный Пролог

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).
8
14.10.2008 15:18:09
я ожидал найти пример пролога. большой! :-)
Paulo Guedes 14.11.2008 12:37:49

Bourne Shell: функциональный

factorial() {
  if [ $1 -eq 0 ]
  then
    echo 1
    return
  fi

  a=`expr $1 - 1`
  expr $1 \* `factorial $a`
}

Также работает для Korn Shell и Bourne Again Shell. :-)

1
1.09.2008 12:04:27

Лисп рекурсивный:

(defun factorial (x) 
   (if (<= x 1) 
       1 
       (* x (factorial (- x 1)))))
1
1.09.2008 12:17:22
рекурсивный да, но вы должны сделать его рекурсивным, чтобы избежать переполнения стека.
Svante 11.01.2009 00:49:59

JavaScript Использование анонимных функций:

var f = function(n){
  if(n>1){
    return arguments.callee(n-1)*n;
  }
  return 1;
}
1
1.09.2008 13:02:56

Странные примеры? Как насчет использования гамма-функции! Так, 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)))
7
1.09.2008 21:30:12

C: один лайнер, процедурный

int f(int n) { for (int i = n - 1; i > 0; n *= i, i--); return n ? n : 1; }

Я использовал int для краткости; используйте другие типы для поддержки больших чисел.

1
2.09.2008 01:10:45