Clasa a XII-a · Recapitulare pentru bacalaureatRead in English

Matrice — contururi concentrice în C++

În engleză: Matrix: concentric borders

O(n²)C++1759 de linii2 exemple

Ideea

Cerința (tip subiectul III.2): se citește n (2 ≤ n ≤ 20). Construiți în memorie o matrice cu n linii și n coloane în care elementele de pe conturul exterior sunt 1, cele de pe conturul următor 2 și așa mai departe, apoi afișați-o. În loc să „desenăm” contur după contur, observăm că elementul (i, j) (numerotare de la 0) se află pe conturul dat de distanța lui până la cea mai apropiată margine: min(i, j, n-1-i, n-1-j) + 1. Așa fiecare element se calculează direct, o singură dată.

Descrierea în engleză

The task (exam part III.2 style): n is read (2 ≤ n ≤ 20). Build in memory a matrix with n rows and n columns in which the elements on the outer border are 1, those on the next border 2 and so on, then print it. Instead of 'drawing' border after border, we notice that the element (i, j) (numbered from 0) lies on the border given by its distance to the nearest edge: min(i, j, n-1-i, n-1-j) + 1. This way every element is computed directly, exactly once.

Complexitate
O(n^2)
Clasa
Clasa a XII-a (Grade 12)

Exemple

Exemplul 1

Intrare

5

Ieșire așteptată

1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1
Exemplul 2

Intrare

4

Ieșire așteptată

1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

matrice-contururi-concentrice.cpp
/*
 * Titlu: Matrice — contururi concentrice
 * Clasa: 12
 * Capitol: Recapitulare pentru bacalaureat
 * Descriere: Cerința (tip subiectul III.2): se citește n (2 ≤ n ≤ 20). Construiți
 *            în memorie o matrice cu n linii și n coloane în care elementele de pe
 *            conturul exterior sunt 1, cele de pe conturul următor 2 și așa mai
 *            departe, apoi afișați-o. În loc să „desenăm” contur după contur,
 *            observăm că elementul (i, j) (numerotare de la 0) se află pe conturul
 *            dat de distanța lui până la cea mai apropiată margine:
 *            min(i, j, n-1-i, n-1-j) + 1. Așa fiecare element se calculează
 *            direct, o singură dată.
 * Complexitate: O(n^2)
 *
 * Exemplu
 * Intrare: 5
 * Ieșire:
 * 1 1 1 1 1
 * 1 2 2 2 1
 * 1 2 3 2 1
 * 1 2 2 2 1
 * 1 1 1 1 1
 *
 * Exemplu
 * Intrare: 4
 * Ieșire:
 * 1 1 1 1
 * 1 2 2 1
 * 1 2 2 1
 * 1 1 1 1
 */
#include <iostream>
using namespace std;

int main()
{
    int n, a[20][20];
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            int d = i;
            if (j < d)
                d = j;
            if (n - 1 - i < d)
                d = n - 1 - i;
            if (n - 1 - j < d)
                d = n - 1 - j;
            a[i][j] = d + 1;
        }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.