Info2/2008tavasz/C

A MathWikiből
A lap korábbi változatát látod, amilyen Wettl (vitalap | szerkesztései) 2008. március 14., 16:44-kor történt szerkesztése után volt.

Tartalomjegyzék

1. gyakorlat (2008-02-12 és 2007-02-15)

A gyakorlat célja, hogy a C nyelvű programozáshoz használandó eszközökkel megismerkedjünk. A bemutatott eszközök: kate, gcc, terminálablak. A gyakorlatnak nem célja megtanítani, hogy a program (pl. hello100.c) hogyan működik, miért azt csinálja, amit csinál, ezt majd előadáson tanuljuk meg.

Linuxos környezet

A PageUp-pal és PageDown-nal történő history-kereséshez az ~/.inputrc fájlukba írjuk bele:

set meta-flag on
set input-meta on
set convert-meta off
set output-meta on
"\e[5~": history-search-backward
"\e[6~": history-search-forward

Ezután vagy nyissunk új terminálablakot, vagy adjuk ki:

$ bind -f ~/.inputrc

Az aktuális terminálablakban használhatjuk a history parancsot, egy már becsukott terminálablak esetén pedig a ~/.bash_history fájlt. Érdemes e fájlból a legfontosabb parancsokat másik fájlba írni, mert a bash a régi bejegyzéseket eldobja. A limit megnövelhető, ha a ~/.bashrc-nkbe elhelyezzük az alábbi sort:

export HISTSIZE=9999    

Az első C program

Az info2 mappát és a tartalmát csupa kisbetűvel kell létrehozni, vagy ha nagybetűs lett, akkor át kell nevezni kisbetűre.

A kate nevű szövegszerkesztőt használjuk.

~/info2/hello.c:

#include <stdio.h>
int main(void) {
  printf("Hello, World!\n");
  return 0;
}

A sor elején levő szóközök (az ún. behúzás angolul indentation) nem a gép számára, hanem a programot olvasó ember számára hasznosak.

Hasznos parancsok (csak a $ utáni részt kell begépelni, a többit a gép írja ki).

$ mkdir ~/info2
$ cd ~/info2
$ kate hello.c
$ gcc -W -Wall -s -O2 -o hello hello.c
$ ./hello
Hello, World!

A kate parancsot indíthatjuk menüből is, vagy külön terminálablakból, és akkor a következő parancs kiadásához nem kell kilépni belőle.

A gcc-parancssor elemeinek jelentése

Ezt nem kell tudni, csak tájékoztatásul került a wikibe. Az alábbi parancsot elemezzük:

$ gcc -W -Wall -s -O2 -lm -o <program> <program>.c
  • gcc: a fordítóprogram neve. A GNU C Compiler és egyben a GNU Compiler Collection rövidítése. Házi feladat a Wikipédián utánanézni, mi az a GNU.
  • -Wall: a legfontosabb figyelmeztető üzeneteket (warning) bekapcsolja
  • -W: még néhány fontos figyelmeztető üzenetet bekapcsol
  • -s: a fölösleges részeket (pl. nyomkövetési információk és szimbólumok) eltávolítja kimenetből. Nélküle nagyobb lenne a kimenet.
  • -O2: bekapcsolja a második szintű optimalizálást. A harmadik szintű azért rossz, mert a kód lassan fordul, és túl nagy lesz. Az első szintű azért rossz, mert a kód túl lassú lesz, és esetleg túl nagy is. Vannak egyéb szintek is, például alapból a nulladik szint érvényes. Nem nulla, hanem nagy O betű van a kapcsolóban.
  • -lm: a matematikai függvényeket (pl. sqrt és cos) tartalmazó matematikai függvénykönyvtárat teszi elérhetőve. Emellett a forráskódban szerepelnie kell még az #include <math.h>-nak is a matematikai függvényekhez. Nem egyes, hanem kis l betű van a kapcsolóban.
  • -o <program>: a kimeneti futtatható fájl nevét adja meg
  • <program.c>: bemeneti forrásfájl nevét adja meg

Kismillió egyéb fordítási opciója is van még a gcc-nek (lásd még man gcc és info gcc), ezek a tárgy elvégzése szempontjából nem érdekesek.

Windows alatt

DevC++ konfigurálása

Nyelv kiválasztása

  • Először nyugodtan válasszuk a magyart mindkétszer, később azonban álljunk át angolra
  • a dev-C++ gyorsbillentyű-beállításai ütik egymást a magyar billentyűzeten a pontosvessző (AltGr+,) kombinációjával, ezért első futtatáskor tedd a következőt:
    "Eszközök" -> "Gyorsbillentyűk konfigurálása" ->
    "Szerkeszés:Megjegyzés Be" ill. "Szerkesztés:Megjegyzés Ki"
    "ESC"<- (törli a gyorsbillentyűt)
    "Ok"<-

Windows alatt a kipróbálás úgy történik, hogy Dev-C++-ban lefordítjuk, majd kézzel futtatjuk. A futtatáshoz tehát nem a Dev-C++ Run menüpontját választjuk (mert az a futás befejeztével eltünteti az ablakot), hanem kézzel nyitunk egy parancssor-ablakot, a megfelelő cd paranccsal belépünk a megfelelő mappába, majd ott dir paranccsal megnézzünk, milyen .exe fájlok vannak (pl. hello.exe), és azok egyikét futtatjuk (pl. hello paranccsal).

Teszt

Futtassuk le az alábbi programot mindkét oprendszer alatt!

~/info2/hello100.c:

#include <stdio.h>
int main(void) {
  int c;
  for (c=0;c<100;c++) {
    printf("Hello, World!\n");
  }
  return 0;
}

A behúzás (beljebbezés) szabályai

