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

Rekurzivna funkcija-vracanje najveceg indeksa niza

[es] :: C/C++ programiranje :: C/C++ za početnike :: Rekurzivna funkcija-vracanje najveceg indeksa niza

[ Pregleda: 4557 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

marli
Hrvatska

Član broj: 71985
Poruke: 8
*.adsl.net.t-com.hr.



Profil

icon Rekurzivna funkcija-vracanje najveceg indeksa niza26.08.2006. u 22:32 - pre 197 meseci
Postovane kolege,

Spremam se za ispit iz programiranja u C++-u gdje trebam nauciti i rekurzivnu funkciju.
Evo primjera funkcije koju sam nasao u knjizi i koja nema main metode pa ju ne shvacam:
Code:

int indeks(int polje[], int i, int n){
    int tmax;
    if(i>= n - 1) return n - 1;
    tmax = indeks(polje, i + 1, n);
    if(polje[i] > polje[tmax]) return i;
    return tmax;
}

Funkcija treba vratiti indeks najveceg elementa u nizu cjelobrojnih brojeva.Da li bi mi netko mogao napisati ostatak koda,tj. cjelokupni program i eventualno ga komentirati?

Bio bih Vam veoma zahvalan jer je to jedan od vjerovatnih zadataka na ispitu!
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4894
*.static.po.sbb.co.yu.

Jabber: xfiles@elitesecurity.org


+637 Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza27.08.2006. u 09:59 - pre 197 meseci
Citat:

Evo primjera funkcije koju sam nasao u knjizi i koja nema main metode pa ju ne shvacam:

Naravno da nema main(). Ni jedna funkcija se ne zove main(), sem glavne. To sto si pokazao
je samo funkcija, a ne ceo program.

Pod pretpostavkom da je funkcija za rekurzivno izracunavanje max indeksa tacna, ceo kod
bi mogao da izgleda ovako /NETESTIRANO/:

Code:

// zbog printf/scanf
#include "stdio.h"

// zbog onoga system( "PAUSE" )
#include "stdlib.h"

// ovo je tvoja funkcija (pod pretpostavkom da je tacna)
int indeks(int polje[], int i, int n){
    int tmax;
    if(i>= n - 1) return n - 1;
    tmax = indeks(polje, i + 1, n);
    if(polje[i] > polje[tmax]) return i;
    return tmax;
}

// ovde pocinje program
int main()
{
   // ovaj niz cemo predati funkciji da odredi max index niza
   int neki_niz[] = { 4, 5, 3, 0, 10, 2, 3, 3, 9, 1 };

   // promenljive koje definisu interval u kome se vrsi pretraga (mislim da indeksi idu od JEDINICE, a ne od NULE !!!)
   int pocetak, kraj;

   // unos pocetka, npr: 1
   printf( "Upisi odakle pocinje pretraga: " );
   scanf( "%d", &pocetak );

   // unos kraja, npr: 10
   printf( "Upisi dokle ide pretraga: " );
   scanf( "%d", &kraj );

   // ispis sa direktnim izracunavanjem.
   printf( "Indeks najveceg elementa je %d\n", indeks( neki_niz, pocetak, kraj ) );

   // zaustavi program (da se vidi rezultat), pre nego sto nestane sa ekrana
   system( "PAUSE" );
   return 0;
}

 
Odgovor na temu

toxi_programer
Nemanja Todić
Beograd

Član broj: 104396
Poruke: 464
*.smin.sezampro.yu.

Sajt: www.articles411.com


+8 Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza28.08.2006. u 14:48 - pre 197 meseci
@X File , tvoj kod nije valjan a i da napomenem da indexiranje u C/C++ pocinje od 0 ne od 1, vrlo bitna stvar
A evo i ispravnog koda

#include<iostream>
using namespace std;

int index(int polje[], int poc, int kraj)
{
//rekurzivno racunanje najveceg elementa niza polje[]
//bitno je da max bude static!( da joj se ne bi dodelila nula stalno)
static int max = 0;
max = polje[poc] > polje[max] ? poc : max;
if(poc+1 != kraj) index(polje, poc+1, kraj);

return max;
}

int main(void)
{ /*kraj predstavlja velicinu niza( ovo ti i nije potrebno ali posto hoces da f-ji prosledis
i velicinu...*/
const int poc = 0, kraj = 10;
int polje[kraj] = { 45,96,-1,7569,7134,444,1007,4223,1,8 };

//pozovi f-ju koja ce da vrati index najveceg elementa
cout << "Najveci element je " << polje[index(polje, poc, kraj)] << endl;

return 0;
}
 
Odgovor na temu

marli
Hrvatska

Član broj: 71985
Poruke: 8
*.adsl.net.t-com.hr.



Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza28.08.2006. u 22:07 - pre 197 meseci
Postovani kolega Toxi,
Hvala na rijesenju,samo sto program vraca najveci broj a ne najveci index.

Hvala takodjer X-files-u,isprobao sam njegov algoritam i radi,samo sta mislim da bi za pocetak trebalo proslijediti da je i=0,te n kao duljinu niza koji je argument for petlje(u njoj unosimo elemente niza ).
Samo jos da skuzim kako radi ovaj segment koda i na konju sam:
Code:

    tmax = indeks(polje, i + 1, n);
    if(polje[i] > polje[tmax]) return i;
    return tmax;

Ako netko moze da mi prokomentira ili opise ova 3 retka koda,bio bih zahvalan jer mi rekurzije nikako da sjednu.
 
Odgovor na temu

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
*.ptt.yu.

ICQ: 195487525
Sajt: cpptea.com


+1 Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza28.08.2006. u 22:39 - pre 197 meseci
Rekurzija liči na piramidu, građenje kula na kuli, stavljanje kutija u kutije itd. Zavisno od mesta u funkciji na kome se dešava rekurzija, pre ili kasnije će se doći do zadnjeg rekurzivnog poziva (kao da se penješ na piramidu po pravoj liniji) a onda počinje lagano spuštanje (došao si do vrha i nastavljaš pravo, spuštajući se). Prvo će se završiti poslednji poziv funkcije, a prvi tek na kraju po završetku svih ostalih (poslednji stepenik je poslednji na koga si kročio ali prvi ispod čije visine je stalo tvoje stopalo prilikom spuštanja; prvi stepenik je prvi na koga si kročio, ali poslednji ispod čije visine je stalo tvoje stopalo prilikom spuštanja).

Ja ću koracima algoritma koje si naveo dodati i prethodni da bih mogao opisati ponašanje algoritma.

1. provera da li se došlo do kraja niza. ( if(i>= n - 1) )
2. traženje indeksa maksimalnog broja na pozicijama iza i
3. ako je broj sa indeksom i veci od pretho nađenog, vrati i
4. u supritnom vrati taj prethodno nađeni broj

Npr. kod niza 45,96,-1,7569,7134 bi to izgledalo ovako (indeksi iste dubine pripadaju istom pozivu):

1. index(i(=0),n(=5)) - tvoj poziv
1.1. traženje indeksa maksimalnog broja na pozicijama iza 0; to jest index(i(=1),n(=5))
1.1.1 traženje indeksa maksimalnog broja na pozicijama iza 1; to jest index(i(=2),n(=5))
1.1.1.1 traženje indeksa maksimalnog broja na pozicijama iza 2; to jest index(i(=3),n(=5))
1.1.1.1.1 traženje indeksa maksimalnog broja na pozicijama iza 3; to jest index(i(=4),n(=5))
1.1.1.1.2 pošto je ovde i>=n-1 vraca se n-1, tj. 4
1.1.1.2 tmax dobija prethodno vraćenu vrednost 4
1.1.1.3 polje[i(=3)] > polje[tmax(=4)] je true, vraca se i(=3)
1.1.2 tmax dobija prethodno vraćenu vrednost 3
1.1.3 polje[i(=2)] > polje[tmax(=3)] je false, ništa se ne dešava
1.1.4 vraća se tmax(=3)
1.2 tmax dobija prethodno vraćenu vrednost 3
1.3 polje[i(=1)] > polje[tmax(=3)] je false, ništa se ne dešava
1.4 vraća se tmax(=3)
2. tmax dobja prethodno vraćenu vrednost 3
3. polje[i(=0)] > polje[tmax(=3)] je false, nista se ne desava
4. vraca se tmax(=3)

I stvarno, najveci broj niza (7569) ima indeks 3. Ovde je prikazano pet poziva iste funkcije. Višestruko dodeljivanje vrednosti tmax i i ne stvara pometnju jer svaki od pet poziva poseduje svoje sopstvene.

[Ovu poruku je menjao Mali Misha dana 29.08.2006. u 00:05 GMT+1]
Ipak se ++uje.
 
Odgovor na temu

marli
Hrvatska

Član broj: 71985
Poruke: 8
*.adsl.net.t-com.hr.



Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza29.08.2006. u 00:05 - pre 197 meseci
Postovani kolega,

Hvala na iscrpnom odgovoru,sad cu ja malo sjesti pa probat skuziti.
 
Odgovor na temu

toxi_programer
Nemanja Todić
Beograd

Član broj: 104396
Poruke: 464
*.smin.sezampro.yu.

Sajt: www.articles411.com


+8 Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza29.08.2006. u 13:21 - pre 197 meseci
Ma napisao bi ja tebi kod koji je skroz u redu ali nisam, predpostavi zasto
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4894
*.static.po.sbb.co.yu.

Jabber: xfiles@elitesecurity.org


+637 Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza29.08.2006. u 18:50 - pre 197 meseci
Citat:

@X File , tvoj kod nije valjan a i da napomenem da indexiranje u C/C++ pocinje od 0 ne od 1, vrlo bitna stvar

Nisam isprobao program, ali ne znam na sta si mislio...

Naravno da indexi u C/C++ pocinju od NULE ;) Mislim da funkcija vraca index od NULE pa nadalje,
ali sam interfejs cini mi se uzima u obzir JEDINICU kao pocetak (jos jednom kazem, nisam ispitao).


