#582 · Subiectul II · Programare

Media numerelor prime din șirul lui Fibonacci aflate într-o matrice (fibo și divprim)

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

Enunț

În fișierul atestat.in, pe prima linie se află două numere n și m (2≤n,m≤20), numărul de linii și de coloane ale unui tablou bidimensional, iar pe următoarele n linii câte m numere naturale mai mici sau egale cu 200.

Se consideră subprogramele:

fibo, care primește prin parametrul n un număr natural (1≤n≤200) și furnizează prin parametrul x o valoare naturală: cel mai mic număr mai mic sau egal cu n care face parte din șirul lui Fibonacci;
divprim, care primește prin parametrul a un număr natural (2≤a≤200) și returnează cel mai mic divizor prim al lui a.

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

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

c. Scrieți programul care citește datele din atestat.in și, folosind apeluri utile ale subprogramelor fibo și divprim, scrie în atestat.out media aritmetică a elementelor tabloului care sunt numere prime și fac parte din șirul lui Fibonacci; dacă nu există niciun astfel de număr, se scrie mesajul nu exista.

⚠️ Inconsecvență în enunț. „Cel mai mic număr ≤ n din șirul lui Fibonacci” este întotdeauna 1, deci fibo nu ar spune nimic despre n. Rezolvarea citește definiția ca „cel mai mare număr Fibonacci ≤ n”: așa, n este în șir exact când fibo îl returnează pe n însuși, iar exemplul oficial dă rezultatul cerut.

Exemple

`atestat.in`	`atestat.out`	Explicații
`3 4` `9 7 21 4` `13 8 2 6` `28 3 10 5`	`5.75`	Prime din șirul Fibonacci: `13, 2, 3, 5`; `(13+2+3+5)/4 = 5.75`

Rezolvare

C++

#include <fstream>
using namespace std;

void fibo(int n, int &x) {
    int a = 1, b = 2;                    // termenii 1, 2, 3, 5, 8, ...
    x = 1;
    while (a <= n) {
        x = a;                           // ultimul termen <= n
        int c = a + b;
        a = b;
        b = c;
    }
}

int divprim(int a) {
    for (int d = 2; d * d <= a; d++)
        if (a % d == 0) return d;
    return a;                            // nu are divizori pana la radical: e prim
}

int main() {
    ifstream f("atestat.in");
    ofstream g("atestat.out");
    int n, m, x, v, nr = 0;
    long long s = 0;
    f >> n >> m;
    for (int i = 0; i < n * m; i++) {
        f >> v;
        if (v < 2) continue;             // divprim cere a >= 2
        fibo(v, x);
        if (x == v && divprim(v) == v) { // Fibonacci si prim
            s += v;
            nr++;
        }
    }
    if (nr == 0) g << "nu exista";
    else g << (double)s / nr;
    return 0;
}

Exersează mai departe

Probleme cu aceeași tehnică

#579ProgramareEliminarea coloanei cu k elemente formate doar din cifre impare #581ProgramareNumărul prim cu cele mai multe cifre pare dintr-o matrice (prim și contorizare recursiv)#583ProgramareCel mai mare palindrom de pe diagonalele matricei (oglindit și maxim)#045ProgramareSă se afişeze indicii coloanelor care au toate elementele impare #048ProgramareSă se afişeze cel mai mare element din matrice şi poziţiile pe care apare #049ProgramareSă se afişeze cel mai mic element din matrice şi poziţiile pe care apare