algorytm.org

Silnia



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Silnia
Ocena użytkowników:***** / 168
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 26 lipca 2005 20:33

Silnia (n!) to iloczyn n kolejnych liczb naturalnych, przy czym dodatkowo zachodzi 0! = 1.
Obliczanie silni jest sztandarowym przykładem używania rekurencji:
n! = n * (n-1)!

Rekurencyjne obliczanie silni może być opisane następującym schematem blokowym:
schemat blokowy silni (rekurencyjnie)
Przykład:
5!=5*4!=5*4*3!=5*4*3*2!=5*4*3*2*1!=5*4*3*2*1*0!=5*4*3*2*1*1=120

Jak można zauważyć po rozpisaniu silnię można obliczyć również z użyciem algorytmu iteracyjnego:
n! = 1 * 2 * 3 * ... n
Przy czym cały czas należy pamiętać o wyjątku dla 0! = 1.

Iteracyjne obliczanie silni może być opisane następującym schematem blokowym:
schemat blokowy silni (iteracyjnie)


Złożoność obliczeniowa przedstawionych metod to O(n).

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 5
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 20
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 5
MarianC/C++C++ - silnia rekurencyjnie
.cpp
.cpp
***** / 73
MarianC/C++C++ - silnia iteracyjnie
.cpp
.cpp
***** / 20
Adrian WijasC/C++C++ - rekurencyjnie
.cpp
.cpp
***** / 3
Adrian WijasC/C++C++ - iteracyjnie
.cpp
.cpp
***** / 4
Bartosz BednarczykC/C++C++ Wersja iteracyjna dla dużych liczb
.cpp
.cpp
***** / 8
Michał KnasieckiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 4
Adam ChrapkowskiHaskellRekurencyjnie
.hs
.hs
***** / 2
Adam ChrapkowskiHaskellIteracyjnie
.hs
.hs
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 22
Maciej LipińskiJavaScriptfunkcja + test
.js
.js
***** / 6
ddominikpPhpIteracyjnie
.php
.php
***** / 10
Adrian DymekPython
.py
.py
***** / 71
Nikodem SolarzRubyMetoda obliczająca. Rozwiązanie iteracyjne.
.rb
.rb
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 22 maja 2012 13:34
Komentarze
photo
0 # qebek 2010-02-10 11:41
wszystko ok ale niema bloku wprowadzającego n
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # Tomasz Lubiński 2010-02-13 14:59
Blok wprowadzający dane, nie jest obowiązkowy. Jeżeli nie chcesz zaciemniać algorytmu i skupić się tylko na jego istocie możesz założyć, że dane są już wprowadzone go pominąć. Podsumowywując, obie wersje są poprawne.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-4 # johny 2013-01-20 17:15
wynik = n*silnia(n-1)

A ile wynosi silnia? co to w ogóle jest w tym schemacie? Jak dla mnie to nie jest poprawne. Szukam dalej w tonie śmieci internetu
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-4 # Witamaster 2013-01-31 19:44
Cytat:
wynik = n*silnia(n-1)
A ile wynosi silnia?


Odpowiedź na Twoje pytanie zawiera artykuł:
Cytat:
Obliczanie silni jest sztandarowym przykładem używania rekurencji: n! = n * (n-1)!


Algorytm jak i schematy są poprawne, albo przeczytałeś nieuważnie albo nie rozumiesz pojęcia rekurencji www.algorytm.org/kurs-algorytmiki/rekurencja.html
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # Macho 2013-03-13 13:09
Brak bloku wprowadzającego n.
Nie spotkałem się jeszcze z takim schematem blokowym bez bloku wejsciowego
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Nusz 2019-12-10 13:35
Istnieje alternatywny sposób obliczania silni (zwłaszcza dla większych liczb) opierający się na systemach niedziesiątkowy ch.
Schemat: liczba 10 w systemie o podstawie n
pętla: konwersja na system i=(i-1); mnożenie przez dziesiątkę tego systemu;
zakończenie: liczba w systemie binarnym.

Długi ciąg cyfr. Lepiej jest najpierw policzyć 9! w systemie o podstawie n+1, po czym działaniami pętli doprowadzić do systemu dziesiątkowego, w którym znajdzie się wartość n!.

Konwersja w tym przypadku to 3 proste operacje w pętli od dwu do wszystkich cyfr; cyfry najbardziej znaczące są używane, pozostałe czekają.
Przebieg: dołączenie kolejnej cyfry do używanych; do każdej używanej cyfry dodaj jej poprzedniczkę (równocześnie); przenieś nadmiary tego systemu jak przy dodawaniu pisemnym.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz