Info2/2008tavasz/kuka
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.