problema matrice binara c++

O matrice binara este o matrice în care orice element are valoarea 0 sau 1.
Pentru o valoarea naturala n (3 ≤ n ≤ 20) citita de la tastatura, se doreste alcatuirea unei matrice binare cu n coloane si 2n-2 linii cu urmatoarele proprietati:
• nu exista doua linii identice în matrice;
• doua linii consecutive din matrice au n-2 pozitii cu valori identice iar celelalte 2 pozitii contin valori diferite.

ex:
0 0 1
1 0 0
0 1 0
1 1 1

Nu am nicio idee la aceasta problema...va cer ajutorul!! Multumesc!

Din exemplu dat de tine eu am observat urmatorul lucru:
001 ->  1  in baza 10
010 ->  2  in baza 10
111 ->  3  in baza 10
100 -> 4  in baza 10

De asemenea se mai observa urmatoarele:
nr de liniii = max( Numar in baza 10)
nr de coloane =  cantiatea minima necesara de biti pt a afisa in baza 2  valoarea lui max(Numar in baza 10)
atat timp cat ai numere unice in baza 10, automat vei avea si linii diferite in matrice

Edited by Iulius-Foyas, 02 July 2019 - 11:36.

la fiecare pas se genereaza o noua luinie:
prima linie o consideri 0 0 0 ... 0 1 si il muti succesiv pe 1 catre stanga. generam astfel n linii;( 0 ... 0 1 0, etc)
plecam de la ultima linie generata: 1 0 ... 0 0 0 si generam din ea 1 0 ... 0 1 1; generam urmatoarele linii mutandu-l acum pe 1 cel mai dn stanga cate o pozitie catre dreapta:
0 1 0... 0 1 1, apoi  0 0 1 .... 0 1 1 si in final 0 0 .... 0 1 1 1 generand atfel inca n-2 linii;  demonstreaza ca matricea astfel obtinuta indelpineste cerintele problemei

Edited by Stef_Stef, 02 July 2019 - 11:39.

 Iulius-Foyas, on 02 iulie 2019 - 11:32, said:

cum afisez numerele in baza 10 in functie de nr de coloane?
de ex daca n-ul e 4 sau mai mult

Quote

Pe baza carui criteriu ajungi sa pui  11  la dreapta dintr-o data ?

Edited by Iulius-Foyas, 02 July 2019 - 11:50.

pt respectarea cerintei nr 2: doua linii consecutive din matrice au n-2 pozitii cu valori identice iar celelalte 2 pozitii contin valori diferite.

 MihaelaEla, on 02 iulie 2019 - 11:46, said:

https://despretot.in...a-2-in-baza-10/
si invers:
https://despretot.in...a-10-in-baza-2/
Odata aflat MSB-ul valorii care reprezinta numarul de coloane, pt fiecare numar ( a carei reprezentare binara este o linie), se completeaza cu zerouri la stanga
doarece acestea nu schimba valoarea numarului in sine.
Exemplu:
3 in baza 2 inseamna 1 1 1. (am nevoie de minim 3 pozitii pentru a reprezenta aceasta valoare in baza 2)
3 in baza 2  pe 4 pozitii: 0 1  1  1, este aceiasi valoare insa reprezentata pe 4 pozitii

3 in baza 2 pe 7 pozitii sa zicem:  0 0 0 0  1 1 1
3 in baza 2 pe 8 pozitii(octet) : 0 0 0 0 0 1 1 1

Asadar  fiecare linie de matrice reprezinta de fapt configuratia binara a unui numar din baza 10, dispusa pe  M pozitii, unde M = cantitatea minima necesara de biti  pt a reprezenta
numarul total de linii (acel n din datele problemei).

Quote

pai N-ul  este 4 in acest caz.

 Stef_Stef, on 02 iulie 2019 - 11:50, said:

pai aici e chestia: 11 trebuie sa apara la dreapta  "ca trebuie sa picam pe datele problemei"  sau este de fapt consecinta logica a unei  actiuni ?

Edited by Iulius-Foyas, 02 July 2019 - 12:13.

