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

ilosc rozkladow liczby na sume liczb fibonacci'ego

VPS Starter Arubacloud
+1 głos
392 wizyt
pytanie zadane 8 stycznia 2023 w C i C++ przez polandonion Mądrala (6,970 p.)
edycja 10 stycznia 2023 przez polandonion

witam, zabralem sie dzisiaj za problem wyznaczenia ilosci unikatowych rozkladow liczby na liczby fibonacciego (tzn. np dla liczby 10 bedzie odp: 2, poniewaz 10 = 8 + 2 = 5 + 3 + 2).

zauwazylem, ze w tym zadaniu (podobnie jak w algorytmie wydawania reszty) trzeba bedzie zastosowac programowanie dynamiczne. niestety rozwiazanie to daje mi 59% (dwa testy daja bledna odp. w tym przypadku obydwa bledy brzmia: wczytano '2' a oczekiwano '1').

pomozecie okreslic gdzie lezy blad w mojej implementacji algorytmu?

dodam rowniez, ze dla jednego testu mam przekroczenie limitu czasu (a to oznacza, ze prawdopodobnie bede musial utworzyc tablice sum prefiksowych liczb fibonacciego i zamiast naiwnie szukac liczby fibonacciego mniejszej od liczby, ktora chce rozlozyc, bede musial wyszukiwac binarnie taka liczbe)

zadanie: link

wyniki: link

kod:

#include <bits/stdc++.h>

using namespace std;

void genLicFib(int n);
int roz(int n, int ind);

vector <int> fib;

int main() {
	int n;
	cin >> n;

	genLicFib(n);

	cout << roz(n, fib.size() - 1);
}

void genLicFib(int n) {
	fib.push_back(1);
	fib.push_back(2);

	while (fib.back() < n)
		fib.push_back(fib.back() + fib[fib.size() - 2]);
}

int roz(int n, int ind) {
	if (n == 0)
		return 1;

	int sum = 0;

	for (int i = ind; i >= 0; i --) {
		if (fib[i] > n)
			continue;

		sum += roz(n - fib[i], i - 1);
	}

	return sum;
}
komentarz 9 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
przeszło?
komentarz 9 stycznia 2023 przez polandonion Mądrala (6,970 p.)
tak, tylko chciałbym uzyc rekurencji, bo nauczyciel tego wymaga, dzieki za wzorcowke ale moglbys pokazac jak zmodyfikowac moj kod aby liczyl tylko te sumy gdzie czynnikow jest min 2
komentarz 9 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Te zle wyniki powinny odpasc, gdy napiszesz mniej wiecej cos takiego:

for (int i = 0; i < FIB.size(); ++i)
        if (FIB[i] == n)
            dp[n]--;

W sensie musisz przeiterować się po wszystkich liczbach fibonaciego, i odjąć 1 jesli wczytana liczba jest liczbą fibonacciego, bo np dla liczby 8 liczysz 5 + 3, 5 + 2 + 1, 8, a 8 to tylko jedna liczba a nie 2. Co do przekroczenia limitu czasu, to nwm czy da się to zrobić szybciej niż plecak. Tylko zamiast dp[n] musisz odjac jeden od tego swojego liczniku

komentarz 9 stycznia 2023 przez polandonion Mądrala (6,970 p.)
okej
komentarz 9 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 9 stycznia 2023 przez pasjonat_algorytmiki
Przeszło? btw, ta rekurencja jest akurat w tym zadaniu zdecydowanie przesadzona, na początku pomyślałem sobie, że skoro ciag fibonaciego rośnie wykładniczo, to może przejdzie back tracking w O(2^fib_size), ale dopiero 30 liczba fibonaciego to około 10^6, wiec O(2^30) zdecydowanie zawolne. Do uzycia plecaka narzucajace jest to, że n <= 10^6, a plecak ma O(n * fib_size).

Pisałeś, że dopiero zaczynasz z dynamikami, więc masz listę kilku zadań, wykładów, które moim zdaniem są warto obejrzenia / zrobienia.

- Klocki final OIG-a https://szkopul.edu.pl/problemset/problem/UUw6ABmeLv0dpfsviYlhdnnz/site/?key=statement , omówione przez Pana Daniela Olkowskiego na OKI: https://www.youtube.com/watch?v=OafWtKkbGmw&t=6279s

- Waga finał OIG - trudny plecak (trzeba przerzucic na jedna strone) https://szkopul.edu.pl/problemset/problem/BrQp-HTIOGxQM6aruH7KJprP/site/?key=statement

- Wycinka drzew 1 etap XVI OIJ - dynamik 1d z binary searchem

- Rezerwacja Sal wykładowych final OI, ale poziom prawie taki sam jak wycinka drzew. Praktycznie te same zadania.

- Bracia finał 5 OIG-a (można w 10 linii zaklepać) https://szkopul.edu.pl/problemset/problem/KkZDP16mELVF692Bf-NJsN1L/site/?key=statement

- Mnożenie 1 etap XVI OIJ (z optymalizacja 2^n) https://szkopul.edu.pl/problemset/problem/a1YWxmi8ot8piqA29nEhEANx/site/?key=statement

super wykład Pana Lecha Duraj-a na Zdalnych Warsztatach Olimpijskich Dla juniorów 2020 z dynamików, zadania na dynamiki to (mosięzny most, piramida, neon, skarb faraona, diamenty, zygzak(BFS rownolegly), zadanie marchewka jest w wykladzie z dynamikami, ale mozna je napewno zrobic stosem monotonnicznym lub binary searchem po wyniku. https://sio2.mimuw.edu.pl/c/zwo20/p/ , wykład masz na kanale OIJ-a

zadanie antytrójkątowe pudełko z finału 15 OIJ-a. Jest tu na forum wątek o nim

I spoko jest też spojny podciag o największej sumie (spoko zadanie Stonks z Zdalnych Warsztatów Dla Juniorów 2021 - jest na sio2)

I na OKI mają być zajęcia z dynamików w najbliższej przyszłosci

2 odpowiedzi

+2 głosów
odpowiedź 9 stycznia 2023 przez diedassel Użytkownik (570 p.)
edycja 26 lutego 2023 przez diedassel
 
Najlepsza

Witam,

  • W pętli for wyknujesz zbyt dużo niepotrzebnych operacji. Nie trzeba tutaj używać dp. Wygodniej będzie użyć tablicy / wektora sum prefiksowych liczb fibonacci'ego (na potrzeby wyjaśnienia nazwijmy tą strukturę sumy[]).
  • W pętli for za każdym razem dokonaj porównania sumy[i] oraz liczby, którą masz rozłożyć. Jeżeli okaże się, że zszedłeś do liczb, których suma prefiksowa jest mniejsza od liczby, którą chcesz rozłozyć przerwij pętle. 
if (sumy[i] < n)
			break;
  • To powinno dać ci maksymalną ilość punktów. Dla moich testów poprawka ta dla max wartości jest znacznie szybsza.

Pozdrawiam :D

komentarz 9 stycznia 2023 przez polandonion Mądrala (6,970 p.)

Ale, że wystarczyła taka mała poprawka... dzięki z całego serca

I także pozdrawiam.

dla przyszłych użytkowników przesyłam wzorcówkę:

#include <bits/stdc++.h>

using namespace std;

void genFibNum(int n);
int fac(int n, int last);

vector <int> fib = {1, 2};
vector <int> fibSuf = {1};

int main() {
	int n;
	cin >> n;

	genFibNum(n);

	cout << fac(n, fib.size() - 1);
}

void genFibNum(int n) {
	while (fib.back() < n) {
		fib.push_back(fib.back() + fib[fib.size() - 2]);
		fibSuf.push_back(fibSuf.back() + fib[fibSuf.size()]);
	}
		
	fib.pop_back();		
}

int fac(int n, int last) {
	if (n == 0)
		return 1;
 
	int sum = 0;
 
	for (int i = last; i >= 0; i --) {
		if (fib[i] > n)
			continue;

		if (fibSuf[i] < n)
			break;
 
		sum += fac(n - fib[i], i - 1);
	}
 
	return sum;
}

 

+1 głos
odpowiedź 9 stycznia 2023 przez adrian17 Ekspert (344,100 p.)
edycja 9 stycznia 2023 przez adrian17

Dla pewności, powtórki są zakazane? Tzn 10 == 5 + 5 ? 

Możesz po prostu podrzucić całe zadanie?

dodam rowniez, ze dla jednego testu mam przekroczenie limitu czasu (a to oznacza, ze prawdopodobnie bede musial utworzyc tablice sum prefiksowych liczb fibonacciego i zamiast naiwnie szukac liczby fibonacciego mniejszej od liczby, ktora chce rozlozyc, bede musial wyszukiwac binarnie taka liczbe

Uhh... co? Ale pisałeś że zrobiłeś to z programowaniem dynamicznym, ale nie zrobiłeś jeszcze głównej optymalizacyjnej części programowania dynamicznego czyli memoizacji, nie? (Albo alternatywnie odwrócenia rekursji i budowania od dołu, tak jak zrobiłeś z generowaniem liczb fibonacciego - ale tego z głowy bym nie umiał odwrócić, a memoizacja brzmi intuicyjnie)

komentarz 9 stycznia 2023 przez polandonion Mądrala (6,970 p.)

tutaj treść zadania: link.

i tak, powtórki są zakazane, kazda liczba moze zostac uzyta max 1 raz w rozkladzie.

Uhh... co? Ale pisałeś że zrobiłeś to z programowaniem dynamicznym, ale nie zrobiłeś jeszcze głównej optymalizacyjnej części programowania dynamicznego czyli memoizacji, nie? 

nie jestem jeszcze doświadczony jeśli xhodzi o programowanie dynamiczne, jest to moze moj drugi, max. trzeci program na uzycie takiego podejscia algorytmicznego. co do memoizacji, nigdy tego nie uzywalem, ale jesli ma pomoc w szybkosci mozesz podac przyklad uzycia.

Podobne pytania

0 głosów
1 odpowiedź 158 wizyt
pytanie zadane 20 maja 2023 w C i C++ przez Igaiga Nowicjusz (120 p.)
0 głosów
0 odpowiedzi 431 wizyt
pytanie zadane 3 lutego 2021 w Python przez AgentTecza Obywatel (1,810 p.)
0 głosów
2 odpowiedzi 2,049 wizyt
pytanie zadane 30 października 2020 w C i C++ przez forvev Początkujący (390 p.)

92,452 zapytań

141,262 odpowiedzi

319,077 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...