Új hozzászólás Aktív témák

• Csaby25 őstag

  #11569

  #11567 Sirpi

  2021-06-06 09:19:22

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  Csaby25

  őstag

  #11567 Sirpi

  #11567 Sirpi

  Én mind a két implementációt optimalizálnám.

  Az elsőnél az a gond, hogy így baromi lassú, F(n)-t pont F(n) időben fogja kiszámolni, tehát lineáris helyett exponenciális lesz a futásidő. Ezen a már kiszámolt értékek eltárolásával lehet segíteni. Próbáld nagyobb értékkel futtatni, azt hiszem, az int-be 44-ig nem csordul túl, de ha átírod long-ra, akkor 89-ig próbálkozhatsz, azt pedig már lehetetlen kivárni.

  A másodiknál pedig felesleges lefoglalni egy teljes tömböt, elég tudni mindig a két utolsó értéket:

  if (n <= 1)
return n;
int a = 0;
int b = 1;
for (int i = 2; i <= n; i++) {
  int c = a + b;
  a = b;
  b = c;
}
return b;

  Az van, hogy codingbat-on elkezdtem megoldani a rekurziós feladatokat rekurzióval és ciklussal is (már megvan 17 a 30-ból ), a saját tesztje azt mondta, hogy ok és továbbléptem

• Csaby25 őstag

  #11568

  #11567 Sirpi

  2021-06-06 09:10:15

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  Csaby25

  őstag

  #11567 Sirpi

  #11567 Sirpi

  Én mind a két implementációt optimalizálnám.

  Az elsőnél az a gond, hogy így baromi lassú, F(n)-t pont F(n) időben fogja kiszámolni, tehát lineáris helyett exponenciális lesz a futásidő. Ezen a már kiszámolt értékek eltárolásával lehet segíteni. Próbáld nagyobb értékkel futtatni, azt hiszem, az int-be 44-ig nem csordul túl, de ha átírod long-ra, akkor 89-ig próbálkozhatsz, azt pedig már lehetetlen kivárni.

  A másodiknál pedig felesleges lefoglalni egy teljes tömböt, elég tudni mindig a két utolsó értéket:

  if (n <= 1)
return n;
int a = 0;
int b = 1;
for (int i = 2; i <= n; i++) {
  int c = a + b;
  a = b;
  b = c;
}
return b;

  Köszi ! Én sajnos nem gondoltam arra, hogy belassul csak arra, hogy megoldjam .
  Gondolom még nem vagyok olyan szinten, hogy az optimális megoldást keressem...
  Amúgy a tömbös megoldás gyorsaság szempontjából jó, viszont a helyfoglalás miatt tényleg az általad említett jobb..

Új hozzászólás Aktív témák