Tehnica BACKTRACKING - teorie si exemple (The backtracking technique - theory and examples)

Rezolvarea, in limbajul C++, a problemelor:
Permutari
#1281 Regine1
#196 Aranjamente
#197 Combinari
Mediul de programare Code Blocks

Solving in C++ the problems:
Permutations
#1281 Queens 1
#196 Arrangements
#197 Combinations
The CodeBlocks programming environment

[ShadowHeroo]

Un video excepțional, in sfârșit am înțeles backtracking asa cum trebuie, mulțumesc! 😎🙏

[ameliastefania]

Multumesc mult, chiar ati reusit sa ma faceti sa inteleg cum n-au reusit multi profi!! Explicarea pas cu pas babeste si apoi pe implementarea algoritmica sunt cele mai bune variante prin care sa intelegi cod si ma bucur ca ati procedat intocmai!

[silviudinca]

Un video foarte bine explicat . Asta inseamna pana la urma informatica, stai si gandesti pas cu pas ce ai de facut si abia dupa scrii cod . Felicitari pentru acest canal si aceste videoclipuri .Mi-ar placea sa faceti si un videoclip despre programare dinamica .

[lia_dilia]

Ai un stil foarte frumos de a explica. Iti recomand sa faci si variante in limba engleza. Cred ca ar avea mare succes. Ai si dictie frumoasa si voce clara. Din intamplare am dat peste acest tutorial. De obicei caut i8n Engleza pentru ca resursele sunt mai multe. Dar n-am gasit niciun tutorial asa frumos explicat ca acesta.

[oanaciuca]

Pe aceeasi linie nu se pot afla din constructia stivei. abs(i-k) nu-si are rostul. Oricum k>i. Puneai simplu k-i

[john_ipu]

Pentru Permutari:

int n, k, x[10];

void afisare() //afişarea soluţiei curente
{
for(int i=1; i<=n; i++) cout<<x[i]<<" ";
cout<<endl;
}

int test(int k) //testarea condiţiilor de continuare pentru x[k]
{
for(int i=1; i<k; i++) //dacă elementul curent (x[k]) este egal cu un element generat anterior,
if (x[i]==x[k]) return 0; //valorile din x nu sunt distincte, deci ele nu pot reprezenta o permutare
return 1;
}

int main()
{
cin>>n; //numărul de elemente de permutat
k=1; //se începe generarea cu prima poziţie a vectorului
x[k]=0; //se iniţializează x[k] cu o valoare mai mică cu o unitate decât cea mai mică
//valoare posibilă pentru x[1]

while(k>0) //cât timp nu s-au generat toate soluţiile posibile
{
while (x[k]<n) //cât timp nu s-au încercat toate valorile posibile pentru elementul x[k]
{
x[k]++; //se încearcă următoarea valoare disponibilă

 if (test(k)) //se verifică pentru x[k] îndeplinirea condiţiilor de continuare
if (k==n) afisare(); //dacă x[k] trece testul şi s-au generat toate cele n elemente necesare
//se afişează soluţia obţinută
else
{
k++; //în caz contrar se avansează la elementul următor de generat şi se
x[k]=0; //iniţializează acest element cu o valoare mai mică cu o unitate
} //decât cea mai mică valoare posibilă pentru el
}
k- - ; //dacă pentru x[k] s-au încercat toate valorile posibile, se revine la x[k-1] şi
//se încearcă pentru el o valoare nouă
}
}

[mateimatey]

ai putea sa faci alt video cu backtracming cu metoda recursiva si sa o explici?

[lorinciubeica]

Cum as putea modifica primul cod ca sa fac permutari de litere ale alfabetului?

[MikeyFlorensia]

Foarte folositoare video-urile cu comentarii! Multumesc

[kalytheo]

Backtracking recursiv - generarea permutărilor
#include <iostream>
using namespace std;
int n, st[30], i;
int valid(int k)
{
bool ev=1;
for(int i=1;i<k;i++)
if(st[k]==st[i])
ev=0;
return ev;
}
void afisare()
{
for(int i=1;i<=n;i++)
cout<<st[i]<<" ";
cout<<endl;
}
void back(int k)
{
for(int i=1;i<=n;i++)
{
st[k]=i;
if(valid(k))
if(k==n)
afisare();
else
back(k+1);
}
}
int main()
{
cout << "n=";cin>>n;
back(1);
return 0;
}

[alexlefterie]

Ai putea face un video asemanator pentru programarea dinamica?

[Alex.Geornoiu]

Foarte bun video doar ca nu afiseaza bine codul de la regine

[goldiemusic]

foarte slab, puteam sa citesc din carte ...