La ora de informatica, elevii din clasa a 11-a au avut de rezolvat o problema care determina cate cifre au numerele dintr-o matrice.
Pentru rezolvarea acestei probleme, acestia au fost nevoiti sa respecte anumite reguli date de profesor.
Scrieti un program care sa-I ajute pe profesor sa le explice cat mai bine elevilor sai rezolvarea acestei probleme.
Restrictii:
● 0 < N < 10;
● Elementele matricei < 10 000.
⮚ Sectiunea 1
Creati urmatoarele functii in cadrul programului vostru:
● Functia recursiva numarCifre care determina cate cifre are fiecare element din vector si adauga numar de cifre intr-un alt vector.
● Functia sortare care sorteaza vectorul in ordine crescatoare.
● Functia elimElemIdentice care elimina elementele identice din vectorul de cifre.
⮚ Sectiunea 2
Realizarea metodei Main:
● Cititi de la tastatura un numar natural N.
● Cititi de la tastatura o matrice patratica cu N linii si N coloane.
● Creati un vector cu N*N elemente si adaugati elementele din matrice.
● Adaugati intr-un vector nou numarul de cifre al fiecarui element din vectorul precedent prin apelarea functiei numarCifre.
● Sortati vectorul care contine numar de cifre prin apelarea functieii de sortare.
● Eliminati elementele identice din vectorul de mai sus prin apelarea functiei elimElemIdentice.
● Scrieti intr-un fisier text rezultatul final.
Răspunsuri la întrebare
Răspuns:
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
int numarCifre(int numar);
void sortare(std::vector<int>& vectorNumere);
void elimElemIdentice(std::vector<int>& vectorNumere);
int main()
{
int N; /* numărul de linii și coloane */
std::cout << "Introdu N >> ";
std::cin >> N;
/* ne alocăm dinamic o matrice pătratică de N linii și coloane pe care o și populăm cu numere*/
int** pMatrice = new int*[N];
for (int i{}; i < N; i++) {
pMatrice[i] = new int[N];
for (int j{}; j < N; j++) {
std::cout << "pMatrice[" << i << "][" << j << "] = ";
std::cin >> pMatrice[i][j];
}
}
/* calculăm capacitatea vectorului pentru a evita viitoarele realocări */
size_t capacitateVector{ static_cast<size_t>(N * N) };
std::vector<int> vectorNumere;
vectorNumere.reserve(capacitateVector);
/* adăugăm numerele din matrice în vectorNumere */
for (int i{}; i < N; i++) {
for (int j{}; j < N; j++) {
vectorNumere.push_back(pMatrice[i][j]);
}
}
/* creăm vectorul în care salvăm contorul cifrelor */
std::vector<int> vectorContorCifre;
vectorContorCifre.reserve(capacitateVector);
for (size_t i{}; i < capacitateVector; i++) {
vectorContorCifre.push_back(numarCifre(vectorNumere.at(i)));
}
/* sortăm vectorContorCifre și eliminăm duplicatele */
sortare(vectorContorCifre);
elimElemIdentice(vectorContorCifre);
/* deschidem un std::ofstream pentru a scrie rezultatul în fișier */
std::ofstream fout("rezultat.txt", std::ios::out);
/* dacă nu s-a deschis cu succes ieșim din program */
if (!fout.good()) {
std::cout << "Nu s-a putut deschide fisierul!\n";
exit(EXIT_FAILURE);
}
/* altfel scriem rezultatul în fișier */
for (size_t i{}; i < vectorContorCifre.size(); i++) {
fout << vectorContorCifre.at(i) + " ";
}
/* dealocăm memoria alocată mai sus */
for (int i{}; i < N; i++) {
delete[] pMatrice[i];
}
delete[] pMatrice;
return 0;
}
/*
(apelul principal al funcției) numarCifre(1024) returnează 1 + 3 = 4 (deoarece numărul >= 10)
(apel recursiv) numarCifre(102) returnează 1 + 2 = 3 (deoarece numărul >= 10)
(apel recursiv) numarCifre(10) returnează 1 + 1 = 2 (deoarece numărul >= 10)
(apel recursiv) numarCifre(1) returnează 1 (deoarece numărul nu e >= 10)
*/
int numarCifre(int numar)
{
return (numar >= 10) ? 1 + numarCifre(numar / 10) : 1;
}
void sortare(std::vector<int>& vectorNumere)
{
/* ne folosim de std::sort pentru a sorta numerele din vector (poți folosi un algoritm de sortare dacă nu vrei cu std::sort) */
std::sort(vectorNumere.begin(), vectorNumere.end());
}
void elimElemIdentice(std::vector<int>& vectorNumere)
{
/* aici ai mai multe variante, poți să-ți definești tu algoritmul care să-ți șteargă duplicatele sau ne putem folosi de std::unique care înlocuiește următorul element (dacă există duplicări între două elemente) cu unul diferit față de cel anterior, restul elementelor sunt mutate-n dreapta vectorului (ceva de genul, ca să funcționeze vectorul trebuie să fie sortat crescător/descrescător) mai poți crea un set din elementele vectorului care by default va șterge duplicatele ca mai apoi să adaugi elementele fără duplicate înapoi în vector */
/* eu voi folosi std::unique pentru că avem deja o funcție cu care putem sorta vectorul */
/* dacă să zicem că inițial avem următoarea matrice
|1 22 3 |
|44 5 66|
|7 88 9 |
vectorul cu elementele din matrice este [1, 22, 3, 44, 5, 66, 7, 88, 9]
iar vectorul cu numărul cifrelor este [1, 2, 1, 2, 1, 2, 1, 2, 1]
după ce l-am sortat vectorul devine [1, 1, 1, 1, 1, 2, 2, 2, 2]
std::unique transformă vectorul astfel [1, 2, 1, 1, 1, 1, 2, 2, 2]
și returnează un iterator V
lastElem
acuma folosindu-ne de iteratorul respectiv putem scăpa de restul elementelor și rămânem doar cu valori unice cu std::erase */
/* auto (pentru a deduce tipul de dată returnat ca să nu mai scrii tu std::vector<int>::iterator */
auto lastElem{ std::unique(vectorNumere.begin(), vectorNumere.end()) };
vectorNumere.erase(lastElem, vectorNumere.end());
}