Informatică, întrebare adresată de GabiAlex99, 8 ani în urmă

Se dă un număr natural N. Să se afișeze toate șirurile de caractere de lungime N formate din primele 'N' litere mici ale alfabetului care nu au două vocale alăturate, iar fiecare literă apare o singură dată.

Date de intrare
De pe prima linie se va citi numărul N.

Date de ieșire
Pe ecran se vor afișa toate șirurile cu proprietatea cerută, câte un șir pe fiecare linie. Șirurile trebuie afișate în ordine alfabetică

Restricții
1 ≤ N ≤ 9
Exemplu

Date de intrare
4

Date de ieșire
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

Daca se poate, as dori si o explicatie, multumesc!


GabiAlex99: E de pe wellcode. Daca era dp pbinfo puneam si numarul :)) Nu conteaza ca nu ia 100p, ma int rezolvarea (si explicatia daca tot)
GabiAlex99: Ma poti ajuta sa rezolv problema asta ?..
boiustef: dacă învăţ tema Backtracking, da :))) Se pare că e de la această temă, da?
GabiAlex99: Da, este de la aceasta tema :). Dumneavoastra sunteti profesor de informatica?
boiustef: facultate mate în 1974 şi nişte cursuri de formare şi la info prin 1990
boiustef: c++ din apr 2018
GabiAlex99: Am inteles. Ati lucrat in Pascal inainte ? Adica stiu ca acesta se folosea inainte :))
boiustef: da, numai pascal
boiustef: vezi cum lucrează.. :)))
boiustef: am folosit vector de la 1 la n, dar pentru a trece a caractere la număr se adaugă 96, deoarece codul literei "a" este 97, adică 1+96

Răspunsuri la întrebare

Răspuns de boiustef
3

Răspuns:

#include <iostream>

#include <cstring>

#define MAX 10

using namespace std;

int n,v[MAX] ;

int valid(int k);

int solutie(int k);

void afisare(int k);

void BK(int k);

int main()

{cout<<"n= "; cin>>n;

BK(1);

return 0;

}

void BK(int k)

{int i;

for (i=1;i<=n;i++)

{v[k]=i;

if (valid(k))

{if (solutie(k))

afisare(k);

else

BK(k+1);

}

}

}

int valid(int k)

{int i;

char voc[]="aei";

for (i=1;i<=k-1;i++)

if (v[i]==v[k] || (strchr(voc,(char)(v[k]+96)) && strchr(voc,(char(v[k-1]+96)))))

return 0;

return 1;

}

int solutie(int k)

{if (k==n)

return 1;

return 0;

}

void afisare(int k)

{int i;

for (i=1;i<=k;i++)

cout<<(char)(v[i]+96)<<" ";

cout<<endl;

}

Explicație:

parcă e aşa...  este o problemă.. pentru n mai mic ca 5 afişează toate sirurile, dar pentru n mai mare nu se văd toate...  adică nu le văd pe cele generate primele...

Am lăsta la afişare spaţiu între caractere. Dacă vrei, îl ştergi


GabiAlex99: Multumesc ! Ia limita la 1 test, dar nu e problema (probabil ca la n mai mare decat 5??)
http://prntscr.com/nnbhqi
Multumesc oricum, imi e de ajuns :))
boiustef: Depăşire timp?
boiustef: cred tr. de modificat puţin functia vald
boiustef: Încearcă această funcţie valid:
int valid(int k)
{int i;
char voc[]="aei";
if (strchr(voc,(char)(v[k]+96)) && strchr(voc,(char(v[k-1]+96)))) return 0;
else {
for (i=1;i <= k-1;i++)
if (v[i]==v[k])
return 0;}
return 1;
}
boiustef: cred va lucra mai repede...
GabiAlex99: Este la fel.. In fine, nu mai conteaza, lasati asa, imi este de ajuns atat :D. Nu prea vad unde ar putea lua limita de timp sa fiu sincer :))
GabiAlex99: Am inlocuit endl cu "\n" si am luat 100p. Multumesc :)!
boiustef: haha..
Alte întrebări interesante
Matematică, 8 ani în urmă