Matematické Fórum

kubahosi · 13. 04. 2010 00:33

prosim vas nevedel by nekdo jak na toto zadani?
Zjistěte kolikrát se v celočíselné matici A(m,n) vyskytují jednotlivá čísla z vektoru B(k). Výsledek uložte do vektoru četnosti C(k).
Vstup: m, n, k, matice A, vektor B
Výstup: vektory B, C

marikacz · 13. 04. 2010 17:56

Jestli tomu správně rozumím, tak k je velikost vektoru B, resp. C. V tom případě budeš postupně číst jednotlivé prvky matice. Ke každému prvku najdeš ve vektoru B jeho výskyt, pokud existuje. Zapamatuješ si index h hledaného prvku ve vektoru B a inkrementuješ hodnotu C[h]. Je to takovy primocary postup. Nevím jestli to jde rychleji, asi ano, ale na úkor prostoru.

pseudokod by vypadal takto:

Code:

for(h=0;h<k;h++) C[h]=0;   // inicializace vektoru cetnosti

for(i=0;i<m;i++) {
  for(j=0;j<n;j++) {
     for(h=0;h<k;h++) {
       if(A[i,j]==B[h]) C[h] = C[h]+1;
       break;
     }
  }
}

check_drummer

Určitě by šlo pole B setřídit - tím klesne časová složitost od faktoru ".k" k faktoru .log(k). Ovšem je nutné zvážit i další okolnosti - pokud např. pro všechna i,j,k bude A[i,j] = B[k], pak bude složitost (asymptoticky) stejná jako algoritmu marikacz.

... ovšem pokud bude m.n < log(k), nemá asymptoticky smysl pole B třídit (pokud neobsahuje hodnoty z malého rozsahu, na které by bylo možno aplikovat radixsort)

Matematické Fórum

#1 13. 04. 2010 00:33

informatika

#2 13. 04. 2010 17:56

Re: informatika

Code:

#3 15. 04. 2010 20:26 — Editoval check_drummer (15. 04. 2010 21:03)

Re: informatika

Zápatí