problema matrice binara c++

Stef_Stef, on 02 iulie 2019 - 15:36, said:

Quote

Da

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

Stef_Stef, on 02 iulie 2019 - 15:36, said:

Iulius-Foyas, on 02 iulie 2019 - 15:37, said:

Ba nu.

@Iulius-Foyas: Ai examinat doar numere mici. Ia vezi ce se intampla cand treci de la 7 la 8…

Cand convertesti index_linie * 2 in baza 2, nu faci altceva decat sa numeri in baza 2 dar de fiecare data sa ai un bit 0 adaugat in plus le dreapta. Prin urmare daca se face carry peste mai mult de 1 cifra sau nu se face deloc atunci nu se respecta conditiile problemei. Chiar in exemplul tau, primele 2 linii nu difera decat la o singura pozitie nu 2 cum se cere.

@MihaelaEla:
Nu stiu daca exista un algoritm ‘clasic’ pentru a rezolva problema ta.

Un backtracking ar trebui sa mearga. Ai 2ⁿ valori distincte de n biti si tie iti trebuie doar 2n-2 din ele. Deci s-ar putea sa gaseasca o solutie destl de rapid.

Altfel, imi pare ca exista o solutie destul de simpla. Pornesti cu prima linie 0 0 … 0. In prima etapa, pentru a genera o noua linie negi cate 2 biti alaturati ai liniei anterioare, incepand cu primele 2 pozitii din stanga, apoi a 2-a si a 3-a, etc. Asa mai obtii n - 1 linii. In a doua etapa faci din nou acelasi lucru dar numai de n - 2 ori, adica te opresti inainte de a nega ultima pereche (total: 1 + n-1 + n-2 = 2n - 2 linii). Cred ca iese ce trebuie, dar nu am incercat.

A treia solutie ar fi sa apelezi la ceva clasic inrudit cu problema ta: coduri Gray. Generezi un cod Gray de n - 1 biti, si la fiecare linie adaugi alternativ cate un bit 0/1 la dreapta (sau stanga, sau in alta pozitie fixa, cum preferi).

Edited by sags, 02 July 2019 - 16:58.

Quote

insa nici exemplu dat de autori nu respecta cerintele problemei chiar si pt numere mici. Asadar ce este corect pana la urma ?

Edited by Iulius-Foyas, 02 July 2019 - 17:01.

‘Exemplul dat de autori’, adica acesta?

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

Eu vad ca respecta cerintele impuse. Am subliniat pozitiile care difera fata de linia anterioara.

Quote

n = 3 => n-2 pozitii = 3-2 = 1 , deci prima pozitie trebuie sa fie identica la doua linii consecutive.

Quote

Edited by Iulius-Foyas, 02 July 2019 - 18:03.

Eu inteleg ca n-2 din pozitii trebuie sa fie identice, acestea putand fi oricare din cele n nu neaparat primele sau consecutive sau etc. Si de la o pereche de linii consecutive la alta pot fi alte n-2 pozitii, nu neaparat aceleasi. Celelalte 2 trebuie sa fie diferite.

Dealtfel daca ‘prima pozitie trebuie sa fie identica la [oricare] doua linii consecutive’ se deduce prin inductie ca prima pozitie (sau primele n-2 in cazul general) a tuturor liniilor trebuie sa fie aceeasi (aceleasi). Raman sa varieze doar ultimele 2 pozitii, adica cel mult 4 combinatii distincte…

Edited by sags, 02 July 2019 - 18:07.

sags, on 02 iulie 2019 - 18:04, said:

Adica acel (n-2) sa reprezinte numarul de elemente al intersectiei dintre multimea elementelor liniei 1 si multimea elementelor liniei 2 ?