Question

Pbinfo 3146
Laurențiu este un copil pasionat de teoria numerelor, dar și de informatică. Astfel, în timp ce își savura limonada după o zi obositoare de scoală alături de prietenii săi, acestuia i-a venit în minte o problemă interesantă: dându-se un șir de n numere naturale, sortați-l descrescător după numărul de cifre distincte, la număr de cifre distincte egal sortați-l crescător după suma cifrelor, la suma cifrelor egală sortați-l crescător după produsul cifrelor, iar dacă și produsul cifrelor este egal, atunci numerele se vor sorta crescător după valorile lor.

Exemplu
sort4.în
5
111 19 223 51 37

sort4.out
51 223 19 37 111

Imi poate verifica cineva algoritmul, va rog? Mie imi afiseaza 51 223 37 19 111 si nu stiu de ce :(


#include
#include



using namespace std;

int cif( int x )
{
int k=0;
while ( x )
{
if ( x%10!=(x/10)%10 ) k++;
x=x/10;
}
return k;
}

int sum(int x )
{
int s=0;
while ( x )
{
s=s+x%10;
x=x/10;
}
return s;
}

int produs(int x )
{
int p=1;
while ( x )
{
p=p*x%10;
x=x/10;
}
return p;
}

int main()
{
ifstream f ("sort4.in");
ofstream g ("sotr4.out");
int n, i, j, v[10000];
f >> n;
for ( i=1;i<=n;i++ )
f >> v[i];

for ( i=1;i for ( j=i+1;j<=n;j++ )
{
if ( cif(v[i])
{
int aux=v[i];
v[i]=v[j];
v[j]=aux;
}
else
if ( cif(v[i])==cif(v[j]) )
{
if ( sum(v[i])>sum(v[j]) )
{
int aux=v[i];
v[i]=v[j];
v[j]=aux;
}
else
if ( sum(v[i])==sum(v[j]) )
if ( produs(v[i])>produs(v[j]) )
{
int aux=v[i];
v[i]=v[j];
v[j]=aux;
}
else if ( produs(v[i])==produs(v[j]) )
if ( v[i]>v[j] )
{
int aux=v[i];
v[i]=v[j];
v[j]=aux;
}

}

}
for ( i=1;i<=n;i++ )
g << v[i] << " ";
g.close();
f.close();
return 0;
}

Answer 1

Răspuns:

Explicație:

Codul tau are doua probleme.

1. functia cif nu e corecta decat in cazul in care cifrele identice sunt pe pozitii consecutive.

Sugestie: sorteaza numarul crescator sau descrescator (dupa cifre) la inceputul functiei.

2. sortarea ta e haotica in sensul in care la o parcurgere a celui de-al doilea for se poate alege un numar de interschimbat pe criterii diferite.

Sugestie: sorteaza intai descrescator dupa cif() tot vectorul.

Apoi sorteaza crescator dupa sum() gruparile de elemente din vector cu acelasi cif.

Apoi sorteaza crescator dupa produs() gruparile cu acelasi cif si acelasi sum.

Apoi sorteaza crescator dupa valoare tot ce are acelasi sum, cif si produs.

Pentru cele 4 sortari propun sa folosesti sortari de tip Insertion sau Selection.

Sugestie de implementare: foloseste un vector auxiliar cu acelasi numar de elemente ca si vectorul initial si pune 0 pe fiecare pozitie.

dupa o sortare, schimba 0 cu 1 pe pozitiile cu cif unic.

adica,

ai 111 19 223 51 37 si 0 0 0 0 0

dupa o sortare dupa cif, vei avea 19  223 51 37 111 si 0 0 0 0 1.

in acest moment vei face sortare dupa sum doar pentru numerele cu pozitii care corespund zerourilor in vectorul auxiliar.

la urmatoarea sortare, dupa sum, vei avea

51 223 19 37 111 si 1 1 0 0 1, si faci sortare dupa prod pentru numerele carora le corespund zerouri.

la urmatoarea sortare vei avea 51 223 19 37 111 si 1 1 1 1 1 si te opresti pentru ca nu are rost sa mai sortezi crescator dupa valoare.

Daca ai probleme cu implementarea sau ai dori sa iti propun una efectiv, contacteaza-ma prin mesaj si te ajut in continuare. Spor!