Wyzwanie:

Napisz program lub funkcję, która wprowadza liczbę dodatnią i zwraca jej silnię .

^{Uwaga: jest to pytanie trollujące kod . Proszę nie brać poważnie pytania i / lub odpowiedzi. Więcej informacji tutaj . Każde pytanie trollujące kod jest również pytaniem o popularność , więc wygrywa najwyższa odpowiedź.}

Jest to bardzo prosty numeryczny problem obliczeniowy, który możemy rozwiązać za pomocą przybliżenia Stirlinga :

Jak widać, ta formuła zawiera pierwiastek kwadratowy, który również będziemy potrzebować w przybliżeniu. Wybieramy do tego tak zwaną „metodę babilońską” , ponieważ jest ona prawdopodobnie najprostsza:

Pamiętaj, że obliczenie pierwiastka kwadratowego w ten sposób jest dobrym przykładem rekurencji.

Połączenie tego wszystkiego w programie Python daje nam następujące rozwiązanie twojego problemu:

def sqrt(x, n): # not the same n as below
    return .5 * (sqrt(x, n - 1) + x / sqrt(x, n - 1)) if n > 0 else x

n = float(raw_input())
print (n / 2.718) ** n * sqrt(2 * 3.141 * n, 10)

Po prostej modyfikacji powyższy program może wygenerować porządną tabelę silni:

1! =    0.92215
2! =    1.91922
3! =    5.83747
4! =   23.51371
5! =  118.06923
6! =  710.45304
7! = 4983.54173
8! = 39931.74015
9! = 359838.58817

Ta metoda powinna być wystarczająco dokładna dla większości aplikacji.

DO#

Przykro mi, ale nie znoszę funkcji rekurencyjnej.

public string Factorial(uint n) {
    return n + "!";
}

Jawa

public int factorial ( int n ) {
switch(n){
case 0: return 1;
case 1: return 1;
case 2: return 2;
case 3: return 6;
case 4: return 24;
case 5: return 120;
case 6: return 720;
case 7: return 5040;
case 8: return 40320;
case 9: return 362880;
case 10: return 3628800;
case 11: return 39916800;
case 12: return 479001600;
default : throw new IllegalArgumentException();
}
}

Pyton

Oczywiście najlepszym sposobem rozwiązania dowolnego problemu jest użycie wyrażeń regularnych:

import re

# adapted from http://stackoverflow.com/q/15175142/1333025
def multiple_replace(dict, text):
  # Create a regular expression  from the dictionary keys
  regex = re.compile("(%s)" % "|".join(map(re.escape, dict.keys())))
  # Repeat while any replacements are made.
  count = -1
  while count != 0:
    # For each match, look-up corresponding value in dictionary.
    (text, count) = regex.subn(lambda mo: dict[mo.string[mo.start():mo.end()]], text)
  return text

fdict = {
    'A': '@',
    'B': 'AA',
    'C': 'BBB',
    'D': 'CCCC',
    'E': 'DDDDD',
    'F': 'EEEEEE',
    'G': 'FFFFFFF',
    'H': 'GGGGGGGG',
    'I': 'HHHHHHHHH',
    'J': 'IIIIIIIIII',
    'K': 'JJJJJJJJJJJ',
    'L': 'KKKKKKKKKKKK',
    'M': 'LLLLLLLLLLLLL',
    'N': 'MMMMMMMMMMMMMM',
    'O': 'NNNNNNNNNNNNNNN',
    'P': 'OOOOOOOOOOOOOOOO',
    'Q': 'PPPPPPPPPPPPPPPPP',
    'R': 'QQQQQQQQQQQQQQQQQQ',
    'S': 'RRRRRRRRRRRRRRRRRRR',
    'T': 'SSSSSSSSSSSSSSSSSSSS',
    'U': 'TTTTTTTTTTTTTTTTTTTTT',
    'V': 'UUUUUUUUUUUUUUUUUUUUUU',
    'W': 'VVVVVVVVVVVVVVVVVVVVVVV',
    'X': 'WWWWWWWWWWWWWWWWWWWWWWWW',
    'Y': 'XXXXXXXXXXXXXXXXXXXXXXXXX',
    'Z': 'YYYYYYYYYYYYYYYYYYYYYYYYYY'}

