Question

Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 9 ca
sumă a cel puţin două numere naturale nenule distincte. Termenii descompunerii sunt în
ordine strict crescătoare. Soluţiile se generează în ordinea: 1+2+6, 1+3+5, 1+8,
2+3+4, 2+7, 3+6 şi 4+5. Se aplică exact aceeaşi metodă pentru scrierea lui 12. Scrieţi
în ordine toate soluţiile de forma 3+...?

Answer 1

Pentru generarea tuturor soluțiilor în care numărul 9 este scris ca sumă a cel puțin două numere naturale nenule distincte, în ordine strict crescătoare, se poate utiliza metoda backtracking. Aceasta începe cu un termen de bază (de exemplu, 1) și adaugă termeni suplimentari până când suma se apropie sau atinge numărul 9. Dacă suma depășește 9, atunci se încearcă un alt termen. Dacă suma este 9, atunci se înregistrează această soluție.

Soluțiile pentru numărul 9 sunt: 1 + 2 + 6, 1 + 3 + 5, 1 + 8, 2 + 3 + 4, 2 + 7, 3 + 6, 4 + 5.

Pentru numărul 12, soluțiile sunt: 1 + 2 + 3 + 6, 1 + 2 + 4 + 5, 1 + 3 + 4 + 4, 1 + 11, 2 + 2 + 8, 2 + 3 + 7, 2 + 10, 3 + 9, 4 + 8, 5 + 7.

Pentru soluțiile de forma 3 + ..., acestea sunt: 3 + 6, 3 + 9.