Info2/2008tavasz/kuka

A MathWikiből
(Változatok közti eltérés)
149. sor: 149. sor:
 
   1 2 3 4 5 6 7 8 9
 
   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++)
 +
    printf("%d \n", tomb[i]);
 +
  return 0;
 +
}
 +
 +
Kipróbálás:
 +
 +
$ ./beszurorendezes > rendezett # és beírunk 16 álvéletlen számot
 +
86 36 16 58 2 64 40 7 14 31 50 96 54 18 76 61
 +
$ 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:
 +
 +
#include <stdio.h>
 +
int main(void) {
 +
  int a[10][6], b[6][10], n, m;
 +
 +
  for (n=0; n < 10; 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 < 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;
 +
}
 +
 +
Ez nem volt előadáson, de érdekes (segédtömb használata nélkül transzponálja a mátrixot):
 +
 +
~/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 21., 21:35-kori változata

Tartalomjegyzék

2. előadás (2008-02-22)

Változók, alap adattípusok, konstansok

Utasítások

Vigyázzunk a pontosvesszőkre

if (a > b);
  b = a;
if (a > b)
  b = a;
do {
  ...
} while (a < b);
while (a < b) {
  ...
}

Műveletek, relációk

++ --
csak változó előtt/után
i---j
mohó lexikális elemzés miatt = i-- - j
---i
értelmetlen (mohó algoritmus miatt = -- -i)
bitműveletek
~ bitenkénti NOT
& | ^ AND, OR, XOR
logikai műveletek
&& || !

Bitszámlálás*

Számoljuk meg az unsigned i, egészként deklarált szám 2-es számrendszerbeli alakjában az 1-es biteket.

unsigned i;
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 bitet törli (MIÉRT?). Ezt kihasználva cseréljük ki a fenti sort egy vele ekvivalens, de gyorsabbra (amely ráadásul int-nek deklarált i-re is jól fut).

Precedencia (műveletek végrehajtási sorrendje)

if ( a&04 ) ... ;
if ( a&04 != 0 ) ... ;
if ( a & (04!=0) ) ... ;
bajt = felso<<4 + also;
bajt = felso << (4 + also);
bajt = (felso<<4) + also;
bajt = felso<<4 | also;
if ( ( (ev%4 == 0) && (ev%100 != 0) ) || (ev%400 = 0) ) printf("szokoev");
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

Egy <= irány

a = b = c = 0;

Egy => irány

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:

if ( a == 0 )
  if ( b == 0 )
    return 0;
else {
  c = f(a,b);
  return c;
}

Az else mindig a legközelebbi else-nélküli if-hez tartozik!

Javítás: (a kapcsos zárójelek használata segít)

if ( a == 0 ) {
  if ( b == 0 )
    return 0;
} else {
  c = f(a,b);
  return c;
}


Tömbök

Asszimetrikus korlátok

Írjunk Mapleben 1-től, majd k-tól 7-elemű ciklust:

for i from 1 to 7 do ... end do;
for i from k to k+7-1 do ... end do;

A tömbök indexelése 1-től! Szimmetrikus intervallum!

- + - - - - - - + - - -
 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:

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 (for) ciklussal, pl. angol abc, mátrix kinullázása
  • hogyan lehet beszúró rendezéssel egy tömböt rendezni
  • 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++)
    printf("%d \n", tomb[i]);
  return 0;
}

Kipróbálás:

$ ./beszurorendezes > rendezett # és beírunk 16 álvéletlen számot
86 36 16 58 2 64 40 7 14 31 50 96 54 18 76 61 
$ 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:

#include <stdio.h>
int main(void) {
  int a[10][6], b[6][10], n, m;

  for (n=0; n < 10; 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 < 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;
}

Ez nem volt előadáson, de érdekes (segédtömb használata nélkül transzponálja a mátrixot):

~/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;
}
Személyes eszközök