Utilizând metoda backtracking se generează toate modalitățile de a scrie numărul 9 ca sumă de numere naturale prime. Termenii fiecărei sume sunt în ordine crescătoare. Cele patru soluții sunt obținute în această ordine: 2+2+2+3; 2+2+5; 2+7; 3+3+3.
Aplicând același algoritm, scrieti numai ultimele 2 solutii generate pentru n=15.Scrieti solutiile la fel ca in exemplul prezentat(solutiile se termina cu ; iar intre solutii se pune un singur spatiu).
Răspunsuri la întrebare
#include <iostream>
using namespace std;
// Functie care verifica daca un numar este prim
bool is_prime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// Functie care genereaza toate modalitatile de a scrie numarul 15 ca suma
// de numere naturale prime, folosind metoda backtracking
void generate_sums(int target, int current_sum, int* current_numbers, int current_numbers_size) {
// Daca suma curenta este mai mare decat 15, nu mai este nevoie
// sa continuam procesul de generare a combinatiilor
if (current_sum > target) {
return;
}
// Daca suma curenta este 15, inseamna ca am gasit o solutie
// valida si putem afisa lista de numere prime curenta
if (current_sum == target) {
for (int i = 0; i < current_numbers_size; i++) {
cout << current_numbers[i] << " ";
}
cout << "; ";
return;
}
// Daca suma curenta nu este nici mai mare decat 15, nici egala cu 15,
// inseamna ca putem incerca sa adaugam un nou numar prim la lista
// de numere curente si sa continuam procesul de generare a combinatiilor
for (int i = current_numbers[current_numbers_size - 1] + 1; i <= target; i++) {
if (is_prime(i)) {
current_numbers[current_numbers_size] = i;
generate_sums(target, current_sum + i, current_numbers, current_numbers_size + 1);
}
}
}
int main() {
int current_numbers[15];
current_numbers[0] = 0;
// Generam toate modalitatile de a scrie numarul 15 ca suma de numere
// naturale prime
generate_sums(15, 0, current_numbers, 1);
return 0;
}