Info2/2008tavasz/C
1 435. sor: | 1 435. sor: | ||
== 5. gyakorlat == | == 5. gyakorlat == | ||
− | 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 | + | '''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 | 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 | 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 | ||
1 502. sor: | 1 502. sor: | ||
} | } | ||
--> | --> | ||
+ | |||
+ | '''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. | ||
A lap 2008. március 12., 13:31-kori változata
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 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 aif(!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.
#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
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; }
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; }