A sor elején levő szóközök számára vonatkozó beljebb kezdési szabály (sokféle változata lehetséges, itt csak a tárgy keretében használatosat értelmezzük):

  • Beljebb kezdésre csak szóközöket használunk, tabulátort nem.
  • A záró kapcsos zárójel sosem kerül egy sor végére, hanem előtte mindig soremelés van. A soremelés és a záró kapcsos zárójel közé pontosan annyi szóköz kerül, ahány szóköz volt a hozzá tartozó nyitó kapcsos zárójelet tartalmazó sor elején.
  • Minden egyéb sor elején pontosan kétszer annyi szóköz van, ahány (bezáratlan) kapcsos zárójelen belül van az adott sor.

A beljebb kezdéshez hasznos tippek:

  • A Kate (főleg Enter leütésekor) hajlamos a sor elején 8 egymás utáni szóközöt 1 db tabulátorra cserélni. Ez nekünk nem kívánatos, úgyhogy beszéljük le róla: ikszeljük be a File / Configure Kate / Editor / Indentation / Use spaces instead of tabs to indent jelölőnégyzetet.
  • Egyes fejlesztőkörnyezetnek van Smart indent opciója. Ezt kapcsoljuk át Autoindentre. Sajnos Dev-C++-ban csak Smart indent van. A Smart indent azt csinálja, hogy a soreleji szóközöket igyekszik kváziintelligensen magától meghatározni, pl. ha a sor elején beírunk egy záró kapcsot, magától csökkenti a soreleji szóközök számát. Néha jól, néha rosszul. Kezdetben kapcsoljuk ki, mint hogy figyelnünk kelljen a hibázásaira, és folyamatosan küzdenünk kelljen vele. Később, kipróbálhatjuk a következő beállításokat:

Angol esetén

Auto Indent: checked
Use Tab Character: not checked
Smart Tabs: not checked
Keep Trailing Spaces: checked
Backspace Unindents: checked
Enhanced Home Key: checked

Magyar esetén

Automatikus bekezdés: pipa
Tab használata: üres
Rövid tabok: üres
Sorvégi "space"-ek megtartása: pipa
Visszatörléssel bekezdés ki: pipa
Módosított Home billentyű: pipa
Zárójelpárok kiemelése: pipa  (javasolt)
Tab mérete: 2


További példák

Hasznos parancsok:

$ cd ~/info2
$ kate hello100.c
$ gcc -W -Wall -s -O2 -o hello100 hello100.c
$ ./hello100
Hello, World!
...
Hello, World!
$ ./hello100 | wc -l
100
$ ./hello100 >hello100.out
$ kate hello100.out
$ ./negyzet100 | more
$ ./negyzet100 | less

~/info2/negyzet100.c:

#include <stdio.h>
int main(void) {
  int c;
  for (c=0;c<=100;c++) {
    printf("szam: %3d, negyzete: %5d\n", c, c*c);
  }
  return 0;
}

~/info2/kettohatvany100.c:

#include <stdio.h>
int main(void) {
  int c;
  for (c=0;c<=100;c++) {
    printf("szam: %3d, kettohatvany: %d\n", c, 1<<c);
  }
  return 0;
}

Az a<<b művelet a-t megszorozza 2 a b-edikennel oly módon, hogy `a' bináris alakját `b' bittel balra tolja, és visszaadja az eredményt. Hasonló az a>>b, de szorzás helyett oszt (a 0 felé kerekítve).

Figyeljük meg, hogy 1<<31 már negatív, és 1<<32 == 1. Ezek a túlcsordulás (az előjelbitre csordulás) miatt vannak.

1. előadás (2008-02-15)

A C nyelv

  • története
    • C programozási nyelv: Dennis Ritchie 1972, Bell Telephone Laboratories
    • K&R C 1978 (Brian Kernighan, Dennis Ritchie: The C Programming Language)
    • ANSI (American National Standards Institute) 1989 -> C89
    • ISO (International Organization for Standardization) ISO/IEC 9899:1990 -> C90 (lényegében azonos)
    • ISO 9899:1999 (ANSI 2000) -> C99
    • hatás, utódok: Objective-C, C++, C#
  • tulajdonságai
    • általános célú, blokkstruktúrált, imperatív (utasításokból áll, melyek megváltoztatják a program állapotát), procedurális (az előbbi megvalósítása eljáráshívásokkal) nyelv
    • Unixra készült, ma szinte minden platformon
    • rendszerprogramok, beágyazott rendszerek, alkalmazási programok
    • alacsony szintű memóriahozzáférés, hatékonyan fordul gépi kódra
    • támogatja a gépfüggetlen programozást

Fordítás

A fordítás lépései

gcc -E hello.c >hello.ee    (csak az előfeldolgozó fut le  -> standard outputra ír)
gcc -S hello.c              (fordít, de az assembler nem   -> hello.s -- assembly kód)
gcc -c hello.c              (fordít, de nem szerkeszt      -> hello.o -- object file)
gcc hello.c                 (előfeldolgoz+fordít+szerkeszt -> a.out -- futtatható állomány)

A -o opció nélkül a.out lesz a futtatható állomány neve.

Példák

Állománymásoló három változatban:

~/info2/allomanymasolo1.c

#include <stdio.h>
int main (void)
{
  int c;
  c = getchar();
  while (c != EOF) {
    putchar(c);
    c = getchar();
  }
  return 0;
}

~/info2/allomanymasolo2.c

#include <stdio.h>
int main (void)
{
  int c;
  while ((c = getchar()) != EOF) putchar(c);
  return 0;
}

~/info2/allomanymasolo3.c

#include <stdio.h>
main ()
{
  int c;
  while ((c = getchar()) != EOF) putchar(c);
}

