Jak znaleźć silnię liczby dodatniej?

18

Wyzwanie:

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

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

alephalpha
źródło
6
Zobacz także programista The Evolution of Haskell .
Petr Pudlák
4
-1, przepraszam, ponieważ dostajemy ogromną liczbę tych pytań trollujących kod, a to tak naprawdę nie dodaje do nich nic nowego
Klamka
Trolling kodu jest w trakcie usuwania, zgodnie z oficjalnym stanowiskiem. To pytanie ma sporą liczbę głosów z wieloma odpowiedziami, z których wiele jest bardzo wysoko głosowanych. Otrzymał nieco ponad 50% głosów „usuń” w ankiecie , ale jest wyjątkowy, ponieważ otrzymał tak wiele odpowiedzi i głosów, więc blokuję to ze względu na znaczenie historyczne.
Klamka

Odpowiedzi:

46

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

Wzór 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:

Metoda babilońska

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.

nwk
źródło
16
+1 Prostota i dokładność tej metody sprawia, że ​​jest wyraźnym zwycięzcą
Joe the Person
44

DO#

Przykro mi, ale nie znoszę funkcji rekurencyjnej.

public string Factorial(uint n) {
    return n + "!";
}
tia
źródło
1
Technicznie spełniłeś wytyczne! ;) +1 za krótkie nadużycie
WallyWest
36

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();
}
}
emory
źródło
16
Próbowałem - bardzo wydajny. Wysyłamy z następną wersją. :)
Johannes,
Oprócz „syndromu magicznych liczb” może to być naprawdę dobra implementacja, o ile n <13, a co za tym idzie znacznie mniej stosów. Napisz „przypadek 4: zwróć 4 * 3 * 2;” i miałbyś przyzwoitą klasę, znacznie szybciej niż stara rekurencyjna.
Fabinout,
6
@ Fabinout, implementacja jest poprawna nawet dla n> = 13. 13!> Integer.MAX_VALUE.
emory
21

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)
Petr Pudlák
źródło
1
Oczywiście, że tak :)
Pierre Arlaud
15

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

jgon
źródło
Obrzydliwe, a jednocześnie tak eleganckie, jednocześnie.
PLL
1
Czy jesteś pewien problemu z pamięcią? W dowolnym momencie musisz zachować w pamięci: - listę [1..n]. - Jedna szczególna permutacja [1..n], sprowadzona do thunk dla reszty permutacji (wielomian w n). - Akumulator dla lengthfunkcji.
John Dvorak,
Racja, prawdopodobnie nie w rzeczywistości. Nie za bardzo o tym myślałem. Dodam komentarz na dole.
jgon
10

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);
}
Moshe Katz
źródło
Matlab dla studentów zaczyna się od 100 $. Wersje profesjonalne lub licencje witryn mogą przejść do tysięcy.
Moshe Katz,
4
Moshe Katz - uzasadniony, ponieważ silnia.
Mike H.
9

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;
    }
}
Matt Sieker
źródło
Masz wąskie gardło wysyłające to wszystko przez jeden procesor lub rdzeń, co myślę, że mogłem rozwiązać w mojej odpowiedzi :-)
Paul
9
#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 )

Ben Jackson
źródło
Czy jest tu jakiś sens - 1 + 1? Mój kompilator optymalizuje go (nie jest liczbą zmiennoprzecinkową, w której optymalizacja takiego kodu może być niebezpieczna), więc wydaje się niepotrzebna.
Konrad Borowski
4
@xfix: double z = n - 1jest częścią przybliżenia funkcji gamma. Pochodzi + 1ze związku, który gamma(n + 1) = n!dla liczby całkowitej n.
Ben Jackson
9

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.

nitro2k01
źródło
Szkoda, że ​​nie mogę dać dodatkowych głosów na opis, ale Python jest do bani
Mark K Cowan
1
Śmiałem się z „fac you”
Number9
8

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?
John Dvorak
źródło
8

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
migimunz
źródło
7

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;
}
Luka
źródło
1
Możesz wytłumaczyć?
Mhmd
7
1 nie jest funkcją. Twój kod jest więc wolny.
Pierre Arlaud
4
@ArlaudPierre na r = -~(function(){})pewno to rozwiąże.
nitro2k01
4
Jestem na komputerze roboczym, więc tak naprawdę nie chcę instalować tego języka. Gdzie mogę znaleźć wersję, która będzie działać w mojej przeglądarce?
joeytwiddle
3
Trochę boję się korzystać z Google, ponieważ mój szef ma z nimi konto i nie chcę, żeby wiedział, że gram w golfa w pracy. Szukałem rozszerzenia do przeglądarki Firefox, które mogłoby obsługiwać JavaScript, ale nie mogę go znaleźć. Niektórzy z moich znajomych używają Javascript na jsfiddle.net, ale to wykorzystuje energię kogoś innego, co jest trochę jak kradzież. Moja mama powiedziała, że ​​nie powinienem spędzać czasu z takimi ludźmi, ale oni są moimi przyjaciółmi, więc co mogę zrobić? W każdym razie czasami bierze więcej śmietanki niż potrzebuje. Dzięki za porady, używam Ctrl-Shift-J lub K w Firefox. Zastrzeżenie: # comment-trolling
joeytwiddle
5

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.

James Hagborg
źródło
4

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
Paweł
źródło
TIL, że w perlu ARGV[0]jest tak naprawdę pierwszym argumentem, a nie skryptem!
ThinkChaos,
@plg Uważam, że 0 $ może zawierać nazwę pliku skryptu, ale to nie to samo, co $ ARGV [0]
Paul
Tak, właśnie to czytałem. Zaskoczyło mnie to, że w Perlu nie $ARGV[0]
dzieje się
4

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
Sudharsan Mohan
źródło
3

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

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

Spokojnie huh :) Powodzenia!

Martijn Courteaux
źródło
2
Nie znam GolfScript, ale ten mnie rozczarowuje ... Na podstawie innych przykładów GolfScript na tej stronie spodziewałbym się, że odpowiedź będzie!
Pan Lister
1
To jest operator negacji. 0 staje się 1, a wszystko inne staje się 0.
Martijn Courteaux
3

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.

Stephen Montgomery-Smith
źródło
3

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

przepisane
źródło
2

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.

Daniel Gratzer
źródło
2

Pyton

Poniżej znajduje się wersja rozwiązania w języku Python, która nie jest ograniczona do 32-bitowego (lub 64-bitowego w najnowszym systemie) limitu liczb całkowitych w Pythonie. Aby obejść to ograniczenie, użyjemy łańcucha jako danych wejściowych i wyjściowych dla factorialprocedury i wewnętrznie podzielimy łańcuch na cyfry, aby móc wykonać mnożenie.

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

brm
źródło
W Pythonie nie ma limitu liczb całkowitych ... prawda? Być może trzeba to wyjaśnić lepiej.
Riking
@Riking Tak, w pythonie nie ma limitu liczb całkowitych. Dodałem kilka notatek, aby było bardziej przejrzyste.
brm
2

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
PygameNerd
źródło
2

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


źródło
2

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?

Dan the Man
źródło
1

TI-Basic 84

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

To naprawdę działa :)

Timtech
źródło
1

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);
scrblnrd3
źródło
1

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
dan04
źródło
1

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 $?
alaroldai
źródło
1

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!
Siema'
źródło
1

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
jippie
źródło
1
polecam niedoceniane pastepolecenie:seq 1 $n | paste -sd\* | bc
Aaron Davies
2
@AaronDavies pastewygląda jak zwykłe angielskie słowo i łatwo je zapamiętać. Czy naprawdę tego chcemy? ; o)
jippie