Info2/2008tavasz

A MathWikiből
(Változatok közti eltérés)
695. sor: 695. sor:
  
 
  $ ./beszurorendezes > rendezett # és beírunk 16 álvéletlen számot
 
  $ ./beszurorendezes > rendezett # és beírunk 16 álvéletlen számot
  86 36 16 58 2 64 40 7 14 31 50 96 54 18 76 61  
+
  86  
 +
36  
 +
16  
 +
...
 +
61  
 
  $ sort -n | diff rendezett -    # és beírjuk pontosan ugyanazokat a számokat
 
  $ sort -n | diff rendezett -    # és beírjuk pontosan ugyanazokat a számokat
  86 36 16 58 2 64 40 7 14 31 50 96 54 18 76 61  
+
  86  
 +
36  
 +
16  
 +
...
 +
61  
 
  # és itt semmit sem szabad kiírnia, hiszen nincs eltérés a Unixos és az
 
  # é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
 
  # általunk írt rendezés eredménye között
756. sor: 764. sor:
 
     printf("\n");
 
     printf("\n");
 
   }
 
   }
 +
  return 0;
 +
}
 +
 +
== 3. gyakorlat (2008-02-25) ==
 +
 +
Í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
 +
 +
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 <code>tomb[p]=1</code>), 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.
 +
 +
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 <code>tomb[valami]</code> helyett elég <code>tomb[valami/2]</code>-t írni, és kettesével ugrálni.
 +
 +
~/info2/erszita3.c
 +
 +
#include <stdio.h>
 +
char tomb[500000];
 +
int main (void) {
 +
  int i,j;
 +
 +
 +
 
   return 0;
 
   return 0;
 
  }
 
  }

A lap 2008. február 25., 21:52-kori változata

Ez a wikioldal 2008 februárjától a BME alkalmazott matematikus hallgatói számára oktatott Informatika 2 tárgy honlapja. Kiindulási alapja a 2007-ben Szabó Péter által tartott kurzus. A tárgy oktatásához felhasznált, http://wiki.math.bme.hu/ -n belüli wikioldalak GNU FDL licenc vagy (választás szerint) CC-BY-SA-2.0 licenc szerint szabadon használhatók és terjeszthetők.

Tartalomjegyzék

A tárgyról

Oktatók

  • Az előadásokat és a gyakorlatokat Wettl Ferenc tartja <wettl kukac math p bme p hu>.
  • Tűz Csaba javítja a házi feladatokat és a ZH-kat, gondozza a SIO rendszert és konzultációkat tart.

Egyéb személyek:

Hallgatók

A gyakorlati ismeretek kellő elsajátításához elengedhetetlen, hogy a gyakorlati kurzuson mindenki saját számítógéppel dolgozzon.

A Neptun beosztásához képest a hallgatók tankört cserélhetnek az egyenletes beosztás követelményét figyelembe véve.


Tárgykövetelmények

A szorgalmi időszakban teljesítendő:

  • A kiadott házi feladatok megoldása és beadása a SIO rendszeren keresztül. Csak azt a feladatot kell beadni, amelynek a beadási határideje ezen a wikioldalon szerepel. Addig kell próbálkozni, amíg a rendszer OK-val el nem fogadja a megoldást. Az el nem fogadott megoldás és a meg sem kisérelt megoldás is 0 pontot ér feladatonként. Az elfogadott megoldás 1 pontot ér.
  • Az első ZH megírása. A ZH valószínűleg papíralapú lesz. Az első ZH témája: C programozási nyelv és egyszerű algoritmusok. Csak azt kell tudni, ami előadáson vagy gyakorlaton elhangzott. Puskát lehet majd használni. Lásd még a #Az első ZH c. szakaszt.
  • A második ZH témája: Ruby programozási nyelv és objektum-orientált programozás. Csak azt kell tudni, ami előadáson vagy gyakorlaton elhangzott. Puskát lehet majd használni.

A félévközi jegy a fentiek összesítésével lesz meghatározva. Elégtelen osztályzatot kap,

  • aki a gyakorlatok több, mint 30%-áról hiányzott;
  • aki a jegybeiratásig (de legkésőbb a szorgalmi időszak végéig) nem adta be OK-val elfogadva az összes kötelező házi feladatot;
  • aki a két ZH egyikét sem teljesíti legalább elégségesre, vagy az elégtelenre sikerült, illetve meg nem írt ZH-t a pótlás alkalmával sem tudja megírni legalább elégségesre;