Bájtszámláló

~/info2/bajtszamlalo.c:

/* Megszámolja és kiírja, hogy a bemenet hány bájtból áll.
 * `n=n+1' helyett `n++'-ot írtunk.
 */
#include <stdio.h>
int main(void) {
  int n=0;
  while (0<=getchar()) n++;
  printf("%d\n", n);
  return 0;
}

Kipróbálás:

$ echo sok | ./bajtszamlalo
4
$ echo -n sok | ./bajtszamlalo
3

Sorszámláló

~/info2/sorszamlalo.c:

/* Megszámolja és kiírja, hogy a bemenet hány sorból áll.
 * Az utolsó sor nem számít, ha nincs a végén soremelés.
 */
#include <stdio.h>
int main(void) {
  int c, n=0;
  while (0<=(c=getchar())) {
    if (c=='\n') n++;
  }
  printf("%d\n", n);
  return 0;
}

Kipróbálás:

 $ ls /bin/bash /usr/bin/id /dev/null /etc/inputrc | ./sorszamlalo
 4

~/info2/szoszamlalo.c (ld. K&R alapján)

/* Megszámolja és kiírja, hogy a bemenet hány bájtból,
 * hány szóból és hány sorból áll. Szó a bemenet olyan
 * maximális része, melyben nincs szóköz, tabulátor és
 * újsor karakter.
 */
#include <stdio.h>
#define KINN 0
#define BENN 1
int main(void) {
  int c, bajtok_sz, szavak_sz, sorok_sz, allapot=KINN;
  bajtok_sz=szavak_sz=sorok_sz=0;
  while ((c=getchar()) != EOF) {
    ++bajtok_sz;
    if (c == '\n') sorok_sz++;
    if (c == ' ' || c == '\n' || c == '\t')
      allapot = KINN;
    else if (allapot == KINN) {
      allapot = BENN;
      szavak_sz++;
    }
  }
  printf("%d %d %d\n", bajtok_sz, szavak_sz, sorok_sz);
  return 0;
}

2. gyakorlat (2008-02-19, 22)

SIO megismerése

https://sioweb.math.bme.hu

Tasks Submit solution My submissions

Change password Logout

Available contests

Bemenet fájlból teszteléshez

Ha egy programnak többször akarjuk ugyanazt a bemenetet adni, akkor a bemenetet írjuk be fájlba (pl. prog.in), és irányítsuk át. Ennek segítségével könnyen ellenőrizhető, hogy a program két változata (prog1 és prog2) ugyanazt a kimenetet produkálja-e:

$ ./prog1 <prog.in >prog1.out
$ ./prog2 <prog.in >prog2.out
$ diff prog1.out prog2.out

A diff program kimenetét kell figyelni.

Ha a program bemenetét UNIX-on a terminálon gépeljük be, akkor az alábbiakra figyeljünk:

  • Egy egész sort be kell írni (és Enter-rel lezárni), és a program csak ezután kapja meg az egész sort.
  • A sorvégi Enter-t a program '\n'-ként kapja.
  • A bemenet végét (EOF, -1) Enter, majd Ctrl-D lenyomásával jelezhetjük. Ezután a program következő getchar() hívása -1-et ad vissza, a scanf() pedig (általában) nullát.
  • Windows alatt Ctrl-D helyett Enter, Ctrl-Z, Enter.
  • Ha Ctrl-C-t nyomunk, az örökre megszakítja a program futását, tehát ha a program kilépés előtt még kiírt volna valamit, akkor azt már nem fogja kiírni.

Számkitalálós program (embergondol.c)

Feladat (ember gondol, gép talál ki): Írj C programot, mely egy 'a' és 'b' (legyen pl. a=1, b=100) közé eső számot kitalál az általa föltett kérdésekra adott igen/nem (i/n) válaszokból!

~/info2/embergondol.c

#include <stdio.h>
int main(void) {
  int a=1, b=100, f, c;
  printf("Gondolj egy szamot %d es %d kozott (zart)!\n", a, b);
  while (a!=b) {
    f=(a+b)/2;
    printf("Nagyobb, mint %d?\n", f);
    while ((c=getchar())=='\n') {}
    if (c=='i') a=f+1;
    else if (c=='n') b=f;
  }
  return 0;
}

A program találja ki a gondolt számot. Az ember i-vel vagy n-nel válaszol pl. arra a kérdésre, hogy A gondolt szám nagyobb, mint 50?. Az ember válaszát getchar()-ral kel beolvasni.

Szám beolvasása

~/info2/duplazas.c

#include <stdio.h>
   
int main(void){
  long int tmp;
  while (1==scanf("%d",&tmp)){
    tmp=tmp*2;
    printf("%d\n",tmp);
  }
  return 0;
}


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! 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 (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 
...
61 
$ sort -n | diff rendezett -    # és beírjuk pontosan ugyanazokat a számokat
86 
36 
16 
...
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>
#define SOR 3
#define OSZ 4

int main(void) {
  int a[SOR][OSZ], b[OSZ][SOR], n, m;

  for (n=0; n < SOR; n++) {
    printf("Ird be a(z) %d. sort (%d db számot):\n", n+1, OSZ);
    for(m=0; m < OSZ; m++) {
      scanf("%d", &a[n][m]);
    }
  }

  for (n=0; n < SOR; n++)
    for(m=0; m < OSZ; m++)
      b[m][n] = a[n][m];

  for (n=0; n < OSZ; n++) {
    for(m=0; m < SOR; m++) {
      printf("%6d ", b[n][m]);
      /* persze kiirhatnank a[m][n]-et is, es akkor nem is kell transzponalni */
    }
    printf("\n");
  }
  return 0;
}

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;
}

