nizovi & nizovi

[ deda Miloje @ 11.02.2002. 15:14 ] @

Problem:
Niz A[] ima N 16-bitnih clanova, a niz B[] ima N 8-bitnih clanova.
npr A[0000111100001111,...,0011001100110011] a B[11110000,...00001000]
Sad , potrebno je za svaki A[j] proveriti da li u njemu sadrzan njegov odgovarajuci B[j]
(npr A[1]={0000111100001111} sadrzi B[1]={11110000} u sebi)
i izbaciti sve A[j] clanove koji ne sadrze u sebi svoj odgovarajuci B[j]
(recimo ovaj A[n] u primeru ne sadrzi svoj B[n] u sebi)

Ne trazim da mi napisete program, samo dajte neki hint.
Da li moze i kako A[C[j]] i B[D[j]]?
Ako ima neko neki primer niza nizova neka posalje ovde ili na mail.

[ Dragi Tata @ 11.02.2002. 16:30 ] @

Auuu, dobar, dobar! Na "prvu loptu" rešenje bi moglo da bude sledeće:

za svaki "par" koji želiš da proveriš, napravi jednu malu for petlju. U okviru petlje, "zamaskiraj" gornjih 8 bitova u A, pa uporedi sa B. Onda "šiftuj" A udesno, pa tako redom.

Pseudo-kod primer:

Code:

short tempA = A[k];
for (j = 0; j < 8; j++)
{
  short masked = tempA & 0x00ff; // maskiraj gornje bitove
  if (masked == B[k])
  {
   //uslov ispunjen
   ...
   break;
  }
  tempA >> 1;
}

Nego, evo dok čekam da se opere veš (znam šta mislite mangupi, ali pitaću vas kad se oženite) sastavio sam ceo primer (uploadovan uz poruku)

[Ovu poruku je menjao Dragi Tata dana 10.09.2002 u 10:55 AM GMT]

[Ovu poruku je menjao Dragi Tata dana 10.09.2002 u 10:56 AM GMT]

[ jc denton @ 17.02.2002. 06:35 ] @

mozda se butam de ne treba jer radim u VB-u, ali evo ideje pa je prebudzite na C++ :

dim c (n) as long ' to je zeljeni novodobijeni niz
for i =1 to n
if Instr(trim(str(a(i))), trim(str(b(i))), 1) >0 then c(i)=a(i)
next

jebem li ga sta je ekvivalent za Instr u C++ ...

[ Dragi Tata @ 18.02.2002. 21:05 ] @

Citat:

jc denton:
jebem li ga sta je ekvivalent za Instr u C++ ...

Ekvivalent je string::find(). Ali čini mi se da je postavka zadatka bila takva da se na ulazu traži broj, a ne string koji sadrži nule i jedinice. Naravno, uvek možeš iz broja da dobiješ takav niz, ali to je malo "izokola".

[ jc denton @ 19.02.2002. 01:21 ] @

Dobro, uzmimo da je string.

Koja bi metoda bila brza ?

[ Dragi Tata @ 19.02.2002. 01:38 ] @

Citat:

jc denton:
Dobro, uzmimo da je string.

Koja bi metoda bila brza ?

Ako je string, onda je tvoja metoda "prava". Ona koju sam ja naveo gore, radi samo za brojeve.

A inače, šta je brže a šta ne, retko može da se uspešno proceni na osnovu koda. Treba probati pa izmeriti.

[ jc denton @ 19.02.2002. 01:50 ] @

Postavio sam pitanje oko brzine zato sto sam svojevremeno pisao neki SW za tombolu, pa je tu neku pretrazivanje listica itd.

Naguram ti ja sve listice (po 15 dvocifrenih brojeva po listicu) u string, pa tom kverujem preko Instr.

Znas za koliko je nalazio listic na nekih 50 000 * 15 pretrazenih karaktera ?

Na tadasnjem Intel Pentium 133 MHz , cirka 11 sec. !!!

Koliko bi to bilo brzo u C++??

[ Dragi Tata @ 19.02.2002. 02:00 ] @

Citat:

jc denton:

Koliko bi to bilo brzo u C++??

Verovatno bi bilo brže, ali koliko ne bih znao. Treba probati pa videti.

Sa optimizacijom je jedino sigurno to da nikad nisi siguran šta ćeš da dobiješ.

[ deda Miloje @ 22.02.2002. 22:09 ] @

ljudi , thanks

[ sportbili @ 10.09.2002. 19:43 ] @

Citat:

Dragi Tata:

za svaki "par" koji želiš da proveriš, napravi jednu malu for petlju. U okviru petlje, "zamaskiraj" gornjih 8 bitova u A, pa uporedi sa B. Onda "šiftuj" A udesno, pa tako redom.
Pseudo-kod primer:

Code:

short tempA = A;
for (j = 0; j < 8; j++)
{
short masked = tempA & 0x00ff; // maskiraj gornje bitove
if (masked == B)
{
//uslov ispunjen
...
break;
}
tempA >> 1;
}

Stara je tema ali me interesuje samo jedna stvar. Cemu siftovanje A u desno nakon maskiranja? Da li zbog sledeceg:

0011001101011101 (prviniz[0] naprimer) & 0000000011111111 ('A')
i dobijemo 0000000001011101 koji je eventualno druginiz[0].

Onda siftujemo prviniz[0] za 1 u desno i dobijamo
0001100110101110.

OK, ali zasto siftujemo? Da bi smo proverili da li se u njemu (dakle stringu 0001100110101110) sadrzi druginiz[0]? To je pitanje. :-)

Mada ako posmatramo brojeve a ne stringove onda nam ne treba to vec samo prvi slucaj sa maskiranjem?

[ Dragi Tata @ 10.09.2002. 20:05 ] @

Recimo da imamo 16-bitni broj 0011011011011001 i da treba da proverimo da li je niz bitova 01101100 sadržan u njemu.

Najpre zamaskiramo gornjih 8 bitova i dobijemo 0000000011011001. Kad to uporedimo sa 01101100, videćemo da nije isto. Onda šiftujemo gornji broj za jedan udesno i dobijemo 0001101101101100; kad zamaskiramo gornje bitove, to je 0000000001101100 a to jeste jednako 01101100.

Znači, da nismo šiftovali, mi bismo proverili samo da li je 01101100 prvih 8 bitova sa desne strane, a ne bismo znali da li ta kombinacija bitova postoji negde drugde unutar broja.