Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Probleme sistem audio mașina

Radio care se incinge

problema -amplificator cu tranzis...

Retragere bani din cont inainte d...
 Plata cu cardul si bacsisul

Primire bani din Danemarca prin N...

Alerta securitate Fedora Linux 40...

Problemuțe sistem audio ma&#...
 Renovare balcon

installation has failed there was...

Montura polara.....

Sfat inchiriere locuinta unei per...
 Sursa stereo -> amplif mono

Dan Blondu vs. Marian Piciu

Side - Antalya

Nume fetita - international dar c...
 

Matrix/Submatrix.

- - - - -
  • Please log in to reply
9 replies to this topic

#1
g0dafk

g0dafk

    Member

  • Grup: Members
  • Posts: 462
  • Înscris: 10.11.2016
Avem o matrice de 10 pe 10 care are doar valori de 0 si 1 sa zicem. In interiorul ei, valorile de 1 sunt grupate astfel incat sa formeze un patrat, sau un dreptunghi. Cum pot extrage acele valori din matrice si sa formez o noua matrice din ele?
Dimenisunile/pozitia pot varia.

Nu ma intereseaza neaparat un limbaj de programare specific, ci mai degraba un algoritm, dar daca chiar e nevoie o sa-l scriu in Matlab.

Tot ce am reusit sa fac pana acum e sa parcurg matricea, sa creez un vector care detine toate valorile de 1 pe lungime si alt vector care le detine pe toate pe latime. Acum problema e ca daca am 2 grupuri de astea de 1 trebuie sa scot 2 matrici si aici iar... nu am idee cum sa fac, deoarece in vector am valori precum: 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1, si acum doar am redus problema initiala la 1 dimensiune.

Un exemplu de matrice...

0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 1 1 1
0 1 1 1 1 0 0 1 1 1
0 1 1 1 1 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0

Iar ca iesire m-ar interesa:

1 1 1 1
1 1 1 1
1 1 1 1
Si

1 1 1
1 1 1
1 1 1
v1=zeros(1,width);
v2=zeros(height,1);
for x=1:width

for y=1:height

	 if(imag(y,x)~=0)

		 v1(x)=v1(x)+1;
		 v2(y)=v2(y)+1;

	 end

end

end


Pe internet nu am gasit ceva care sa fie ce vreau eu, sau cel putin nu mi-am dat seama ca e ce-mi trebuie.
Si dupa cum ziceam, acum am sfarsit cu 2 vectori asemanatori cu matricea de mai sus..

Edited by g0dafk, 16 November 2019 - 12:27.


#2
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,269
  • Înscris: 24.02.2007
Fiecare valoare de 1 o poti considera ca o matrice 1x1. De aici nu-ti ramane decat sa verifici ce matrici se alatureaza incat sa le poti "mari".

Ce faci insa in situatii mai ambigue cum ar fi:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0
0 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Care ar trebui sa fie rezultatul aici?

#3
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,519
  • Înscris: 10.08.2005

View Postg0dafk, on 16 noiembrie 2019 - 12:26, said:

deoarece in vector am valori precum: 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1, si acum doar am redus problema initiala la 1 dimensiune.
si care e problema daca are  o dimensiune, tot matrice este

#4
MembruAnonim

MembruAnonim

    MembruAnonim

  • Grup: Banned
  • Posts: 399,715
  • Înscris: 08.10.2015
Backtrack recursiv cumva? Pentru o pozitie oarecare data se verifica conditia m[i, j] == 1 si daca da se verifica conditia pentru m[i + 1, j] si m[i, j + 1] adica vecinii, dreapta si jos. Ideea e ca daca  un vecin nu indeplineste conditia te opresti si returnezi rezultatul. Daca nu ma insel bactrack da toate rezultatele posibili ale unei probleme.

#5
g0dafk

g0dafk

    Member

  • Grup: Members
  • Posts: 462
  • Înscris: 10.11.2016

View PostMarianG, on 16 noiembrie 2019 - 13:53, said:

si care e problema daca are  o dimensiune, tot matrice este

Pai asta zic, cu alte cuvinte nu am reusit sa fac nici un pas inainte...

#6
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,519
  • Înscris: 10.08.2005
pentru exemplul dat de tine, si cel dat de @dani.user care sunt matricelile care pot fi extrase?

#7
g0dafk

g0dafk

    Member

  • Grup: Members
  • Posts: 462
  • Înscris: 10.11.2016