3. gyakorlat (2008-02-26, 29)

1. Feladat: Írjuk ki az egymilliónál kisebb prímszámokat az Eratoszthenészi szita segítségével ~/info22/erszita1.c néven.

~/info2/erszita1.c:

#include <stdio.h>
int main (void) {
  int i,j;
  char tomb[1000000];
   


  return 0;
}

Kipróbálás:

$ cd ~/info2
$ gcc -W -Wall -s -O2 -o erszita1 erszita1.c
$ ./erszita1 | wc  -l
78498
$ ./erszita1 | head -5
2
3
5
7
11
$ ./erszita1 | tail -5
999953
999959
999961
999979
999983

Egy lehetséges megoldás:

#include <stdio.h>
int main (void) {
  int i,j;
  char tomb[1000000];
  for(i=2;i<1000000;i++) {
    tomb[i]=0;
  }
  for(i=2;i<1000000;i++) {
    if (tomb[i]!=1){
      printf("%d\n", i);
      for (j=2*i; j<1000000; j+=i) {
        tomb[j]=1;
      }
    }
  }
  return 0;
}


2. Feladat: Ezután javítsunk a program sebességén úgy, hogy

  • az 1000 fölötti prímek többszöröseit ne húzza ki (tehát nincs tomb[p]=1), mert azokat már az 1000 alatti prímek többszöröseként kihúzta;
  • ha a talált prím p, akkor csak p*p-től 999999-ig kell kihúzni a többszörösöket.
  • amikor p*p először nő 999999 fölé, kilépünk a for-ciklusból, és egy második for-ciklisban kiírjuk az 1000 fölötti prímeket.

~/info2/erszita2.c:

#include <stdio.h>
char tomb[1000000];
int main (void) {
  int i,j;



  return 0;
}

Kipróbálás ugyanúgy, mint erszita1 esetén, de erszita1 helyett erszita2-vel.

Megjegyzés: nagy tömböket (> kb. 8 MB) a függvényen kívülre érdemes rakni, mert különben Segmentation fault (Szegmens hiba) lesz.

Egy lehetséges megoldás:

#include <stdio.h>
char tomb[1000000];

int main (void) {
  int i,j;
  for (i=2; i<1000000; i++) {
    tomb[i]=0;
  }
  for (i=2; i<1000000; i++) {
    if (i*i>=1000000)
      goto hoppa;
    if (tomb[i]!=1){
      printf("%d\n", i);
      for (j=i*i; j<1000000; j+=i) {
        tomb[j]=1;
      }
    }
  }

hoppa:
  for(; i<1000000; i++) {
    if (tomb[i]!=1)
      printf("%d\n", i);
  }
  return 0;
}

Szorgalmi feladat: Az eratoszthenészi szitát csak a páratlan számokra alkalmazzuk. Tehát például a p=13-nak megfelelő hely a tomb[6], a p=17-nek megfelelő hely pedig a tomb[8]. Ehhez tomb[valami] helyett elég tomb[valami/2]-t írni, és kettesével ugrálni.

~/info2/erszita3.c

#include <stdio.h>
char tomb[500000];
int main (void) {
  int i,j;



  return 0;
}

Egy megoldás:

#include <stdio.h>
char tomb[500000];
int main (void) {
  int i,j;
  for(i=0; i<500000; i++) {
    tomb[i]=0;
  }
  printf("2\n");
  for(i=3;i<1000000;i+=2) {
    if (i*i>=1000000)
      goto hoppa;
    if (tomb[i/2]!=1){
      printf("%d\n", i);
      for (j=i*i; j<1000000; j+=2*i) {
        tomb[j/2]=1;
      }
    }
  }
hoppa:
  for(; i<1000000; i+=2) {
    if (tomb[i/2]!=1)
      printf("%d\n", i);
  }
  return 0;
}


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ó
    • 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 );
    • ha a függvény definíciója az első hívása mögött van, szokás a prototípusát legelőre írni (különben warning):

~/info2/negyzet.c

#include <stdio.h>
int negyzet(int x);
int main(void) {
  printf("%d\n", negyzet(15));
  return 0;
}
int negyzet(int x) {
  return x*x;
}

de persze az is jó, hogy

#include <stdio.h>
int negyzet(int x) {
  return x*x;
}
int main(void) {
  printf("%d\n", negyzet(15));
  return 0;
}
    • 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;
}

Változók

Lokális és globális változók

Változók hatóköre (scope)

~/info2/scope.c

#include <stdio.h>

int main(void)
{
  int i = 0;                             // i a külső blokkban
  do {
    int i = 0;                           // egy másik i
    ++i;                                 // és ez erre vonatkozik
    printf("i = %d\n", i);
  } while( ++i < 5 );                    // ez megint a külső i
  printf("i = %d\n", i);
  return 0;
}

Statikus változók

~/info2/static.c

/* statikus <-> automatikus változók */
#include <stdio.h>
 
void fv1(void);
void fv2(void);

int main(void)
{
  int i;
  for(i = 0; i < 4; i++ )
  {
    fv1();
    fv2();
  }
  return 0;
}

/* fv1 automatikus változóval */
void fv1(void)
{
  int szamlalo = 0;
  printf("fv1:          szamlalo = %d\n", ++szamlalo );
}

/* fv2 statikus változóval */
void fv2(void)
{
  static int szamlalo = 0;
  printf("fv2: statikus szamlalo = %d\n", ++szamlalo );
}

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

~/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;

4. gyakorlat (2008-03-04, 2008-03-07)

