Info2/2008tavasz/kuka

A MathWikiből
(Változatok közti eltérés)
1. sor: 1. sor:
== 2. előadás (2008-02-22) ==
+
== 3. előadás (2008-02-29) ==
  
===Változók, alap adattípusok, konstansok===
+
=== 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ó
  
===Utasítások===
+
==== Érték szerinti átadás (két változó értékének cseréje) ====
  
====Vigyázzunk a pontosvesszőkre====
+
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:
  
  if (a > b);
+
  #include <stdio.h>
   b = a;
+
 +
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;
 +
}
  
if (a > b)
+
==== Cím szerinti paraméterátadás ====
  b = a;
+
  
do {
+
~/info2/csere.c -- ez már jó:
  ...
+
} while (a < b);
+
  
  while (a < b) {
+
  #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;
 
  }
 
  }
  
====Műveletek, relációk====
+
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 változó előtt/után
+
  * Csak akkor működik helyesen, ha kitevo>=0.
;i---j
+
  * pow(0,0)==1
:mohó lexikális elemzés miatt = i-- - j
+
  */
;---i
+
int pow(int alap, int kitevo) {
:értelmetlen (mohó algoritmus miatt = -- -i)
+
  if (kitevo<=0) return 1;
 +
  return alap*pow(alap, kitevo-1);
 +
}
  
;bitműveletek
+
Példa moduláris hatványozás rekurzív számolására (~/szimp2/powmod.c):
:~ bitenkénti NOT
+
:& | ^ AND, OR, XOR
+
  
;logikai műveletek
+
/** 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;
 +
}
  
====Bitszámlálás*==== 
+
Példa moduláris hatványozás rekurzív számolására az előzőnnél gyorsabban (~/szimp2/powmod2.c):
  
Számoljuk meg az unsigned i, egészként deklarált szám 2-es
+
/** Visszadja a az alap**kitevo hatványozás eredményének modulo modulus vett
számrendszerbeli alakjában az 1-es biteket.
+
  * 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;
 +
}
  
unsigned i;
+
A fenti powmod2 például 5 a 11-edikent modulo 10 így számolja ki:
int sz;
+
...
+
for (sz=0; i != 0; i >>= 1) if (i & 01) sz++;
+
...
+
  
Ha i 2-es komplemens alakban van tárolva, akkor i&(i-1) az utolsó 1-es
+
o=5 % 10;
bitet törli (MIÉRT?). Ezt kihasználva cseréljük ki a fenti sort egy vele
+
p=o*o % 10;
ekvivalens, de gyorsabbra (amely ráadásul int-nek deklarált i-re is
+
q=5*p*p % 10;
jól fut).
+
r=5*q*q % 10;
 +
return r;
  
====Precedencia (műveletek végrehajtási sorrendje)====
+
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):
  
  if ( a&04 ) ... ;
+
  /** 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);
 +
}
  
  if ( a&04 != 0 ) ... ;
+
  /** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
  if ( a & (04!=0) ) ... ;
+
  * kitevo>=0.
 +
  */
 +
  int powmod3b(int alap, int kitevo, int modulus) {
 +
  return powmod3c(alap, kitevo, modulus, powmod3b(alap, kitevo/2, modulus));
 +
}
  
  bajt = felso<<4 + also;
+
  /** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
  bajt = felso << (4 + also);
+
  * 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);
 +
}
  
  bajt = (felso<<4) + also;
+
  /** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
  bajt = felso<<4 | also;
+
  * kitevo>=0.
 +
  */
 +
  int powmod3d(int alap, int kitevo, int modulus, int felnegyzet) {
 +
  if (kitevo%2==0) return felnegyzet;
 +
  return (alap*felnegyzet)%modulus;
 +
}
  
if ( ( (ev%4 == 0) && (ev%100 != 0) ) || (ev%400 = 0) ) printf("szokoev");
+
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.
if ( (ev%4 == 0 && ev%100 != 0) || ev%400 = 0 ) printf("szokoev");
+
if ( ev%4 == 0 && ev%100 != 0 || ev%400 = 0 ) printf("szokoev");
+
  
====Kiértékelési sorrend====
+
Példa a faktoriális rekurzív számolására (~/szimp2/fakt.c):
  