Aki nem elégtelen osztályzatot kap, annak az osztályzata a ZH-kra kapott pontszámok összegéből számítódik.

Ha a jegybeiratás előtt bebizonyítódik, hogy valaki nem maga készítette a házi feladatát, vagy elkészítette valaki más házi feladatát, akkor az érintettek ellen fegyelmi eljárás indul a TVSz szerint.

Katalógus

A gyakorlatok látogatása kötelező, minden gyakorlaton van katalógus.

A hallgatók munkája

Előadáson a hallgatók figyelnek és jegyzetelnek. Gyakorlaton a gyakorlat ideje alatt a hallgatók megoldják a kitűzött feladatokat. Minden hallgatónak saját számítógépen dolgozik. Gyakorlaton praktikusabb füzet helyett fájlba jegyzetelni. A gyakorlatvezető segít, és ellenőrzi is a megoldást. A gyorsan haladók (a) szorgalmi feladatot kapnak, vagy kitalálnak naguknak (b) segítik a mellettük ülő lemaradt diákok munkáját. Ennek érdekében a hallgatók úgy ülnek le, hogy minden kezdő mellé üljön egy profi. Profinak számít az, aki az alábbiakból sokat tud: Linux grafikus felületek haladó felhasználói szintű ismerete, Linux parancssor felhasználói szintű ismerete, hatékony munka Linux parancssorban, hatékony munka Midnight Commanderben, angol nyelvtudás, jó hibadiagnosztizálási és hibajavítási készség, az órán kívül is gyakran használ Linuxot, tetszőleges programozási nyelv legalább hobbi-szintű ismerete, ismeretlen program működésének megértése weben fellelhető információk alapján, ismeretlen program működésének megértése man page alapján, tetszőleges program telepítése Windowsra, tetszőleges program telepítése valamely Linux-disztribúcióra. A profinak nem kell ismernie se a C nyelvet, se a Ruby nyelvet.

A hallgatók rendszeresen tanulnak például az ajánlott irodalomból, esetleg az órai jegyzetükből, és saját, vagy a labor gépein gyakorolnak egy pl. adott feladatot adott módon megoldó program elkészítésével, vagy ilyen példaprogramok tanulmányozásával.

A hallgatók egyénileg (pl. otthon vagy a számítógép-laborban) megcsinálják a házi feladatokat, és beküldik a SIO rendszerbe. A beküldéshez internetelérés (web) szükséges. Ha valaki megakad a feladat megoldásában, kérdezzen a konzultáción, vagy évfolyamtársaitól, de *NE CSINÁLTASSA MEG MÁSSAL*!


Ajánlott szoftverek

C nyelvhez Linux alatt ajánlott:

  • sima szövegszerkesztő: kate
  • fordítóprogram: gcc
  • fejlesztőkörnyezet: Kdevelop

C nyelvhez Windows alatt ajánlott:

Ruby nyelvhez Linux alatt ajánlott:

Ruby nyelvhez Windows alatt ajánlott:

Erő Zsolt egy Live CD-t készített, amin a fenti linuxos szoftverek megtalálhatók, és hosszadalmas telepítés nélkül kipróbálhatók. Barbalinux

Tananyag

  • algoritmusok C nyelven
  • objektum-orientált programozás Ruby nyelven

Ajánlott irodalom:

(Letölt, telepít, elindít.)

Egyéb irodalom:

BarbaLinux

Azok számára, akik a C programozást a gyakorlatokon megszokott környezetben (Kate és GCC) szeretnék gyakorolni, Erő Zsolt készített egy CD-t, amely tartalmazza ezeket a programokat. Köszönet érte!

Részleteket a Barbalinux wiki oldalán találhattok itt: Barbalinux

Konvenciók

A konvenciók mind a hallgatók, mind az oktatók számára kötelezően betartandók.

  • A tárggyal kapcsolatos fájlokat mindenki a ~/info2 mappába helyezze.
  • Minden fájlnév és mappanév kisbetűs.
  • A fájlnevek ékezetes betűket és szóközöket nem tartalmaznak.
  • A forrásfájlok (*.c és *.rb) ékezetes betűket nem tartalmaznak.
  • Minden program forráskódja külön (*.c vagy *.rb) fájlba kerül. Tehát nem írunk felül egyetlen korábban létrehozott fájlt sem, hanem lemásoljuk a fájlt, és más néven mentjük el. A más néven mentést még a fájl tartalmának módosítása előtt végrehajtjuk.
  • A sor elején levő szóközök számának megállapításánál betartjuk a beljebb kezdési szabályt (C nyelvhez lásd az 1. gyakorlat anyagában).


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

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

