[es] - rekurzija-problem?

edit
Edin Dazdarevic
Sarajevo

Član broj: 23538
Poruke: 14
*.hrc.ba.

Profil

^{13.04.2005. u 13:39 - pre 231 meseci}

Napisati rekurzivnu funkciju koja će odrediti koji se znak u nekom sortiranom znakovnom polju dimenzije n+1 najčešće pojavljuje. Izlazni argument je nađeni znak, a funkcija vraća broj pojavljivanja tog znaka. Prototip funkcije je:
int mode (char *tekst, int n, char *znak);

Za li ko ovo?

bla...bla..bla........

Odgovor na temu

_owl_

Član broj: 318
Poruke: 1043
*.drenik.net.

+3 Profil

Re: rekurzija-problem?

^{13.04.2005. u 14:55 - pre 231 meseci}

Za pocetak mozes da napises i nerekurzivnu funkciju cisto da vidis kako sve to radi (to pretpostavljam znas). Poenta je da ako se neki znak ponavlja onda on moze da se nalazi samo ispred istog takvog znaka (posto je string sortiran). Kod rekurzivne funkcije treba stalno da pozivas mode((tekst+1), n, znak) dok ne dodjes do kraja stringa, tada ces se vratiti unazad i utvrditi koji se znak najvise puta ponavlja (za ovo je potrebno da unutar same funkcije pamtis trenutno najcesce ponavljani znak kao i koliko se puta pojavio do sada).

Owl

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: rekurzija-problem?

^{13.04.2005. u 15:46 - pre 231 meseci}

Mislim da ovo ne moze da se resi potpuno matematicki rekurzivno (tj. jedan znak - jedan poziv funkcije). Za tako nesto kao da nedostaje jedan parametar. Ovo moze da se resi ako se funkcija rekurzivno poziva za grupu istih znakova. Znaci:

- ako je znak '' onda vracas 0 i izlaznu vrednost '',
- brojis iste znakove sve dok ne dodjes do razlicitog znaka,
- za razlicit znak rekurzivno pozoves funkciju,
- povratni rezultat je maksimum od onoga sto je izbrojano i sto je rekurzivni poziv vratio, izlazna vrednost odgovara maksimumu.

Odgovor na temu

Alef
Viktor Kerkez
Novi Sad

Član broj: 505
Poruke: 188
*.041net.co.yu.

Profil

Re: rekurzija-problem?

^{13.04.2005. u 16:20 - pre 231 meseci}

Ovo ja za opšti string… Za sortirani može da se optimizuje…

Code:

int func(char *s, char znak)
{
    if (*s == '\n')
        return 0;
    else if (*s != znak)
        return func(s+1, znak);
    else return 1+func(s+1, znak);
}

Odgovor na temu

RnD57
Djordje Petrovic
Novi Sad

Član broj: 54969
Poruke: 31
*.nat-pool.nsad.sbb.co.yu.

ICQ: 298181189

Profil

Re: rekurzija-problem?

^{13.04.2005. u 21:19 - pre 231 meseci}

@Alef: Ovo je funkcija za rekurzivno brojanje odredjenog znaka u nizu znakova. Ti ni u jednom trenutku ne menjash vrednost parametra 'char znak', sve shto vracash je broj ponavljanja znaka koji je zadat pri prvom pozivu funkcije.
Izgleda da si pogreshno skont'o...

random...

Odgovor na temu

Alef
Viktor Kerkez
Novi Sad

Član broj: 505
Poruke: 188
*.041net.co.yu.

Profil

Re: rekurzija-problem?

^{13.04.2005. u 23:42 - pre 231 meseci}

Tako mi i treba kad me mrzi da pročitam do kraja

. Evo jedna malo nakaradna verzija, dok ne smislim bolje

Code:

int func(char *s, char c)
{
    static int max = 0, tmp = 0, znak = 0;

    if (*s == c) {
        tmp++;
        func(s+1, c);
    } else {
        if (max < tmp) {
            max = tmp;
            znak = *(s-1);
        }
        tmp = 1;
        if (*s != '\0') func(s+1, *s);
    }
    return znak;
}

Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.nat-pool.nsad.sbb.co.yu.

