Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Problem sa sumiranjem

[es] :: Pascal / Delphi / Kylix :: Problem sa sumiranjem

[ Pregleda: 4654 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Bageri
Djordje Milovanovic
Sabac

Član broj: 2530
Poruke: 16
*.rcub.bg.ac.yu



Profil

icon Problem sa sumiranjem13.03.2002. u 16:42 - pre 268 meseci
Problem izgleda ovako:

Imamo dve datoteke(ili nizovi) celobrojnog tipa. Napraviti program koji pravi trecu datoteku koja se sastoji od elemenata druge datoteke koji se mogu dobiti
sabiranjem elemenata prve datoteke(nije vazno koliko sabviraka).

NAPOMENA: Svi algoritmi su pozeljni. Imam neko resenje, ali mislim da se na prostiji nacin moze doci do resenja.
ZDRAVO DJACI!!!
 
Odgovor na temu

Riste Pejov
Team Leader/Senior Software Developer @
Ein-Sof ltd Skopje
Skopje, Macedonia

Član broj: 128
Poruke: 571
212.110.78.*

Jabber: richie@bagra.net.mk
ICQ: 154236769
Sajt: riste.softver.org.mk


Profil

icon Re: Problem sa sumiranjem14.03.2002. u 01:56 - pre 268 meseci
Ako uzmemo da imam tri niza prvi[], drugi[] i rezultat[] onda bi nesto slicno ovome proradilo:
Code:

var:
   p:integer; //counter
.....
function test(Osnov,Cilj,PocetakNiz:integer;NizOstalih:array [1..100] of integer):boolean;
var
k:integer;
begin
for k:=PocetakNiz to 100 do
begin
if (Osnov+NizOstalih[k])=Cilj then
  begin
  test:=true;
  Break;
  end else
  begin
  if test((Osnov+NizOstalih[k]),cilj,k,NizOstalih) then
     begin
     test:=true;
     break;
     end else test:=false;
  end;
end;
end;
//......... kraj funkcije za test sabiranja
// Implementacija funkcije
for p:=1 to 100 do
  begin
  if test(0,drugi[p],1,prvi) then
  rezultat[p]:=1 
else 
  rezultat[p]:=0
  end;


kad se ovo zavrsi onda bi u rezultat[] niz dobio 1 za svakog clana niza drugi[] koji se moze pretstaviti kao zbir clanova niza prvi[], a 0 kad je to nemoguce
MISLIM da bi ovo trebalo raditi, nisam imao vremena probati
jos nesto, u ovom primeru nizovi su od 1 do 100 to prilagodi prema potrebama
People who think they know everything tend to irritate those of us who do.
 
Odgovor na temu

Bageri
Djordje Milovanovic
Sabac

Član broj: 2530
Poruke: 16
*.rcub.bg.ac.yu



Profil

icon Re: Problem sa sumiranjem14.03.2002. u 09:42 - pre 268 meseci
Riste,kod ti nije los, ali ne odgovara bas najbolje zahtevu.
Mozda sam ja konfuzno napisao zahtev ili si ti prevideo.
-U tvom kodu ce ispisati u rezultat, ako su elementi drugog niza suma 1,2 i 3, ispisace ako su suma 1,2,3,4 i 5, ali nece ispisati ako su suma 7,8 i 9, a pogotovo
npr. 3, 8 i 15. Nije vazno koji se clanovi sabiraju!
-Interesuje me resenje kada je nepoznato koliko ima clanova u prvom, odnosno drugom nizu( zbog toga sam napomenuo datoteke-nemaju poznatu gornju granicu broja clanova ).

Vidim da dobro vladas rekurzijama. Ja sam ovako zadat zahtev pokusavao, ali nikad nisam uspeo da resim na taj nacin. Mislim da se pomocu njih moze doci do resenja i da bi to znacajno skratilo ceo zapis.
ZDRAVO DJACI!!!
 
Odgovor na temu

Riste Pejov
Team Leader/Senior Software Developer @
Ein-Sof ltd Skopje
Skopje, Macedonia

Član broj: 128
Poruke: 571
212.110.78.*

Jabber: richie@bagra.net.mk
ICQ: 154236769
Sajt: riste.softver.org.mk


Profil

icon Re: Problem sa sumiranjem14.03.2002. u 13:41 - pre 268 meseci
Ok, sad znam sta se trazi :)
idemo opet :D
sad imamo malu izmenu. To jest, svi nizovi su deklarirani sa nekim blesavim granicama(kao max vrednosti) a broj clanova u nizu t.j. realni kraj pretstavlja
Niz[NizKraj], sto znaci da nas ostali clanovi iza nizKraj ne interesuju.
pretpostavljam da radis u pascalu, posto mi ovo deluje kao zadatak sa etf, i radi toga nisam ni pomenuo dinamicke nizove. Jos nesto je bitno, _pretpostavljam_ da nizovi sadrze striktno pozitivne brojeve, zato sto koristim -1 da oznacim odsustvo broja u nizu. To koristim u slucaju kad je clan niza vec iskoriscen u zbir.
Code:

var: 
p:integer; //counter 
..... 
function test(Osnov,Cilj,NizKraj:integer;NizOstalih:array [1..1000] of integer):boolean; 
var 
k,temp:integer; 
begin 
for k:=1 to NizKraj do 
begin 
test:=false; // pre pocetak iteracije idemo pretpostavkom da zbir ne postoji
if NizOstalih[k]<>-1 then //prvo proveri dali clan niza ne postoji u zbiru
if (Osnov+NizOstalih[k])=Cilj then 
begin 
test:=true; 
Break; 
end else 
begin 
if (Osnov+temp)>Cilj then continue;
{jos jedna optimizacija, ukoliko je zbir veci od onog koji zelimo dobiti nema potrebe od rekurzije jednostavno predji na sledeci clan niza }
temp:=NizOstalih[k];
NizOstalih[k]:=-1; //clan usao u zbir, obrisi ga iz NizOstalih
if test((Osnov+temp),cilj,NizKraj,NizOstalih) then 
begin 
test:=true; 
break; 
end else test:=false; 
end; 
end; 
end; 
//......... kraj funkcije za test sabiranja 
// Implementacija funkcije 
for p:=1 to 100 do 
begin 
if test(0,drugi[p],1,prvi) then 
rezultat[p]:=1 
else 
rezultat[p]:=0 
end; 


Pokusaj ovo ... u najmanju ruku dobices ideju :)
People who think they know everything tend to irritate those of us who do.
 
Odgovor na temu

Bageri
Djordje Milovanovic
Sabac

Član broj: 2530
Poruke: 16
*.gw.krusevac.tehnicom.net



Profil

icon Re: Problem sa sumiranjem16.03.2002. u 16:27 - pre 268 meseci
Riste, cini mi se da ni ova rekurzija nije totalno resenje zadatog zahteva(npr. ako u prvom nizu imamo clanove vrednosti 1,2,3 ,a u trazimo sumu za clan drugog niza vrednosti 4 Osnov ce dobiti vrednost 3 posle sabiranja prva dva clana i ispitace samo (Osnov+temp)>Cilj za treci clan, a nece naci kombinaciju 1+3=4 ,ispravi me ako gresim).
U prvoj poruci sam u NAPOMENI naglasio da imam vec neko resenje. Ono sto me zaista zanima je da li i kako ovaj zadatak moze da se resi pomocu rekurzija, jer sam ja prvo pokusao tako da ga resim i nikako nisam mogao da uspem.
Ako te ne mrzi pokusaj da mi das kompletno resenje, a ja cu ti sad poslati moje resenje zauzvrat za koje mislim da je veoma zanimljvo i primenjivo na mnoge jos komplikovanije zadatke. Ako ti nikad nije palo na pamet nesto ovako nadam se da ce ti pomoci u resavanju nekog komplikovanijeg problema.
Code:

...............
function test(broj,brojel,cilj:integer;prvi:array [1..1000] of integer);
var i,k,do,mo,suma:integer;
begin
 test:=false;
 for I:=3 to broj do
  begin
  k:=1;
  suma:=0;
  do:=i;
  while k<=brojel do 
    begin
    mo:=do mod 2;
    do:=do div 2;
    suma:=suma+prvi[k]*mo;
    k:=k+1;    
    end;  
  if suma=cilj then begin
                           test:=true;
                           break;
                           end;  
  end;