[Ovu poruku je menjao X Files dana 29.08.2006. u 20:02 GMT+1]
 
Odgovor na temu

itf
Zagreb

Član broj: 59794
Poruke: 993
161.53.55.*



+9 Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza31.08.2006. u 10:34 - pre 197 meseci
Citat:
marli: Postovane kolege,

Spremam se za ispit iz programiranja u C++-u gdje trebam nauciti i rekurzivnu funkciju.
Evo primjera funkcije koju sam nasao u knjizi i koja nema main metode pa ju ne shvacam:
Code:

int indeks(int polje[], int i, int n){
int tmax;
if(i>= n - 1) return n - 1;
tmax = indeks(polje, i + 1, n);
if(polje[i] > polje[tmax]) return i;
return tmax;
}

Funkcija treba vratiti indeks najveceg elementa u nizu cjelobrojnih brojeva.Da li bi mi netko mogao napisati ostatak koda,tj. cjelokupni program i eventualno ga komentirati?

Bio bih Vam veoma zahvalan jer je to jedan od vjerovatnih zadataka na ispitu!

Ovo je primjer iz knjige C++ Analiza i primjena. Jel da? Prepoznajem programski kod jer ja sam autor te knjige. Šteta što to nisam prije primjetio pa da dobiješ objašnjenje iz "prve ruke" :) ali i Mali Misha ti je super objasnio.
 
