Question

Bună! 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.
b) Scrieți programul C/C++ corespunzător algoritmului proiectat.

Answer 1

Răspuns:

#include <fstream>

#include <algorithm>

#include <iostream>

using namespace std;

int v[1000000];

int main(){

int x, p = 0;

ifstream fin("bac.txt");

while(fin >> x){

v[p++] = x;

}

fin.close();

sort(v, v+p, [](int a, int b) -> bool {return (a%2) == (b%2) ? a < b : (a%2) > (b%2); });

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

cout << v[i] << ' ';

}

Explicație:

Se citesc toate numerele, se memoreaza intr-un vector, si se sorteaza astfel:

Daca 2 numere au aceasi paritate, atunci cel mai mic dintre ele este asezat inaintea celui mai mare.

Daca 2 numere au paritate diferita, atunci cel impar este asezat inaintea celui par.

Si apoi se afiseaza vectorul rezultat.