end; 
//..........   kraj funkcije
begin
//............  odredjivanje vrednosti promenjive broj
  broj:=1;
  for j:=1 to brojel do
     broj:=broj*2;
  broj:=broj-1;
// implementacija funkcije
  for j:=1 to brojel2 do
    if test(broj,brojel,drugi[j],prvi ) then treci[j]:=1
                                                  else treci[j]:=0; 


Sve kombinacije se kupe tako sto se odgovarajuci brojevi niza mnoze odgovarajucim elementima binarnog zapisa (npr. ako je niz od pet clanova iako je binarni zapis 10110 to je zbir prvog,treceg i cetvrtog clana). Primetio si da je promenjiva broj tako odredjena da joj je binarni zapis sve jedinice.
Jedino sto ce ovakva funkcija ispisati i neke elemente drugog niza koji su pojavljuju samo jednom u prvom nizu(npr. za binarni zapis 10000), ali i to moze lako da se ostrani.
Slicne funkcije mogu da se primene u mnogim tezim zadacima(npr. azbuka reda cetiri za prolazak kroz matricu ).

Riste, molim te posali mi ovaj zadatak resen preko rekurzija, ako uspes da ga resis.

Uzgred, nisam sa ETF-a, nego sa FON-a. POZDRAV!
ZDRAVO DJACI!!!
 
Odgovor na temu

Riste Pejov
Team Leader/Senior Software Developer @
Ein-Sof ltd Skopje
Skopje, Macedonia

Član broj: 128
Poruke: 571
*.mt.net.mk

Jabber: richie@bagra.net.mk
ICQ: 154236769
Sajt: riste.softver.org.mk


Profil

icon Re: Problem sa sumiranjem18.03.2002. u 14:04 - pre 268 meseci
Generalno rekurzija je LOSE resenje !
ukoliko se problem moze resiti bez rekurzija, resenje je brze i zahteva manje resura,

zamisli samo koliko puta bi se u mom algoritmu trebao alocirati nov stek
za svaku instancu funkcije. rekurzije se primenjavaju samo u nekim
extremnim slucajevima kad se problem ne moze resiti preko obicnih iteracija
( ali kad mozes resiti nesto rekurzijom onda MORA da moze i bez nje )

btw, moje resenje radi (uz male ispravke)
1:
Code:

....
temp:=NizOstalih[k];  // ovaj red treba biti ispred testa osnov+temp>cilj 
if (Osnov+temp)>Cilj then continue; 
{jos jedna optimizacija, ukoliko je zbir veci od onog koji zelimo dobiti nema 
potrebe od rekurzije jednostavno predji na sledeci clan niza } 
//temp:=NizOstalih[k];  red kojeg smo prebacili gore !
NizOstalih[k]:=-1; //clan usao u zbir, obrisi ga iz NizOstalih 
...

2:
Code:

....
for p:=1 to DrugiKrajNiz do 
begin 
//ostala greska iz prve implementacije umesto if test(0,drugi[p],1,prvi) then  treba
//PrviKrajNiz oznacava kraj prvog niza, a DrugiKrajNiz oznacava kraj drugog niza
if test(0,drugi[p],PrviKrajNiz,prvi) then 
rezultat[p]:=1 
else 
rezultat[p]:=0 
end; 
...

People who think they know everything tend to irritate those of us who do.
 
Odgovor na temu

Bageri
Djordje Milovanovic
Sabac

Član broj: 2530
Poruke: 16
*.rcub.bg.ac.yu



Profil

icon Re: Problem sa sumiranjem25.03.2002. u 11:46 - pre 267 meseci
Riste, hvala ti sto si se potrudio oko ove rekurzije.
Nadam se da cemo se ubuduce opetsresti pri resavanju nekog problema.
ZDRAVO DJACI!!!
 
Odgovor na temu

[es] :: Pascal / Delphi / Kylix :: Problem sa sumiranjem

[ Pregleda: 4654 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.