matemātika - matrica

[capsx]

helou visiem.

 

vot man te ir mazinhsh matematikas uzdevums:

 

ir matrica 100x100 katra matricas veertiiba ir skaitlis 1 2 3 ... x ... pedejaa ir 10000

mums ir dotas kaukadas veertiibas, piem. 1,2,3,55,67,78,89,90 ... x ...

uzdevums ir atrast matricu ar noteiktu izmeeru, piem 10x10, kura ir shinii matricaa 100x100 un kura satur visvairaak dotaas veertiibas ( tās 1,2,3,55,67,78,89,90)

 

tikko sāku lauzīt galvu pr šo, bet mož kāds matemātikas cilvēks te apgrozaas :D

 

no offence ...

[codez]

Vienkāršais variants:

uztaisa masīvu 100x100, kurā aizpilda ar viens tos matricas laukus, kuros ir vajadzīgies skaitļi.

Ja masīvs ir NxN un kvadrāts, kurā meklē KxK

Tad pilnā pārlase:

1)variants. Ņemam katru no punku no 0..N-K+1,0..N-K+1 un skaitam ciklā KxK cik tajā kvadrātā ir atzīmes. Apskatot katru KxK kvadrātu saglabājam labāko. Algorima laiks (N-K+1)^2*K^2

2)variants. Ņemam katru no punku no 0..N-K+1,0..N-K+1, bet ņemot nākamo punktu nepārlasām visu KxK kvadrātu, bet norēķinām nonst pēdējo kvadrāta kollonu un pieskaitām klāt nākamo KxK kvadrāta kollonu. Laiks (N-K+1)^2*2K.

 

Cita pieeja:

Ja skaitļi ir salīdzinoši maz.

Pieņemam, ka atzīmēto skaitļu skaits ir P.

Ņemam katru skaitli no P un aprēķinām viņa koordinātes X,Y, tad skaitam cik citu skaitļu iekļaujās X+K-1,Y+K-1 robežās.

Laiks P^2.

Šim variantam var krietni uzlabot ātrdarbību, ja sakārtojam vērtības pa X un Y asīm un tad piemeklējot apskatīt tikai punktus intervālā no X līdz X+K-1 un Y+K-1.

 

 

ūber-profesionālais varaints:

Taisam no punktiem R-tree un tad apskatām katru punktu, kā K*K kvadrāta stūri. Laiks P*ln(P)

Edited November 14, 2008 by codez