Divide et impera și backtracking

Metode de programare — divide et impera și backtracking

Aplicarea schemei divide et impera la căutarea binară și la determinarea maximului, cu justificarea numărului de pași.
Descrierea mecanismului de backtracking și generarea permutărilor, aranjamentelor, combinărilor, submulțimilor și produsului cartezian.
Determinarea numărului de soluții și a ordinii în care sunt generate.

Divide et impera împarte problema în subprobleme de același tip, le rezolvă recursiv și combină rezultatele; cazul de bază este intervalul cu un element sau vid.
Căutarea binară cere un tablou ordonat și face de ordinul log2(n) comparații, pentru că la fiecare pas aruncă o jumătate din interval.
Maximul prin înjumătățire face 2 * n - 1 apeluri, deci nu este mai rapid decât parcurgerea; câștigul apare la interclasare, unde combinarea face munca utilă.
Backtracking completează un vector soluție poziție cu poziție, verifică o condiție de continuare și dă înapoi când valorile unei poziții s-au epuizat.
Aceeași schemă generează permutări, aranjamente, combinări, submulțimi și produs cartezian; se schimbă doar mulțimea valorilor și condiția.
Dacă valorile se încearcă crescător, soluțiile apar în ordine lexicografică.
Numerele de soluții sunt n!, n! / (n - k)!, n! / (k! * (n - k)!), 2^n și n1 * n2 * … * nk.