1 de pe prima pozitie nu poate fi modificat la urmatorul pas, atfel dam peste o linie deja generata; ca urmare, se modifica 2 pozitii cu 0, si le-am ales pe cele mai din dreapta

 Iulius-Foyas, on 02 iulie 2019 - 11:55, said:

am facut ceva...dar nu merge, te poti uita te rog peste? poate iti dai seama ce e gresit...

#include <iostream>
using namespace std;
int c, l, A[101][101], cc, n;
int main()
{
    cin >> n;
    c=n;
    l=2*n-2;
    for(int i=1; i<=l; i++)
    {
    for(int j=c; j>=1; j--)
    {
    if(i != 0)
    {
    cc=i%2;
    i=i/2;
    A[i][j]=cc;
    }
    else
    A[i][j] = 0;
    }
    }
    for(int i=1; i<=l; i++)
    {
    for(int j=1; j<=c; j++)
   cout << A[i][j] << " ";
    cout << endl;
    }
    return 0;
}

mi-am dat seama pana la urma...trebuia retinut i intr-o variabila.


#include <iostream>
using namespace std;
int c, l, A[101][101], cc, n;
int main()
{
    cin >> n;
    c=n;
    l=2*n-2;
    for(int i=1; i<=l; i++)
    {  int a=i;
    for(int j=c; j>=1; j--)
    {
    if(a != 0)
    {
    cc=a%2;
    a=a/2;
    A[i][j]=cc;
    }
    else
    A[i][j] = 0;
    }
    }
    for(int i=1; i<=l; i++)
    {
    for(int j=1; j<=c; j++)
   cout << A[i][j] << " ";
    cout << endl;
    }
    return 0;
}



Multumesc mult pentru tot!!

 Iulius-Foyas, on 02 iulie 2019 - 11:32, said:

Am gresit eu, 111 este 7 nu 3 deci avem in baza 10 : 1,2,4,7

nu inteleg o chestie:

Quote

In cazul de fata n = 3 coloane => linii = 3x2-2 = 4 linii

Apoi, pt doua linii consecutive:
avem n-2 pozitii cu valori identice =>  3-2  = 1 pozitie cu valori identice  si 2 pozitii cu valori diferite

Pentru exemplu de mai sus care sunt acele doua linii consecutive care au o pozitie identica si  2 pozitii diferite ?

Sigur nu este asa ?
0 0  1
0 1  0
1 0  0
1 1  1
Si in acest caz, avem pt doua liniii consecutive (prima si a doua) aceiasi valoare (adica zero) pt prima pozitie si valori diferite pt celalalte doua pozitii
iar pt urmatoarele doua linii consecutive(a treia si a patra) aceiasi valoare(adica unu) pt prima pozitie si valori diferite pt celelalte doua pozitii.
Adica avem alte date ale problemei.

Apoi daca insa aleg doua linii consecutive :linia 2 si linia 3  nu respecta cerintele problemei doarece aceste linii au valori diferie pe toate pozitiile.
Sigur datele intiale ale problemei sunt corecte ?
Cum aleg aceasta grupare de doua linii consecutive ? Plec de la prima linie a matricei si compar doua cate doua sau aleg aleatoriu un numar de linie si vad daca aceasta formeaza
fie cu linia de sus sau cu linia de jos , o grupare de doua linii consecutive care sa respecta cerinta ?

Edited by Iulius-Foyas, 02 July 2019 - 13:37.

 Iulius-Foyas, on 02 iulie 2019 - 13:09, said:

da, asa-i....
datele sunt corecte...problema e din variante de bac 20017, var 100, SIII problema 2

Asa cum ?
Cum ai dat tu sau cum am zis eu ?

Quote

Link catre varianta ceva ?

Edited by Iulius-Foyas, 02 July 2019 - 13:45.

 Iulius-Foyas, on 02 iulie 2019 - 13:44, said:

e cum ai zis tu
http://www.ududec.co...formatica_C.pdf
varianta 100, ultima

Interesant ca daca ultima linie 111 este inlocuita cu 101 (5) sau cu 110(6) respecta cerinta problemei
Interesant ca daca prima linie 001 este inlocuita cu 000(0)  se respecta datele problemei.

de sunt impotante aceasta observatii ? pt ca daca inlocuiesc cu 110(6 in baza 10)  si pe  001 cu 000(0 in baza 10)  atunci tabloul se prezinta astfel:

000 = 0 => 2  x 0, pentru linia cu index 0
010 = 2 => 2  x 1, pentru linia cu index 1
100 = 4 => 2  x 2, pentru linia cu index 2
110 = 6 => 2  x 3, pentru linia cu index 3

adica am gasit o formula prin care imi pot genera numerele din baza 10  si care imi respecta cerintele problemei:si anume : 2  x  indecsul de linie

Insa aceasta este o simpla ipoteza. Hai sa vedem daca cel putin aceasta ipoteza se confirma si pt un alt caz:

fie n = 4 coloane => linii =  2n-2  =  2*4 -2 => 6 linii
fie k = n-2 pozitii diferite => k = 4-2 => k = 2 pozitii diferite

Deci vom avea un tablou cu 4 coloane, 6 linii. Fiecare grupare de linii consecutive va avea: primele 2 pozitii acelasi si ultimele 2 diferite.
Avem:
2 x 0 = 0 =>  0  0  0  0
2 x 1 = 2 =>  0  0  1  0
2 x 2 = 4 =>  0  1  0  0
2 x 3 = 6 =>  0  1  1  0
2 x 4 = 8 =>  1  0  0  0
2 x 5 = 10=> 1  0  1  0

Edited by Iulius-Foyas, 02 July 2019 - 14:44.

ok

Edited by MihaelaEla, 02 July 2019 - 14:57.

Urmeaza insa partea de generare a matricei.
Avand

• n = nr de coloane,
  
• fie b = numarul minim de biti pt a reprezenta numarul in binar(il afli cand faci conversia din baza 10 in baza 2)

determini  numarul de zerouri care trebuiesc puse la stanga pt a reprezenta numarul in binar pe n pozitii(unde n = nr de coloane)

Pt tabloul de mai sus , distributia acestui numar de zerouri pt fiecare linie va fi :

2 x 0 = 0 =>  0  0  0  0
2 x 1 = 2 =>  0  0  1  0
2 x 2 = 4 =>  0  1  0  0
2 x 3 = 6 =>  0  1  1  0
2 x 4 = 8 =>  1  0  0  0
2 x 5 = 10=> 1  0  1  0

formezi linia dupa urmatorul pattern: [ numar de zerouri necesare pt completare ] [ b ]
si aduagi linia la matrice si gata programul.

Ai urmatorii pasi pt fiecare iteratie:

• generezi numarul in baza 10 folosind formula:  2 * index_linie
  
  
• convertesti numarul din baza 10 in baza 2 si stochezi valoarea fiecarui bit intr-un vector(atentie la ordinea de aflare a bitilor in urma operatiei de conversie si cum trebuiesc ei rearanjati in realitate, ca sa arata ca in exemplu de mai sus).Indiciu: acestia ies in ordine inversa in urma operatiei de conversie, de aceea  trebuie sa inversezi din nou elementele vectorului dupa conversie.
  
• retii numarul minim de biti necesar pt conversia din baza 10 in baza 2
  
  
• stiind numarul de coloane si numarul minim de biti necesari , afli numarul de zerouri necesar pt completare
  
  
• in cadul iteratiei curente inserezi elemente cu valoarea zero la stanga vectorului de mai sus atat cat indica numarul de zerouri
  
  
• acel vector este  linia finala, pe care o adaugi la o  matrice.

Edited by Iulius-Foyas, 02 July 2019 - 15:26.

Progrmaul tau contine: inserare intr-un vector, inversare elemente intr-un vector, "inserare la stanga"  intr-un vector, inserarea unui vector intr-o matrice.

"inserare la stanga"  intr-un vector =  permutari circulare ale elementelor intr-un vector
https://profs.info.u...ectii/5/510.pdf

sau poti face altfel: contruiesti intai vectorul de zerouri necesare dupa care adauge elementele care reprezinta biti numarului respectiv.
Cum vrei tu.

Edited by Iulius-Foyas, 02 July 2019 - 15:32.

se respecta si cerinta 2: doua linii consecutive din matrice au n-2 pozitii cu valori identice iar celelalte 2 pozitii contin valori diferite?