Soluzioni ottimizzate per i miei compiti

Una lumaca si insinua x un muro durante il giorno. Dopo tutto il lavoro che fa durante il giorno, si ferma a riposare un po '... ma si addormenta !! La mattina dopo si sveglia e scopre che è scivolata giù durante la notte.Soluzioni ottimizzate per i miei compiti

Se questo accade ogni giorno, quante volte la lumaca si insinua per coprire n muri di diversa altezza?

Ho scritto una funzione per contare il numero di brividi della lumaca come illustrato di seguito:

void count(int move_forward, int move_backward, int number_walls, int[] height) 
    { 
     int count = number_walls, diff = move_forward - move_backward; 
     while (number_walls--) 
      for (move_backward = move_forward; move_backward < height[number_walls]; move_backward += diff) 
       count++; 
    }

Sta funzionando bene. Ma volevo sapere se esiste un altro modo per risolvere questo problema per ottimizzare ulteriormente la velocità del programma.

fonte

2011-09-25 iJade

(height-x)/(x-y) +1, nessun loop richiesto – amit

@Jay, BTW - Il consiglio che hai ricevuto nella prima domanda sull'uso di nomi di variabili significative è discutibile nel contesto dei loop interni. Troppi nomi troppo lunghi rendono il tuo codice tanto illeggibile quanto una serie di nomi criptici di una e due lettere. È tutto sull'equilibrio. – dmckee

Ancora un commento finché mi sto conficcando il naso. Il punto di questo esercizio potrebbe essere quello di mostrarti quel po 'seduto e pensare per un po' che puoi il problema dei singoli muri da "O (altezza)" (il come lo stavate provando) a 'O (1)' (il modo in cui amit lo risolve). – dmckee

soluzione è ((height-x)/(x-y))+1, nessun loop richiesto.

la lumaca ha bisogno di salire a: height-x, e ci vuole ((height-x)/(x-y)) giorni. Una volta lì, gli ci vuole un giorno in più per scalare la x rimanente.

EDIT: come accennato nei commenti, questa soluzione risolve il problema per ogni parete, avrete bisogno di iterare il vostro heights array, e riassumere questi risultati, consentendo di risparmiare almeno il ciclo interno, rendendolo O (n), invece O (n * h), dove n è il numero di muri, e h sono le altezze delle pareti.

(*) nota: è possibile che si desideri salvare il promemoria per ciascun muro [vale a dire quanto la lumaca può continuare a camminare dopo aver superato questo muro] e sottrarla dal muro successivo, dipende dalla descrizione del compito ... Se la chiocciola può superare un massimo di un muro al giorno, ignorare quest'ultimo commento.

fonte

2011-09-25 14:48:55 amit

verrà elaborato il downvoter? – amit

Non sono il downvoter, ma immagino sia perché l'altezza è una serie di valori. Avrai comunque bisogno di un loop per ottenere l'altezza totale o applicare la soluzione ad ogni altezza. – tinman

@tinman: sei corretto, questa risposta mostra come farlo per un singolo muro, lo menzionerò esplicitamente. grazie per il commento. – amit

Soluzioni ottimizzate per i miei compiti

risposta

Problemi correlati