http://www.algorytm.org/images/schematy_blokowe/silnia_rek.gif
Próbuje przepisać ten algorytm
Mam taki kod
int main() {
int input;
int result;
cin >> input;
if(input <=1) {
result = 1;
cout << "Result = 1";
} else {
}
return 0;
}
jak jest wynik = n * silnia(n-1) to czym jest ta silnia? Jaką zmienną muszę utworzyc pod to?
Jeśli próbujesz napisać algorytm rekurencyjny to musisz mieć funkcję, którą będziesz rekurencyjnie wywoływał. Zacznij od zdefiniowania osobnej funkcji silnia()
kq napisał(a):
Jeśli próbujesz napisać algorytm rekurencyjny to musisz mieć funkcję, którą będziesz rekurencyjnie wywoływał. Zacznij od zdefiniowania osobnej funkcji silnia()
Czy powinienem pisac iteracyjnie czy rekurencyjnie? Dopiero zaczałem studia informatyczne i próbuję robić zadania.
Zgodnie z treścią pierwszego posta, chcesz zaimplementować "ten" algorytm. "Ten" algorytm to rekurencyjne obliczanie silni. Teraz pytasz co chcesz zrobić?
Zakładam, że masz ostatecznie napisać tak i tak, aby poznać różnice między tymi podejściami.
W przypadku silni to niewiele zmienia, ale już dla takiego fibonacciego wersja iteracyjna będzie wielokrotnie lepsza :)
kq napisał(a):
Zgodnie z treścią pierwszego posta, chcesz zaimplementować "ten" algorytm. "Ten" algorytm to rekurencyjne obliczanie silni. Teraz pytasz co chcesz zrobić?
Zakładam, że masz ostatecznie napisać tak i tak, aby poznać różnice między tymi podejściami.
Po prostu zadania zostały udostępnione, ale jeszcze nie przerabialiśmy pisania algorytmów, a chce sobię już poćwiczyć.
No ok. W takim razie imo powinieneś poćwiczyć oba te podejścia. Tak jak @Shalom napisał, jak napiszesz (później, zacznij od silni) Fibonacciego to zobaczysz, że naiwne podejście jest bardzo bolesne dla wydajności.
A teraz, skoro masz już schemat blokowy silni rekurencyjnej, to napisz ją. A iteracyjnie potem.
Czy powinienem pisac iteracyjnie czy rekurencyjnie?
To zalezy. Np. algorytmy na drzewach sie rekurencyjnie strzela ale przepisanie silnii na iteracje/rekursje ogonowa jest na tyle proste, ze rekursja ktora puchnie stos nie ma sensu.
No to iteracyjnie: http://www.algorytm.org/images/schematy_blokowe/silnia_iter.gif
int wynik =1;
int i = 1;
int input;
cout << "Podaj liczbę: ";
cin >> input;
while(i<input) {
i=i+1;
wynik=wynik*i;
cout << wynik;
}
return 0;
}
Robie tak jak na obrazku, a wychodzi jakiś chory wynik. To n na obrazku to jest input?
Ten schemat blokowy jest niepoprawny bo n jest z kosmosu
Descendant napisał(a):
jak jest wynik = n * silnia(n-1) to czym jest ta silnia? Jaką zmienną muszę utworzyc pod to?
Może odpowiem bardziej bezpośrednio: przedstawiony schemat jest dla mnie osobiście troszkę niekompletny, bo brakuje mu oznaczenia, że silnia jest funkcją, której działanie ma ten schemat reprezentować. Tak więc – owa "silnia", o którą pytasz, tutaj reprezentuje funkcję (np. w C++).
Descendant napisał(a):
No to iteracyjnie: http://www.algorytm.org/images/schematy_blokowe/silnia_iter.gif
(…)
Robie tak jak na obrazku, a wychodzi jakiś chory wynik. To n na obrazku to jest input?
n, zgodnie z tym: http://www.algorytm.org/algorytmy-arytmetyczne/silnia.html, wydaje się oznaczać liczbę, której silnię masz policzyć.
Drukujesz wszystkie etapy po kolei, a nie tylko wynik. Czyli 2, 6, 24, 120.
Na tym poziomie, pierw zacznij od tego, aby robić funkcję służącą obliczeniu czegoś i tylko temu. Nie służącą przyjęciu danych od użytkownika, albo wypisaniu ich. Niech silnia będzie osobną funkcją.
stivens napisał(a):
Ten schemat blokowy jest niepoprawny bo n jest z kosmosu
Chyba to jest taki przypadek, że schemat bardzo źle wyraża rekurencję.
Gdzieś tu padło: dla prostych programów schemat nie jest potrzebny, dla skomplikowanych niczego nie rozjaśnia. Rekurencja też jest ciężka do plastycznego wyrażenia
#include <iostream>
using namespace std;
int main()
{
int n,i,x;
x=1;
i=1;
cin >> n;
for (i==1;i<=n;i++) {
x=x*i;
}
cout << x;
return 0;
}
stivens napisał(a):
Ale co niby chcesz zrobic jak to nie jest spelnione?
Wyrzucić jakiś error lub tekst, po prostu zakończyć program.
No to do tego sluzy if ale w tym przypadku to przeciez nie ma sensu:d
Bo 0! to 1 i 1! to 1 (0,1 nie spelniaja nierownosci <1)
Czemu iteracyjnie mi to działa
int main()
{
int n;
cin >> n;
int wynik = 1;
for(int i=1; i<=n; i++) {
wynik = wynik*i;
}
cout << wynik;
return 0;
}
a gdy wrzucam to w funkcje to już nie?
int silnia(int n) {
int wynik = 1;
for(int i=1; i<=n; i++) {
wynik = wynik*i;
}
}
int main()
{
int n;
cin >> n;
cout << silnia(n);
return 0;
}
Nie zwracasz wyniku
@stivens: Dzięki
mam jeszcze pytanie odnosnie rekurencji
Jak mam takie coś
int silnia(int n) {
if(n<=1) return 1;
int wynik;
wynik=n*silnia(n-1);
return wynik;
}
załóżmy, że n to 5, czyli wynik = 5*silnia(5-1) , co oznacza wtedy ten wyraz silnia? Ile razy to się wykona, bo nie potrafię tego zrozumiec.
Jak kompilujesz program?
Jakbys uzywal dodatkowych flag kompilacji to kompilator raczej by Cie poinformowal ze cos zrobiles zle
alias cc="gcc -std=gnu18 -Wall -Wextra -Wshadow -O2 -lm"
alias ccpp="g++ -std=gnu++17 -Wall -Wextra -Wshadow -O2"
ccpp test.cpp
test.cpp: In function ‘int silnia(int)’:
test.cpp:7:1: warning: no return statement in function returning non-void [-Wreturn-type]
7 | }
| ^
test.cpp: In function ‘int main()’:
test.cpp:12:5: error: ‘cin’ was not declared in this scope
12 | cin >> n;
| ^~~
test.cpp:14:5: error: ‘cout’ was not declared in this scope
14 | cout << silnia(n);
| ^~~~
int silnia(int n) {
if(n<=1) return 1;
int wynik;
wynik=n*silnia(n-1);
return wynik;
}
to jest typowa reukrencja, silnia jest zdefiniowana na podstawie wywołania tej funkcji dla innej wartości. Czyli dla n = 5:
wynik=n*silnia(n-1); oznacza wynik=5*silnia(5-1);.
Teraz musimy policzyć silnia(4):
wynik=4*silnia(4-1);
i tak dalej aż n = 1.
Ostatecznie masz więc 5 wywołań (dla 5,4,3,2 i 1)
Tylko po kiego grzyba tak komplikować?
int silnia(int n) { return n>1?n*silnia(n-1):1; }
@Descendant: myślę, że by zrozumieć funkcję rekurencyjną, pomaga patrzenie na taką funkcję jak na listę linii. Wykonując ją, zaczynasz na linii nr 1, czyli na nagłówku funkcji (= jej liście argumentów). Idziesz do linii nr 2. I teraz, zanim wykonasz jej instrukcje, musisz sprawdzić warunek: jeżeli napotkasz wywołanie tej samej funkcji, to wracasz do linii nr 1, za argumenty podstawiając te argumenty, które są w napotkanym wywołaniu; a jeżeli nie, to wykonujesz instrukcje linii nr 2 i idziesz do linii nr 3. I tak za każdą kolejną linią aż do końca funkcji.