Il modo migliore per gestire Floors e Ceiling quando si utilizza il metodo di sostituzione per risolvere le ricorrenze

Question

Il modo migliore per gestire Floors e Ceiling quando si utilizza il metodo di sostituzione per risolvere le ricorrenze

#1 da (1 voti)

5

Attualmente sto usando un metodo di sostituzione per risolvere le recidive. Il problema che sto avendo riguarda T (n) che ha o soffitti o pavimenti. Ad esempio nel seguente esempio vedi l'esempio qui .

Finiscono per usare l'ipotesi: T(n) ≧ c(n+2) lg(n+2)

La mia prima ipotesi è stata T(n) ≧ n lg(n) , che risulta non funzionare, ma il mio problema è finire con il dover indovinare per provare a far funzionare uno. Quindi le domande sono le seguenti:

Qual è il modo migliore per gestire questi piani e il soffitto in generale?
Per quanto riguarda le ipotesi, questo viene con la pratica o ci sono migliori modi per dedurre la corretta ipotesi dal primo colpo senza dover usare gli alberi di ricorsione.

(PS non so come scrivere equazioni in notazione matematica, è la mia prima volta che uso questo forum)

recursion

posta user481610 27.08.2014 - 21:55

fonte

1 risposta

Leggi altre domande sui tag recursion

Coping con i requisiti degli ordini di build nei build automatici In una rete di mutuo, come programmeresti un giubileo automatico?

score 1 · Answer 1

Nel tentativo di rispondere alla domanda 2, vorrei citare il seguente

Ultimately, there is only one fail-safe method to solve any recurrence:

Guess the answer, and then prove it correct by induction.

Controlla il seguente link: link . Descrive le tecniche per genera supposizioni che sono garantite per essere corrette, a patto che le utilizzi correttamente. È stato qualche tempo fa che ho fatto qualcosa in questo senso, ma penso anche che seguire un processo in un libro come suggerito da Andrew sia la soluzione migliore dal momento che non è qualcosa che può essere rapidamente descritto in un post sul forum.