Ezen a gyakorlaton a függvények használatát gyakorljuk:

  • a kód egyszerűsítése az ismétlődő feladatok függvénybe rakásával
  • érték szerinti paraméterátadás
  • rekurzió
  • érték módosítása cím szerinti paraméterátadással
  • több érték visszadása cím szerinti paraméterátadással

Feladat: Törtszámösszeadó programot fogunk írni. Minden tört egy egész értékű számálálóból és egy nem nulla egész értékű nevezőből áll. A tört értéke a számláló és a nevező hányadosa. Egy tört egyszerűsítve van, ha a nevezője pozitív, és a számláló és a nevező legnagyobb közös osztója 1. Két tört összeadása úgy történik, hogy először egyszerűsítjük őket (külön-külön); majd képezzük a két nevező legkisebb közös többszörösét; bővítjük mindkét törtét úgy, hogy a közös nevezőjük a legkisebb közös többszörös legyen; a bővített számlálókat összeadjuk; az eredményt egyszerűsítjük.

A törtszámösszeadó program a bemenetről beolvas két törtet as/an, bs/bn formában (valójában négy egész számot), majd kiszámolja az as/an' és bs/bn törtek összegét, és perjellel elválasztva kiírja az eredmény számlálóját (es) és nevezőjét (en) egy sorba. Ezután a következő feladványsor beolvasásásval folytatja.

Példa bemenet (~/info2/tortad1.in):

1/2 3/4
3/4 5/-6
3/4 -5/6
-3/4 5/6
3/6 30/20
-15579/-25862 9268/-90517

Példa kimenet (~/info2/tortad1.exp):

5/4
-1/12
-1/12
1/12
2/1
1/2

A megírandó program vázlata (~/info2/tortad.c):

#include <stdio.h>
#include <stdlib.h>

/* Az a és b pozitív egész számok legnagyobb közös osztóját adja vissza.
 * Tilos negatív számmal hívni.
 */
int lnko(int a, int b) {
  if (a<0 || b<0) abort();
  ... /* Euklideszi algoritmus: ha b==0, akkor a, egyébként ... rekurzió */
}

/* Az a és b pozitív egész számok legkisebb közös többszörösét adja vissza.
 * Tilos 0-val vagy negatív számmal hívni.
 */
int lkkt(int a, int b) {
  if (a<1 || b<1) abort();
  ... /* használjuk az lnko()-t */
}

/* Az s/n törtet egyszerűsíti. A negatívságot felviszi a számlálóba, és
 * mindkét számot leosztja a legnagyobb közös osztójukkal. Nulla nevezővel
 * tilos meghívni.
 */
void egyszerusit(int *s, int *n) {
  if (*n==0) abort();
  ...
}

/* Az as/an törthöz hozzáadja a bs/bn törtet, és az eredményt az es/en
 * törtben adja vissza.
 */
void osszead(int as, int an, int bs, int bn, int *es, int *en) {
  ... /* egyszerűsít, közös nevezőre hoz, összead, egyszerűsít */
}

int main(void) {
  int as, an, bs, bn, es, en;
  while (4==scanf("%d/%d%d/%d", &as, &an, &bs, &bn)) {
    ... /* az osszead() függvényt kell megfelelő paraméterekkel meghívni */
    ... printf("%d\n", es); /* en-t is ki kell még írni egy perjel után */
  }
  return 0;
}

A kész program (~/info2/tortad.c):

#include <stdio.h>
#include <stdlib.h>

/* Az a és b pozitív egész számok legnagyobb közös osztóját adja vissza.
 * Tilos negatív számmal hívni.
 */
int lnko(int a, int b) {
  if (a<0 || b<0) abort();
  if (b==0) return a;
  return lnko(b, a%b);
}

/* Az a és b pozitív egész számok legkisebb közös többszörösét adja vissza.
 * Tilos 0-val vagy negatív számmal hívni.
 */
int lkkt(int a, int b) {
  if (a<1 || b<1) abort();
  return a/lnko(a,b)*b;
  /* ^^^ először osztunk, utána szorzunk, hogy ne legyen túlcsordulás */
}

/* Az s/n törtet egyszerűsíti. A negatívságot felviszi a számlálóba, és
 * mindkét számot leosztja a legnagyobb közös osztójukkal. Nulla nevezővel
 * tilos meghívni.
 */
void egyszerusit(int *s, int *n) {
  int c;
  if (*n==0) abort();
  if (*n<0) {
    *n=-*n;
    *s=-*s;
  }
  if (*s<0) {
    c=lnko(-*s,*n);
  } else {
    c=lnko(*s,*n);
  }
  /* a c-t jobb előre kiszámolni, mert ha lent c helyére lkno(*s,*n) kerülne,
   * akkor a második lnko(*s,*n) már a módosított s-sel számolna, ami nem jó
   */
  *s/=c;
  *n/=c;
  /* nincs return, mert void a visszatérési érték */
}

/* Az as/an törthöz hozzáadja a bs/bn törtet, és az eredményt az es/en
 * törtben adja vissza.
 */
void osszead(int as, int an, int bs, int bn, int *es, int *en) {
  egyszerusit(&as,&an);
  egyszerusit(&bs,&bn);
  *en=lkkt(an,bn);
  *es=(*en/an)*as+(*en/bn)*bs;
  egyszerusit(&*es,&*en);
  /* ^^^ az & az egyszerusit() deklarációjában levő * miatt kell */
  /* ^^^ a  * az osszead()     deklarációjában levő * miatt kell */
  /* ^^^ megjegyzés: &* kihagyható, csak didaktikai okokból van bent */
}

int main(void) {
  int as, an, bs, bn, es, en;
  while (4==scanf("%d%d%d%d", &as, &an, &bs, &bn)) {
    osszead(as, an, bs, bn, &es, &en);
    printf("%d/%d\n", es, en);
  }
  return 0;
}


