Info2/2008tavasz/kuka

A MathWikiből
(Változatok közti eltérés)
1. sor: 1. sor:
== 3. előadás (2008-02-29) ==
+
== 4. előadás (2008-03-07) ==
  
Függvényekkel kapcsolatos alapfogalmak:
+
=== Karakterláncok (sztringek) ===
  
* függvény, visszatérési érték, paraméter
+
* karakterlánc = karakterek tömbje, melyet egy 0-kódú karakter zár. Pl.
* függvény definíciója
+
  E  z \n e  g  y      \" a   r  a  k  t  e  r  l  a  n  c  \" \0
  visszatérési_érték_típusa függvénynév ( formális paraméterek listája vesszővel elválasztva )
+
69 122 10 101 ...      32  34 ...                                                  0
  {
+
  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ó''
+
** a visszatérési érték nem lehet tömb vagy függvény, de lehet ezeket megcímzõ mutató,
+
  
* 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 ===
+
Az alábbi programban összefűzünk két karaketrláncot úgy, hogy az első végéről levesszük a '\0' karaktert, majd odamásoljuk a második karakterláncot, amit '\0'-val zárunk.
  
~/info2/parameteratadas.c
+
~/info2/osszefuz.c
  
 
  #include <stdio.h>
 
  #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;
 
}
 
 
===Statikus változó===
 
 
~/info2/static.c
 
 
/* statikus <-> automatikus változók */
 
#include <stdio.h>
 
 
 
void fv1(void);
 
void fv2(void);
 
 
   
 
   
 
  int main(void)
 
  int main(void)
 
  {
 
  {
   int i;
+
   char str1[60]="Ez\negy \"karakterlanc\"";
   for(i = 0; i < 4; i++ )
+
   //  char str1[60]="Ez egy \"karakterlanc\", de nagyon-nagyon hosszu";
   {
+
   char str2[60]=", ez pedig egy masik, amiben van \\.";
    fv1();
+
  unsigned sz1 = 0;
    fv2();
+
   unsigned sz2 = 0;
   }
+
  return 0;
+
}
+
 
   
 
   
/* fv1 automatikus változóval */
+
  while (str1[sz1]) sz1++;   // az első karakterlánc hossza
void fv1(void)
+
   while (str2[sz2]) sz2++;   // a második karakterlánc hossza
{
+
  int szamlalo = 0;
+
   printf("fv1:          szamlalo = %d\n", ++szamlalo );
+
}
+
 
   
 
   
/* fv2 statikus változóval */
+
  if(sizeof str1 < sz1 + sz2 + 1)
void fv2(void)
+
    printf("\nAz osszefuzes nem fog menni.\n");
{
+
  else {
  static int szamlalo = 0;
+
    sz2 = 0;
  printf("fv2: statikus szamlalo = %d\n", ++szamlalo );
+
    while(str2[sz2]) str1[sz1++] = str2[sz2++];
}
+
   
 
+
    str1[sz1] = '\0';        // 0-val zárjuk a karakterláncot
 
+
    printf("\n%s\n", str1);
===Rekurzió===
+
    printf("%d %d %d %d\n",str1[0],str1[1],str1[2],str1[3]);
 
+
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;
 
   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
 
 
~/info2/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 (~/info2/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;
 

A lap 2008. március 6., 21:15-kori változata

4. előadás (2008-03-07)

Karakterláncok (sztringek)

  • karakterlánc = karakterek tömbje, melyet egy 0-kódú karakter zár. Pl.
E   z  \n  e   g   y       \"  k   a   r   a   k   t   e   r   l   a   n   c   \" \0
69 122 10 101 ...      32  34 ...                                                  0


Az alábbi programban összefűzünk két karaketrláncot úgy, hogy az első végéről levesszük a '\0' karaktert, majd odamásoljuk a második karakterláncot, amit '\0'-val zárunk.

~/info2/osszefuz.c

#include <stdio.h>

int main(void)
{
  char str1[60]="Ez\negy \"karakterlanc\"";
  //  char str1[60]="Ez egy \"karakterlanc\", de nagyon-nagyon hosszu";
  char str2[60]=", ez pedig egy masik, amiben van \\.";
  unsigned sz1 = 0;
  unsigned sz2 = 0;

  while (str1[sz1]) sz1++;   // az első karakterlánc hossza
  while (str2[sz2]) sz2++;   // a második karakterlánc hossza

  if(sizeof str1 < sz1 + sz2 + 1)
    printf("\nAz osszefuzes nem fog menni.\n");
  else {
    sz2 = 0;
    while(str2[sz2]) str1[sz1++] = str2[sz2++];
   
    str1[sz1] = '\0';        // 0-val zárjuk a karakterláncot
    printf("\n%s\n", str1);
    printf("%d %d %d %d\n",str1[0],str1[1],str1[2],str1[3]);
  }
  return 0;
}
Személyes eszközök