Пи Оккама

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
:

Scala: Рекурсивный

• Должен скомпилировать в то, чтобы быть рекурсивным хвостом. Если!

.

def factorial( value: BigInt ): BigInt = value match {
  case 0 => 1
  case _ => value * factorial( value - 1 )
}

Вот интересная версия Ruby. На моем ноутбуке это найдет 30000! менее чем за секунду. (У 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

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

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

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

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

var f = function(n){
  if(n>1){
    return arguments.callee(n-1)*n;
  }
  return 1;
}

рекурсивный Lisp:

(defun factorial (x) 
   (if (<= x 1) 
       1 
       (* x (factorial (- x 1)))))

OCaml

, Чтобы любой не верит OCaml и чудаку, идет рука об руку, я думал, что обеспечу нормальную реализацию факториала.

# let rec factorial n =
    if n=0 then 1 else n * factorial(n - 1);;

я не думаю, что изложил доводы очень хорошо...

Подлинно функциональная 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;
    }
  }

}

C # факториал с использованием рекурсии в одной строке

private static int factorial(int n){ if (n == 0)return 1;else return n * factorial(n - 1); }

Python, C/C++ (переплетается): многоязычный, Процедурный

Четыре реализации:

• [переплетаются]
• [Python]
• [психо]
• [список]

Код:

#!/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)"

1. n = 12

   • [ткут] 0,70 µ секунда ( 2 )
   • [Python] 3,8 µ секунда ( 9 )
   • [психо] 1,2 µ секунда ( 3 )
   • [список] 0,43 µ секунды ( 1 )

2. n = 20

   • [ткут] 0,85 µ секунда ( 2 )
   • [Python] 9,2 µ секунда ( 21 )
   • [психо] 4,3 µ секунда ( 10 )
   • [список] 0,43 µ секунда ( 1 )

µ секунда стоит в течение многих микросекунд.

Golfscript: разумеется, предназначенный для игры в гольф

~),1>{*}*

• ~ вычисляет входную строку (в целое число)
• ) увеличивает число
• , является диапазоном (4, становится [0 1 2 3])
• 1> выбирает значения, индекс которых равен 1 или больше
• {*}* складывает умножение по списку
• Содержимое стека печатается после завершения программы.

Для запуска:

echo 5 | ruby gs.rb fact.gs

Python:

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

Вот мое предложение. Работает в 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]

Обновление Хорошо, вот как это работает: функция посещения из книги Алгоритмов Седжвика, она «посещает» все перестановки длины n. При посещении он вызывает функцию f с перестановкой в ​​качестве аргумента.

Итак, Factorial перечисляет все перестановки длины n, и для каждой перестановки счетчик res увеличивается, таким образом вычисляя n! в O (n + 1)! время.

REBOL

Математика определенно не является одной из сильных сторон REBOL, поскольку в ней отсутствуют целые числа произвольной точности. Ради полноты я подумал, что все равно добавлю это.

Вот стандартная, наивная рекурсивная реализация:

fac: func [ [catch] n [integer!] ] [
    if n < 0 [ throw make error! "Hey dummy, your argument was less than 0!" ]
    either n = 0 [ 1 ] [
        n * fac (n - 1)
    ]
]

И это все. Двигайтесь, ребята, здесь нечего видеть ...:)

Лисп: хвостовая рекурсия