Profil

Re: rekurzija-problem?

^{14.04.2005. u 00:57 - pre 231 meseci}

Evo mog jos nakaradnijeg resenja, ali radi. E posto nisam c-jas nemojte mi zameriti. I nisam uspeo da napravim da i sacuvam koje je to slovo. ???

Code:

int niz[256];

int func(int *niz,char *s, int n , int pos, int max , char maxznak)
{
    *(niz+ *(s+pos))= *(niz+ *(s+pos)) + 1;
    if (pos == n)
    {
        if (*(s+pos)== maxznak)
        {
            return max+1;
        }
        else
        {
            if (*(niz+ *(s+pos))>max)
            {
                return *(niz+ *(s+pos));
            }
            else
            {
                return max;
            }
        }
    }
    {
        if (*(s+pos)== maxznak)
        {
            return func(niz,s,n,pos+1, max + 1 ,maxznak);
        }
        else
        {
            if (*(niz+ *(s+pos))>max) return (func(niz,s,n,pos+1, *(niz+ *(s+pos)), *(s+pos)));
            else return func(niz, s,n,pos+1, max ,maxznak);
        }
    }
}

Don’t do drugs, sleep deprivation is better.

Odgovor na temu

the_beast

Član broj: 53537
Poruke: 1
*.nspoint.net.

Profil

Re: rekurzija-problem?

^{14.04.2005. u 11:40 - pre 231 meseci}

Evo ti moje resenje, nije cista rekurzija, ali mislim da je to otprilike to.

Code:

int mode (char *tekst, int n, char *znak)
{
    int bp, nextbp;
    char c;

    bp=0;
    c=*tekst;

    while(c==*tekst)
    {
        bp++;
        tekst++;
        n--;
        if (n==0)
        {
            *znak=c;
            return bp;
        }
    }

    nextbp=mode(tekst,n,znak);

    if(bp>=nextbp)
    {
        *znak=c;
        return bp;
    }
    else
        return nextbp;
}

Kad ga isprobas recimo sa:

Code:

int main(void)
{
    char cMax;
    int  bpMax;
    char nizslova[]="aaabccccddeeeee fffffff";
    char *pok;
    pok=nizslova;
    bpMax=mode(pok,23,&cMax);
    printf("Najvise se pojavljuje znak %c i to %d puta.",cMax,bpMax);
        return 0;
}

dobijes ono sto treba

Odgovor na temu

rumpl

Član broj: 54959
Poruke: 156
*.net81-67-220.noos.fr.

Profil

Re: rekurzija-problem?

^{14.04.2005. u 12:38 - pre 231 meseci}

Rumpl

int mode(char *str, int n, char *c)
{
static int max = 0;
static int maxcur = 1;

if(!str[n])
return(max);

if(str[n] == str[n+1])
maxcur++;

if(str[n] != str[n+1] && max < maxcur)
{
max = maxcur;
maxcur = 1;
*(c) = str[n];
}

return(mode(str, n+1, c));
}

int main()
{
int i;
char *str;
char a;

str = "aabbbc";
i = mode(str, 0, &a);
printf("%d %c\n", i, a);

return(0);
}
--------------------------------------------------------------------------------

alexscott

int mode(char *str, int n, char *pmax)
{
static int max = 0;
static int cur = 1;

if(!n)
*pmax = (( *str ) ? *str : 0);

if( (! *(str+(n++))) || (! *(str+1)) )
return((!max && *str) ? 1 : max);

if(max < (cur = ( *(str+n-1) == *(str+n) ) ? cur+1 : 1))
{
max = cur;
*pmax = *(str+n);
}

return(mode(str, n, pmax));
}

int main(int argc, char **argv)
{
char c;

printf("%d %c\n", mode(((argc-1) ? argv[1] : ""), 0, &c), c);

return(0);
}