def fact(n):
    return len(multiple_replace(fdict, chr(64 + n)))

if __name__ == "__main__":
    print fact(7)

Haskell

Krótki kod jest wydajnym kodem, więc spróbuj tego.

fac = length . permutations . flip take [1..]

Dlaczego trolling:

Śmiałbym się z każdego programisty, który to napisał ... Nieefektywność jest piękna. Prawdopodobnie również niezrozumiały dla żadnego programisty Haskell, który tak naprawdę nie potrafi napisać funkcji silni.

Edycja: Opublikowałem to jakiś czas temu, ale pomyślałem, że wyjaśnię przyszłym ludziom i ludziom, którzy nie potrafią czytać Haskell.

Kod tutaj bierze listę liczb od 1 do n, tworzy listę wszystkich permutacji tej listy i zwraca długość tej listy. Na moim komputerze 13 minut zajmuje około 20 minut. A potem powinno to zająć cztery godziny na 14! a potem dwa i pół dnia za 15! Tyle że w pewnym momencie zabrakło ci pamięci.

Edycja 2: W rzeczywistości prawdopodobnie nie zabraknie ci pamięci z powodu tego, że jest to Haskell (patrz komentarz poniżej). Być może będziesz w stanie zmusić go do oceny listy i zachować ją w pamięci, ale nie wiem wystarczająco dużo o optymalizowaniu (i nieoptymalizowaniu) Haskella, aby wiedzieć dokładnie, jak to zrobić.

DO#

Ponieważ jest to problem matematyczny, do wykonania tych obliczeń warto użyć aplikacji zaprojektowanej specjalnie do rozwiązywania problemów matematycznych ...

Krok 1:

Zainstaluj MATLAB. Myślę, że wersja próbna będzie działać, ale ten bardzo skomplikowany problem jest prawdopodobnie wystarczająco ważny, aby zasługiwać na zakup pełnej wersji aplikacji.

Krok 2:

Dołącz składnik MATLAB COM do swojej aplikacji.

Krok 3:

public string Factorial(uint n) {
    MLApp.MLApp matlab = new MLApp.MLApp();
    return matlab.Execute(String.Format("factorial({0})", n);
}

DO#

Czynniki są operacjami matematycznymi wyższego poziomu, które mogą być trudne do strawienia za jednym razem. Najlepszym rozwiązaniem w takich problemach programistycznych jest rozbicie jednego dużego zadania na mniejsze zadania.

Teraz n! jest zdefiniowane jako 1 * 2 * ... * n, więc w zasadzie powtarzane mnożenie, a mnożenie jest niczym innym jak powtarzanym dodawaniem. Mając to na uwadze, następujące rozwiązanie rozwiązuje ten problem:

long Factorial(int n)
{
    if(n==0)
    {
        return 1;
    }

    Stack<long> s = new Stack<long>();
    for(var i=1;i<=n;i++)
    {
        s.Push(i);
    }
    var items = new List<long>();
    var n2 = s.Pop();
    while(s.Count >0)
    {
        var n3 = s.Pop();
        items.AddRange(FactorialPart(n2,n3));
        n2 = items.Sum();
    }
    return items.Sum()/(n-1);
}

IEnumerable<long> FactorialPart(long n1, long n2)
{
    for(var i=0;i<n2;i++){
        yield return n1;
    }
}

#include <math.h>

int factorial(int n)
{
    const double g = 7;
    static const double p[] = { 0.99999999999980993, 676.5203681218851,
                                -1259.1392167224028, 771.32342877765313,
                                -176.61502916214059, 12.507343278686905,
                                -0.13857109526572012, 9.9843695780195716e-6,
                                1.5056327351493116e-7 };
    double z = n - 1 + 1;
    double x = p[0];
    int i;
    for ( i = 1; i < sizeof(p)/sizeof(p[0]); ++i )
        x += p[i] / (z + i);
    return sqrt(2 * M_PI) * pow(z + g + 0.5, z + 0.5)  * exp(-z -g -0.5) * x + 0.5;
}

Trolle:

• W 100% poprawny sposób obliczania silni, który całkowicie pomija sens iteracji lub rekurencji.
• Nie masz pojęcia, dlaczego to działa i nie możesz uogólnić go, aby zrobić cokolwiek innego.
• Bardziej kosztowne niż obliczanie go za pomocą matematyki liczb całkowitych.
• Najbardziej oczywisty „nieoptymalny” kod ( z = n - 1 + 1) jest w rzeczywistości samo-dokumentujący, jeśli wiesz, co się dzieje.
• Dla dodatkowego trollingu powinienem obliczyć p[]za pomocą rekurencyjnego obliczenia współczynników szeregowych!

(To przybliżenie Lanczosa do funkcji gamma )

Wszyscy wiemy z uczelni, że najskuteczniejszym sposobem obliczenia mnożenia jest zastosowanie logarytmów. W końcu dlaczego ludzie mieliby używać tabel logarytmicznych przez setki lat?

Na podstawie tożsamości a*b=e^(log(a)+log(b))tworzymy następujący kod Python:

from math import log,exp

def fac_you(x):
    return round(exp(sum(map(log,range(1,x+1)))))

for i in range(1,99):
    print i,":",fac_you(i)

Tworzy listę liczb od 1do x( +1jest to potrzebne, ponieważ Python jest do bani), oblicza logarytm każdego z nich, sumuje liczby, podnosi e do potęgi sumy i ostatecznie zaokrągla wartość do najbliższej liczby całkowitej (ponieważ Python jest do bani) . Python ma wbudowaną funkcję obliczania silni, ale działa tylko dla liczb całkowitych, więc nie może generować dużych liczb (ponieważ Python jest do bani). Dlatego potrzebna jest powyższa funkcja.

Btw, ogólna wskazówka dla studentów jest taka, że ​​jeśli coś nie działa zgodnie z oczekiwaniami, to prawdopodobnie dlatego, że język jest do bani.

Niestety Javascript nie ma wbudowanej metody obliczania silni. Możesz jednak użyć jego znaczenia w kombinatorykach, aby ustalić wartość:

Silnia liczby n jest liczbą permutacji listy o tym rozmiarze.

Możemy więc wygenerować każdą listę liczby n-cyfrowej, sprawdzić, czy jest to permutacja, a jeśli tak, zwiększyć licznik:

window.factorial = function($nb_number) {
  $nb_trials = 1
  for($i = 0; $i < $nb_number; $i++) $nb_trials *= $nb_number
  $nb_successes = 0
  __trying__:
  for($nb_trial = 0; $nb_trial < $nb_trials; $nb_trial++){
    $a_trial_split = new Array
    $nb_tmp = $nb_trial
    for ($nb_digit = 0; $nb_digit < $nb_number; $nb_digit++){
      $a_trial_split[$nb_digit] = $nb_tmp - $nb_number * Math.floor($nb_tmp / $nb_number)
      $nb_tmp = Math.floor($nb_tmp / $nb_number)
    }
    for($i = 0; $i < $nb_number; $i++)
      for($j = 0; $j < $nb_number; $j++)
        if($i != $j)
          if($a_trial_split[$i] == $a_trial_split[$j])
            continue __trying__
    $nb_successes += 1
  }
  return $nb_successes
}

alert("input a number")
document.open()
document.write("<input type = text onblur = alert(factorial(parseInt(this.value))))>")
document.close()

Trolle:

• Wpisuje węgierską notację, snake_case i niepotrzebne . Jak złe to jest?
• Wymyśliłem własną konwencję dla etykiet skoków, niezgodną z obecnym użyciem tej konwencji.
• Każda możliwa zmienna jest przypadkowo globalna.
• Rozwiązanie to nie O(n), nie O(n!), aleO(n^n) . Już to wystarczyłoby, aby się tutaj zakwalifikować.
• Zwiększanie liczby, a następnie konwersja jako base-n to zły sposób na wygenerowanie listy sekwencji. Nawet gdybyśmy chcieli duplikatów. Tajemnicze zerwanie dla n> 13 nie jest jedynym powodem.
• Oczywiście moglibyśmy użyć number.toString(base), ale to nie działa dla baz powyżej 36. Tak, wiem 36! to dużo , ale wciąż ...
• Czy wspominałem, że JavaScript ma operator modułu? LubMath.pow ? Nie? No cóż.
• Odmowa użycia ++poza pętlami for czyni go jeszcze bardziej tajemniczym. Jest też ==zły.
• Głęboko zagnieżdżone konstrukcje bez ramiączek. Zagnieżdżone warunki warunkowe zamiast AND. Można również uniknąć stanu zewnętrznego, kończąc wewnętrzną pętlę na$i .
• Funkcje new Array, document.write(z przyjaciółmi) ialert (zamiast wiersz lub etykietę wejściowego) tworząc kompletny trifecta grzechów wyboru funkcji. Dlaczego mimo wszystko wkład jest dynamicznie dodawany?
• Inline obsługi zdarzeń. Aha, a głębokie rurociągi to piekło do debugowania.
• Nieopisane atrybuty są zabawne, a przestrzenie wokół = sprawiają, że są jeszcze trudniejsze do odczytania.
• Czy wspominałem już, że nienawidzę średników?

Ruby and WolframAlpha

To rozwiązanie wykorzystuje interfejs API REST WolframAlpha do obliczania silni, RestClient pobiera rozwiązanie, a Nokogiri analizuje je. Nie wymyśla żadnych kół i wykorzystuje sprawdzone i popularne technologie, aby uzyskać wynik w najbardziej nowoczesny sposób.

require 'rest-client'
require 'nokogiri'

n = gets.chomp.to_i
response = Nokogiri::XML(RestClient.get("http://api.wolframalpha.com/v2/query?input=#{n}!&format=moutput&appid=YOUR_APP_KEY"))
puts response.xpath("//*/moutput/text()").text

JavaScript

JavaScript jest funkcjonalnym językiem programowania, co oznacza, że ​​musisz używać funkcji do wszystkiego, ponieważ jest szybszy.

function fac(n){
    var r = 1,
        a = Array.apply(null, Array(n)).map(Number.call, Number).map(function(n){r = r * (n + 1);});
    return r;
}

Korzystanie z Bogo-Sort w Javie

public class Factorial {
    public static void main(String[] args) {
        //take the factorial of the integers from 0 to 7:
        for(int i = 0; i < 8; i++) {
            System.out.println(i + ": " + accurate_factorial(i));
        }
    }

    //takes the average over many tries
    public static long accurate_factorial(int n) {
        double sum = 0;
        for(int i = 0; i < 10000; i++) {
            sum += factorial(n);
        }
        return Math.round(sum / 10000);
    }

    public static long factorial(int n) {
        //n! = number of ways to sort n
        //bogo-sort has O(n!) time, a good approximation for n!
        //for best results, average over several passes

        //create the list {1, 2, ..., n}
        int[] list = new int[n];
        for(int i = 0; i < n; i++)
            list[i] = i;

        //mess up list once before we begin
        randomize(list);

        long guesses = 1;

        while(!isSorted(list)) {
            randomize(list);
            guesses++;
        }

        return guesses;
    }

    public static void randomize(int[] list) {
        for(int i = 0; i < list.length; i++) {
            int j = (int) (Math.random() * list.length);

            //super-efficient way of swapping 2 elements without temp variables
            if(i != j) {
                list[i] ^= list[j];
                list[j] ^= list[i];
                list[i] ^= list[j];
            }
        }
    }

    public static boolean isSorted(int[] list) {
        for(int i = 1; i < list.length; i++) {
            if(list[i - 1] > list[i])
                return false;
        }
        return true;
    }
}

To faktycznie działa bardzo powoli i nie jest dokładne dla wyższych liczb.

PERL

Silnia może być trudnym problemem. Technika mapowania / zmniejszania - podobnie jak Google - może podzielić matematykę, przerywając wiele procesów i zbierając wyniki. To dobrze wykorzysta wszystkie te rdzenie lub procesory w twoim systemie w mroźną zimową noc.

Zapisz jako f.perl i chmod 755, aby mieć pewność, że możesz go uruchomić. Masz zainstalowany Patologicznie Eklektyczny List Śmieci, prawda?

#!/usr/bin/perl -w                                                              
use strict;
use bigint;
die "usage: f.perl N (outputs N!)" unless ($ARGV[0] > 1);
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);
    }
}

