Salut! Ma puteti ajuta va rog la aceste 3 probleme? Sunt de clasa a 11-a la backtracking. As avea nevoie la fiecare de cod complet si explicatii (de ce am utilizat var sau de ce am facut operatia asta). Multumesc anticipat!
1) Scrieţi programul care generează şi numără câte cuvinte de cinci litere ale alfabetului englez se pot forma, cu condiţia să nu existe două consoane alăturate şi nici două vocale alăturate.
2) 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.
3) Dintr-un grup de n persoane, dintre care p femei, trebuie formată o delegaţie de k persoane, din care l femei. Să se precizeze toate delegaţiile care se pot forma.
Răspunsuri la întrebare
#include <cstring>
#include <iostream>
using namespace std;
char v[6]; // Vectorul solutie
int contor=0; //Contorizeaza nr de solutii
bool vocala(char x){
//Returneaza TRUE daca x este vocala; returneaza false daca e consoana
return strchr("aeiou", x);
}
bool valid(int n){
//Functie care verifica daca literele consecutive sunt valide
//Daca vectorul are un element nu putem compara cu elementul anterior; deci e valid.
if(n==1) return true;
//Daca avem doua vocale / consoane alaturate aceasta solutie nu e valida.
if(vocala(v[n]) == vocala(v[n-1])) return false;
return true;
}
void afisare(){
//Functie pentru afisarea solutiei
for(int i=1; i<=5; i++){
cout << v[i];
}
cout << endl;
//Incrementeaza nr de solutia
contor++;
}
void bkt(int n){
//Functie principala backtracking
//Itereaza fiecare litera
for(int i='a';i<='z';i++){
v[n] = i;
//Verifica daca pana aici solutia e valida
if(valid(n)){
//Verifica daca avem solutie completa (5 litere). Daca da afiseaza, daca nu treci la pozitia urmatoare
if(n==5) afisare();
else bkt(n+1);
}
}
}
int main(){
//Apelam funtia responsabila de backtracking
bkt(1);
//Afisam numarul de solutii
cout << contor;
}
Ar trebui precizat faptul ca numarul de solutii este imens (286650 de solutii mai exact), o sa dureze putin pana cand programul se executa complet.
Pentru celelalte probleme adauga te rog intrebare separata si voi incerca sa iti raspund.