(defun factorial(x)
  (labels((f (x acc)
             (if (> x 1)
                 (f (1- x)(* x acc))
                 acc)))
         (f x 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 как excersize для читателя

Язык Common LISP

• Зовет его по имени: !
• Хвост, рекурсивный
• , язык Common LISP обрабатывает произвольно большие количества

(defun ! (n)
  "factorial"
  (labels ((fac (n prod)
             (if (zerop n)
                 prod
                 (fac (- n 1) (* prod n)))))
    (fac n 1)))

редактирование : или с аккумулятором как дополнительный параметр:

(defun ! (n &optional prod)
  "factorial"
  (if (zerop n)
      prod
      (! (- n 1) (* prod n))))

или как уменьшение, за счет большего объема потребляемой памяти и более концентрирования:

(defun range (start end &optional acc)
  "range from start inclusive to end exclusive, start = start end)
      (nreverse acc)
      (range (+ start 1) end (cons start acc))))

(defun ! (n)
  "factorial"
  (reduce #'* (range 1 (+ n 1))))

ActionScript: процедурный / ООП

function f(n) {
    var result = n>1 ? arguments.callee(n-1)*n : 1;
    return result;
}
// function call
f(3);

В MUMPS:

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

Фактор

ИСПОЛЬЗОВАНИЕ: math.ranges

: факториал (n - n!) 1 [a, b] произведение;

Python, один лайнер:

немного более чистый, чем другой ответ Python. Это и предыдущий ответ, перестанут работать, если вход будет меньше чем 1.

факт определения (n): возврат уменьшает (интервал mul, xrange (2, n))

Исвим / Люсид:

factorial = 1 fby factorial * (time+1);

R - использующий методы S4 (рекурсивно)

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

dc

Примечание: блокирует регистры e и f:

[2++d]se[d1-d_1<fd0>e*]sf

Чтобы использовать, поместите значение, которое вы хотите получить, на множитель в верхней части суммировать, а затем выполнить lfx (загрузить регистр f и выполнить его), который затем выталкивает вершину стека и помещает факториал этого значения.

Объяснение: если вершина стека равна x, то первая часть делает вершину стека похожей на (x, x-1). Если новая вершина стека неотрицательна, она вызывает факториал рекурсивно, поэтому теперь стек равен (x, (x-1)!) для x> = 1 или (0, -1) для x = 0. Затем, если новый top-of-stack отрицателен, он выполняет 2++d, который заменяет (0, -1) на (1, 1). Наконец, он умножает два верхних значения в стеке.

Mathematica, мемоизованный

f[n_ /; n < 2] := 1
f[n_] := (f[n] = n*f[n - 1])

Mathematica поддерживает n! исходно, но это показывает, как сделать определения на лету. При выполнении f[2] этот код сделает определение f [2] =2, которое будет впоследствии выполняться не по-другому, чем если бы Вы трудно кодировали он; никакая потребность во внутренней структуре данных; Вы просто используете собственное функциональное оборудование определения языка.

Еще один рубиновый.

class Integer
  def fact
    return 1 if self.zero?
    (1..self).to_a.inject(:*)
  end
end

Это работает, если to_proc поддерживается для символов.

SETL

.. . где Haskell и Python заимствовали свое понимание списков из.

proc factorial(n);
    return 1 */ {1..n};
end factorial;

А встроенный тип INTEGER имеет произвольную точность, так что он будет работать для любого положительного n .

Befunge:

0&>:1-:v v *_$.@ 
  ^    _$>\:^

BLUCE

Я вижу, что общие решения Lisp, злоупотребляющие рекурсию, петлю и даже формат Отказ Я думаю, пришло время для того, чтобы кто-нибудь написать решение, которое злоупотребляет скину!

(defgeneric factorial (n))
(defmethod factorial ((n (eql 0))) 1)
(defmethod factorial ((n integer)) (* n (factorial (1- n))))

(Может ли ваш диспетчера объектной системы Listan Language?)

Oh fork() еще один пример в Perl

Это позволит использовать ваши многоядерные процессоры... хотя, возможно, не самым эффективным образом. Оператор open клонирует процесс с помощью fork и открывает канал от дочернего процесса к родительскому. Работа по умножению чисел по 2 за раз распределяется между деревом очень короткоживущих процессов. Конечно, этот пример немного глуповат. Суть в том, что если бы вам действительно нужно было выполнить более сложные вычисления, то этот пример иллюстрирует один из способов параллельного разделения работы.

#!/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);
    }
}