Info2/2008tavasz/C
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 $ _
