Info2/2008tavasz/kuka
1. sor: | 1. sor: | ||
== 3. előadás (2008-02-29) == | == 3. előadás (2008-02-29) == | ||
− | + | Függvényekkel kapcsolatos alapfogalmak: | |
* függvény | * függvény | ||
12. sor: | 12. sor: | ||
* rekurzió | * rekurzió | ||
− | + | === Érték és cím szerinti paraméterátadás === | |
~/info2/parameteratadas.c | ~/info2/parameteratadas.c | ||
33. sor: | 33. sor: | ||
f(x); // f nem változtatja meg x értékét | f(x); // f nem változtatja meg x értékét | ||
printf("x f utan = %d\n",x); | printf("x f utan = %d\n",x); | ||
+ | // x címét &x jelöli | ||
g(&x); // g megváltoztatja x értékét | g(&x); // g megváltoztatja x értékét | ||
printf("x g utan = %d\n",x); | printf("x g utan = %d\n",x); | ||
38. sor: | 39. sor: | ||
} | } | ||
− | ==== | + | ==== 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: | 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: | ||
57. sor: | 58. sor: | ||
return 0; | return 0; | ||
} | } | ||
− | |||
− | |||
~/info2/csere.c -- ez már jó: | ~/info2/csere.c -- ez már jó: | ||
77. sor: | 76. sor: | ||
return 0; | return 0; | ||
} | } | ||
+ | |||
+ | |||
+ | |||
Példa a hatványozás rekurzív számolására (~/szimp2/pow.c): | Példa a hatványozás rekurzív számolására (~/szimp2/pow.c): | ||
84. sor: | 86. sor: | ||
* pow(0,0)==1 | * pow(0,0)==1 | ||
*/ | */ | ||
+ | |||
int pow(int alap, int kitevo) { | int pow(int alap, int kitevo) { | ||
if (kitevo<=0) return 1; | if (kitevo<=0) return 1; | ||
91. sor: | 94. sor: | ||
Példa moduláris hatványozás rekurzív számolására (~/szimp2/powmod.c): | 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. | * maradékát. | ||
* Csak akkor működik helyesen, ha alap>=0 és kitevo>=0 és modulus>=2. | * Csak akkor működik helyesen, ha alap>=0 és kitevo>=0 és modulus>=2. |
A lap 2008. február 28., 19:37-kori változata
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 és cím szerinti paraméterátadás
~/info2/parameteratadas.c
#include <stdio.h> void f (int x) // x egész { x++; } void g (int* px) // px egy cím, ahol egy egész van tárolva { // amelyre *px hivatkozik *px=*px+1; } int main (void) { int x=3; f(x); // f nem változtatja meg x értékét printf("x f utan = %d\n",x); // x címét &x jelöli g(&x); // g megváltoztatja x értékét printf("x g utan = %d\n",x); return 0; }
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; }
~/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.