Autor Wątek: Java ciąg Fibonacciego  (Przeczytany 3619 razy)

Offline Zarejestruj

  • Użytkownik

# Grudzień 02, 2015, 22:25:07
Witam

Czy ktoś może pomóc w zrozumieniu o co chodzi w tym zadaniu? Nie chodzi o pomoc w napisaniu tylko w zrozumieniu.

"Napisz program który na wejściu przyjmie wartości początkowe, np. a i b i 12 razy wyświetli je w postaci ciągu fibonacciego, tj. jeżeli wywołam z konsoli:
java <moja klasa> a b
wynikiem będzie ciąg:
a
b
ab
bab
abbab
bababbab
abbabbababbab
bababbababbabbababbab
itd."

Czy chodzi o to, że jak np. podam 4 i 5 jako a i b, to program ma wypisać
4
5
9
14
23
itd. aż do 12 linijek?

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Kos

  • Użytkownik
    • kos.gd

  • +1
# Grudzień 02, 2015, 22:34:28
Ja rozumiem że a i b mają być tu typu napisowego i mają być dodawane jako napisy a nie jako liczby, więc jeśli podasz '4' i '5' to powinno wyjść

4
5
45
545
45545
54545545
....

Offline Xion

  • Moderator
    • xion.log

# Grudzień 03, 2015, 09:11:51
Każda następna linijka to dwie poprzednie złączone ze sobą. Innymi słowy, jest to normalny ciąg Fibonacciego tylko że zamiast dodawania liczb mamy konkatenację stringów.

Offline DMX

  • Użytkownik

# Grudzień 05, 2015, 00:16:26
Nie chodzi o funkcję rekurencyjną, która odwoła się do siebie 12 razy? Ciąg Fibonacciego często się wykorzystuje do zaprezentowania działania rekurencji.

Offline Zarejestruj

  • Użytkownik

# Grudzień 06, 2015, 20:28:21
A czy dodając do elementu x-2 element x-1 (zamiast odwrotnie) to dalej będzie można nazwać ciągiem Fibonacciego?  Tylko w ten sposób działa to poprawnie dla Stringów. Dodawanie jest niby przemienne ale sam już nie wiem.

Offline Kos

  • Użytkownik
    • kos.gd

  • +1
# Grudzień 06, 2015, 22:57:21
Tylko w ten sposób działa to poprawnie dla Stringów.

Cytuj
Dodawanie jest niby przemienne ale sam już nie wiem.

Konkatenacja stringów to nie jest to samo co dodawanie i nie jest przemienna.
Dodawanie też nie jest przemienne, jeśli dodajesz floaty :))

Offline hashedone

  • Użytkownik

  • +1
# Grudzień 07, 2015, 10:44:08
Dodawanie jest przemienne tylko w pierścieniach przemiennych, a nie we wszystkich zbiorach. Ciąg Fibonacciego (a właściwie ciąg homeomorficzny do Fibonacciego, bo ciąg Fibonacciego z definicji ma Fib(0) = 0, Fib(1) = 1) można spokojnie zdefiniować na dowolnym zbiorze w którym określi się jedno działanie (nie musi być ono ani przemienne, ani łączne). Co prawda ta matematyczna gadka brzmi bardzo dziwnie, ale w praktyce oznacza to, że ciąg fibonacciego można na przykład zdefiniować na floatach (które potrafią przechowywać na 4 bajtach znacznie większe liczby, niż inty - tyle że z utraconą precyzją). I tak samo można dla zobrazowania jakiegoś problemu zdefiniować liczby fibonacciego na stringach z konkatenacją (która bardzo często w programowaniu jest domyślnym działaniem "dodawania" stringów - jak w C++, Javie, C#).

Offline Xender

  • Użytkownik

# Grudzień 07, 2015, 11:21:18
Jeśli chodzi o samo zadanie, to ja zrozumiałem to tak, że a i b mają być zmiennymi liczbowymi, których wartość podaje użytkownik.
Następnie należy utworzyć ciąg a'la ciąg Fibonacciego, gdzie wartościami początkowymi zamiast 1, 1 będą a, b.


Ale poprawna odpowiedź to jak i większość pytań z gatunku "nie rozumiem treści zadania" jest tylko jedna: zapytaj tego, kto zlecił Ci to zadanie do wykonania.

Z naszego zgadywania może wyjść dobra odpowiedź albo krzywe kluchy. Nie wiadomo.
Jak się dopytasz tej samej osoby, która zadanie zleciła i będzie przyjmować rozwiązanie, to taka odpowiedź jest wiążąca.


Nie chodzi o funkcję rekurencyjną, która odwoła się do siebie 12 razy? Ciąg Fibonacciego często się wykorzystuje do zaprezentowania działania rekurencji.
Jeśli nie mówisz o rekurencji ogonowej, to nie, po prostu nie....

Fibonacci daje się ślicznie napisać w wersji iteracyjnej albo ogonowej, która ma jedną zaletę - nie przepełnia stosu.


<offtop>
Fibonacci na stringach?

To mi przypomina moje ulubione L-systemy:
https://en.wikipedia.org/wiki/L-system#Example_1:_Algae

Nie jest to dokładnie treść zadania, ale wariacja na ten temat (wystarczy porównać sobie wyjścia).

I bardzo miły zjadacz czasu - "No wisi nade mną zadanie/robota, ale te drzewka są takie faajnee~". :)
</offtop>