A kipróbálás előtt készítsük el a mintabemenetet (~/info2/tortad1.in) és a mintakimenetet (~/info2/tortad1.exp), lásd fent. Ezután kipróbálható:

$ cd ~/info2
$ gcc -W -Wall -s -O2 -o tortad tortad.c
$ ./tortad <tortad1.in
5/4
-1/12
-1/12
1/12
2/1
1/2
$ ./tortad <tortad1.in >tortad1.out
$ diff tortad1.exp tortad1.out


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
  • Karakterlánc deklarálása inicializásással:
char str[] = "6 betu";

vele ekvivalens a következő (miért 7?):

char str[7] = "6 betu";
  • Karakterlánc scanf-fel való beolvasásánál nincs & a tömb neve előtt (miért? ld. később).

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);
  }
  return 0;
}

Feladat: Olvassuk be valaki nevét és korát vesszővel elválasztva, majd írjuk ki a nevét és a korát, de az utóbbiból tagadjunk le 10 évet! Használjuk a %[...] formátumot és a stdlib.h atoi nevű függvényét!

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  char nev[60];
  char kor[4];
  int sz1 = 0, sz2 = 0, k = 0; 

  scanf("%[^,], %[0123456789]", nev, kor);
  while (nev[sz1]) sz1++;   // az első karakterlánc hossza
  while (kor[sz2]) sz2++;   // a második karakterlánc hossza
  k=atoi(kor)-10;

  printf("Neved: %s, korod: %d\n", nev, k);

  return 0;
}

Mutató (pointer)

  • Mutató deklarálása:
int *pn;
  • NULL egy (több headerfájlban is definiált) konstans cím, mely a memóriában nem mutat sehová.
int *pn=NULL;
  • A NULL cím egyszerűen tesztelhető, vagyis hogy egy mutatónak adtunk-e már valódi címet: az if(pn==NULL) ekvivalens a if(!pn) kóddal.
  • & a címet adó unér művelet:
int n;
int *pn=&n;
  • (*pn)++ nem ugyanaz, mint *pn++ a precedenciaszabályok miatt.
  • pn++ a *pn típusának megfelelő bájtértékkel növeli a mutató értékét, tehát pl. char esetén 1-gyel, int esetén 4-gyel.
  • a scanf függvény mutatót vár, ezért a következőképp olvashatunk be egész számot:
int n = 0, *pn;
pn=&n;
scanf("%d",pn);

vagy

scanf("%d",&n);

Az alábbi példában az n változóra mutat a pn mutató. Vizsgáljuk meg az értékeiket a (*pn)++; és a pn++; utasítások után!

~/info2/mutato.c

#include <stdio.h>
int main(void)
{
  int n, *pn = NULL;  // pn egy mutató, mely egy egészre mutat
  n = 5;
  pn = &n;

  printf("\nn címe:     %p\n", &n); 
  printf("n mérete:   %d\n", sizeof n);
  printf("n értéke:   %d\n", n);
  printf("pn címe:    %p\n", &pn);
  printf("pn mérete:  %d\n", sizeof pn);
  printf("pn értéke:  %p\n", pn);
  printf("*pn értéke: %d\n", *pn);

  (*pn)++;
  printf("    (*pn)++;\n");
  printf("pn értéke:  %p\n", pn);
  printf("*pn értéke: %d\n", *pn);

  pn++;
  printf("    pn++;\n");
  printf("pn értéke:  %p\n", pn);
  printf("*pn értéke: %d\n", *pn);

  return 0;
}

Egy futás eredménye:

n címe:     0xbfa8d2f0
n mérete:   4
n értéke:   5
pn címe:    0xbfa8d2ec
pn mérete:  4
pn értéke:  0xbfa8d2f0
*pn értéke: 5
    (*pn)++;
pn értéke:  0xbfa8d2f0
*pn értéke: 6
    pn++;
pn értéke:  0xbfa8d2f4
*pn értéke: -1079454960
  • Konstansok:
int n=5;
const int *pn = &n;

esetén *pn értéke konstans, vagyis ez nem változtatható, de n értéke igen.

int c=5;
int *const pc=&c;

esetén pc nem változtatható, de *pc igen.

Tömb és mutató

  • A tömb neve önmagában, index nélkül mutatóként viselkedik (ld. scanf karakterlánc beolvasásánál).

~/info2/tombmutato.c

#include <stdio.h>
int main(void)
{
  int i=0;
  char t[] = "karakterlanc";
  char *p = &t[0];
  printf("a tömb első elemének címe: %p\n", p);
  printf("a tömb címe              : %p\n", t);
  for(; t[i]; i++) 
    printf("%p címen: %c\n", p+i, *(p+i) );

  return 0;
}

ugyanez egészekkel: ~/info2/tombmutato1.c

#include <stdio.h>
int main(void)
{
  int i=0, t[3]={11,12,13};
  int *p = &t[0];
  printf("a tömb első elemének címe: %p\n", p);
  printf("a tömb címe              : %p\n", t);
  for(; i<3; i++) 
    printf("%p címen: %d\n", p+i, *(p+i) );

  return 0;
}
  • a fenti példák alapján tehát: a t tömb t[i] eleme megegyezik *(p+i) vagy *(t+i) értékével, míg a cím, ahol van, a p+i vagy t+i vagy &t[i].
  • egy többdimenziós (pl. t[3][3]) tömb esetén t, t[0] és &t[0][0] mutatók megegyeznek.

~/info2/tombmutato2.c

