Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
joc idem Half Life gratis

PC game stream catre Nvidia Shiel...

Pompa de apa HEPU ?!

Vreau o masina electrica de tocat...
 Cum ajunge remorca de tir inapoi ...

Alt "Utilizator nou" pe T...

ULBS INFORMATICA

Index preturi
 Boxa membrana tweeter infundata

Am nevoie de poze cu un curcubeu

Whisky for Mac

Xiaomi 14 Gpay
 Izolare zid exterior de scandura

Dezinstalare drivere W11 23H3

Recomandare masina de spalat fiab...

BSOD din cauza Intel Audio DSP dr...
 

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,233
  • Î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,426
  • Î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: 398,284
  • Î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,426
  • Î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,233
  • Î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,426
  • Î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

Neurochirurgie minim invazivă Neurochirurgie minim invazivă

"Primum non nocere" este ideea ce a deschis drumul medicinei spre minim invaziv.

Avansul tehnologic extraordinar din ultimele decenii a permis dezvoltarea tuturor domeniilor medicinei. Microscopul operator, neuronavigația, tehnicile anestezice avansate permit intervenții chirurgicale tot mai precise, tot mai sigure. Neurochirurgia minim invazivă, sau prin "gaura cheii", oferă pacienților posibilitatea de a se opera cu riscuri minime, fie ele neurologice, infecțioase, medicale sau estetice.

www.neurohope.ro

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