Trolle:

• rozwidla procesy O (log2 (N))
• nie sprawdza, ile masz procesorów lub rdzeni
• Ukrywa wiele konwersji bigint / tekst, które występują w każdym procesie
• Pętla for jest często szybsza niż ten kod

Pyton

Tylko algorytm O (n! * N ^ 2) do znalezienia silni. Obsługiwana skrzynka podstawowa. Brak przelewów.

def divide(n,i):
    res=0
    while n>=i:
         res+=1
         n=n-i
    return res

def isdivisible(n,numbers):
    for i in numbers:
         if n%i!=0:
             return 0
         n=divide(n,i)
    return 1

def factorial(n):
    res = 1
    if n==0: return 1 #Handling the base case
    while not isdivisible(res,range(1,n+1)):
         res+=1
    return res

Cóż, w Golfscript istnieje łatwe rozwiązanie. Możesz użyć interpretera Golfscript i uruchomić ten kod:

.!+,1\{)}%{*}/

Spokojnie huh :) Powodzenia!

Matematyka

factorial[n_] := Length[Permutations[Table[k, {k, 1, n}]]]

To nie wydaje się działać dla liczb większych niż 11, a silnia [11] zamroziła mój komputer.

Rubin

f=->(n) { return 1 if n.zero?; t=0; t+=1 until t/n == f[n-1]; t }

