Pripreme za algoritme(24)

Kao što sam već prije najavio objavit će bazu zadataka koje do sada niste mogli naći na web stranicama, a mogu vam puno pomoći pri vježbanju za nadolazeće školsko natjecanje koje je po rasporedu 21. sječnja.
Baza zadataka:

• Zadaci
• Zadaci
• Zadaci 
• Zadaci

Zadaci su preuzeti sa natjecanja III. gimnazije u Zagrebu. A usput ću i proći kroz jedan zadatak.

Zadatak - Arhimed

Malo ograničenje na N (20) odaje da se zadatak može riješiti pažljivo implementiranom brute-force metodom, u kojoj se ispituju sve moguće kombinacije brojeva.
Prema tome zadatak se sastoji od dva dijela:
1. generiranje svih mogućih kombinacija
U rješenju sam generirao sve kombinacije s pomoću bitmaski (trajanje je O(N∙2^N)).
2. pretraživanje svih mogućih kombinacija
Kako je broj rješenja potencijalno velik (2²⁰), potrebno je efikasno pretražiti pronađene brojeve.
U rješenju sve kombinacije sortiramo efikasnim algoritmom za sortiranje (quicksortom) te prolazimo kroz sortirani niz, prebrojavajući jedinstvene vrijednosti.
Generiranje svih kombinacija s pomoću bitmaske
Ideja je da se svaka kombinacija od N brojeva (a ima ih 2^N -1 jer nam kombinacija sa svim nulama ne treba) može prikazati kao binarni broj s N bitova. U tom broju 1 govori da je neki element kombinacije zastupljen, a 0 da nije. Dakle sve kombinacije mogu se prikazati kao brojevi od 1 do 2^N-1.
Za svaku kombinaciju uzimaju se samo onih elementi koji su u toj kombinaciji jedinice.

v[3]=3	v[2]=2	v[1]=1
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

//generiranje suma svih kombinacija s pomoću bit maske
for j:=1 to(2**N)-1 do
begin

komb[j]:=0;

t:=1;

for i:=1 to N do

begin

if j and t = t then komb[j]:=komb[j]+v[i];

t := tshl 1;

end;

end;

Evo toliko za danas. Budući da imate dosta zadataka za rješavanje i ako imate nekakvo pitanje slobodno pitajte. U planu je do samog školskog natjecanja je obraditi još nekoliko algoritama i zadataka.
Pozdrav!