1266 - Cauta Nr In Matrice: Difference between revisions

From Bitnami MediaWiki
No edit summary
Line 19: Line 19:


== Exemplul 1 ==
== Exemplul 1 ==
;Intrare
 
;cautanrinmatricein.txt
;cautanrinmatricein.txt
: 3 4
: 3 4
Line 27: Line 27:
: 3
: 3
: 11 24 38
: 11 24 38
;Iesire
 
:Datele introduse corespund restrictiilor impuse.
:Datele introduse corespund restrictiilor impuse.
;cautanrinmatriceout.txt
;cautanrinmatriceout.txt
Line 35: Line 35:


== Exemplul 2 ==
== Exemplul 2 ==
;Intrare
 
;cautanrinmatricein.txt
;cautanrinmatricein.txt
: 3 2
: 3 2
Line 41: Line 41:
: 12 19
: 12 19
: 23 21
: 23 21
;Iesire
 
:Datele introduse nu corespund restrictiilor impuse.
:Datele introduse nu corespund restrictiilor impuse.


Line 47: Line 47:


<syntaxhighlight lang="python3" line="1">
<syntaxhighlight lang="python3" line="1">
def cauta_in_matrice(matrice, numar):
def cautare_in_matrice(matrice, p, numere_cautate):
     for i in range(len(matrice)):
    rezultate = []
        for j in range(len(matrice[i])):
 
     for numar in numere_cautate:
        gasit = False
        i, j = 0, 0
 
        while i < len(matrice) and j < len(matrice[0]):
             if matrice[i][j] == numar:
             if matrice[i][j] == numar:
                 return i + 1, j + 1  # Adăugăm 1 pentru a afișa linia și coloana în formatul din enunț
                 gasit = True
    return 0, 0 # Numărul nu a fost găsit în matrice
                rezultate.append((i + 1, j + 1)) # Linia și coloana în matrice (indexare de la 1)
                break
            elif matrice[i][j] < numar:
                i += 1
            else:
                j += 1
 
        if not gasit:
            rezultate.append((0, 0))
 
    return rezultate


def main():
def main():
     # Citirea datelor de intrare din fișier
     # Citim datele de intrare din fișier
     with open("cautanrinmatricein.txt", "r") as f:
     with open("cautanrinmatricein.txt", "r") as f:
         n, m = map(int, f.readline().split())
         n, m = map(int, f.readline().split())
Line 62: Line 77:
         numere_cautate = list(map(int, f.readline().split()))
         numere_cautate = list(map(int, f.readline().split()))


     # Deschiderea fișierului de ieșire pentru scriere
     # Căutăm fiecare număr în matrice
     with open("cautanrinmatriceout.txt", "w") as g:
    rezultate = cautare_in_matrice(matrice, p, numere_cautate)
        # Căutarea și scrierea rezultatelor în fișierul de ieșire
 
         for numar in numere_cautate:
    # Scriem rezultatele în fișierul de ieșire
             linie, coloana = cauta_in_matrice(matrice, numar)
     with open("cautanrinmatriceout.txt", "w") as f:
            g.write(f"{linie} {coloana}\n")
         for rezultat in rezultate:
             f.write(f"{rezultat[0]} {rezultat[1]}\n")


if __name__ == "__main__":
if __name__ == "__main__":
     main()
     main()
</syntaxhighlight>
</syntaxhighlight>



Revision as of 09:05, 27 December 2023

Cerinta

Se dă o matrice cu n linii şi m coloane ce conţine numere naturale astfel încât parcurgând matricea pe prima linie de la stânga la dreapta, pe a doua linie de la dreapta la stânga, pe a treia linie de la stânga la drepta, ş.a.m.d., toate elementele matricei vor forma un şir strict crescător. Fiind date p numere naturale ordonate strict crescător, să se afişeze pentru fiecare numărul liniei şi coloanei unde acesta se găseşte în matrice, respectiv 0 dacă acesta nu se găseşte în matrice.

Date de intrare

Fișierul de intrare cautanrinmatricein.txt conține pe prima linie numerele n şi m reprezentând dimensiunile matricei , pe următoarele n linii câte m numere aranjate conform enunţului reprezentând elementele matricei, pe următoarea linie numărul p, iar pe ultima linie cele p numere în ordine strict crescătoare ce trebuie căutate în matrice.

Date de iesire

Fișierul de ieșire cautanrinmatriceout.txt va conține pe primele p linii numărul liniei şi coloanei pe care se află în matrice fiecare din cele p numere date, respectiv 0 dacă numărul nu se găseşte în matrice.

Restrictii si precizari

  • 1 ⩽ n , m ⩽ 1000
  • elementele matricei sunt numere naturale mai mici decât 2.000.000.000
  • 1 ⩽ p ⩽ 1.000.000
  • cele p numere vor fi mai mici decât 2.000.000.000

Exemplul 1

cautanrinmatricein.txt
3 4
2 5 11 14
29 27 23 19
32 38 44 59
3
11 24 38
Datele introduse corespund restrictiilor impuse.
cautanrinmatriceout.txt
1 3
0
3 2

Exemplul 2

cautanrinmatricein.txt
3 2
5 8
12 19
23 21
Datele introduse nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def cautare_in_matrice(matrice, p, numere_cautate):

   rezultate = []
   for numar in numere_cautate:
       gasit = False
       i, j = 0, 0
       while i < len(matrice) and j < len(matrice[0]):
           if matrice[i][j] == numar:
               gasit = True
               rezultate.append((i + 1, j + 1))  # Linia și coloana în matrice (indexare de la 1)
               break
           elif matrice[i][j] < numar:
               i += 1
           else:
               j += 1
       if not gasit:
           rezultate.append((0, 0))
   return rezultate

def main():

   # Citim datele de intrare din fișier
   with open("cautanrinmatricein.txt", "r") as f:
       n, m = map(int, f.readline().split())
       matrice = [list(map(int, f.readline().split())) for _ in range(n)]
       p = int(f.readline())
       numere_cautate = list(map(int, f.readline().split()))
   # Căutăm fiecare număr în matrice
   rezultate = cautare_in_matrice(matrice, p, numere_cautate)
   # Scriem rezultatele în fișierul de ieșire
   with open("cautanrinmatriceout.txt", "w") as f:
       for rezultat in rezultate:
           f.write(f"{rezultat[0]} {rezultat[1]}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicatie

Numărul 11 se află în matrice pe linia 1 coloana 3, numărul 24 nu se află în matrice, iar numărul 38 se află în matrice pe linia 3, coloana 2.