Info2/2008tavasz/kuka

A lap 2008. február 29., 00:07-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
• függvény definíciója

visszatérési_érték_típusa  függvénynév ( formális paraméterek listája vesszővel elválasztva )
{
  utasitasok;
}

• • a blokkok egymásba ágyazhatók, de függvény nem definiálható függvényben
  • minden itt definiált változó lokális változó
• prototípus

visszatérési_érték_típusa  függvénynév ( formális paraméterek listája vesszővel elválasztva );

• függvényhívás

függvénynév ( aktuális paraméterek listája vesszővel elválasztva );

• • a függvény első hívása előtt vagy a definíciónak vagy a prototípusnak szerepelnie kell;

int fv ( int a )
{
  ...
}
main() {
  fv(x);
}

vagy

int fv ( int a );
main() {
  fv(x);
}
int fv ( int a )
{
  ...
}

• • formális paraméter ill. aktuális paraméter más elnevezéssel paraméter ill. argumentum
• érték szerinti paraméterátadás -- cím szerinti paraméterátadá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;
}

Rekurzió

Példa a faktoriális rekurzív számolására (~/info2/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 (~/info2/fakt2.c; nem kell érteni, hogy miért jobb a fakt2, mint a fakt):

#include <stdio.h> 

unsigned long fakt2b(int n, unsigned long szorzo) {
  if (n<2) return szorzo;
  return fakt2b(n-1, szorzo*n);
}

unsigned long fakt2(int n) {
  return fakt2b(n, 1);
}

int main(void)
{
  int n;
  while(1 == scanf("%d", &n)){
    printf("%lu\n",fakt2(n));
  }
  return 0;
}

Példa a Fibonacci-sorozat rekurzív számolására

~/info2/fib.c

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

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 hatványozás rekurzív számolására (~/info2/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 (~/info2/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;