Реализации алгоритмов/Факториал: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 450: | Строка 450: | ||
</source> |
</source> |
||
===Программируемые калькуляторы «Электроника» |
===Программируемые калькуляторы «Электроника»=== |
||
Примечание: команда ВП по адресу <code>00.</code> превращает 0 в 1, позволяя корректно вычислять ''0! = 1''. |
Примечание: команда ВП по адресу <code>00.</code> превращает 0 в 1, позволяя корректно вычислять ''0! = 1''. |
||
====Вариант № 1==== |
====Вариант № 1==== |
||
С использованием счётчика в адресуемом регистре (в качестве r следует выбрать один из регистров: 0, 1, 2, 3). |
С использованием счётчика в адресуемом регистре (в качестве r следует выбрать один из регистров: 0, 1, 2, 3). |
||
<source> |
|||
⚫ | |||
<code> |
|||
</source> |
|||
⚫ | |||
</code> |
|||
====Вариант № 2==== |
====Вариант № 2==== |
||
С использованием регистров стека X, Y, Z (значение, находившееся в регистре Y, сохраняется). |
С использованием регистров стека X, Y, Z (значение, находившееся в регистре Y, сохраняется). |
||
<source> |
|||
00. ВП 01. В↑ 02. КНОП 03. 1 04. − 05. Fx≠0 06. 11 07. × 08. FВx 09. БП |
|||
<code> |
|||
10. 03 11. F⟳ 12. С/П |
|||
</ |
</source> |
||
====Вариант № 3==== |
====Вариант № 3==== |
||
С использованием регистров стека X, Y, Z, T (т. е. стек используется целиком). |
С использованием регистров стека X, Y, Z, T (т. е. стек используется целиком). |
||
<source> |
|||
00. ВП 01. ↔ 02. FВx 03. В↑ 04. FВx 05. 1 06. - 07. × 08. Fx=0 09. 03 |
|||
<code> |
|||
10. ↔ 11. С/П |
|||
</ |
</source> |
||
=== AT&T x86 Assembler === |
=== AT&T x86 Assembler === |
Версия от 20:41, 25 апреля 2017
Рекурсивные методы
Примеры реализаций рекурсивных функций для вычисления факториала.
Pascal
function fact(n : integer) : longint;
begin
if n <= 1 then fact := 1 else fact := n * fact(n - 1);
end;
Delphi
С подключённым модулем System.Math
function fact(n : integer) : int64;
begin
Result:=IfThen(n <= 1, 1, n * fact(n - 1));
end;
C/C++
int factorial(int n) {
return n<=1 ? 1 : n * factorial(n-1);
}
Common Lisp
(defun factorial (n)
(if (= n 0)
1
(* (factorial (- n 1)) n)))
Clojure
(defn fact[x]
(if (<= x 1) 1 (* x (fact (- x 1)) )))
Forth
: factorial ( n -- n! )
dup 0= if
drop 1
else
dup 1- recurse *
endif ;
Go
func Factorial(n uint) uint {
if n == 0 {
return 1
}
return n * Factorial(n - 1)
}
Scheme
(define (factorial n)
(if (= n 0)
1
(* (factorial (- n 1)) n)))
Ruby
def factorial n
n > 1 ? n * factorial(n - 1) : 1
end
Rust
fn factorial_recursive (n: u64) -> u64 {
match n {
0 => 1,
_ => n * factorial_recursive(n-1)
}
}
fn main () {
println!("{}", factorial_recursive(5))
}
PHP
function factorial($n)
{
return $n ? $n * factorial($n-1) : 1;
}
Perl
#!/usr/bin/perl
sub factorial {
my $n = shift;
if ($n==0) {
return 1;
} else {
return $n*factorial($n-1);
}
}
print factorial(shift);
или однострочник
perl -e 'sub f{ $_[0] <= 1 ? 1 : $_[0] * f($_[0] - 1)}; print f(shift)' number
Simula
integer procedure factorial (n); integer n;
factorial := if n=0 then 1 else n*factorial(n-1);
begin
integer n;
n:=10
outint(n,5);
outtext("! = ");
outint(factorial(n),10);
outimage;
end
Smalltalk
factorial
"Answer the factorial of the receiver."
self = 0 ifTrue: [^ 1].
self > 0 ifTrue: [^ self * (self - 1) factorial].
self error: ’Not valid for negative integers’
Swift
func factorial(n: Int) -> Int {
return n == 0 ? 1 : n * factorial(n - 1)
}
Algol 68
PROC factorial = (INT n) INT:
BEGIN
IF n=0 THEN
1
ELSE
n*factorial(n-1)
FI
END;
print (factorial(10))
Ada
function Factorial (N: Natural) return Natural is
begin
if N = 0 then
return 1;
else
return N * Factorial(N - 1);
end if;
end Factorial;
или используя «if expression» (Ada 2012)
function Factorial (N: Natural) return Natural is
begin
return (if N = 0 then 1 else N * Factorial(N - 1));
end Factorial;
LaTeX
\documentclass{article}
\usepackage{ifthen}
\newcounter{multi} \newcounter{multa}
\newcommand{\mult}[2]{ \setcounter{multi}{1} \setcounter{multa}{#1}
\whiledo{\themulti < #2}{ \addtocounter{multa}{#1} \stepcounter{multi} } }
\newcounter{faki} \newcounter{faka}
\newcommand{\fac}[1]{
\setcounter{faka}{1} \setcounter{faki}{2}
\whiledo{\thefaki < #1}{
\mult{\thefaka}{\thefaki}
\setcounter{faka}{\themulta}
\stepcounter{faki}}
\mult{\thefaka}{\thefaki} \themulta}
\begin{document}
\Huge $10!=\fac{10}$
\end{document}
Java и C#
public int fact(int num) {
return (num == 0) ? 1 : num * fact(num - 1);
}
JavaScript
var factorial = function factorialis (m) {
var n = parseInt(m);
return (n < 0 || m != n) ? NaN : (n == 0 ? 1 : n * factorialis(n - 1));
}
CoffeeScript
factorial = (n) -> !n and 1 or n * factorial(n - 1);
Python
def factorial(x):
return 1 if x==0 else x * factorial(x-1)
или
factorial = lambda x: x and factorial(x - 1) * x or 1
или
import math
math.factorial(x)
Refal
Factorial {
0 = 1;
s.Value = <Mul s.Value <Factorial <Sub s.Value 1>>>;
}
Haskell
factorial :: Integer -> Integer
factorial 0 = 1
factorial n | n > 0 = n * factorial (n - 1)
factorial _ = error "Факториал не определен для отрицательных чисел"
или
factorial :: Integer -> Integer
factorial n = product [1..n]
D
long Factorial(int n)
{
if (n <= 1)
return 1;
return n * Factorial(n - 1);
}
Нерекурсивные методы
Примеры реализаций нерекурсивных функций для вычисления факториала.
Pascal
function factorial(n : integer) : longint;
var
i : integer;
f : longint;
begin
f := 1;
for i := 2 to n do
f := f * i;
factorial := f
end;
Perl
#!/usr/bin/perl
sub factorial {
my $f=1;
my @fct= $f .. $_[0];
foreach (@fct) {$f*=$_;} $f;
}
C/C++
int factorial(int n) {
int result = 1;
for ( int i = 2; i <= n; i++ ) {
result *= i;
}
return result;
}
Java и C#
public static int factorial(int num) {
int fact = 1;
for (; num > 0; fact *= num--);
return fact;
}
JavaScript
function factorial (m) {
var n = parseInt(m);
if (n < 0 || m != n) return NaN;
for (var i = 1, r = 1; i <= n; i++) {
r *= i;
}
return r;
}
CoffeeScript
factorial = (n) ->
res = 1
res *= n-- while n > 1
res
или
factorial = (n) -> [1..n].reduce (x,y) -> x * y || 1
Lisp
(defun factorial (n)
(if (< n 1)
1
(do ((f 1) (i 2 (1+ i)))
((> i n) f)
(setq f (* f i)))))
Fortran
integer function fact (n)
integer n
fact = 1
do i = 1,n
fact = fact * i
enddo
return
end
program factorial
integer fact
external fact
n = 10
write (*,*) n,"! = ",fact(n)
end program factorial
Unix Shell
#!/bin/sh
result=1
for (( factor=$1 ; $factor ; factor=$factor-1 ))
do
let -i result=$result*$factor
done
echo $result
CMD Shell
@echo off
:: factcmd.cmd - factorial of the first parameter.
set /a n=%1
set f=1 & for /l %%i in (1,1,%n%) do set /a f=%%i*f
echo %f%
PHP
function factorial($n)
{
$result = 1;
for ($i=2; $i<=$n; $i++)
$result *= $i;
return $result;
}
или
function factorial($n) {
return ($n <= 1) ? 1 : array_product(range(1,$n));
}
Cobol
identification division.
program-id. factorial.
environment division.
data division.
working-storage section.
77 result pic 9(8).
77 n pic 9(8).
77 i pic 9(8).
procedure division.
main-line.
display "Enter a positive number: " with no advancing
accept n
move 1 to result.
perform varying i from 1 by 1 until i>n
multiply result by i giving result
end-perform
display "Factorial(" n ")= " result
stop run.
Basic
input "N = "; n
f=1
for i = 1 to n
f=f*i
next i
print n;"! = ";f
Программируемые калькуляторы «Электроника»
Примечание: команда ВП по адресу 00.
превращает 0 в 1, позволяя корректно вычислять 0! = 1.
Вариант № 1
С использованием счётчика в адресуемом регистре (в качестве r следует выбрать один из регистров: 0, 1, 2, 3).
00. ВП 01. Пr 02. 1 03. ИПr 04. × 05. FLr 06. 03 07. С/П
Вариант № 2
С использованием регистров стека X, Y, Z (значение, находившееся в регистре Y, сохраняется).
00. ВП 01. В↑ 02. КНОП 03. 1 04. − 05. Fx≠0 06. 11 07. × 08. FВx 09. БП
10. 03 11. F⟳ 12. С/П
Вариант № 3
С использованием регистров стека X, Y, Z, T (т. е. стек используется целиком).
00. ВП 01. ↔ 02. FВx 03. В↑ 04. FВx 05. 1 06. - 07. × 08. Fx=0 09. 03
10. ↔ 11. С/П
AT&T x86 Assembler
factorial.s: .globl factorial
factorial:
movl $1, %eax
jmp .L2
.L3:
imull 2(%esp), %eax
decl 78(%esp)
.L2:
cmpl $1, 4(%esp)
jg .L3
ret
factorial-main.c: #include <stdio.h>
extern int factorial (int n);
int main () {
int n = 10;
printf ("%d! = %d\n", n, factorial (n));
}
gcc factorial-main.c factorial.s
Refal+
$func Factorial s.n = s.fact;
Factorial s.n =
1 s.n $iter <Mult s.fact s.n> <Sub s.n 1> :: s.fact s.n,
s.n : 0 =
s.fact;
Ruby
def factorial n
(1..n).inject(:*) || 1
end
Без итераторов:
def factorial n
f = 1
for i in 2..n
f *= i
end
f
end
Python
def factorial(x):
return reduce(lambda x, y : x * y, xrange(1, x + 1), 1)
С while циклом:
def factorial(x):
res = 1
while x > 0:
res *= x
x -= 1
return res
J
factorial=: */@(>:@i.)
RSL (Object RSL)
Macro factorial (n)
if (n < 0)
fact = "Enter a positive number";
elif (n == 0)
fact = 1;
else
fact = i = 1;
while (i <= n)
fact = fact*i;
i = i + 1;
end;
end;
return fact;
end;
Ada
function Factorial (N: Natural) return Natural is
Acc : Natural := 1;
begin
for I in 2 .. N loop
Acc := Acc * I;
end loop;
return Acc;
end Factorial;