#include <stdio.h>
int main(void)
{
  int i, j, t[2][2] = { {1,2}, {3,4} };

  for(i=0; i<2; i++) {
    for(j=0; j<2; j++) {
      printf(" %d", *(*t + 2*i + j));
    }
    printf("\n");
  }

  for(i=0; i<4; i++)
    printf(" %d", *(*t + i));
  printf("\n");
  return 0;
}

Az alábbi ábra a t tömb és a t illetve t[0] és t[1] mutatók működését szemlélteti. --> a mutatóból a mutatott helyre mutat, az = az adott címen lévő tartalom ekvivalens megadásait jelenti:

t --> t[0] --> t[0][0] = *t[0] = **t                   t[0][1] = *(t[0]+1) = *(*t+1)
      t[1] --> t[1][0] = *(t[0]+2) = *(*t+2) = *t[1]   t[1][1] = *(t[0]+3) = *(*t+3) = *(t[1]+1)


5. gyakorlat

1. Feladat (Vigenère-titkosítás): Egy olyan szöveget titkosítunk, melyben csak az angol ábécé betűi szerepelnek A-tól Z-ig. A kulcs is csak e betűket tartalmazza. Képzeletben a nyílt szöveg alá írjuk a kulcsot. Ha a kulcs rövidebb, többször is leírjuk egymás után. Ezután a nyílt szöveg minden betűje helyébe az a betű kerül a titkos szövegbe, amelyik annyival van hátrébb az ábécében, amennyi az alatta lévő betű sorszáma. A sorszámozást 0-val kezdjük, tehát A, B, C,..., Z sorszáma 0, 1, 2,..., 25. A ,,hátrébb az ábécében" úgy értendő, hogy a Z után ciklikusan A következik. Például

A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Nyílt szöveg:    T  I  T  K  O  S  I  T  A  N  D  O ...
Betű kódja:     19  8 19 10 14 19  8 19  0 13  3 14 ...
Kulcs (ZZABB):   Z  Z  A  B  B  Z  Z  A  B  B  Z  Z  A  B  B
Kulcs kódja:    25 25  0  1  1 25 25  0  1  1 25 25  0  1  1 

Titkos kódja:   18  7 19 11 15 18  7 19  1 14  2 13 ...
Titkos szöveg:   S  H  T  L  P  S  H  T  B  O  C  N ...
#include <stdio.h>

int hossz(??? szoveg)
{
 ...
}

void vigenere(??? nyilt, ??? kulcs, ??? titkos)
{
 ...
}

int main(void)
{
  char nyilt[] ="EZATITKOSITANDOSZOVEGAZAZANYILTSZOVEG";
  char kulcs[] ="ZZABB";
  char titkos[]="xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
  vigenere( ??? );
  printf(titkos);
  printf("\n");
  return 0;
}

A megoldás:

#include <stdio.h>

int hossz(char *szoveg) 
     // vagy int hossz(char szoveg[])
{
  int i=0;
  while(szoveg[i]) i++;
  return i;
}

void vigenere(char *nyilt, char *kulcs, char *titkos)
     // vagy void vigenere(char nyilt[], char kulcs[], char titkos[])
{
  int n,j,k;
  n=hossz(nyilt);
  k=hossz(kulcs);
  for(j=0; j<n; j++)
    titkos[j]=(nyilt[j]-'A'+kulcs[j%k]-'A')%('Z'-'A'+1) + 'A';
}

int main(void)
{
  char nyilt[] ="EZATITKOSITANDOSZOVEGAZAZANYILTSZOVEG";
  char kulcs[] ="ZZABB";
  char titkos[]="xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
  vigenere(nyilt, kulcs, titkos);
  printf(titkos);
  printf("\n");
  return 0;
}


2. Feladat: Írjunk egy függvényt, mely megkeresi egy mátrix legnagyobb elemét. A függvény első paraméterében a mátrix, második és harmadik paraméterében a vizsgálandó mátrix sorainak és az oszlopainak száma szerepeljen. A memóriában a mátrix egy 10x10-es mátrix részmátrixaként szerepel.


#include <stdio.h>

#define SOROKSZ 10
#define OSZLOPOKSZ 10

int legnagyobb(int a[][OSZLOPOKSZ], int ssz, int osz);

int main()
{
  int t[SOROKSZ][OSZLOPOKSZ] = { {21, 22, 13},
                                 {35, 20, 15} };
  ... 
  m = legnagyobb( t, ssz, osz);

  printf("A legnagyobb érték %d.\n", m);
  return 0;
}

int legnagyobb(int a[][OSZLOPOKSZ], int ssz, int osz)
{
  int i, j;
  int mx = a[0][0];

  ...

  return mx;
}

A megoldás:

#include <stdio.h>

#define SOROKSZ 10
#define OSZLOPOKSZ 10

int legnagyobb(int a[][OSZLOPOKSZ], int ssz, int osz);

int main()
{
  int t[SOROKSZ][OSZLOPOKSZ] = { {21, 22, 13},
                                 {35, 20, 15} };
  int ssz = 2;
  int osz = 3;
  int m;

  m = legnagyobb( t, ssz, osz);

  printf("A legnagyobb érték %d.\n", m);
  return 0;
}

int legnagyobb(int a[][OSZLOPOKSZ], int ssz, int osz)
{
  int i, j;
  int mx = a[0][0];

  for( i = 0; i < ssz; i++)
    for( j = 0; j < osz; j++)
      if ( a[i][j] > mx)
        mx = a[i][j];
  return mx;
}


5. előadás (2008-03-14)

Tömbök és függvények átadása paraméterként (csak mutatókkal)

Index jelölés

ld. a gyakorlaton: ~/info2/mx.c

Mutató jelölés, típuskényszerítés (casting)

~/info2/mx2.c

#include <stdio.h>

#define SOROKSZ 10
#define OSZLOPOKSZ 10

