Nov 2022
2 / 10
Nov 2022
Jun 2023
tjm
Nov '22

Przykładowe wejście:

1000000000

Jako ciekawostka, funkcjonalność kompilatora clang pozwalająca na identyfikację błędów takich jak w załączonym programie:

$ clang++ -g -fsanitize=integer a.cpp
$ 1000000000 | ./a.out 
a.cpp:11:65: runtime error: unsigned integer overflow: 17490168 - 722019349 cannot be represented in type 'unsigned long long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior a.cpp:11:65 in 
761306912

(Informacja o “undefined-behavior” jest niestety technicznie niepoprawna w tym przypadku).

yula
Nov '22
supermedyk

link do swojej wersji usunąłeś prawidłowo… Link do zadania niepotrzebnie przyda się jeśli ktoś jeszcze podepnie sie… Chyba że możesz usunąć cały wątek.

yula
Nov '22

Mogę prosić od odpowiedzi dla wejść:
1000000000
999999999

6 months later
yula
Jun '23
1

Jak można przyśpieszyć czy inaczej zrobić (przekroczono limit czasu)
AC

tjm
Jun '23

Jedna droga do poprawy wyniku to takie przeformułowanie zależności aby uzyskać tylko jedno wywołanie rekurencyjne i uniknąć w ten sposób konieczności zapamiętywania wyników obliczeń.

Pomysł zasadniczo opera się na obliczaniu wartości dwóch kolejnych elementów ciągu Fibonacciego równocześnie, czego można dokonać wyrażając Fib(2n) i Fib(2n+1) przy pomocy Fib(n) i Fib(n+1).

yula
Jun '23

nie rozumiem, wyrazić F(2n) i F(2n+1) za pomocą F(n) i F(n+1) to nie problem, ale co to daje ? I tak trzeba obliczyć to F(n) i F(n+1)… Czegoś nie łapię…

tjm
Jun '23

Może poniższy szkic funkcji skuteczniej przekaże idea rozwiązania. Docelowo f(k//2) to jedyne wywołanie rekurencyjne:

def f(k):
    """f(k) = fib(k), fib(k+1)"""
    if k == 0:
        return 0, 1
    a, b = f(k // 2)
    if k % 2 == 0:
      # k = 2n
      # a = fib(n)
      # b = fib(n+1)
      # return fib(2n), fib(2n+1)
    else:
      # k = 2n+1
      # a = fib(n)
      # b = fib(n+1)
      # return fib(2n+1), fib(2n+2)
yula
Jun '23

Dzięki