Najwolniejszy liniowiec, jaki mogę sobie wyobrazić. Obliczenie zajmuje procesorowi i7 2 minuty 6!.

Prawidłowym podejściem do tych trudnych problemów matematycznych jest DSL. Więc zamodeluję to pod kątem prostego języka

data DSL b a = Var x (b -> a)
             | Mult DSL DSL (b -> a)
             | Plus DSL DSL (b -> a)
             | Const Integer (b -> a) 

Aby ładnie napisać nasz DSL, pomocne jest wyświetlenie go jako wolnej monady generowanej przez funktor algebraiczny

F X = X + F (DSL b (F X)) -- Informally define + to be the disjoint sum of two sets

Możemy to napisać w Haskell jako

Free b a = Pure a
         | Free (DSL b (Free b a))

Pozostawię czytelnikowi wyprowadzenie trywialnej implementacji

join   :: Free b (Free b a) -> Free b a
return :: a -> Free b a
liftF  :: DSL b a -> Free b a

Teraz możemy opisać operację modelowania silni w tej DSL

factorial :: Integer -> Free Integer Integer
factorial 0 = liftF $ Const 1 id
factorial n = do
  fact' <- factorial (n - 1)
  liftF $ Mult fact' n id

Teraz, kiedy to modelowaliśmy, musimy po prostu zapewnić rzeczywistą funkcję interpretacyjną dla naszej darmowej monady.

denote :: Free Integer Integer -> Integer
denote (Pure a) = a
denote (Free (Const 0 rest)) = denote $ rest 0
...

Pozostałą część denotacji pozostawiam czytelnikowi.

Aby poprawić czytelność, czasami pomocne jest przedstawienie konkretnego AST formularza

data AST = ConstE Integer
         | PlusE AST AST
         | MultE AST AST

a potem trywialna refleksja

reify :: Free b Integer -> AST

a następnie rekursywna ocena AST jest łatwa.

Pyton

Oto więc kod: getDigitsfunkcja dzieli ciąg reprezentujący liczbę na swoje cyfry, więc staje się „1234” [ 4, 3, 2, 1 ](odwrotna kolejność tylko upraszcza funkcje increasei multiply). increaseFunkcja przyjmuje taką listę i zwiększa się o jeden. Jak sama nazwa wskazuje, multiplyfunkcja się zwielokrotnia, np. multiply([2, 1], [3])Zwraca[ 6, 3 ] ponieważ 12 razy 3 to 36. Działa to w taki sam sposób, jak pomnożysz coś za pomocą pióra i papieru.

Następnie factorialfunkcja wykorzystuje te funkcje pomocnicze do obliczenia faktycznej silni, na przykład factorial("9")podaje "362880"jako wynik.

import copy

def getDigits(n):
    digits = []
    for c in n:
        digits.append(ord(c) - ord('0'))

    digits.reverse()
    return digits