SIO megismerése

https://sioweb.math.bme.hu

Tasks Submit solution My submissions

Change password Logout

Available contests

Bemenet fájlból teszteléshez

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

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

A diff program kimenetét kell figyelni.

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

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

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

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

~/info2/embergondol.c

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

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

Szám beolvasása

~/info2/duplazas.c

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


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

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

Utasítások

Vigyázzunk a pontosvesszőkre

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

Műveletek, relációk

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

Bitszámlálás*

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

unsigned i;
int sz;
...
for (sz=0; i != 0; i >>= 1) if (i & 01) sz++;
...

Ha i 2-es komplemens alakban van tárolva, akkor i&(i-1) az utolsó 1-es bitet törli (MIÉRT?). Ezt kihasználva cseréljük ki a fenti sort egy vele ekvivalens, de gyorsabbra (amely ráadásul int-nek deklarált i-re is jól fut).

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

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

Kiértékelési sorrend

Egy <= irány

a = b = c = 0;

Egy => irány

if ( n!=0 && osszeg/n < atlag ) ... ;
if ( n==0 || osszeg/n < epszilon ) ... ;

Lógó else

Helyes:

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

Helytelen:

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

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

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

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


Tömbök

Asszimetrikus korlátok

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

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

A tömbök indexelése 1-től! Szimmetrikus intervallum! Az intervallum hossza = felső határ - alsó határ + 1.

- + - - - - - - + - - -
 0 1 2 3 4 5 6 7 8 9
   ^           ^
- + - - - - - - + - - -
 1 2 3 4 5 6 7 8 9
   ^           ^

Írjunk C-ben 0-tól, majd k-tól 7-elemű ciklust! Az intervallum hossza = felső határ - alsó határ.

for ( i=0; i<7; i++) ... ;
for ( i=k; i<k+7; i++) ... ;

A tömbök indexelése 0-tól! Aszimmetrikus intervallum!

- + - - - - - - + - - 
   0 1 2 3 4 5 6 7 8
   ^             ^
- + - - - - - - + - - 
 1 2 3 4 5 6 7 8 9
   ^             ^

Tömbök definiálása, deklarálása

  • [0..(n-1)] indexeljük az n elemű tömböt
    • tömbelem hozzáférése nagyon gyors (konstans időben történik)
    • nagy félrecímzés általában gyors és feltűnő, kicsi félrecímzés alattomos és nehezen felderíthető hibához vezet
  • több (pl. kettő) dimenziós tömbök definiálása és deklarálása
  • tömbelemek inicializálása (for) ciklussal, pl. angol abc, mátrix kinullázása
  • hogyan lehet beszúró rendezéssel egy tömböt rendezni
  • hogyan lehet mátrixot transzponálni
  • a "%6d" formázó sztringgel a printf a 6-nál nem több számjegyű számokat „szépen”, jobbra igazítva fogja kiírni
  • a 0x100 az hexadecimális, azaz 16-os számrendszerben vett 100, tehát 256

~/info2/beszurorendezes.c:

/* A bemenetről beolvasott számokat beszúró rendezéssel rendezi,
 * majd kiírja a kimenetre.
 */
#include <stdio.h>
#define MAX 0x10
int main(void) {
  int tomb[MAX], elem, i, j; 
  for(i = 0; i != MAX; i++)
    scanf("%d", &tomb[i]);
  for (i = 1; i < MAX; i++) {
    elem = tomb[i];
    j = i-1;
    while (j >= 0 && tomb[j] > elem) {
      tomb[j+1] = tomb[j];
      j--;
    }
    tomb[j+1] = elem;
  }
  for(i = 0; i != MAX; i++)
    printf("%d \n", tomb[i]);
  return 0;
}

Kipróbálás:

$ ./beszurorendezes > rendezett # és beírunk 16 álvéletlen számot
86 
36 
16 
...
61 
$ sort -n | diff rendezett -    # és beírjuk pontosan ugyanazokat a számokat
86 
36 
16 
...
61 
# és itt semmit sem szabad kiírnia, hiszen nincs eltérés a Unixos és az
# általunk írt rendezés eredménye között

~/info2/matrixtranszponalas.c:

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

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

  for (n=0; n < 10; n++) 
    for(m=0; m < 6; m++)
      b[m][n] = a[n][m];

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

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-25)

Í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

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.

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