Egy <= irány
+
int fakt(int n) {
 +
  if (n<2) return 1;
 +
  return n*fakt(n-1);
 +
}
  
a = b = c = 0;
+
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):
  
Egy => irány
+
  int fakt2(int n) {
 
+
   return fakt2b(n, 1);
  if ( n!=0 && osszeg/n < atlag ) ... ;
+
if ( n==0 || osszeg/n < epszilon ) ... ;
+
 
+
====Lógó else====
+
 
+
Helyes:
+
 
+
if ( a == 0 )
+
   if ( b == 0 )
+
    return 0;
+
  else {
+
    c = f(a,b);
+
    return c;
+
  }
+
 
  }
 
  }
  
Helytelen:
+
/** n!*szorzo -t adja vissza. */
 
+
  int fakt2b(int n, int szorzo) {
  if ( a == 0 )
+
   if (n<2) return szorzo;
   if ( b == 0 )
+
   return fakt2b(n-1, szorzo*n);
    return 0;
+
else {
+
   c = f(a,b);
+
  return c;
+
 
  }
 
  }
  
Az else mindig a legközelebbi else-nélküli if-hez tartozik!
+
Példa a Fibonacci-sorozat rekurzív számolására (~/szimp2/fib.c; ez szerepelt is a táblán előadáson):
  
Javítás: (a kapcsos zárójelek használata segít)
+
  int fib(int n) {
 
+
   if (n<2) return n;
  if ( a == 0 ) {
+
   return fib(n-1)+fib(n-2);
   if ( b == 0 )
+
    return 0;
+
} else {
+
   c = f(a,b);
+
  return c;
+
 
  }
 
  }
  
 +
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:
  
===Tömbök===
+
Példa a Fibonacci-sorozat iteratív számolására (~/szimp2/fib2.c; ez is szerepelt a táblán):
  
====Asszimetrikus korlátok====
+
  int fib(int n) {
 
+
  int a, b, regib;
Írjunk Mapleben 1-től, majd k-tól 7-elemű ciklust:
+
  if (n<2) return n;
 
+
   a=0; b=1;
  for i from 1 to 7 do ... end do;
+
   while (n>1) {
for i from k to k+7-1 do ... end do;
+
     regib=b; b+=a; a=regib;
 
+
    n--;
A tömbök indexelése 1-től! Szimmetrikus intervallum! Az intervallum hossza = felső határ - alsó határ + 1.
+
 
+
- + - - - - - - + - - -
+
  0 1 2 3 4 5 6 7 8 9
+
    ^          ^
+
- + - - - - - - + - - -
+
  1 2 3 4 5 6 7 8 9
+
    ^          ^
+
 
+
Írjunk C-ben 0-tól, majd k-tól 7-elemű ciklust! Az intervallum hossza = felső határ - alsó határ.
+
 
+
for ( i=0; i<7; i++) ... ;
+
for ( i=k; i<k+7; i++) ... ;
+
 
+
A tömbök indexelése 0-tól! Aszimmetrikus intervallum!
+
 
+
- + - - - - - - + - -
+
    0 1 2 3 4 5 6 7 8
+
    ^            ^
+
- + - - - - - - + - -
+
  1 2 3 4 5 6 7 8 9
+
    ^            ^
+
 
+
====Tömbök definiálása, deklarálása====
+
 
+
* [''0''..''(n-1)''] indexeljük az ''n'' elemű tömböt
+
** tömbelem hozzáférése nagyon gyors (konstans időben történik)
+
** nagy félrecímzés általában gyors és feltűnő, kicsi félrecímzés alattomos és nehezen felderíthető hibához vezet
+
* több (pl. kettő) dimenziós tömbök definiálása és deklarálása
+
* tömbelemek inicializálása (<tt>for</tt>) ciklussal, pl. angol abc, mátrix kinullázása
+
* hogyan lehet beszúró rendezéssel egy tömböt rendezni
+
** költsége O(<math>n^2</math>), viszont nincs járulékos tárhely igénye
+
** <tt>#define MAX 0x100</tt> után a fordító <tt>MAX</tt>-ot 0x100-ra fogja mindig kicserélni
+
** az algoritmus működéséről egy szép animáció: http://www.cs.bme.hu/~gsala/alg_anims/3/isort-e.html
+
* hogyan lehet mátrixot transzponálni
+
* a "%6d" formázó sztringgel a printf a 6-nál nem több számjegyű számokat „szépen”, jobbra igazítva fogja kiírni
+
* a 0x100 az hexadecimális, azaz 16-os számrendszerben vett 100, tehát 256
+
 
+
~/info2/beszurorendezes.c:
+
 
+
/* A bemenetről beolvasott számokat beszúró rendezéssel rendezi,
+
  * majd kiírja a kimenetre.
+
  */
+
#include <stdio.h>
+
#define MAX 0x10
+
int main(void) {
+
  int tomb[MAX], elem, i, j;  
+
   for(i = 0; i != MAX; i++)
+
    scanf("%d", &tomb[i]);
+
   for (i = 1; i < MAX; i++) {
+
     elem = tomb[i];
+
    j = i-1;
+
    while (j >= 0 && tomb[j] > elem) {
+
      tomb[j+1] = tomb[j];
+
      j--;
+
    }
+
    tomb[j+1] = elem;
+
 
   }
 
   }
  for(i = 0; i != MAX; i++)
+
   return b;
    printf("%d \n", tomb[i]);
+
   return 0;
+
 
  }
 
  }
  
