Info2/2008tavasz/kuka

A MathWikiből
A lap korábbi változatát látod, amilyen Wettl (vitalap | szerkesztései) 2008. február 28., 17:53-kor történt szerkesztése után volt.

Tartalomjegyzék

3. előadás (2008-02-29)

Függvényekkel kapcsolatos alapfogalmak

  • függvény
  • visszatérési érték
  • paraméter
  • lokális változó
  • érték szerinti paraméterátadás
  • cím szerinti paraméterátadás
  • mellékhatás
  • rekurzió

Érték szerinti átadás (két változó értékének cseréje)

Az alábbi megoldás nem jól cserél, mert érték szerint veszi át a-t és b-t, tehát a hívás pillanatában lemásolja, és csak a másolatot cseréli, noha az eredetit kéne:

#include <stdio.h>

void rosszcsere(int a, int b) {
  int abak=a;
  a=b;
  b=abak;
}

int main(void) {
  int x=5, y=6;
  printf("csere elott x=%d, y=%d\n", x, y); /* 5, 6 */
  rosszcsere(&x, &y);
  printf("csere utan  x=%d, y=%d\n", x, y); /* 5, 6 -- rossz */
  return 0;
}

Cím szerinti paraméterátadás

~/info2/csere.c -- ez már jó:

#include <stdio.h>

void csere(int *a, int *b) {
  int abak=*a;
  *a=*b;
  *b=abak;
}

int main(void) {
  int x=5, y=6;
  printf("csere elott x=%d, y=%d\n", x, y);
  csere(&x, &y);
  printf("csere utan  x=%d, y=%d\n", x, y);
  return 0;
}

Példa a hatványozás rekurzív számolására (~/szimp2/pow.c):

/** Visszadja a az alap**kitevo hatványozás eredményét.
 * Csak akkor működik helyesen, ha kitevo>=0.
 * pow(0,0)==1
 */
int pow(int alap, int kitevo) {
  if (kitevo<=0) return 1;
  return alap*pow(alap, kitevo-1);
}

Példa moduláris hatványozás rekurzív számolására (~/szimp2/powmod.c):

/** Visszadja a az alap**kitevo hatványozás eredményének modulo modulus vett
 * maradékát.
 * Csak akkor működik helyesen, ha alap>=0 és kitevo>=0 és modulus>=2.
 * powmod(0,0,modulus)==1
 */
int powmod(int alap, int kitevo, int modulus) {
  if (kitevo<=0) return 1;
  return ((alap%modulus)*pow(alap, kitevo-1, modulus))%modulus;
}

Példa moduláris hatványozás rekurzív számolására az előzőnnél gyorsabban (~/szimp2/powmod2.c):

/** Visszadja a az alap**kitevo hatványozás eredményének modulo modulus vett
 * maradékát.
 * Csak akkor működik helyesen, ha alap>=0 és kitevo>=0 és modulus>=2.
 * powmod2(0,0,modulus)==1
 */
int powmod2(int alap, int kitevo, int modulus) {
  int ret;
  if (kitevo<=0) return 1;
  alap%=modulus;
  ret=powmod2(alap, kitevo/2, modulus);
  if (ret!=0) {
    ret=(ret*ret)%modulus;
    if (kitevo%2!=0) ret=(alap*ret)%modulus;
  }
  return ret;
}

A fenti powmod2 például 5 a 11-edikent modulo 10 így számolja ki:

o=5 % 10;
p=o*o % 10;
q=5*p*p % 10;
r=5*q*q % 10;
return r;

Csemegeként (nem kerül számonkérésre) következzen a powmod2 olyan változata, ami a lokális változók értékét nem módosítja (~/szimp2/powmod3.c):

/** Visszadja a az alap**kitevo hatványozás eredményének modulo modulus vett
 * maradékát.
 * Csak akkor működik helyesen, ha alap>=0 és kitevo>=0 és modulus>=2.
 * powmod2(0,0,modulus)==1
 */
int powmod3(int alap, int kitevo, int modulus) {
  int ret;
  if (kitevo<=0) return 1;
  return powmod3b(alap%modulus, kitevo, modulus);
}
/** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
 * kitevo>=0.
 */
int powmod3b(int alap, int kitevo, int modulus) {
  return powmod3c(alap, kitevo, modulus, powmod3b(alap, kitevo/2, modulus));
}
/** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
 * kitevo>=0.
 */
int powmod3c(int alap, int kitevo, int modulus, int fele) {
  if (fele==0) return 0;
  return powmod3d(alap, kitvo, modulus, (fele*fele)%modulus);
}
/** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
 * kitevo>=0.
 */
int powmod3d(int alap, int kitevo, int modulus, int felnegyzet) {
  if (kitevo%2==0) return felnegyzet;
  return (alap*felnegyzet)%modulus;
}

Megjegyzés: a powmod3 függvény Cékla nyelven is működik. A Cékla nyelvet majd a Deklaratív programozás tárgy keretében fogjuk tanulni.

Példa a faktoriális rekurzív számolására (~/szimp2/fakt.c):

int fakt(int n) {
  if (n<2) return 1;
  return n*fakt(n-1);
}

Példa a faktoriális rekurzív számolására akkumulátorral és jobbrekurzióval (~/szimp2/fakt2.c; nem kell érteni, hogy miért jobb a fakt2, mint a fakt):

int fakt2(int n) {
  return fakt2b(n, 1);
}
/** n!*szorzo -t adja vissza. */
int fakt2b(int n, int szorzo) {
  if (n<2) return szorzo;
  return fakt2b(n-1, szorzo*n);
}

Példa a Fibonacci-sorozat rekurzív számolására (~/szimp2/fib.c; ez szerepelt is a táblán előadáson):

int fib(int n) {
  if (n<2) return n;
  return fib(n-1)+fib(n-2);
}

Miért olyan lassú fib(1000)-t kiszámolni? Azért, mert fib(1000)-hez pl. fib(1)-et és fib(2)-t rengetegszer kell kiszámolni, noha elég lenne egyszer is. Ilyenkor az iteratív (értsd: for-ciklusos) megoldás jóval gyorsabb:

Példa a Fibonacci-sorozat iteratív számolására (~/szimp2/fib2.c; ez is szerepelt a táblán):

int fib(int n) {
  int a, b, regib;
  if (n<2) return n;
  a=0; b=1;
  while (n>1) {
    regib=b; b+=a; a=regib;
    n--;
  }
  return b;
}

Példa a legrövidebb közös részstring hosszának rekurzív meghatározására (~/szimp2/lkrh.c). Ezt még nem kell érteni.

int max(int a, int b) {
  return a>b ? a : b;
}
int lkrh(char *s, char *t) {
  if (*s=='\0') return 0; /* ha az s üres, akkor lkrh==0 */
  if (*s=='\0') return 0; /* ha a  t üres, akkor lkrh==0 */
  if (*s==*t) { /* az első karakter azonos */
    return 1+lkrh(s+1, t+1);
  } else {
    return max(lkrh(s+1, t), lkrh(s, t+1));
  }
}

A fenti lkrh függvény túl lassú, mert rekurzív hívásakor ugyanarra az s--t párra többször is meghívódik (és tovább hívja magát rekurzívan). Jó lenne az első hívás után letárolni az eredményt.

Személyes eszközök