Odgovor na temu

marli
Hrvatska

Član broj: 71985
Poruke: 8
*.cmu.carnet.hr.



Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza01.09.2006. u 08:38 - pre 197 meseci
Da,
Knjiga je C++ Analiza i primjena.Iz nje se spremam za ispit iz c++ i to je jedan od zadataka koji je bio na ispitnom roku.Knjiga je relativno dobra za ucenje i pregledna.
 
Odgovor na temu

itf
Zagreb

Član broj: 59794
Poruke: 993
161.53.55.*



+9 Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza01.09.2006. u 09:05 - pre 197 meseci
Ajd nek je barem relativno dobra :) Hvala
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4894
*.static.po.sbb.co.yu.

Jabber: xfiles@elitesecurity.org


+637 Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza01.09.2006. u 09:08 - pre 197 meseci
ajd' posalji nam e verziju :)
 
Odgovor na temu

itf
Zagreb

Član broj: 59794
Poruke: 993
161.53.55.*



+9 Profil

icon Re: Rekurzivna funkcija-vracanje najveceg indeksa niza01.09.2006. u 11:08 - pre 197 meseci
Citat:
X Files: ajd' posalji nam e verziju :)

Završio bih odmah na sudu :) Sve je pod ugovorom.
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: Rekurzivna funkcija-vracanje najveceg indeksa niza

[ Pregleda: 4557 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

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