def increase(d):
    d[0] += 1
    i = 0
    while d[i] >= 10:
        if i == len(d)-1:
            d.append(0)

        d[i] -= 10
        d[i+1] += 1
        i += 1

def multiply(a, b):
    subs = [ ]
    s0 = [ ]
    for bi in b:

        s = copy.copy(s0)
        carry = 0
        for ai in a:
            m = ai * bi + carry
            s.append(m%10)
            carry = m//10

        if carry != 0:
            s.append(carry)

        subs.append(s)
        s0.append(0)

    done = False
    res = [ ]
    termsum = 0
    pos = 0
    while not done:
        found = False
        for s in subs:
            if pos < len(s):
                found = True
                termsum += s[pos]

        if not found:
            if termsum != 0:
                res.append(termsum%10)
                termsum = termsum//10
            done = True
        else:
            res.append(termsum%10)
            termsum = termsum//10
            pos += 1

    while termsum != 0:
        res.append(termsum%10)
        termsum = termsum//10

    return res

def factorial(x):
    if x.strip() == "0" or x.strip() == "1":
        return "1"

    factorial = [ 1 ]
    done = False
    number = [ 1 ]
    stopNumber = getDigits(x)
    while not done:
        if number == stopNumber:
            done = True

        factorial = multiply(factorial, number)
        increase(number)

    factorial.reverse()

    result = ""
    for c in factorial:
        result += chr(c + ord('0'))

    return result

print factorial("9")

Notatki

W Pythonie liczba całkowita nie ma limitu, więc jeśli chcesz to zrobić ręcznie, możesz to zrobić

fac = 1
for i in range(2,n+1): 
    fac *= i

Istnieje również bardzo wygodna math.factorial(n)funkcja.

To rozwiązanie jest oczywiście o wiele bardziej skomplikowane, niż musi być, ale działa i faktycznie ilustruje, w jaki sposób można obliczyć silnię w przypadku ograniczenia przez 32 lub 64 bity. Więc chociaż nikt nie uwierzy, że jest to rozwiązanie, które wymyśliłeś dla tego prostego (przynajmniej w Pythonie) problemu, możesz się czegoś nauczyć.

Pyton

Najbardziej rozsądnym rozwiązaniem jest sprawdzenie wszystkich liczb, aż znajdziesz tę, która jest silnią podanej liczby.

print('Enter the number')
n=int(input())
x=1
while True:
    x+=1
    tempx=int(str(x))
    d=True
    for i in range(1, n+1):
        if tempx/i!=round(tempx/i):
            d=False
        else:
            tempx/=i
    if d:
        print(x)
        break

Najbardziej eleganckie rozwiązanie rekurencyjne w C.

Każdy wie, że najbardziej eleganckie rozwiązania silni są rekurencyjne.

Factorial:

0! = 1
1! = 1
n! = n * (n - 1)!

Ale mnożenie może być również definiowane rekurencyjnie jako kolejne dodawanie.

Mnożenie:

n * 0 = 0
n * 1 = n
n * m = n + n * (m - 1)

I tak można dodawać jako kolejne przyrosty.

Dodanie:

n + 0 = n
n + 1 = (n + 1)
n + m = (n + 1) + (m - 1)

W C, możemy używać ++xi --xobsługiwać operacje pierwotne (x + 1)i (x - 1)odpowiednio, więc mamy wszystko zdefiniowane.

#include <stdlib.h>
#include <stdio.h>

// For more elegance, use T for the type
typedef unsigned long T;

// For even more elegance, functions are small enough to fit on one line

// Addition
T A(T n, T m) { return (m > 0)? A(++n, --m) : n; }

// Multiplication
T M(T n, T m) { return (m > 1)? A(n, M(n, --m)): (m? n: 0); }

// Factorial
T F(T n) { T m = n; return (m > 1)? M(n, F(--m)): 1; }

int main(int argc, char **argv)
{
    if (argc != 2)
        return 1;

    printf("%lu\n", F(atol(argv[1])));

    return 0;
}

Wypróbujmy to:

$ ./factorial 0
1
$ ./factorial 1
1
$ ./factorial 2
2
$ ./factorial 3
6
$ ./factorial 4
24
$ ./factorial 5
120
$ ./factorial 6
720
$ ./factorial 7
5040
$ ./factorial 8
40320

Idealnie, chociaż 8! z jakiegoś powodu zajęło dużo czasu. No cóż, najbardziej eleganckie rozwiązania nie zawsze są najszybsze. Kontynuujmy:

$ ./factorial 9

Hmm, dam ci znać, kiedy wróci ...

Pyton

Jak wskazała odpowiedź @ Matt_Siekera, silnie można podzielić na dodatkowe - dlaczego rozkładanie zadań jest istotą programowania. Ale możemy podzielić to na 1!

def complicatedfactorial(n):
    def addby1(num):
        return num + 1
    def addnumbers(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addby1(cp2)
            b -= 1
    def multiply(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addnumbers(cp2,cp2)
    if n == 0:
        return 1
    else:
        return multiply(complicatedfactorial(n-1),n)

Myślę, że ten kod gwarantuje błąd SO, ponieważ

1. Rekursja - rozgrzewa

2. Każda warstwa generuje połączenia w celu pomnożenia

3. który generuje wywołania do liczb dodatkowych

4. który generuje połączenia z addby1!

Za dużo funkcji, prawda?

Wystarczy wejść do Google i wpisać silnię:

5!

http://lmgtfy.com/?q=5!

TI-Basic 84

:yumtcInputdrtb@gmail And:cReturnbunchojunk@Yahoo A!op:sEnd:theemailaddressIS Crazy ANSWER LOL

To naprawdę działa :)

JavaScript

Oczywiście zadaniem programisty jest wykonanie jak najmniej pracy i wykorzystanie jak największej liczby bibliotek. Dlatego chcemy importować jQuery i math.js . Teraz zadanie jest proste:

$.alert=function(message){
    alert(message);
}$.factorial=function(number){
    alert(math.eval(number+"!"));
    return math.eval(number+"!");
}
$.factorial(10);

Pyton

Po niewielkiej modyfikacji standardowej rekurencyjnej implementacji czynnikowej staje się ona niedopuszczalnie powolna dla n> 10.

def factorial(n):
    if n in (0, 1):
        return 1
    else:
        result = 0
        for i in range(n):
            result += factorial(n - 1)
        return result

Grzmotnąć

#! /bin/bash

function fact {
    if [[ ${1} -le 1 ]]; then
        return 1
    fi;

    fact $((${1} - 1))
    START=$(date +%s)
    for i in $(seq 1 $?); do sleep ${1}; done
    END=$(date +%s)
    RESULT=$(($END - $START))
    return $RESULT
}

fact ${1}
echo $?

Spróbujmy to zrobić metodą Monte Carlo . Wszyscy wiemy, że prawdopodobieństwo równości dwóch losowych n- uprawnień wynosi dokładnie 1 / n! . Dlatego możemy po prostu sprawdzić, ile testów jest potrzebnych (nazwijmy ten numer b ), dopóki nie otrzymamy c trafień. Więc n! ~ b / c .

Sage, też powinien działać w Pythonie

def RandomPermutation(n) :           
    t = range(0,n)                   
    for i in xrange(n-1,0,-1):       
        x = t[i]                     
        r = randint(0,i)             
        t[i] = t[r]                  
        t[r] = x                     
    return t                         

def MonteCarloFactorial(n,c) :   
    a = 0                            
    b = 0                            
    t = RandomPermutation(n)         
    while a < c :                
        t2 = list(t)                 
        t = RandomPermutation(n)     
        if t == t2 :                 
            a += 1                   
        b += 1                       
    return round(b/c)            

MonteCarloFactorial(5,1000)
# returns an estimate of 5!

grzmotnąć

Czynniki można łatwo ustalić za pomocą dobrze znanych narzędzi wiersza poleceń z bash.

read -p "Enter number: " $n
seq 1 $n | xargs echo | tr ' ' '*' | bc

Jak wspomniano w komentarzach @Aaron Davies, wygląda to na bardziej uporządkowane i wszyscy chcemy mieć ładny i uporządkowany program, prawda?

read -p "Enter number: " $n
seq 1 $n | paste -sd\* | bc