Info2/2008tavasz/C
1 075. sor: | 1 075. sor: | ||
r=5*q*q % 10; | r=5*q*q % 10; | ||
return r; | 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 a==0, akkor b, 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 (a==0) return b; | ||
+ | return lnko(b%a, a); | ||
+ | } | ||
+ | |||
+ | /** 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 | ||
+ | $ _ |
A lap 2008. március 4., 12:54-kori változata
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
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
- költsége O(n2), viszont nincs járulékos tárhely igénye
- #define MAX 0x100 után a fordító MAX-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 ... 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 a==0, akkor b, 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 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 $ _