Cerința

Considerăm codificarea binară a caracterelor, în care fiecărui simbol îi revine reprezentarea pe 8 biţi a codului său ASCII. De exemplu, caracterului 'A', având codul ASCII 65, îi va corespunde reprezentarea binară 01000001. Astfel, un cuvânt C poate fi reprezentat binar, sub forma unui tablou bidimensional, în care fiecare linie i a tabloului reprezintă codificarea binară a literei de pe poziţia i din C, tabloul având în final atâtea linii câte litere are cuvântul, şi 8 coloane.
Scrieţi un program care, citind de la tastatură cuvântul C, construieşte în memorie matricea reprezentării binare, şi afişează pe ecran dimensiunea celei mai mari submatrici pătratice conţinând elemente având toate aceeaşi valoare (fie 0, fie 1).

Date de intrare

Programul citește de la tastatură cuvântul C

Date de ieșire

Programul va afișa pe ecran dimensiunea maximă cerută.

Restricții și precizări

cuvântul are cel mult 100 de caractere, litere mari şi/sau mici ale alfabetului englez

Exemplu

Intrare

IDEEA

Ieșire

Explicație

Pentru şirul de caractere IDEEA, matricea corespunzătoare va fi \(\scriptsize\begin{bmatrix}
0&1&0&0&1&0&0&1\\
0&1&\underline{0}&\underline{0}&\underline{0}&1&0&0 \\
0&1&\underline{0}&\underline{0}&\underline{0}&1&0&1 \\
0&1&\underline{0}&\underline{0}&\underline{0}&1&0&1 \\
0&1&0&0&0&0&0&1
\end{bmatrix}\). Submatricea pătratică de dimensiune maximă este cea cu elementele subliniate.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema dim_maxim_binar:

// o posibila solutie de 100p pentru problema dim_maxim_binar #1459 @pbinfo.ro
// ideile prezentate pot fi imbunatatite
// compilat cu Code::Blocks 13.12

#include <iostream> // std::cin, std::cout
#include <cstring>  // strlen

using namespace std;

int matriceBinara[105][10], numarLinii, numarColoane;
char cuvant[105];

//-------------------------------------------------------------------------------------------------------
// functie care returneaza, prin intermediul parametrului vect (vector de numere intregi), codificarea binara a
// caracterului transmis prin intermediul parametrului caracter (de tip char)
void charToInt(char caracter, int vect[]) {
    int ordinAscii = (int) caracter;
    for(int i = 8; i >= 1; i--) {
        vect[i] = ordinAscii % 2;
        ordinAscii /= 2;
    }
}

//-------------------------------------------------------------------------------------------------------
// transforma matriceBinara (declarata global) in reprezentarea binara a cuvantului citit de la tastatura
void transformareMatrice()
{
    int lungime = strlen(cuvant), vect_local[10];
    for(int i = 1; i <= lungime; i++) {
        charToInt(cuvant[i-1], vect_local);
        for(int j = 1; j <= 8; j++)
            matriceBinara[i][j] = vect_local[j];
    }

    // stabilirea dimensiunilor
    numarLinii = lungime; // lungimea cuvantului
    numarColoane = 8;
}

//-------------------------------------------------------------------------------------------------------
// verifica daca submatricea patratica, delimitata de (i_start, j_start) (colt stanga sus) si
// (i_final, j_final) (colt dreapta jos) are toate elementele egale (0 sau 1)
bool verificareSubmatrice(int i_start, int i_final, int j_start, int j_final)
{
    for(int i = i_start; i <= i_final; i++)
        for(int j = j_start; j <= j_final; j++)
            if(matriceBinara[i][j] != matriceBinara[i_start][j_start])
                return false;
    return true;
}

//-------------------------------------------------------------------------------------------------------
// subprogram care returneaza dimensiunea celei mai mari submatrici patratice avand toate elementele egale
int secventaMaxima()
{
    int secventa_max = 1;
    // parcurgem matricea binara, fara ultima linie si ultima coloana
    for(int i = 1; i < numarLinii; i++)
        for(int j = 1; j < numarColoane; j++)
            // parcurgem toate submatricile patratice posibile, pornind de la pozitia (i, j)
            for(int _i = i + 1, _j = j + 1; _i <= numarLinii && _j <= numarColoane; _i++, _j++)
                if(verificareSubmatrice(i, _i, j, _j)) { // submatricea are toate elementele egale
                    if(_i - i + 1 > secventa_max)
                        secventa_max = _i - i + 1;
                }
                else
                    break;  // oprim for-ul, deoarece nu mai are rost sa continuam cu el
    return secventa_max;
}

//-------------------------------------------------------------------------------------------------------
// Programul principal
int main(void)
{
    cin >> cuvant;

    transformareMatrice();

    cout << secventaMaxima();

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1459 dim_maxim_binar

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1459 dim_maxim_binar de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1459 dim_maxim_binar