#581 · Subiectul II · Programare

Numărul prim cu cele mai multe cifre pare dintr-o matrice (prim și contorizare recursiv)

✓ Rezolvare explicatăBucurești 2020 · nr. 9

Enunț

Fișierul atestat.in conține pe prima linie un număr natural n (2≤n≤20), iar pe următoarele n linii câte n numere naturale nenule cu cel mult 9 cifre, separate prin spațiu.

Se consideră subprogramele:

prim, cu un singur parametru x (număr natural nenul cu cel mult 9 cifre): returnează 1 dacă x este prim, altfel 0;
contorizare (implementat recursiv), cu un singur parametru y (număr natural nenul cu cel mult 9 cifre): returnează numărul cifrelor pare ale lui y.

a. Scrieți definiția completă a subprogramului prim.

b. Scrieți definiția completă a subprogramului contorizare.

c. Scrieți un program care citește datele din atestat.in și, folosind apeluri utile ale subprogramelor prim și contorizare, scrie în atestat.out, pe prima linie, numărul prim din matrice cu cele mai multe cifre pare, iar pe a doua linie numărul acestor cifre. Dacă mai multe prime au același număr maxim de cifre pare, se scrie cel mai mic dintre ele. Dacă în matrice nu există niciun număr prim sau numerele prime nu au cifre pare, se scrie mesajul nu exista.

Exemple

Subiectul dă un exemplu cu rezultatul 421 și 2, dar matricea din PDF nu se poate reconstitui complet (apar doar 20 de valori pentru n = 5). Tabelul de mai jos folosește un exemplu construit pe baza valorilor vizibile:

`atestat.in`	`atestat.out`	Explicații
`5` `12 23 28 29 90` `2 54 101 121 7` `1096 41 9 607 102` `220 34 32 421 6` `3 10 14 16 15`	`421` `2`	`607` și `421` sunt prime și au câte 2 cifre pare; se alege cel mai mic, `421`

Rezolvare

C++

#include <fstream>
using namespace std;

int prim(int x) {
    if (x < 2) return 0;
    for (int d = 2; d * d <= x; d++)
        if (x % d == 0) return 0;
    return 1;
}

int contorizare(int y) {
    if (y == 0) return 0;                          // nu mai sunt cifre
    return (y % 10 % 2 == 0) + contorizare(y / 10); // ultima cifra + restul numarului
}

int main() {
    ifstream f("atestat.in");
    ofstream g("atestat.out");
    int n, x, bestVal = 0, bestCnt = 0;
    f >> n;
    for (int i = 0; i < n * n; i++) {
        f >> x;
        if (!prim(x)) continue;
        int c = contorizare(x);
        if (c > bestCnt || (c == bestCnt && x < bestVal)) {   // mai multe cifre pare, sau egal si mai mic
            bestCnt = c;
            bestVal = x;
        }
    }
    if (bestCnt == 0) g << "nu exista";
    else g << bestVal << "\n" << bestCnt;
    return 0;
}

Exersează mai departe

Probleme cu aceeași tehnică

#573ProgramareNumere cu prima cifră pătrat perfect, ordonate descrescător (p_cifra recursiv și sortare)#579ProgramareEliminarea coloanei cu k elemente formate doar din cifre impare #580ProgramareMatrice inferior triunghiulară și determinantul ei (inftr și produs recursiv)#582ProgramareMedia numerelor prime din șirul lui Fibonacci aflate într-o matrice (fibo și divprim)#583ProgramareCel mai mare palindrom de pe diagonalele matricei (oglindit și maxim)#044ProgramareCel mai mare divizor comun a două numere, folosind o funcție recursivă