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

В моем случае я хотел добавить метод с пользовательским swift-объектом в качестве параметра типа, а имя, которое я дал переменной в параметре, было точно таким же, как имя класса пользовательского объекта

Проблемы были примерно такими:

func moveBlob(**blob** : blob){
    ...code
}

Часть жирным шрифтом вызывала ошибку необъявленного типа

64
задан 13 revs, 4 users 100% 21 September 2014 в 15:40
поделиться

129 ответов

Оболочка Bourne: Функциональный

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

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

Также работы для Korn Shell и Граница Снова Shell.:-)

1
ответ дан 2 revs 24 November 2019 в 15:33
поделиться

Этот не только вычисляет 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
ответ дан 1800 INFORMATION 24 November 2019 в 15:33
поделиться

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

 fact 0 = 1
 fact n = n * fact (n-1)
1
ответ дан Andres 24 November 2019 в 15:33
поделиться

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

int factorial(int x) {
    return x == 0 ? 1 : x * factorial(x-1);
}
1
ответ дан 2 revs 24 November 2019 в 15:33
поделиться

C++

factorial(int n)
{
    for(int i=1, f = 1; i<=n; i++)
        f *= i;
    return f;
}
1
ответ дан Niyaz 24 November 2019 в 15:33
поделиться

Логотип

? to factorial :n
> ifelse :n = 0 [output 1] [output :n * factorial :n - 1]
> end

И вызвать:

? print factorial 5
120

Это использует диалект UCBLogo логотипа.

2
ответ дан mweiss 24 November 2019 в 15:33
поделиться

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
ответ дан 2 revs, 2 users 75% 24 November 2019 в 15:33
поделиться

Delphi, повторяющийся

, В то время как рекурсия может быть единственным достойным решением проблемы для факториалов, это не. Описать это, да. Программировать его, нет. Повторение является самым дешевым.

Эта функция вычисляет факториалы для несколько больших споров.

function Factorial(aNumber: Int64): String;
var
  F: Double;
begin
  F := 0;
  while aNumber > 1 do begin
    F := F + log10(aNumber);
    dec(aNumber);
  end;
  Result := FloatToStr(Power(10, Frac(F))) + ' * 10^' + IntToStr(Trunc(F));
end;

1000000! = 8.2639327850046 * 10^5565708

2
ответ дан stevenvh 24 November 2019 в 15:33
поделиться

Версия языка Common LISP:

(defun ! (n) (reduce #'* (loop for i from 2 below (+ n 1) collect i)))

, Кажется, довольно быстр.

* (! 42)

1405006117752879898543142606244511569936384000000000
2
ответ дан 2 revs 24 November 2019 в 15:33
поделиться

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

fact[n_] := Times @@ Range[n]

, Который является синтаксическим сахаром для Apply[Times, Range[n]]. Я думаю, что это - лучший способ сделать это, не считая встроенное n!, конечно. Обратите внимание, что это автоматически использует сверхбольшие числа.

2
ответ дан dreeves 24 November 2019 в 15:33
поделиться

Perl (Y-combinator/Functional)

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

Все после 'печати' и прежде чем '-> (5)' представляет подпрограмму. Факториальная часть находится в финале "sub {...}". Все остальное должно реализовать Y-combinator.

2
ответ дан 2 revs 24 November 2019 в 15:33
поделиться

Smalltalk, с помощью закрытия

    fac := [ :x | x = 0 ifTrue: [ 1 ] ifFalse: [ x * (fac value: x -1) ]].

    Transcript show: (fac value: 24) "-> 620448401733239439360000"

нбар не работает в Писке, требует полных закрытий.

2
ответ дан 2 revs 24 November 2019 в 15:33
поделиться

Smalltalk, 1 лайнер

(1 to: 24) inject: 1 into: [ :a :b | a * b ] 
2
ответ дан akuhn 24 November 2019 в 15:33
поделиться

Smalltalk, мемоизованные

, Определяют метод на Словаре

Dictionary >> fac: x
    ^self at: x ifAbsentPut: [ x * (self fac: x - 1) ]

использование

 d := Dictionary new.
 d at: 0 put: 1.
 d fac: 24 
2
ответ дан akuhn 24 November 2019 в 15:33
поделиться

J

   fact=. verb define
*/ >:@i. y
)
2
ответ дан geocar 24 November 2019 в 15:33
поделиться

befunge-93

                                    v
>v"Please enter a number (1-16) : "0<
,:             >$*99g1-:99p#v_.25*,@
^_&:1-99p>:1-:!|10          < 
         ^     <

тайный язык Chris Pressey Eye Technologies CAT .

2
ответ дан 2 revs 24 November 2019 в 15:33
поделиться

Эйфелева


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
2
ответ дан 2 revsFrancesco 24 November 2019 в 15:33
поделиться

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
ответ дан 3 revs 24 November 2019 в 15:33
поделиться

Haskell:

factorial n = product [1..n]
2
ответ дан yfeldblum 24 November 2019 в 15:33
поделиться

Ruby: итеративный

def factorial(n)
  (1 .. n).inject{|a, b| a*b}
end

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

def factorial(n)
  n == 1 ? 1 : n * factorial(n-1)
end
2
ответ дан 3 revs, 3 users 63%Peter Morris 24 November 2019 в 15:33
поделиться

JavaScript:

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

я не уверен, что Факториал всего лишь, который делает то, что другие программы делают в JavaScript.

2
ответ дан 2 revs, 2 users 93% 24 November 2019 в 15:33
поделиться
#Language: T-SQL
#Style: Big Numbers

Вот еще одно решение T-SQL - поддержка больших чисел в рубиново-голдберговой манере. Много основанных на множестве операций. Пытался сохранить это однозначно SQL. Ужасная производительность (400! Потребовалось 33 секунды на Dell Latitude D830)

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
2
ответ дан 2 revs 24 November 2019 в 15:33
поделиться
#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
2
ответ дан 2 revs 24 November 2019 в 15:33
поделиться

AWK

#!/usr/bin/awk -f
{
    result=1;
    for(i=$1;i>0;i--){
        result=result*i;
    }
    print result;
}
2
ответ дан dogbane 24 November 2019 в 15:33
поделиться

Common Lisp: FORMAT (обфусцированный)

Хорошо, так что я сам попробую.

(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. Очевидно, я не эксперт ФОРМАТ.

2
ответ дан Matthias Benkard 24 November 2019 в 15:33
поделиться

Common Lisp: Lisp как Бог намеревался использовать его (то есть с LOOP)

(defun fact (n)
  (loop for i from 1 to n
        for acc = 1 then (* acc i)
        finally (return acc)))

Теперь, если кто-то может придумать версию на основе FORMAT ...

2
ответ дан Matthias Benkard 24 November 2019 в 15:33
поделиться

Perl, pessimal:

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

Полагаю, я получаю дополнительные баллы за то, что не использовал оператор '*' ...

2
ответ дан 24 November 2019 в 15:33
поделиться

* NIX Shell

Версия Linux:

seq -s'*' 42 | bc

Версия BSD:

jot -s'*' 42 | bc
2
ответ дан 24 November 2019 в 15:33
поделиться

FORTH, итеративный 1 лайнер

: FACT 1 SWAP 1 + 1 DO I * LOOP ;
2
ответ дан 24 November 2019 в 15:33
поделиться

Развитие схемы

Программа на обычной схеме:

(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 нет продолжений.

Независимый от представления CPS

(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_ .

Независимый от представления CPS с использованием объединений ParentheC

Поскольку представление продолжений находится во вспомогательных процедурах, мы можем переключиться на использование 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))])))

Запутанная, зарегистрированная программа ParentheC

Этого недостаточно. Теперь мы заменяем все вызовы функций, вместо этого устанавливая глобальные переменные и счетчик программы. Процедуры теперь являются метками, подходящими для операторов 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))]))

О, смотрите, теперь у нас тоже есть основная процедура. Теперь все, что осталось сделать, это сохранить этот файл как fact5.pc и запустить его через pc2c ParentheC:

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

2
ответ дан 24 November 2019 в 15:33
поделиться
Другие вопросы по тегам:

Похожие вопросы: