Question

Se considera un numar natural n.
Sa se scrie un algoritm cu ordinul O(n) care sa determine cel mai mic numar natural care se poate forma folosind cifrele numarului n.

Ca justificare calculati ordinul timpului de executie.

Answer 1

Răspuns:

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

int v[10];

for(int i = 0; i < 10; i++)

 v[i] = 0;

int c, smallest = 10; // smallest- cel mai mic care nu e 0

while(n){

 c = n%10; //ultima cifra

 if(c < smallest && c != 0)

   smallest = c;

 v[c]++;

 n = n/10; /*scot ultima cifra din n. n va deveni 0 dupa ce se termina algormtul. dava mai ai nevoie de n, salveaza-l in alta variabila */

}

// construiesc in n

n = smallest;  // am scapat de problema ca ar incepe n cu 0

v[smallest] --;

int i = 0;

// pentru claritate: v[i] = cate cifre sunt pe pozitia i

// i = ce cifra e

while(i < 10){

 if(v[i] != 0){ //adica daca mai sunt cifre pe pozitia i

   n = n * 10 + i;

   v[i]--;

 }

 else{

   i++; //trece pe urm pozitie, nu mai are ce sa faca aici

 }

}

cout << n;

return 0;

}

Explicație:

Pai daca vrei complexitate O(n) pentru problema asta, trebuie sa faci un vector care numara aparitiile fiecarei cifre a numarului n si apoi sa parcurgi de la 0 la 9 punand intr-un numar cat trebuie sa pui. In primul rand, un numar nu poate sa inceapa cu 0, deci trebuie sa pui un 1 la inceput, apoi sa pui toate zerourile sa scapi de ele. Daca nu exista nici un 1, se pune cel mai mic numar care exista. Din moment ce nu ai mentionat limbajul in care se va scrie algoritmul, am sa scriu in C++

BTW // si /*   */  sunt comentarii

Daca vrei sa faci la ultima parte cu for, vezi ca dupa ce adaugi in n, trebuie sa scazi i-ul ca o sa creasca la 2 sau sa te complici cu alt while.