int legnagyobb(int *a, int oszsz, int ssz, int osz)
{
  int i, j;
  int mx = *a;
 
  for( i = 0; i < ssz; i++)
    for( j = 0; j < osz; j++)
      if (  *(a + i*oszsz + j) > mx)
        mx =  *(a + i*oszsz + j);
  return mx;
}

int main()
{
  int t[SOROKSZ][OSZLOPOKSZ] = { {21, 42, 13},
                                 {35, 20, 15} };
  int ssz = 2;
  int osz = 3;
  int m;
 
  m = legnagyobb( (int *)t, OSZLOPOKSZ, ssz, osz);
  
  printf("A legnagyobb érték %d.\n", m);
  return 0;
}

Függvény átadása

Függvénymutató deklarálása:

int (*mutfv)( int )

Ez így még nem mutat sehová, csak egy mutatót deklarál, mely csak olyan függvényre mutathat majd, amelynek egyetlen egész argumentuma van, és amely egy egészt ad vissza.

A zárójel kell, mert

int *mutfv( int )

olyan függvényt deklarálna, mely egészre mutató mutatót ad vissza.

~/info2/fvmut.c

#include <stdio.h>

int ossz(int, int);         // fv prototípusok
int szor(int, int);

int main(void)
{
  int a = 4;
  int b = 3;
  int e = 0;                // eredmény
  int (*fvm)(int, int);     // függvény mutató deklaráció

  fvm = ossz;               // az ossz() függvényre mutat
  e = fvm(a, b);            // ossz(a, b) meghívása
  printf("Az összeg = %d\n", e);
 
  fvm = szor;
  e = fvm(a, b);
  printf("A szorzat = %d\n", e);

  return 0;
}

int ossz(int x, int y) {
  return x + y;
}

int szor(int x, int y) {
  return x * y;
}


Véletlen sorozat generálása

Véletlen számok generálása: rand() az stdlib.h betöltése után egy [0,RAND_MAX] = [0,INT_MAX] intervallumba eső egészt generál. random seed: srand( <szám> ) hívással befolyásolható az elsőnek generált -- és ezzel az összes -- szám, mivel ez csak álvéletlen sorozat. Valódi véletlenség látszatához használjuk a time( NULL ) függvényt.

~/info2/rand.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main (void) {
  int i;

  srand( (unsigned int) time( NULL ));         // seed
  for (i=0; i<5; ++i) printf("%d ",rand()%64); // [0..RAND_MAX]
  printf("\n");

  return 0;
}

Struktúra

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  struct allat                  // struktúra deklaráció
  {
    char nev[20];
    int db;
    struct allat *kov;          // mutató a következőre
  };

  struct allat *elso = NULL;    // mutató az első állatra
  struct allat *ez   = NULL;    // mutató erre az állatra
  struct allat *utso = NULL;    // mutató az előzőre

  char c = '\0';

  for( ; ; )
  {
    printf("\nBeviszed egy allat adatait? (i/n) ");

    scanf(" %c",&c);
    if(c == 'n' || c == 'N') break;

    // memóriaallokáció
    ez = (struct allat*) malloc(sizeof(struct allat));

    if(elso == NULL) elso = ez; // mutató az első állatra

    if(utso!= NULL) utso -> kov = ez; 

    printf("\nAz allat neve? ");
    scanf("%s", ez -> nev);

    printf("\nHany %s lesz a hajon? ", ez -> nev);
    scanf("%d", &ez -> db);

    ez->kov = NULL;             // lehet, hogy ez az utolsó
    utso = ez;                  // áttesszük az utso-ba
  }

                               // állatok listájának kiírása
  ez = elso;

  while (ez != NULL)            // amíg ez egy érvényes mutató
  {
    printf("\n%d darab %s,\n", ez->db, ez->nev);
    utso = ez;                  // mentés memóriafelszabadításhoz
    ez = ez->kov;               // mutató a következőre
    free(utso);                 // memóriafelszabadítás
  }
  return 0;
}


Struktúra átadása paraméterként

#include <stdio.h>
#include <stdlib.h>

struct allat *uj_allat(void);

struct allat                  // struktúra deklaráció
{
  char nev[20];
  int db;
  struct allat *elozo;        // mutató az előzőre
  struct allat *kov;          // mutató a következőre
};

int main(void)
{
  struct allat *elso = NULL;    // mutató az első állatra
  struct allat *ez   = NULL;    // mutató erre az állatra
  struct allat *utso = NULL;    // mutató az előzőre
  char c = '\0';

  for(;;)
  {
    printf("\nBeviszed egy allat adatait? (i/n) ");
    scanf(" %c",&c);
    if(c == 'n' || c == 'N') break;

    // memóriaallokáció, adatbevitel
    ez = uj_allat();

    if(elso == NULL)
    {
      elso = ez;
      utso = ez;
    }
    else
    {
      utso->kov = ez;
      ez->elozo = utso;
      utso = ez;
    }
  }

  /* KIÍRÁS */
  ez = elso;
  while (ez != NULL)            // amíg ez egy érvényes mutató
  {
    printf("%d darab %s,\n", ez->db, ez->nev);
    utso = ez;                  // mentés memóriafelszabadításhoz
    ez = ez->kov;               // mutató a következőre
    free(utso);                 // memóriafelszabadítás
  }
  return 0;
}

struct allat *uj_allat(void)
{
  struct allat *a;

  a = (struct allat*) malloc(sizeof(struct allat));

  printf("\nAz allat neve? ");
  scanf("%s", a -> nev);

  printf("\nHany %s lesz a hajon? ", a -> nev);
  scanf("%d", &a -> db);

  a->kov = a->elozo = NULL;

  return a;
}
Személyes eszközök