Offline Xion

  • Moderator
    • xion.log

# Grudzień 07, 2015, 18:30:50
Cytuj
Dodawanie jest przemienne tylko w pierścieniach przemiennyche (...)
Nah, wystarczy grupa abelowa, nie potrzeba zaraz całego pierścienia :)

Offline Xender

  • Użytkownik

# Grudzień 07, 2015, 23:22:09
Dodawanie jest przemienne tylko w pierścieniach przemiennych
Nah, wystarczy grupa abelowa, nie potrzeba zaraz całego pierścienia :)
Grupa przemienna (abelowa) – grupa, w której działanie jest przemienne. Zwyczajowo, w przypadku grup przemiennych stosuje się zapis addytywny.

Czyli z tych wyjaśnień wychodzi na to, że:

Dodawanie jest przemienne tylko tam, gdzie jest przemienne.


W następnym odcinku: forumowicze Warsztatu wyjaśnią, co to jest "odwołanie cykliczne". :)

Offline koirat

  • Użytkownik

# Grudzień 08, 2015, 00:00:12
Raczej wychodzi na to że dodawanie jest przemienne tylko w strukturze określonej na danym zbiorze dla którego działanie zdefiniowane operatorem dodawania spełnia następujący warunek.

a + b = b + a

gdzie a oraz b są elementami tego zbioru.

Offline Lars Kormak

  • Użytkownik

  • +1
# Grudzień 08, 2015, 00:24:11
Jeśli już rzucamy terminami, to struktura, której szukacie, to grupoid abelowy. ;)
« Ostatnia zmiana: Grudzień 08, 2015, 01:38:10 wysłana przez Lars Kormak »

Offline Xion

  • Moderator
    • xion.log

  • +1
# Grudzień 08, 2015, 08:50:19
Jeśli już rzucamy terminami, to struktura, której szukacie, to grupoid abelowy. ;)
Heh, faktycznie.

Ten obrazek dobrze ilustruje różnice (magma/grupoid jest na górze, z domkniętością (closure) jako jedyną własnością):

« Ostatnia zmiana: Grudzień 08, 2015, 08:52:42 wysłana przez Xion »

Offline Kos

  • Użytkownik
    • kos.gd

  • +2
# Grudzień 08, 2015, 09:45:13
@up czy to co wkleiłeś to jest właśnie ten 'pierścień przemienny'? ;-)

Offline hashedone

  • Użytkownik

# Grudzień 10, 2015, 10:29:04
Niet. To co wkleił, to wizualizacja zależności między podstawowymi strukturami algebraicznymi. Żeby sobie tam dorobić pierścień przemienny, to musisz sobie wziąć grupę, teraz tak podmienić jej jedyne działanie, żeby jeszcze było przemienne (wtedy masz grupę abelową - działanie nazwijmy dodawaniem), teraz dodajesz jeszcze drugie działanie które nazwiesz mnożeniem i które będzie łączne (bez żadnych innych ograniczeń). Jak już masz takie mnożenie, to jeszcze się upewniasz, że zachodzą prawa rozdzielności (a * (b + c) = a * b + a * c; (a +b) * c = a * c + b * c). A mój błąd z przytoczeniem pierścienia przemiennego była po prostu pomyłka (miałem na myśli grupę przemienną - o pierścieniach mówimy jak potrzebujemy dwóch działań, a przecież tu jest jedno). Za to na grupoid abelowy to bym nie wpadł (w ogóle ta struktura do czegoś służy oprócz tego że się nazywa?) :D