Salut! Ma puteti ajuta va rog la aceasta problema? Clasa a 11-a la backtracking. As avea nevoie de cod complet si explicatii (de ce am utilizat var sau de ce am facut operatia asta). Multumesc anticipat!
1)Realizaţi un program care generează combinaţii de n cifre 0 şi 1 cu proprietatea că în orice grup de 3 cifre consecutive există cel puţin o cifră de 1. De exemplu, dacă n=4, se afişează combinaţiile: 0010, 0011, 0100, 0101, 0110, 0111, 1001, 1010, 1011, 1100, 1101, 1110, 1111.
Răspunsuri la întrebare
#include <cstring>
#include <iostream>
using namespace std;
char v[100]; // Vectorul solutie
int nr; //Numarul de cifre
bool valid(int x){
//Functie care verifica daca exista cel putin un 1 in ultimele 3 cifre
for(int i=1;i<=x-2;i++){
if(v[i]!='1' && v[i+1]!='1' && v[i+2]!='1') return false;
}
return true;
}
void afisare(){
//Functie pentru afisarea solutiei
for(int i=1; i<=nr; i++){
cout << v[i];
}
cout << endl;
}
void bkt(int n){
//Functie principala backtracking
//Pentru 0
v[n]='0';
//Daca este valid
if(valid(n)){
//Daca avem numarul de pozitii afiseaza
if(n>=nr) afisare();
//Altfel treci la pozitia urmatoare
else bkt(n+1);
}
//Pentru 0
v[n]='1';
//Daca este valid
if(valid(n)){
//Daca avem numarul de pozitii afiseaza
if(n>=nr) afisare();
//Altfel treci la pozitia urmatoare
else bkt(n+1);
}
}
int main(){
//Citim numarul de cifre
cin >> nr;
//Apelam funtia responsabila de backtracking
bkt(1);
}