Evo dva resenja na vas zadtak, malko smo se zekili, primeticete da je jedan kod razunljiviji od drugog...
Pozdrav, saljite nam jos zanimljivih zadatcica

"The problem with the world is that everyone is a few drinks behind."
-Humphrey Bogart

Odgovor na temu

rumpl

Član broj: 54959
Poruke: 156
*.net81-67-220.noos.fr.

Profil

Re: rekurzija-problem?

^{14.04.2005. u 12:56 - pre 231 meseci}

Ups, zaboravili smo [ code ] [ / code ]....

Rumpl :

Code:

int mode(char *str, int n, char *c)
{
  static int max = 0;
  static int maxcur = 1;

  if(!str[n])
      return(max);

  if(str[n] == str[n+1])
    maxcur++;

  if(str[n] != str[n+1] && max < maxcur)
    {
      max = maxcur;
      maxcur = 1;
      *(c) = str[n];
    }

  return(mode(str, n+1, c));
}

int main()
{
  int i;
  char *str;
  char a;

  str = "aabbbc";
  i = mode(str, 0, &a);
  printf("%d %c\n", i, a);

  return(0);
}

__________________________________________________________________________

alexscott:

Code:

int mode(char *str, int n, char *pmax)
{
  static int max = 0;
  static int cur = 1;

  if(!n)
    *pmax = (( *str ) ? *str : 0);

  if( (! *(str+(n++))) || (! *(str+1)) )
    return((!max && *str) ? 1 : max);

  if(max < (cur = ( *(str+n-1) == *(str+n) ) ? cur+1 : 1))
  {
    max = cur;
    *pmax = *(str+n);
  }

  return(mode(str, n, pmax));
}

int main(int argc, char **argv)
{
  char c;

  printf("%d %c\n", mode(((argc-1) ? argv[1] : ""), 0, &c), c);

  return(0);
}

"The problem with the world is that everyone is a few drinks behind."
-Humphrey Bogart

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: rekurzija-problem?

^{14.04.2005. u 13:48 - pre 231 meseci}

Statičke promenljive u telu rekurzivne funkcije najčešće nisu dobra ideja. Šta ako neko želi da pozove funkciju iz više niti? U komplikovanijim slučajevima su i izvor bagova.

Odgovor na temu

RnD57
Djordje Petrovic
Novi Sad

Član broj: 54969
Poruke: 31
*.nat-pool.nsad.sbb.co.yu.

ICQ: 298181189

Profil

Re: rekurzija-problem?

^{15.04.2005. u 02:34 - pre 231 meseci}

Evo i moje verzije. Proizvod chamotinje na predavanjima juche. pri prvom pozivu treba za 'n' proslediti 1, a za 'znak' neki char koji sigurno nece biti prvi u stringu [npr. '$']. Tekst se zavrshava znakom '$', a mozhesh i da promenish.

Code:

int mode (char *tekst, int n, char *znak) {
    if (*znak == tekst[0]) n++;
        else n=1;
    int a=0;
    *znak=tekst[0];
    if (tekst[0] != '$') a = mode (tekst+1, n, znak);
    if (n > a) return n;
        else return a;
}

random...

Odgovor na temu

rumpl

Član broj: 54959
Poruke: 156
*.net81-67-220.noos.fr.

Profil

Re: rekurzija-problem?

^{15.04.2005. u 08:15 - pre 231 meseci}

Mihajlo, slazem se sa tobom, ali ako pogledas, mi smo jedini koji su stvarno napravili pravu rekurzivnu funkciju sa prototipom koji je bio postavljen, ne kazem da su ostale lose, samo sto nije to bio zadatak...
Pozdrav

"The problem with the world is that everyone is a few drinks behind."
-Humphrey Bogart

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: rekurzija-problem?

^{15.04.2005. u 09:33 - pre 231 meseci}

Jedno glupo pitanje: da li mi treba da saljemo ovde gotova resenja, ili

uputstva i smernice?

Odgovor na temu