Question

Fişierul bac.txt conţine un şir de cel puțin două și cel mult 10^6
numere naturale din intervalul
[0,10^3], separate prin câte un spaţiu. Șirul are cel puțin un termen par și cel puțin un termen
impar. Se cere să se afișeze pe ecran termenii șirului, separați prin câte un spaţiu, astfel încât toți
cei impari să apară înaintea tuturor celor pari, şi atât subșirul format din cei impari, cât şi subșirul
format din cei pari, să fie în ordine crescătoare, ca în exemplu. Proiectați un algoritm eficient din
punctul de vedere al timpului de executare.
Exemplu: dacă fişierul conţine numerele 12 2 3 1 2 5
se afişează pe ecran: 1 3 5 2 2 12
a) Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
b) Scrieți programul C/C++ corespunzător algoritmului proiectat.

Answer 1

Răspuns:

#include <iostream>

#include <fstream>

using namespace std;

ifstream fin("bac.txt");

int i,num,v[1002];

int main()

{

   while (fin >> num)

   {

       ++v[num];

   }

   for (num=1; num<1000; num+=2)

   {

       if (v[num])

       {

           for (i=1; i<=v[num]; i++)

               cout << num << " ";

       }

   }

   for (num=0; num<=1000; num+=2)

   {

        if (v[num])

       {

           for (i=1; i<=v[num]; i++)

               cout << num << " ";

       }

   }

   return 0;

}

Explicație:

vector de frecventa...

la afisare se parcurge vectorul de vrecventa de 2 ori, mai intai pentru impare, apoi pentru pare