[ALGORITMI] Esercizio

[stefanaimon1]

Ciao a tutti, mi sono trovato avanti questo problema:

Una societa’ elettrica vuole piazzare dei lampioni lungo un viale rettilineo dove sono situate
delle villette, in modo da illuminare tutte le villette. Ogni lampione riesce ad illuminare tutta la
zona compresa nel raggio di 50 metri. Siano {v1, v2, · · · , vn} le villette e per ogni i = 1, · · · , n−1,
d(i,i+1) la distanza della viletta v i da vi+1.

a) Descrivere ed analizzare un algoritmo che presi in input i valori di,i+1 restituisca il numero
minimo di lampioni necessari per illuminare tutte le villette.

ho pensato di risolverlo in questo modo, ma in verita credo di non aver applicato nessuna tecnica di creazione di algoritmi se non un lontano greedy, che ne pensate?

somma=0;
count=0;
for i=1 to n-1{
   somma+=d(i,i+1)
    if(somma==50){
        count++;
        somma=0
     }
   else if(somma>50){
        count+=(somma-(somma%50))/50;
        somma=(somma%50);
     }
}

[onlyReferee]

Ciao stefanaimon
Secondo me il codice presente nel ciclo interno del for può essere riscritto in maniera molto più semplice. L'idea che sta alla base di tutto per minimizzare il numero di pali necessari a mio parere è quella di piazzare un palo ogni sul tratto rettilineo da coprire non appena ci si accorge che la somma totale delle distanze tra le villette analizzate finora è maggiore o uguale ad un multiplo di 50. Possiamo fare l'ipotesi che sicuramente almeno un palo verrà piazzato lungo il tratto pertanto il nostro conteggio può partire tranquillamente da 1.
A livello di codice l'unico controllo che dobbiamo fare per poter incrementare il numero di pali necessari è vedere se $\text{somma}$ $/$ $50$ è uguale a $\text{count} + 1$.
Dimmi cosa ne pensi.

[stefanaimon1]

Grazie ho semplificato il corpo del for
quindi posso costruire un algoritmo in questo modo senza utilizzare una tecnica precisa?

[onlyReferee]

In realtà questo è un caso particolarmente semplice di programmazione dinamica, nella fattispecie di problema di soddisfacimento dei vincoli, per cui vi sarebbero numerose tecniche apposite. Il paradigma della programmazione logica come approccio per risolvere questo problema (ed in generale molti problemi di soddisfacimento di vincoli) è solitamente quello più adatto ma, come premesso, essendo un caso particolarmente semplice e particolare la programmazione imperativa si adatta meglio in quanto aumenta la leggibilità del codice e richiede meno memoria in fase di esecuzione.

[stefanaimon1]

Grazie mille per le spiegazioni