Kipróbálás:
+
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.
  
  $ ./beszurorendezes > rendezett # és beírunk 16 álvéletlen számot
+
  int max(int a, int b) {
86 36 16 58 2 64 40 7 14 31 50 96 54 18 76 61
+
   return a>b ? a : b;
$ sort -n | diff rendezett -   # és beírjuk pontosan ugyanazokat a számokat
+
  }
86 36 16 58 2 64 40 7 14 31 50 96 54 18 76 61
+
# és itt semmit sem szabad kiírnia, hiszen nincs eltérés a Unixos és az
+
  # általunk írt rendezés eredménye között
+
  
~/info2/matrixtranszponalas.c:
+
  int lkrh(char *s, char *t) {
 
+
   if (*s=='\0') return 0; /* ha az s üres, akkor lkrh==0 */
#include <stdio.h>
+
   if (*s=='\0') return 0; /* ha a  t üres, akkor lkrh==0 */
  int main(void) {
+
  if (*s==*t) { /* az első karakter azonos */
   int a[10][6], b[6][10], n, m;
+
     return 1+lkrh(s+1, t+1);
+
  } else {
   for (n=0; n < 10; n++) {
+
     return max(lkrh(s+1, t), lkrh(s, t+1));
     printf("Ird be a(z) %d. sort (6 db számot):\n", n+1);
+
     for(m=0; m < 6; m++) {
+
      scanf("%d", &a[n][m]);
+
    }
+
 
   }
 
   }
 
  for (n=0; n < 10; n++)
 
    for(m=0; m < 6; m++)
 
      b[m][n] = a[n][m];
 
 
  for (n=0; n < 6; n++) {
 
    for(m=0; m < 10; m++) {
 
      // persze kiirhatnank a[m][n]-et is, es akkor nem is kell transzponalni
 
      printf("%6d ", b[n][m]);
 
    }
 
    printf("\n");
 
  }
 
  return 0;
 
 
  }
 
  }
  
Segédtömb használata nélkül transzponálja a mátrixot:
+
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.
 
+
~/info2/matrixtranszponalas_helyben.c:
+
+
#include <stdio.h>
+
int main(void) {
+
  int a[6][6], c;
+
  unsigned n, m;
+
+
  for (n=0; n < 6; n++) {
+
    printf("Ird be a(z) %d. sort (6 db számot):\n", n+1);
+
    for (m=0; m < 6; m++) {
+
      scanf("%d", &a[n][m]);
+
    }
+
  }
+
+
  for (n=0; n < 6; n++) {
+
    for (m=n+1; m < 6; m++) {
+
      c=a[n][m]; a[n][m]=a[m][n]; a[m][n]=c;
+
    }
+
  }
+
       
+
  for (n=0; n < 6; n++) {
+
    for (m=0; m < 6; m++) {
+
      printf("%6d ", a[n][m]);
+
    }
+
    printf("\n");
+
  }
+
  return 0;
+
}
+

A lap 2008. február 28., 17:53-kori változata

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