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:
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:
Złożoność obliczeniowa przedstawionych metod to O(n).
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:
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:
Złożoność obliczeniowa przedstawionych metod to O(n).
Implementacje
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Tomasz Lubiński | Ada | .ada | .ada | ***** / 5 | |
| Tomasz Lubiński | C# | MS Visual Studio .net | .cs | .cs | ***** / 20 |
| Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 5 | |
| Marian | C/C++ | C++ - silnia rekurencyjnie | .cpp | .cpp | ***** / 72 |
| Marian | C/C++ | C++ - silnia iteracyjnie | .cpp | .cpp | ***** / 20 |
| Adrian Wijas | C/C++ | C++ - rekurencyjnie | .cpp | .cpp | ***** / 3 |
| Adrian Wijas | C/C++ | C++ - iteracyjnie | .cpp | .cpp | ***** / 4 |
| Bartosz Bednarczyk | C/C++ | C++ Wersja iteracyjna dla dużych liczb | .cpp | .cpp | ***** / 8 |
| Michał Knasiecki | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 4 |
| Adam Chrapkowski | Haskell | Rekurencyjnie | .hs | .hs | ***** / 2 |
| Adam Chrapkowski | Haskell | Iteracyjnie | .hs | .hs | ***** / 1 |
| Tomasz Lubiński | Java | .java | .java | ***** / 22 | |
| Maciej Lipiński | JavaScript | funkcja + test | .js | .js | ***** / 6 |
| ddominikp | Php | Iteracyjnie | .php | .php | ***** / 10 |
| Adrian Dymek | Python | .py | .py | ***** / 71 | |
| Nikodem Solarz | Ruby | Metoda obliczająca. Rozwiązanie iteracyjne. | .rb | .rb | ***** / 1 |
Poprawiony: 22 maja 2012 13:34
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
Odpowiedź na Twoje pytanie zawiera artykuł:
Cytat:
Algorytm jak i schematy są poprawne, albo przeczytałeś nieuważnie albo nie rozumiesz pojęcia rekurencji www.algorytm.org/kurs-algorytmiki/rekurencja.html
Nie spotkałem się jeszcze z takim schematem blokowym bez bloku wejsciowego
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.