# Dieta di poldo (ricorsione)

**URL:** <https://forum.olinfo.it/t/dieta-di-poldo-ricorsione/6807>\
**Category:** Aiuto\
**Created:** [25 Novembre 2021, 7:07pm UTC](https://forum.olinfo.it/t/dieta-di-poldo-ricorsione/6807 "2021-11-25T19:07:23Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![flp\_o3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/f9ae1b/32.png) [@flp\_o3](https://forum.olinfo.it/u/flp_o3)\
**Post date:** [25 Novembre 2021, 7:07pm UTC](https://forum.olinfo.it/t/dieta-di-poldo-ricorsione/6807/1 "2021-11-25T19:07:24Z")

</div>

Ciao a tutti. Ho bisogno di aiuto con il problema “la dieta di poldo”. Ho provato a risolverlo con una funzione ricorsiva ma non capisco perchè non funziona. Spero che qualcuno sappia dirmi dove sbaglio, grazie.

```auto
#include <iostream>

#include <fstream>

#include <vector>

using namespace std;

vector<int> v;

int n;

int contatore = 1;

int max(int a, int b)

{

    if (a > b)

    {

        return a;

    }else{

        return b;

    }

}

int function (int k)

{

   

    for (int i = k+1; i < n; i++)

    {

        if (v[i] < v[k])

        {

            contatore = max(contatore, 1 + function(i));

        }

       

    }

   

    return contatore;

   

}

int main()

{

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

    int risultato = 1;

    int appoggio = 0;

    cin >> n;

    //riempimento del vettore in input

    for (int i = 0; i < n; i++)

    {

        cin >> appoggio;

        v.push_back(appoggio);

        appoggio = 0;

    }

    //richiamo la funzione

    for (int j = 0; j < n; j++)

    {

        risultato = max(risultato, function(j));

        contatore = 1;

    }

   

    //stamp il rislutato

    cout << risultato;

    return 0;

}

```

---

<div class="post-metadata">

**Author:** ![samuelemusiani](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/d9b06d/32.png) [@samuelemusiani](https://forum.olinfo.it/u/samuelemusiani)\
**Post date:** [25 Novembre 2021, 11:06pm UTC](https://forum.olinfo.it/t/dieta-di-poldo-ricorsione/6807/2 "2021-11-25T23:06:52Z")

</div>

Ciao @flp_o3,  
Non sono la persona più qualificata del mondo nel spigare programmazione dinamica, di conseguenza se cometto qualche imprecisione spero che qualcuno più abile in questo campo possa coreggermi!

Per il resto questo messaggio sarà diviso in tre parti:

- **Nella prima** cercherò di spiegarti come mai il tuo codice non funziona e ti farò vedere il codice funzionanente che riprende la tua idea di risoluzione.
- **Nella seconda** ti mostrerò la soluzione a mio avviso più semplice per risolvere questo problema nel modo corretto senza uscire dai limiti di tempo.
- **Nella terza** invece ci saranno dei piccoli trucchetti e corezzioni di alcuni errori presenti nel tuo codice che spero possano esserti utili in futuro

**Prima parte:**

L’ide di base è che esiste una fuzione f(k) tale che, quando calcolata, resituisce il valore della sequenza più lunga che si ferma nella posizione k dell’array. Di conseguenza, per trovare la soluzione al problema, è sufficiente iterare su tutti gli elementi dell’array per trovare la sequenza più lunga in generale. Cioe:

soluzione = \max\_{\substack{k = 0 \dots N - 1}} \left(f(k)\right)

**L’idea alla base è giusta** , il problema è che la tua **implementazione è errata**! Il main in generale è abbastanza corretto, ma la funzione _`function`_ che definisci a riga _33_ è sbagliata. Infatti con il _`for`_ a riga _39_ stai richiamando la funzione ricorsivamente, ma **su dei valori che dovrebbe calcolare dopo**. Infatti la funzione non può calcolare le sequenze maggiori che partono da numeri più avanti di k se non ha un modo di recuperare quelle che partono da numeri minori. Inoltre **manca un caso base** per fare in modo che la ricorsione funzioni.

Vediamo come si risolve questo problema ricorsivamente seguengo l’idea indicata sopra:

> La nostra funzione f(k) ci restituisce il valore della sequenza più lunga che termina alla posizione k dell’array. Il caso base in questo caso è f(0) = 1 in quanto se ho un solo elemento l’unica sequenza che posso formare è lunga 1. Per risolvere il problema allora definisco ricorsivamente la funzione in modo tale da poterla costruire da valori “più piccoli” di k: f(k) = \max\left(1, \max\_{\substack{i = 0 \dots k-1 \\ v[i] \< v[k]}} \left(f(i)\right) + 1\right)

In pratica cosa significa la formulona che ho scritto sopra? Che se voglio sapere qual’è la sequenza più lunga che termina in k io devo controllare tutte le sequenze che finisco in posizioni minori di k (i = 0 \dots k-1) che posso prendere (v[i] \< v[k]), e ovviamente prendere la maggiore, sommandoci  
1 essendo l’elemento k compreso nella sequenza che voglio calcolare.

Un esempio di codice che implementa questa soluzione:

> **Soluzione 1**
>
> ```auto
> #include <bits/stdc++.h>
> using namespace std;
> 
> vector<int> v;
> 
> int f(int k) {
> if(k == 0)
> return 1;
> 
> int sol = 1;
>     
> for(int i = k - 1; i >= 0; i--) {
> if(v[i] > v[k])
> sol = max(sol, f(i) + 1);
> }
> 
> return sol;
> }
> 
> int main() {
> freopen("input.txt", "r", stdin);
> freopen("output.txt", "w", stdout);
> 
> //lettura inputs
> 
> int n;
> cin >> n;
> 
> int temp;
> 
> for(int i = 0; i < n; i++) {
> cin >> temp;
> v.push_back(temp);
> }
> 
> //calcolo della soluzione
> 
> int sol = 1;
> 
> for(int i = 0; i < n; i++)
> sol = max(sol, f(i));
> 
> cout << sol;
> 
> return 0;
> }
> 
> ```

Se provi a sottomettere questa soluzione però noterai che il punteggio sarà solo di 35/100, in quanto la ricorsione è troppo lenta. La complessità risulta infatti \mathcal O(2^N) (grazie a @MyK_00L). Vediamo come ottimizzarla!

**Seconda parte:**  
Qui entra in gioco la **programmazione dinamica**! Infatti l’idea della DP (che è la sigla per dynamic programming) sta nel memorizzare i risultati calcolati in modo da non calcolarli vuovamente. Se ci si fa caso infatti, per ogni valore di k, quando si calcola f(k) si ricalcolano da capo tutti i valori di f(h) dove h \< k. Basterebbe quindi memorizzare in un vettore i valori di f(k) già calcolati in modo da non rifarlo tutte le volte. Una soluzione potrebbe essere la seguente:

> **Soluzione 2**
>
> ```auto
> #include <bits/stdc++.h>
> using namespace std;
> 
> vector<int> v, valori;
> vector<bool> calculated;
> 
> int f(int k) {
> if(k == 0)
> return 1;
> 
> if(calculated[k])
> return valori[k];
>     
> calculated[k] = true;
> 
> for(int i = k - 1; i >= 0; i--) {
> if(v[i] > v[k])
> valori[k] = max(valori[k], f(i) + 1);
> }
> 
> return valori[k];
> }
> 
> int main() {
> freopen("input.txt", "r", stdin);
> freopen("output.txt", "w", stdout);
> 
> //lettura inputs
> 
> int n;
> cin >> n;
> 
> int temp;
> 
> for(int i = 0; i < n; i++) {
> cin >> temp;
> v.push_back(temp);
> valori.push_back(1);
> calculated.push_back(false);
> }
> 
> //calcolo della soluzione
> 
> int res = 1;
> 
> for(int i = 0; i < n; i++)
> res = max(res, f(i));
> 
> cout << res;
> 
> return 0;
> }
> 
> ```

L’array _`valori`_ serve per **memorizzare** i valori di f(k) in modo da non ricalcolarli tutte le volte, e lo si inizializza a 1 in quanto ogni sequenza è formata da almeno un elemento. Inoltre l’array _`calculated`_ è un **vettore di booleane** (cioè ogni cella dell’array può assumere solo due valori, _vero_ o _falso_) che tiene traccia dei valori già calcolati. Dentro la funzione _`f`_ bisogna solo controllare, prima di inziare a fare tutti i calcoli, che il valore cercato non sia già stato calcolato in precedeza (`if(calculated[k])`), e in caso positivo si returni semplicmente il valore (`return valori[k]`).

Con questi accorgimenti si arriva ad un 100/100 e ad una complessità di \mathcal O(N^2), quindi il problema potrebbe essere finito qui…e invece no!

Infatti molti problemi di DP sono **facili da pensare ricorsivamente** , ma **più veloci e più comodi da implementare iterativamente**. Ti lascio di seguito la soluzione senza l’utilizzo della ricorsione, se hai qualche dubbio scrivi pure che ti spiego come funziona, perché ti sarà sicuramente utile per problemi futuri!

> **Soluzione 3**
>
> ```auto
> #include <bits/stdc++.h>
> using namespace std;
> 
> int main() {
> freopen("input.txt", "r", stdin);
> freopen("output.txt", "w", stdout);
> 
> ios::sync_with_stdio(0);
> cin.tie(0);
> cout.tie(0);
> 
> int N;
> cin >> N;
> 
> vector<int> v(N);
> 
> for(int i = 0; i < N; i++) cin >> v[i];
> 
> vector<int> sol(N, 1);
> 
> for(int j = 1; j < N; j++) {
> for(int i = 0; i < j; i++) {
> if(v[j] < v[i])
> sol[j] = max(sol[j], sol[i] + 1);
> }
> }
> 
> cout << *max_element(sol.begin(), sol.end());
> 
> return 0;
> }
> 
> ```

Esistono [soluzioni](https://cp-algorithms.com/sequences/longest_increasing_subsequence.html) ancora più effcienti che hanno complessità \mathcal O(NlogN). Ma sono assolutamente esagerate per questo problema.

**Terza parte:**  
Siamo finalmente giunti alla parte conclusiva di questo lunghissimo messaggio dove ti lascio **alcuni suggerimenti e trucchi** che ti potrebbero essere utili in generale per scrivere codice più veloce ed efficiente:

1. Al posto di includere tante librerie diverse scrivi semplicemente `#include <bits/stdc++.h>` e hai tutto quello che ti serve

2. La funzione max è già implementata in C++, non ti serve scriverla tutte le volte da capo

3. Chiamare una funzione _`function`_ non è il massimo, in quanto il nome risulta ambiguo ad alcuni editor e compilatori. Dai nomi brevi, significativi e poco ambigui

4. Generalmente avere variabili globali che si modificano dentro a funzioni ricorsive è molto rischioso, cioè devi essere molto bravo e sapere costa stai facendo per usarle bene (la tua variabile _`contatore`_). Io personalmente ti sconsiglio di usarle se sei alle prime armi

5. Attento alle dichiarazioni dei for. Nella tua funzione _`function`_ dichiari `i = k + 1`, ma se poi chiami la tua funzione con il parametro `k = n - 1`, `i` diventerà uguale ad `n` e si andranno a fare dei casini con gli indici dei vettori

6. Quando prendi in input un vettore un usare `push_back`. Infatti anche se sulla [wiki](https://en.cppreference.com/w/cpp/container/vector/push_back) c’è scritto che ha un tempo costante non è proprio vero, ed è abbastanza lento qando i numeri diventano tanti. Piuttosto dichiara inizialmente la grandezza del vettore (tanto la sai sempre visto che hai `N`) e successivamente utilizza un semplice `cin >> v[i]`. Se il vettore è globale e si dichiara prima che tu prenda in input `N`, allora puoi semplicemente ridimensionarlo appena hai il numero di elementi che contiene con `v.resize(N)`.  
Come suggerisce @MyK_00L puoi anche scrivere `for(int &i:v)cin>>i`. Vedi te cosa preferisci

7. Se aggiungi queste tre istruzioni al tuo programma prenderà gli input più velocemente: `ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);`

8. È inutile ri-inizializzare una variabile a zero se poi la prendi in input (riga 87 del tuo programma).

9. Evita di utilizzare così tanti spazi tra un’istruzione e un altra, rende il codice molto dispersivo e difficile da leggere

Per il resto dovrei averti detto tutto quello che potevo. Se hai qualche domanda falla pure senza problemi (soprattuto se non hai capito qualcosa della spiegazione).

---

<div class="post-metadata">

**Author:** ![MyK\_00L](https://forum.olinfo.it/user_avatar/forum.olinfo.it/myk_00l/32/3000_2.png) [@MyK\_00L](https://forum.olinfo.it/u/MyK_00L)\
**Post date:** [26 Novembre 2021, 1:06pm UTC](https://forum.olinfo.it/t/dieta-di-poldo-ricorsione/6807/3 "2021-11-26T13:06:43Z")

</div>

La complessita’ della prima soluzione dovrebbe essere \mathcal{O}(2^n) (edited, me dumb), ma aggiungedo una memo a quella funzione diventa \mathcal{O}(n^2)  
Comunque esistono diverse soluzioni simili a quelle proposte per questo problema in \mathcal{O}(n \cdot log{n}) (se nella prima soluzione al posto di fare una ricerca lineare del massimo si usa una struttura dati tipo fenwick tree, assume questa complessita’ (obv a quel punto la implementi iterativa tho), oppure c’e’ anche una soluzione con binary search).  
random side note: push\_back e’ costante amortizzato, di fatto puoi considerarlo costante, ma tanto fai prima a scrivere

```auto
vector<int> v(n);
for(int &i:v)cin>>i;

```

che e’ piu veloce

---

<div class="post-metadata">

**Author:** ![flp\_o3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/f9ae1b/32.png) [@flp\_o3](https://forum.olinfo.it/u/flp_o3)\
**Post date:** [26 Novembre 2021, 5:27pm UTC](https://forum.olinfo.it/t/dieta-di-poldo-ricorsione/6807/4 "2021-11-26T17:27:28Z")

</div>

ciao samuele, intanto grazie mille per l’aiuto!  
Ho capito dove sbaglaivo però volevo farti qualche domanda.  
Capisco quello che hai scritto nella parte due della risposta ma non capisco perchè sia necessario l’array di booleani, dato che siamo sicuri che le sequenze che terminano con i valori precedenti alla k siano già stati calcolati, o sbaglio? Infatti io ho riscritto la funzione però ho inserito direttamente un array contenente i risultati della funzione per ogni valore di k e in teoria dovrebbe funzionare. Il problema è che quando lo sottopongo sul portale di allenamento prendo 55/100. Questo però probabilmente perchè il tempo di compilazione viene 2.5 secondi, ma non capisco perchè così tanto.  
e infine ti volevo chiedere anche come evitare di dichiarare la variabile “contatore” globale, dato che non penso sia corretto dichiararla nella funzione nel caso sia ricorsiva, dato che così facendo si dichiarerebbe ad ogni ricorsione.

```auto
#include <bits/stdc++.h>

using namespace std;

int v[3000];

int appoggio[3000];

int n;

int contatore = 1;

int SeriePanini (int k)

{

    if (k == 0)

    {

        return 1;

    }

    for (int i = k; i > 0; i--)

    {

        if (v[i] > v[k])

        {

            contatore = max(contatore, 1 + appoggio[i]);

        }

    }

    return contatore;

}

int main()

{

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

    int risultato = 1;

    cin >> n;

    //riempimento del vettore in input

    for (int i = 0; i < n; i++)

    {

        cin >> v[i];

    }

    //richiamo la funzione

    for (int j = 0; j < n; j++)

    {

        appoggio[j] = SeriePanini(j);

        contatore = 1;

    }

    //stamp il rislutato

    for (int a = 0; a < n; a++)

    {

        risultato = max(risultato, appoggio[a]);

    }

    cout << risultato;

    return 0;

}

```

---

<div class="post-metadata">

**Author:** ![samuelemusiani](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/d9b06d/32.png) [@samuelemusiani](https://forum.olinfo.it/u/samuelemusiani)\
**Post date:** [26 Novembre 2021, 8:53pm UTC](https://forum.olinfo.it/t/dieta-di-poldo-ricorsione/6807/5 "2021-11-26T20:53:56Z")

</div>

Ciao @flp_o3,  
Il tuo codice è **praticamente giusto**! Bisogna solo modificare 3 cose che probabilente ti sei dimenticato di aggiungere oppure proprio non ci hai fatto caso:

1. Nel testo del problema è sempre indicata la **grandezza massima dell’input**. E se controlli il testo dice che n (la quantità di numeri in input) è sempre minore o uguale a 1000. Di conseguenza se dichiari i tuoi due array con una grandezza massima di 3000 non riuscirai a contenere tutti i numeri che ti vengono dati nei vari testcase!
2. Nella tua funzione ricorsiva la variabile i parte da k, ma questo concettualemente è sbagliato in quanto tu devi controllare **solo le sequenze prima della posizione** k, e non k stessa visto che la stai calcolando.
3. Nella condizione del for hai messo i \> 0. Errore piuttosto comune visto che non si è abituati a scrivere for al cotrario. Ma in questo modo la sequenza che parte a posizione 0 non la controlli mai visto che la i si ferma a 1.

Fatti questi piccoli aggiustamenti il tuo programma prende un soddisfacente 100/100!

> **Codice corretto**
>
> ```auto
> #include <bits/stdc++.h>
> 
> using namespace std;
> 
> int v[10001];
> 
> int appoggio[10001];
> 
> int n;
> 
> int contatore = 1;
> 
> int SeriePanini (int k)
> 
> {
> 
> if (k == 0)
> 
> {
> 
> return 1;
> 
> }
> 
> for (int i = k - 1; i >= 0; i--)
> 
> {
> 
> if (v[i] > v[k])
> 
> {
> 
> contatore = max(contatore, 1 + appoggio[i]);
> 
> }
> 
> }
> 
> return contatore;
> 
> }
> 
> int main()
> 
> {
> 
> freopen("input.txt", "r", stdin);
> 
> freopen("output.txt", "w", stdout);
> 
> int risultato = 1;
> 
> cin >> n;
> 
> //riempimento del vettore in input
> 
> for (int i = 0; i < n; i++)
> 
> {
> 
> cin >> v[i];
> 
> }
> 
> //richiamo la funzione
> 
> for (int j = 0; j < n; j++)
> 
> {
> 
> appoggio[j] = SeriePanini(j);
> 
> contatore = 1;
> 
> }
> 
> //stamp il rislutato
> 
> for (int a = 0; a < n; a++)
> 
> {
> 
> risultato = max(risultato, appoggio[a]);
> 
> }
> 
> cout << risultato;
> 
> return 0;
> 
> }
> 
> ```

Per le domande:

1. Hai ragione, **l’array di booleani è inutile**! Abbiamo già sicuramente calcolato tutti i valori precedenti visto che il for che calcola i valori della fuzione parte da 0. Se però partisse dal fondo dell’array e cioè da N - 1 in quel caso allora servirebbe.
2. Il **tempo di compilazione** è **totalmente ininfluente** sull’assegnazione del punteggio!
3. In realtà **è corretto dichiarare la varibiale “contatore” dentro la funzione** in quanto globalmente non ti serve a nulla. Quella variabile viene usata soltanto dentro quella funzione, quindi è molto più “pulito” farla rimanere interna. Non importa se si ridichiara ad ogni ricorsione, in quanto le dichiarazioni non si andrebbero a sommare visto che ogni volta che la funzione termina, quella variabile viene “cancellata” dalla memoria.

Dovrei aver risposto a tutto, ma se hai ancora dubbi scrivi pure!

P.S. Il tuo programma, scritto in questo modo e con l’ausilio dell’array per memorizzare, non è più ricorsivo ma è diventato iterativo! Non so se te ne sei accorto…

---

<div class="post-metadata">

**Author:** ![flp\_o3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/f9ae1b/32.png) [@flp\_o3](https://forum.olinfo.it/u/flp_o3)\
**Post date:** [27 Novembre 2021, 3:56pm UTC](https://forum.olinfo.it/t/dieta-di-poldo-ricorsione/6807/6 "2021-11-27T15:56:12Z")

</div>

ciao @samuelemusiani ho corretto tutto e adesso è 100/100!  
Grazie mille, non solo per l’aiuto per la risoluzione del problema, ma anche per tutti i consigli generali sulla programmazione. Mi hai fatto capire molte cose che finora nessuno mi aveva spiegato. Grazie davvero tanto per la disponibilità.