[unvector]

Mireczki z #programowanie,
#pytanie ile Wam zajmuje zrobienie takiego zadanka: https://www.codewars.com/kata/57040e445a726387a1001cf7
Bo mi łącznie chyba z 15h zajęła rozkminka + 0.5h kod... i nie wiem, czy to takie trudne, czy taki ze mnie łoś :(

#matematyka #codegolf #programista15k

[u.....8]

@unvector: nie umiem odpowiedzieć Ci na pytanie.
Za to wiem, że życiowo najlepszym rozwiązaniem (tam, gdzie od czasu robienia obliczeń zależy kasa / życie itp) to wiedzą matematyczną z zakresu matematyki dyskretnej/konkretnej taki ciąg rekurencyjny powinien być zmieniony w ciąg w postaci jawnej.
Tutaj poprosili wprost o postać rekurencyjną, bo ćwiczenie dotyczy innej umiejętności :-)

[KotFilemon991]

@unvector: o dzieki miałem takie samo domowe i już trzeci dzień siedzę jak to rozgryźć a tu gotowiec ( ͡° ͜ʖ ͡°)

[unvector]

@uhu8 rozwiązałem to zadanie - zastanawiam się po prostu, czy to normalne, że aż tak długo nad nim siedziałem

[arekarek]

@unvector: na niektórych stronach podają czas jaki średnio ludzie potrzebowali na rozwiązanie zadania np https://www.interviewbit.com więc możesz rozwiązać jakieś zadania tam i się porównać

[unvector]

@arekarek dzięki za info ;-)

[u.....8]

@unvector: ja też bym rozwiązał to zadanie (pewnie też siedząc długo). Chodzi o to, że w "życiowych" zastosowaniach przy tego typu problemie nie można sobie pozwolić na tak dramatyczny wzrost czasu obliczeń :)

[kafapre]

@unvector: z ciekawości spróbowałem i wyglądało to tak, że najpierw spróbowałem naiwnej rekursywnej wersji, dla które oczywiście przekroczony został limit stosu. No to zrobiłem własny stos, ale tutaj został przekroczany limit czasu dla testowych danych. Kolejnym krokiem było zastosowanie programowania dynamicznego i po jego wdrożeniu testy już bez problemu przechodziły - na dojście do tego etapu zeszła mi mniej więcej godzina. Niestety dla 'attempt' przekraczało timeout, więc chcąc nie chcąc musiałem

[kafapre]

result = F(1, 0, n)
return F(1, 0, n)

Co ja #!$%@?łem w refaktoryzacji xd. Zrobiłem teraz z tego jedną funkcję, zoptymalizowałem krok dla nieparzystych (można od razu podzielić przez 2 i uniknąć ifa + przypisania) i nareszczie przechodzi :)

[unvector]

@kafapre ja to rozwiązałem w Javie, algorytm ostatecznie jest bardzo prosty. Wyszedłem od zdefiniowania kilku twierdzeń i przekształceń funkcji F. Czy to co napisałeś działa i przechodzi testy w odpowiednim czasie?

[unvector]

Ok, niedoczytałem, ze przechodzi

[unvector]

@kafapre wersja dla zwykłych liczb całkowitych (int):

int fusc(int n) {
----int a = 1, b = 0;
----while (n > 0) {
--------if ((n & 1) == 0) {
------------a += b;
--------} else {
------------b += a;
--------}
--------n >>= 1;
----}
----return b;
 }

w sumie wyglądają podobnie