• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Rozkład Fibonacciego 2 etap XIX OI

Aruba Cloud PRO i VPS, Openstack, VMWare, MS Hyper-V
0 głosów
120 wizyt
pytanie zadane 16 marca w Algorytmy przez pasjonat_algorytmiki Pasjonat (18,860 p.)
Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/w1QbhPufazp-sH6X-u4pTnNu/site/?key=statement

Kompletnie nie wiem jak je zrobić w sensownej złożonności oprócz jakiegoś backtrackingu.

Z góry dziękuję za pomoc!

1 odpowiedź

0 głosów
odpowiedź 16 marca przez Whistleroosh Maniak (55,720 p.)
edycja 16 marca przez Whistleroosh
To takie zadanie w którym trzeba zgadnąć rozwiązanie i sprawdzić np. brutem czy działa. Ja do teraz nie rozumiem dowodu dlaczego wzorcówka działa.

Jakie rozwiązanie nasuwa się w tym zadaniu? Możesz spróbować spojrzeć na prostszą wersję tego zadania, w której można tylko dodawać. Jak wtedy to zrobić?
komentarz 16 marca przez pasjonat_algorytmiki Pasjonat (18,860 p.)
Może robić takiego BFS-a? najpierw wrzucamy log(max_val) na kolejkę i dodajemy od jak największych?
komentarz 16 marca przez pasjonat_algorytmiki Pasjonat (18,860 p.)
log_max, czyli wszystkie liczby fibonacciego nie przekraczające max_val
komentarz 16 marca przez Whistleroosh Maniak (55,720 p.)
Blisko. Czy konieczy jest BFS? Może wystarczy brać zachłannie?
komentarz 16 marca przez pasjonat_algorytmiki Pasjonat (18,860 p.)

W sensie, pomysł taki:

ile_zostalo = N

while(ile_zostalo > 0)
{
biorę największą jaką mogę i ją odejmuję
}

?

komentarz 16 marca przez Whistleroosh Maniak (55,720 p.)
Tak, to zadziała. Da się to jakoś przenieść na wersję z odejmowaniem?
komentarz 16 marca przez pasjonat_algorytmiki Pasjonat (18,860 p.)
Zachłannie dodajemy aż nie przekroczymy, a jak przekroczymy to zachłannie odejmujemy, a ile można zachłannie dodać / odjąć w danym momencie możemy zrobić, napełniając vector liczb fibonnaciego nie przekraczających max_val i binarne szukać?
komentarz 16 marca przez pasjonat_algorytmiki Pasjonat (18,860 p.)
A nie jednak nie to nie zadziała
komentarz 16 marca przez Whistleroosh Maniak (55,720 p.)
Hint: jeśli fib_i <= k < fib_{i+1} to rozwiązanie zawiera i lub i+1 liczbę Fibonacciego
komentarz 16 marca przez pasjonat_algorytmiki Pasjonat (18,860 p.)
troszkę więcej?
komentarz 16 marca przez Whistleroosh Maniak (55,720 p.)
Spójrz na fib_{i+1}-k i k-fib_i Czy da się stwierdzić która liczba ma mniejszą dekompozycje? To cięzko sprawdzić ręcznie, lepiej napisać program który to przetestuje

Podobne pytania

91,798 zapytań

140,459 odpowiedzi

316,881 komentarzy

61,146 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...