Problema #3158 numere123
Cerința
Se citește un număr natural n având cifrele diferite două câte două. Afișați in ordine crescătoare numerele care se pot obține din cifrele lui n și care au același număr de cifre ca n.
Date de intrare
Programul citește de la tastatură numărul n.
Date de ieșire
Programul va afișa pe ecran numerele cerute, câte unul pe fiecare rând.
Restricții și precizări
1 ≤ n ≤ 1.000.000.000
n are cifrele distincte
Exemplu
Intrare
483
Ieșire
348
384
438
483
834
843
PS:Cu metoda backtracking
Răspunsuri la întrebare
Răspuns:
#include <iostream>
using namespace std;
//in 'rezultat' se formeaza numarul
//in 'cifre' sunt cifrele numarului 'n'
//x este un index folosit pentru a itera in liste
int rezultat[10], cifre[10], n, x=0;
//in functia asta se desface numarul 'n' in cifre
void din_numar_in_cifre(int n)
{
int i = 0;
while(n > 0)
{
cifre[i++] = (n - ((n / 10) * 10));
n /= 10;
x++;
}
}
//afiseaza rezultatul
void arata()
{
for(int i=1; i<=x; i++)
{
cout << rezultat[i];
}
cout << endl;
}
//verifica daca se repeta o cifra in 'rezultat'
//daca se repeta returneaza 0 (FALS), daca nu returneaza 1 (ADEVARAT)
int valid(int k)
{
for(int i=1; i<k; i++)
{
if(rezultat[k] == rezultat[i])
{
return(0);
}
}
return(1);
}
//aici sunt introduse si/sau comutate cifrele in 'rezultat'
//'k' este un index folosit pentru a itera lista
//si pentru a opri bucla cand s-a format numarul care ne intereseaza
//adica daca in 'rezultat' avem un numar format din acelasi numar de cifre ca
//si in 'cifre' si nu se repeta nici unul.
//ca sa iti explic cum functioneaza functia 'backtrack' o sa imi ia ceva timp,
//asa ca o sa scriu pe scutr:
//la prima apelare cand ajunge la 'backtrack(k+1)' nu se "autoapeleaza";
//in schimb apeleaza o "copie" a functiei 'backtrack()' s.a.m.d.
//sa presupunem ca functia a terminat cu 'copia backtrack', in momentul asta
//se intoarce la 'backtrack()' si continua daca este cazul daca nu se intoarce la
//'backtrack()' precedent s.a.m.d.
void backtrack(int k)
{
for(int i=0; i<x; i++)
{
rezultat[k] = cifre[i];
if(valid(k))
{
if(k == x)
{
arata();
}
else
{
backtrack(k+1);
}
}
}
}
int main()
{
din_numar_in_cifre(542);
backtrack(1);
return(0);
}