View Postdani.user, on 16 noiembrie 2019 - 13:44, said:

Fiecare valoare de 1 o poti considera ca o matrice 1x1. De aici nu-ti ramane decat sa verifici ce matrici se alatureaza incat sa le poti "mari".

Ce faci insa in situatii mai ambigue cum ar fi:
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0
0 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Care ar trebui sa fie rezultatul aici?


M-am gandit si eu la problema asta, dar cum nu imi intra in cerinta, o s-o ignor deocamdata. Ideea este ca de fapt am o imagine cu forme geometrice si trebuie sa le identific. Cum in imaginea mea exista doar patrate si dreptunghiuri am zis sa mentin lucrurile simple: Daca e patrat trebuie sa aiba laturile egale, daca nu inseamna ca e dreptunghi.

Imaginea este alb/negru deci valori de 0 si 1. Ideea mea era sa sparg imaginea ( matricea ) in 2 matrici mai mici, patratul respectiv dreptunghiul si sa verific dimensiunile. Daca matricea e de NxN e patrat. Alta idee mai buna nu-mi vine...


@MarianG la exemplul dat de @dani.user nu stiu ce sa spun.

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1


Ar fi raspunsul, dar nu stiu cum se poate crea o astfel de matrice. Un vector de vectori? A[0]= 1 1 1 1 1, A[1]= 1 1 1 1 1, A[2]= 1 1 1 1 ?

Edited by g0dafk, 16 November 2019 - 14:24.


#8
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 30,269
  • Înscris: 24.02.2007
Daca tratezi totul ca un graf, poti determina usor Connected Components (insule de 1) http://en.wikipedia...._(graph_theory) descrie si algoritmul oarecum banal.

Odata ce ai insulele (ce pot avea orice forma) determini din ce dreptunghiuri le poti forma.

Edited by MarianG, 16 November 2019 - 14:55.
fixed link


#9
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,519
  • Înscris: 10.08.2005

View Postg0dafk, on 16 noiembrie 2019 - 14:13, said:

@MarianG la exemplul dat de @dani.user nu stiu ce sa spun.

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1

{A2,6,B1,4}
{A3,4,B2,2}

#10
Ltschmer

Ltschmer

    New Member

  • Grup: Junior Members
  • Posts: 9
  • Înscris: 09.10.2017
Intotdeauna cand rezolvi o problema, 50% din munca e descrierea corecta a problemei si a situatiilor care pot aparea.  Implementarea unei solutii decurge din felul cum reusesti sa descrii problema in sine. Deci, din ceea ce inteleg eu din datele problemei, o posibila rezolvare ar fi urmatoarea : O sa avem nevoie  de o structura de date in care salvezi dreptunghiurile deja gasite. Parcurgem linie cu linie, element cu element , pana dam de un 1. Verificam daca acest 1 face parte dintr-un patrulater gasit anterior - deci daca parcurgerea matricei a intalnit latura stanga a unui patrulater deja gasit -  daca face , atunci continuam cautarea pe linie peste latimea patrulaterului respectiv, sau daca e nevoie trecem pe linia urmatoare. Daca nu face parte, atunci inseamna ca am gasit punctul stanga-sus al unei noi figuri. Din punctul stanga-sus, continuam cautarea pe orizontala pana la un 0. Acum avem punctul dreapta-sus. De acolo, coboram in jos pe coloana  pana iarasi dam de 0 (sau pana se termina matricea). Acum avem punctul dreapta-jos. Calculam apoi punctul stanga-jos si adaugam dreptunghiul in lista de figuri gasite. Continuam cautarea pe linie de unde am ramas, adica din punctul dreapta-sus, sau daca nu trecem cu cautarea pe linia urmatoare, sau pana la capat. O sa avem nevoie de cateva tipuri noi de date care sa reprezinte Punct(coordonate x y) si Patrulater( un patrulater are patru puncte). Patrulaterul  va trebui  sa poata furniza informatii legate de latime si laturi. Cautarea intalneste patrulaterul atunci cand x-coord al punctului coincide cu x-coord al punctelor care formeaza latura stanga. Cand cautarea gaseste un 1 , ne va fi utila o functie care parcurge lista de dreptunghiuri gasite si verifica daca cautarea a intalnit latura stanga a vreunei figuri. Daca da, atunci vom avea nevoie de latimea figurii respective.La final printezi latimea X lungimea de-alde 1 pentru fiecare figura. Si am asta e.

Anunturi

Bun venit pe Forumul Softpedia!

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate