Algorytm definiujący funkcję obliczającą dowolny wyraz ciągu

pytanie zadane 8 stycznia 2017 w Algorytmy przez Kamil Maksymowicz Początkujący (400 p.)

Jak napisać algorytm definiujący funkcję obliczającą przy pomocy pętli dowolny wyraz ciągu określonego wzorem

oraz każdy kolejny wyraz jest sumą dwóch poprzednich

komentarz 8 stycznia 2017 przez Kamil Maksymowicz Początkujący (400 p.)
edycja 8 stycznia 2017 przez Kamil Maksymowicz


 function ciąg(a)

Begin

if (a= =0) return 2

if (a= =1) return 3

else return ciąg (a-1) + ciąg (a-2)

end

Miałem zapisać w pseudokodzie. Czy jest poprawnie ?

2 odpowiedzi

odpowiedź 8 stycznia 2017 przez Barus Stary wyjadacz (14,120 p.)

Zależy w jakim języku. Opiszę Ci to w C++ i w C#.

C++ :

Pytasz użytkownika jak długi ma być ciąg, user zapisuje długość ciągu do zmiennej (nazwijmy ją x).
Tworzysz dynamiczną alokację pamięci w której w nawiasach kwadratowych wpisujesz zmienną x.
Do tablicy o indeksie 0 przypisujesz liczbę 2
Do tablicy o indeksie 1 przypisujesz liczbę 3.
Tworzysz pętlę for (może być także while, ale ja opiszę for), która rozpoczyna się od 2, kończy na zmiennej x i inkrementuje co 1.
W ciele pętli sumujesz: tablica[i]=tablica[i-1]+tablica[i-2] i wyświetlasz wynik na konsolę.
Usuwasz dynamicznie zaalokowaną pamięć.

C# :

Pytasz użytkownika jak długi ma być ciąg, user zapisuje długość ciągu do zmiennej (nazwijmy ją x).
Tworzysz tablicę, w której w nawiasach kwadratowych wpisujesz zmienną x.
Do tablicy o indeksie 0 przypisujesz liczbę 2
Do tablicy o indeksie 1 przypisujesz liczbę 3.
Tworzysz pętlę for (może być także while, ale ja opiszę for), która rozpoczyna się od 2, kończy na zmiennej x i inkrementuje co 1.
W ciele pętli sumujesz: tablica[i]=tablica[i-1]+tablica[i-2] i wyświetlasz wynik na konsolę.

Jeżeli jesteś na etapie, w którym nie poznałeś jeszcze tablic, wskaźników i dynamicznej alokacji pamięci to najpierw przerób te materiały, a potem zrobisz bez problemu ten program :)

Pozdrawiam!

komentarz 8 stycznia 2017 przez playerony Pasjonat (15,240 p.)

Wystarczy, że przewinie strone w dół i zrobi to bez wykorzystania tablic itp. btw. po co przechowywać wszystkie wyrazy po czym je usuwać ?

komentarz 8 stycznia 2017 przez Barus Stary wyjadacz (14,120 p.)

Zrobiłeś to kolego innym sposobem (z pewnością lepszym), a ja innym i działa. Miałem na myśli usunięcie dynamicznie zaalokowanej pamięci w celu jej opróżnienia już po wykonaniu pętli.

komentarz 8 stycznia 2017 przez Sinnley Stary wyjadacz (12,810 p.)

Sortowanie bąbelkowe też działa.

Algorytm jest dobry wtedy kiedy jest optymalny a nie wtedy kiedy działa.

odpowiedź 8 stycznia 2017 przez playerony Pasjonat (15,240 p.)

No tutaj się kłania ciąg fibonacciego, tak więc tłumacze:

Kolejne wyrazy ciągu: 2, 3, 5, 8, 13, 21, ...

1. Robisz sobie jakąś funkcje, która zwróci Ci n-ty wyraz ciągu, która jako parametr przyjmnie numer.

2. Wewnątrz trzymasz zmienne odpowiadające za 1 oraz 2 wyraz twojego ciągu, na potrzeby przykładu będą to "a" oraz "b" do których przypiszemy kolejno liczby 2 i 3.

3. Jescze sprzydał by się jakies for wyliczający do naszego przesłanego jako parametr n.

4. No i w forze do drugiej zmiennej dodajesz tę poprzednią np. "b+=a" -> "5+=3" -> "8"

5. Jescze pozostaje wyznaczyć te "a" z podpunktu 4, no tu wystarczy zrobić proste odejmowanie "a = b - a" -> "5 = 8 - 3".

6. W zmiennej "a" będziesz miał szukany n-ty wyraz ciągu.

7. Na koniec dodajesz ify dla warunku kiedy użytkownik poda liczbe mniejsza od zera, równą 1 oraz równa 2.

8. Cieszysz się wykonanym programem.