Info2/2008tavasz

A MathWikiből
(Változatok közti eltérés)
 
(egy szerkesztő 26 közbeeső változata nincs mutatva)
1. sor: 1. sor:
 
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 [http://wiki.math.bme.hu/index.php/SZIMP2 kurzus]. A tárgy oktatásához felhasznált, http://wiki.math.bme.hu/ -n belüli wikioldalak [http://en.wikipedia.org/wiki/GNU_Free_Documentation_License GNU FDL] licenc vagy (választás szerint) [http://hu.wikipedia.org/wiki/Creative_commons CC-BY-SA-2.0] licenc szerint szabadon használhatók és terjeszthetők.
 
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 [http://wiki.math.bme.hu/index.php/SZIMP2 kurzus]. A tárgy oktatásához felhasznált, http://wiki.math.bme.hu/ -n belüli wikioldalak [http://en.wikipedia.org/wiki/GNU_Free_Documentation_License GNU FDL] licenc vagy (választás szerint) [http://hu.wikipedia.org/wiki/Creative_commons CC-BY-SA-2.0] licenc szerint szabadon használhatók és terjeszthetők.
  
== Oktatók ==
+
<strong>Pótlás: 2008-05-23, péntek H45a 10:00</strong>
 +
 
 +
Az [http://www.math.bme.hu/~wettl/okt/info2/2008/zh1_2008tavasz_mo.pdf 1. ZH feladatai és megoldása],
 +
a [http://www.math.bme.hu/~wettl/okt/info2/2008/zh2_2008tavasz.pdf 2. ZH feladatai],
 +
a [http://www.math.bme.hu/~wettl/okt/info2/2008/potzh1_2008tavasz_mo.pdf 1. pótZH feladatai],
 +
a [http://www.math.bme.hu/~wettl/okt/info2/2008/potzh2_2008tavasz_mo.pdf 2. pótZH feladatai].
 +
 
 +
<strong>1. ZH: 2008-04-03 csütörtök 16:00 Ka26</strong>
 +
 
 +
A [[Info2/2008tavasz/C| C nyelvről szóló előadások és gyakorlatok anyaga itt]] található.
 +
 
 +
A [[Info2/2008tavasz/ruby| ruby nyelvről szóló előadások és gyakorlatok anyaga majd itt]] van. És <strong>ugyanitt az info a 2. ZH-ról!</strong>
 +
 
 +
 
 +
== A tárgyról ==
 +
 
 +
=== Oktatók ===
  
 
* Az előadásokat és a gyakorlatokat Wettl Ferenc tartja <wettl kukac math p bme p hu>.
 
* Az előadásokat és a gyakorlatokat Wettl Ferenc tartja <wettl kukac math p bme p hu>.
11. sor: 27. sor:
 
* Az előd tárgy utolsó honlapja Rácz Balázs oldalán található: http://www.ilab.sztaki.hu/~bracz/p/cimp2_2006tavasz.html
 
* Az előd tárgy utolsó honlapja Rácz Balázs oldalán található: http://www.ilab.sztaki.hu/~bracz/p/cimp2_2006tavasz.html
  
== Hallgatók ==
+
=== 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 gyakorlati ismeretek kellő elsajátításához elengedhetetlen, hogy a gyakorlati kurzuson mindenki saját számítógéppel dolgozzon.
18. sor: 34. sor:
  
  
== Tárgykövetelmények ==
+
=== Tárgykövetelmények ===
  
 
A szorgalmi időszakban teljesítendő:
 
A szorgalmi időszakban teljesítendő:
36. sor: 52. sor:
 
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.
 
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 ==
+
=== Katalógus ===
  
 
A gyakorlatok látogatása kötelező, minden gyakorlaton van katalógus.
 
A gyakorlatok látogatása kötelező, minden gyakorlaton van katalógus.
  
== A hallgatók munkája ==
+
=== 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.
 
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.
49. sor: 65. sor:
  
  
== Ajánlott szoftverek ==
+
=== Ajánlott szoftverek ===
  
 
C nyelvhez Linux alatt ajánlott:
 
C nyelvhez Linux alatt ajánlott:
75. sor: 91. sor:
 
[[Barbalinux]]
 
[[Barbalinux]]
  
== Tananyag ==
+
=== Tananyag ===
  
 
* algoritmusok C nyelven
 
* algoritmusok C nyelven
94. sor: 110. sor:
 
* rövid összefoglaló Rubyról: Ruby Quick Reference (Ruby QuickRef): http://www.zenspider.com/Languages/Ruby/QuickRef.html
 
* rövid összefoglaló Rubyról: Ruby Quick Reference (Ruby QuickRef): http://www.zenspider.com/Languages/Ruby/QuickRef.html
  
== BarbaLinux ==
+
=== 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!
 
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!
104. sor: 120. sor:
 
A konvenciók mind a hallgatók, mind az oktatók számára kötelezően betartandó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 (könyvtárba) helyezze.
+
* A tárggyal kapcsolatos fájlokat mindenki a ~/info2 mappába helyezze.
 
* Minden fájlnév és mappanév kisbetűs.
 
* Minden fájlnév és mappanév kisbetűs.
* A fájlnevek ékezetes betűket nem tartalmaznak.
+
* 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.
 
* 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.
 
* 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).
 
* 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).
  
== A gcc-parancssor elemeinek jelentése ==
 
  
Ezt nem kell tudni, csak egy hallgató kérésére, érdekességképp került fel a wikibe. Az alábbi parancsot elemezzük:
+
= Gyakorló feladatok =
  
$ gcc -W -Wall -s -O2 -lm -o <program> <program>.c
+
== Elméleti kérdések ==
  
* ''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.
+
* Tekintsük a <code>struct nagy { int i; char c1, *c2; short s; char c3; double d; }</code> struktúratípust.
* ''-Wall'': a legfontosabb figyelmeztető üzeneteket (warning) bekapcsolja
+
** Mekkora a <code>struct nagy a[10][20][30], *b;</code> változók mérete igazítás (alignment) nélkül? Segítség: a char 1 bájt, a short 2 bájt, a double 8 bájt, a többi 4 bájt.
* ''-W'': még néhány fontos figyelmeztető üzenetet bekapcsol
+
** Mekkora a <code>struct nagy a[10][20][30], *b;</code> változók mérete igazítással? Segítség: a char igazítása 1 bájt, a short igazítása 2 bájt, a többi igazítása 4 bájt.
* ''-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.
+
** Csökkentse minimálisra a struktúra igazításos méretét pusztán a mezők áthelyezésével. Mennyi az új méret?
* ''-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.
+
* Milyen (geometriai) transzformációt végez a derékszögű koordinátarendszerbeli (x,y) ponton az <code>x-=y+=x-=y;</code> utasítás?
* ''-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 <code>#include <math.h></code>-nak is a matematikai függvényekhez. Nem egyes, hanem kis l betű van a kapcsolóban.
+
* Tekintsük a törtszámokat összeadó ''osszead'' függvényt:
* ''-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.
+
... ...(...) {
 +
  egyszerusit(as,an);
 +
  egyszerusit(bs,bn);
 +
  en=lkkt(an,bn);
 +
  es=(en/an)*as+(en/bn)*bs;
 +
  egyszerusit(es,en);
 +
}
  
== 1. gyakorlat (2007-02-13 és 2007-02-16) ==
+
** Egészítse ki a ...-os részeket. A paraméterek sorrendje tetszőleges.
 +
** Pótolja a kihagyott <code>&</code> és <code>*</code> jeleket.
 +
** Változtat-e valamit az eredményen, ha az utolsó utasítást (<code>egyszerusit(es,en);</code>) kihagyjuk? A válasz csak indoklással együtt fogadható el.
 +
* Tekintsük az alábbi függvényt egy amőbajátékot játszó programból. Az aktuális játékállás a ''t'' változóban található. A tábla 19x19 mezőből áll.
  
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.
+
int feladvany1(int n, int m) {
 +
  int x, y;
 +
  char c;
 +
  for (y=0;y<n;y++) {
 +
    for (x=4;x<m;x++) {
 +
      if (0==(c=t[y][x])) {
 +
      } else if (c==t[y][x-1] && c==t[y][x-2] && c==t[y][x-3] && c==t[y][x-4]) {
 +
        return c;
 +
      }
 +
    }
 +
  }
 +
  return 0;
 +
}
  
=== Linuxos környezet javítása ===
+
** Deklarálja a ''t'' változót.
 +
** Mit számol ki (pontosabban: mit ad vissza) a függvény?
 +
** Mit tartalmaz a ''t'' változó a játék kezdetekor?
 +
** Miért lenne rossz, ha a kódban <code>x=4</code> helyett <code>x=0</code> szerepelne?
 +
* Tekintsük az alábbi függvényt. Minden kettőspontra végződő sorhoz adja meg, hogy mit tartalmaz a ''t'' tömb.
  
A PageUp-pal és PageDown-nal történő history-kereséshez az ~/.inputrc fájlukba
+
void feladvany2(void) {
írjuk bele:
+
  int t[9], *p, i;
 +
  t[0]=0; t[1]=1;
 +
  januar:
 +
  for (i=2;i<9;i++) t[i]=t[i-1]+t[i-2];
 +
  februar:
 +
  p=&t[3];
 +
  marcius:
 +
  t[0]=*p++;
 +
  aprilis:
 +
  t[1]=*++p;
 +
  majus:
 +
  t[2]=(*p)++;
 +
  junius:
 +
  t[3]=++(*p);
 +
  julius:
 +
  t[4]=++*p;
 +
  augusztus:
 +
  *p+=*p;
 +
  szeptember:
 +
  ;
 +
}
  
set meta-flag on
+
* Tekintsük az alábbi ciklust:
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:
+
for(i=0;i<=100&&t[i]!=42;i++){}
  
$ bind -f ~/.inputrc
+
** Deklarálja a változókat úgy, hogy a lehető legkevesebb memóriát használja.
 +
** Írja át a ciklust ''for''-ből ''while''-ba.
 +
** Valósítsa meg a ciklust ''goto''-val.
 +
** Rajzolja le a ciklus működését folyamatábrán.
 +
** A ciklus befejeztével mi az ''i'' változó értékének jelentése?
 +
** A ciklus befejeztével az ''i'' változó milyen esetben veszi fel a maximumát?
  
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:
+
* Tekintsük az alábbi programrészletet:
  
  export HISTSIZE=9999   
+
  void helyben_transzponal(int t[9][9])
 +
int x, y
 +
double d, *p
 +
for (y=0;y<9;y++)
 +
p=&t[y][0]
 +
for (x=y+1;x<9;x++)
 +
d=p[x]
 +
p[x]=t[x][y]
 +
p[x]=d
  
=== Az első C program ===
+
** Pótolja a hiányzó pontosvesszőket és kapcsos zárójeleket.
 +
** Pótolja a tanult módon a hiányzó soreleji szóközöket (indentation).
 +
** Lassít vagy gyorsít a függvény futásán, ha <code>y+1</code> helyett <code>y</code>-t írunk?
 +
** Változtat-e a függvény futásának eredményén, ha <code>y+1</code> helyett <code>y</code>-t írunk?
  
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.
+
* Tekintsük az alábbi függvényt:
  
A kate nevű szövegszerkesztőt használjuk.
+
int fib(int n) {
 +
  if (n<1) return 0;
 +
  return fib(n-1)+fib(n-2);
 +
}
  
~/info2/hello.c:
+
** A függvény az ''n''-edik Fibonacci-számot adná vissza, ha helyesen működne. Mi a hiba?
 +
** Javítsa ki a hibát 2 karakter megváltoztatásával.
 +
** A Fibonacci-sorozatot értelmezhetjük negatív ''n''-ekre is (a rekurzív képlet ugyanaz, mint pozitívakra). Módosítsa a programot, hogy negatív ''n''-ekre is működjön. Háromsoros megoldást adjon.
 +
* Tekintsük az alábbi ''keres'' függvényt, amely az ''n'' elemből álló, nagyság szerint rendezett ''t'' tömbben keresi meg az ''e'' értéket, és tekintsük az őt hívó ''feladvany3'' függvényt.
  
#include <stdio.h>
+
  int keres(int t[], int n, int e) {
  int main(void) {
+
   int a=0, b=n-1, f;
   printf("Hello, World!\n");
+
  while (a<=b) {
   return 0;
+
    f=(a+b)/2;
 +
    if (e==t[f]) return f;
 +
    else if (e<t[f]) b=f-1;
 +
    else a=f+1;
 +
  }
 +
   return n;
 
  }
 
  }
  
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.
+
int feladvany3(int t[], int n, int e) {
 +
  int a=keres(t, n, e), b=a;
 +
  while (a>0 && t[a-1]==e) a--;
 +
  while (b<n && t[b]==e) b++;
 +
  return b-a;
 +
}
  
Hasznos parancsok (csak a $ utáni részt kell begépelni, a többit a gép írja ki).
+
** Működik-e a ''keres'' függvény minden monoton csökkenő tömbre? A válasz csak bizonyítással együtt fogadható el.
 +
** Működik-e a ''keres'' függvény minden monoton növekvő tömbre? A válasz csak bizonyítással együtt fogadható el.
 +
** Mit ad vissza a ''keres'' függvény, ha a keresett érték szerepel a tömbben?
 +
** Megtalálja-e a ''keres'' függvény a keresett értéket, ha az többször is szerepel? Ha igen, melyik előfordulását találja meg?
 +
** Mit ad vissza a ''keres'' függvény, ha a keresett érték nem szerepel a tömbben?
 +
** Mit számol ki (pontosabban: mit ad vissza) a ''feladvany3'' függvény, ha a keresett érték szerepel a tömbben?
 +
** Mit ad vissza a ''feladvany3'' függvény, ha a keresett érték nem szerepel a tömbben?
 +
* Tekintsük az alábbi deklarációt és függvényt.
  
  $ mkdir ~/info2
+
  struct csucs {
$ cd ~/info2
+
  int ertek;
  $ kate hello.c
+
  struct csucs bal , jobb;
  $ gcc -W -Wall -s -O2 -o hello hello.c
+
  };
  $ ./hello
+
   
  Hello, World!
+
  int feladvany4 struct csucs gyoker {
 +
  int bal , jobb;
 +
  if gyoker == NULL return 0;
 +
  return feladvany4 gyoker . bal + feladvany4 gyoker . jobb + gyoker . ertek;
 +
  }
  
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.
+
** Pótolja a hiányzó <code>*</code>-okat és zárójeleket (a lehető legkevesebbet).
 +
** Mit számol ki (pontosabban: mit ad vissza) a függvény?
 +
** Hányszor hívja meg önmagát a függvény egy ''n'' csúcsból álló fa esetén? Teljesen pontos választ adjon.
 +
* Tekintsük az alábbi függvényt, ami 3 egész szám összesített eltérését határozza meg a középső elemtől:
  
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 <code>.exe</code> fájlok vannak (pl. <code>hello.exe</code>), és azok egyikét futtatjuk (pl. <code>hello</code> paranccsal).
+
int medianelteres(int a, int b, int c) {
 +
  a=abs(a-kozepso(a, b, c));
 +
  b=abs(b-kozepso(a, b, c));
 +
  c=abs(c-kozepso(a, b, c));
 +
  return a+b+c;
 +
}
  
~/info2/hello100.c:
+
** A függvényben van egy alapvető hiba, például a <code>medianelteres(7, 6, 5)</code> hívás eredménye 6, noha azt szeretnénk, hogy 2 legyen. Javítsa a hibát új változó bevezetésével.
 +
** Javítsa a hibát új változó bevezetése nélkül. (Át kell írni az egész kapcsos zárójelen belüli részt esetszétválasztásosra.)
 +
* Tekintsük az alábbi függvényt:
  
#include <stdio.h>
+
  int feladvany5 int n {
  int main(void) {
+
int c = 0 int d = 2
  int c;
+
if n < 0 n *= - 1
  for (c=0;c<100;c++) {
+
while n > 1{
    printf("Hello, World!\n");
+
if n % d == 0 {
  }
+
n /= d c ++
  return 0;
+
} else {
 +
++ d
 +
}
 +
}
 +
return c
 
  }
 
  }
  
=== A behúzás (beljebbezés) szabályai ===
+
** Pótolja a hiányzó zárójeleket és pontosvesszőket.
 +
** Pótolja a tanult módon a soreleji szóközöket (indentation).
 +
** Mit számol ki (pontosabban: mit ad vissza) a függvény?
 +
* Deklaráljon egy függvényt, ami kiszámolja három egész szám legnagyobb közös osztóját.
 +
* Deklaráljon egy függvényt, ami bővít egy törtet (számláló,nevező) egy adott számmal.
 +
* Deklaráljon egy függvényt, ami összehasonlít két bináris keresőfát, hogy egymás tükörképei-e. Előbb definiálja a használt struktúratípust.
 +
* Deklaráljon egy függvényt, ami lemásol egy bináris keresőfát, és visszaadja a másolatot. Előbb definiálja a használt struktúratípust.
 +
* Deklaráljon egy változót, ami egy int-ekből álló háromdimenziós tömb.
 +
* Deklaráljon egy változót, ami egy short-okra mutató mutatókból álló kétdimenziós tömb.
  
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):  
+
Az alábbiakhoz hasonló, tisztán elméleti feladatok nem lesznek:
  
* Beljebb kezdésre csak szóközöket használunk, tabulátort nem.
+
* Mi a különbség a predekrementálás és a posztdekrementálás között?
* 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.
+
* Mik a C nyelv kulcsszavai?
* 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.
+
* Hogyan kell paraméterezni a scanf függvényt?
 +
* Mi a strúktúratípus-definíció formális szintaxisa?
 +
* Hogyan lehet egy függvényből két értéket visszaadni?
  
A beljebb kezdéshez hasznos tippek:
+
== Programozási feladatok ==
  
* 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.
+
* Írjon olyan függvényt C nyelven, ami visszadja egy bináris fában található csúcsok összegét. Deklaráció: <code>int ertekeket_osszead(struct csucs *gyoker);</code>
* 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. Inkább kapcsoljuk ki, mint hogy figyelnünk kelljen a hibázásaira, és folyamatosan küzdenünk kelljen vele.
+
* Írjon olyan függvényt C nyelven, ami összehasonlít két bináris fát, és 0-t ad vissza, ha megegyeznek, és 1-et, ha különböznek. Az egyezéshez nem elég, hogy ugyanazokat az értékeket tartalmazzák, a gráfnak is meg kell egyeznie. Deklaráció: <code>int osszehasonlit(struct csucs *gyoker1, struct csucs *gyoker2);</code>
 +
* Írjon olyan függvényt C nyelven, ami visszadja egy 1-nél nagyobb egész szám legkisebb, 1-nél nagyobb (prím)osztóját. Deklaráció: <code>int minoszto(int n);</code>. Az osztó keresését 2-től négyzetgyök n-ig végezze.
 +
* Írjon olyan függvényt C nyelven, ami visszadja az n karakterből álló t tömbben  a leghosszabb szó hosszát (ami 0 is lehet, ha egy szó sincs a tömbben). Szónak számít egy szóközt nem tartalmazó, tovább nem bővíthető, összefüggő részsorozat. Deklaráció: <code>int maxszohossz(char t[], int n);</code>
 +
* Írjon egy olyan rekurzív függvényt C nyelven, ami kiszámolja az n alatt a k binomiális együtthatót modulo m. Deklaracio: <code>int binom(int n, int k, int m);</code> Használja ki, hogy 0 alatt a 0 egyenlő 1-gyel, egyébként 0 alatt az n egyenlő 0-val, egyébként pedig n alatt a k egyenlő (n-1) alatt a k plusz (n-1) alatt a (k-1).
 +
* Írjon olyan függvényt C nyelven, ami keres a 100-szor 100-as m mátrixban két azonos sort, és visszadja azok sorszámát (0 <= i < j < 100). Ha nincs két azonos sor, akkor i=j=100-at ad vissza. Deklaráció: void azonos_sort_keres(int m[100][100], int *i, int *j);</code>
 +
* Írjon olyan függvényt C nyelven, ami kiszámolja három szám legnagyobb közös osztóját. Írhat segédfüggvényt is. Deklaráció: <code>int lnko3(int a, int b, int c);</code>
 +
* Írjon olyan függvényt C nyelven, ami meghatározza, hogy egy háromszög derékszögű-e, és 0-et ad vissza, ha nem, 1-et, ha az A csúcsnál van derékszög, 2-t, ha a B csúcsnál, és 3-at, ha a C csúcsnál. A háromszög 3 csúcspontjával van megadva, minden koordináta egész szám. A derékszögűséget vektorok skalárszorzatával határozza meg. Deklaráció: <code>int derekszogu_e(int ax, int ay, int bx, int by, int cx, int cy);</code>.
  
=== További példák ===
+
= Házi feladatok =
  
Hasznos parancsok:
+
A házi feladatokat a [[SIO]] rendszer segítségével kell beadni. Minden SIO-ban kitűzött feladatot be kell adni, kivéve amelyekhez explicit módon oda van írva, hogy szorgalmi feladat.
  
$ cd ~/info2
+
== Technikai részletek ==
$ 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:
+
A C fordításhoz használt szoftver a ''gcc'' (a pontos verzió: <code>gcc 4.1.2 Debian 4.1.1-21</code>).
 +
A házi feladatokat a következő módon fordítjuk:
  
  #include <stdio.h>
+
  $ gcc -x c -O2 -std=c99 -pedantic-errors -static -o <prog> <forrásfájl>.c -lm
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:
+
A feladat megoldásakor előbb nem a fenti paranccsal, hanem az alábbival érdemes előbb kipróbálni a fordítást:
  
  #include <stdio.h>
+
  $ gcc -W -Wall -s -O2 -std=c99 -pedantic-errors -lm -o <program> <program>.c
 +
 
 +
Ez azért jó, mert a <code>-W -Wall</code> sok hasznos figyelmeztető üzenetet megjelenít, és ily módon a hibákra hamar felhívja a figyelmet.
 +
 
 +
<!--
 +
== Kiírt házi feladatok ==
 +
 
 +
{| border="1" cellspacing="0"
 +
! kód
 +
! leírás
 +
! beadási határidő
 +
|-
 +
| <tt>uc</tt>
 +
| [https://sioweb.math.bme.hu/user.phtml?op=inc&id=6 https://sioweb.math.bme.hu/user.phtml?op=inc&id=6]
 +
| 2007. március 31., 24:00 CET
 +
|-
 +
| <tt>lcuc</tt>
 +
| [https://sioweb.math.bme.hu/user.phtml?op=inc&id=7 https://sioweb.math.bme.hu/user.phtml?op=inc&id=7]
 +
| 2007. március 31., 24:00 CET
 +
|-
 +
| <tt>pow2count</tt>
 +
| [https://sioweb.math.bme.hu/user.phtml?op=inc&id=38 https://sioweb.math.bme.hu/user.phtml?op=inc&id=38]
 +
| 2007. március 31., 24:00 CET
 +
|-
 +
| <tt>primecount</tt>
 +
| [https://sioweb.math.bme.hu/user.phtml?op=inc&id=205 https://sioweb.math.bme.hu/user.phtml?op=inc&id=205]
 +
| 2007. március 31., 24:00 CET
 +
|-
 +
| <tt>matmul</tt>
 +
| [https://sioweb.math.bme.hu/user.phtml?op=inc&id=206 https://sioweb.math.bme.hu/user.phtml?op=inc&id=206]
 +
| 2007. március 31., 24:00 CET
 +
|-
 +
| <tt>binfabe</tt>
 +
| [https://sioweb.math.bme.hu/user.phtml?op=inc&id=751 https://sioweb.math.bme.hu/user.phtml?op=inc&id=751]
 +
| 2007. április 12., 24:00 CET
 +
|-
 +
| <tt>unolight</tt>
 +
| https://sioweb.math.bme.hu/user.phtml?op=inc&id=752
 +
| 2007. március 31., 24:00 CET
 +
|-
 +
| <tt>binfabeki</tt>
 +
| [https://sioweb.math.bme.hu/user.phtml?op=inc&id=753 https://sioweb.math.bme.hu/user.phtml?op=inc&id=753]
 +
| 2007. április 12., 24:00 CET
 +
|-
 +
| <tt>tortszoroz</tt>
 +
| https://sioweb.math.bme.hu/user.phtml?op=inc&id=759
 +
| 2007. április 12., 24:00 CET
 +
|-
 +
| <tt>sikidom</tt>
 +
| https://sioweb.math.bme.hu/user.phtml?op=inc&id=762
 +
| 2007. május 10., 24:00 CET
 +
|-
 +
| <tt>binfaber</tt>
 +
| https://sioweb.math.bme.hu/user.phtml?op=inc&id=763
 +
| 2007. május 10., 24:00 CET
 +
|}
 +
-->
 +
 
 +
A házi feladatok listája elérhető a [[SIO]] rendszerben is: [https://sioweb.math.bme.hu/user.phtml?op=zadania https://sioweb.math.bme.hu/user.phtml?op=zadania]
 +
 
 +
== Típushibák a házikban ==
 +
 
 +
* A ''Compile error'' oka lehet az is, hogy a beadott fájl kiterjesztése nem <code>.c</code> . Tipikus rossz kiterjesztések: <code>.cc</code>, <code>.cpp</code>, <code>.cxx</code>.
 +
* A ''runtime error''-nak lehet oka, hogy a <code>return 0;</code> hiányzik a ''main'' függvény végéről.
 +
* A forrásfájl utolsó sorának végén nincs soremelés (emiatt ''compile error'').
 +
* Nagy, 8 MB-nál nagyobb tömb van a main függvényen belül (emiatt ''runtime error'' és ''segmentation fault''). Megoldás: a tömb deklarációját a függvényen kívülre tenni. Például így jobb:
 +
 
 +
char nagytomb[10000000];
 
  int main(void) {
 
  int main(void) {
   int c;
+
   ...
  for (c=0;c<=100;c++) {
+
    printf("szam: %3d, kettohatvany: %d\n", c, 1<<c);
+
  }
+
 
   return 0;
 
   return 0;
 
  }
 
  }
  
Az <code>a<<b</code> 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 <code>a>>b</code>, de szorzás helyett oszt (a 0 felé kerekítve).
+
* A getchar() eredménye ''char'' típusú változóba kerül. Ez azért nem jó, mert a char csak 256 különböző értéket tud tárolni, de nekünk 257 kéne (a 256 karakter, és a fájl végét jelző -1). Megoldás: ''int'' típusú változóba tenni.
 
+
* Függvényen belül függvény van definiálva. Ez nem jó, a függvényeket csak egymás után szabad definiálni.
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.
+
* A program fölösleges szóközöket ír ki (pl. a sor végére), és emiatt ''wrong answer''-ös a megoldás. Ha azt kell kiírni, hogy hello, majd egy soremelést, akkor jó megoldás a <code>printf("hello\n");</code>, rossz megoldás a <code>printf("hello \n");</code>
 +
* Az eratoszthenészi szitát while cikluson belül az összes feladványra végigszámolja, pedig elég lenne összesen egyszer. Emiatt ''time limit exceeded''-es a megoldás.
 +
* Tetszőleges karaktert nem lehet beolvasni gets()-sel vagy fgets()-sel, mert elnyelik a 0-s kódú karaktereket. A helyes megoldás karakter beolvasásásra getchar().
 +
* A program beszélgetni próbál a felhasználóval, pl. kiírja, hogy ''Most kérem a mátrix sorainak számát''. Épp amiatt rossz (''wrong answer'') a kimenet, hogy ez az üzenet is szerepel benne.
 +
* A program egymás alá próbálja igazítani a számokat. Épp amiatt rossz (''wrong answer'') a kimenet, hogy az igazítás miatt fölösleges szóközöket ír ki.
 +
* A program túl sok memóriát használ, például a szitáláshoz használt tömb elemeit ''int''-ekből építi, noha ''char''-okba is beleférne. i386 architektúrán az int 32 bites (ebből 1 előjel), a char 8 bites (ebből 1 előjel), tehát egy charban a [-128,127] zárt intervallumból lehet szám.
 +
* Túl nagynak veszi a tömböt (és amiatt ''memory limit exceeded''-et kap). A feladatkiírásban pontosan meg van adva a bemeneti adatok értéktartománya. Pont akkora (vagy egy hajszálnyival nagyobb) tömböt kell deklarálni, amekkorába az adat belefér.
 +
* A tömb mérete nem konstans. Például hibás az <code>int tomb[n];</code> deklaráció, és helyes az <code>int tomb[500];</code> deklaráció, ha ''n'' értéke legfeljebb 500 lehet (az értéktartományt lásd a feladat szövegében).

A lap jelenlegi, 2008. május 21., 20:34-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.

Pótlás: 2008-05-23, péntek H45a 10:00

Az 1. ZH feladatai és megoldása, a 2. ZH feladatai, a 1. pótZH feladatai, a 2. pótZH feladatai.

1. ZH: 2008-04-03 csütörtök 16:00 Ka26

A C nyelvről szóló előadások és gyakorlatok anyaga itt található.

A ruby nyelvről szóló előadások és gyakorlatok anyaga majd itt van. És ugyanitt az info a 2. ZH-ról!


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


Gyakorló feladatok

Elméleti kérdések

  • Tekintsük a struct nagy { int i; char c1, *c2; short s; char c3; double d; } struktúratípust.
    • Mekkora a struct nagy a[10][20][30], *b; változók mérete igazítás (alignment) nélkül? Segítség: a char 1 bájt, a short 2 bájt, a double 8 bájt, a többi 4 bájt.
    • Mekkora a struct nagy a[10][20][30], *b; változók mérete igazítással? Segítség: a char igazítása 1 bájt, a short igazítása 2 bájt, a többi igazítása 4 bájt.
    • Csökkentse minimálisra a struktúra igazításos méretét pusztán a mezők áthelyezésével. Mennyi az új méret?
  • Milyen (geometriai) transzformációt végez a derékszögű koordinátarendszerbeli (x,y) ponton az x-=y+=x-=y; utasítás?
  • Tekintsük a törtszámokat összeadó osszead függvényt:
... ...(...) {
  egyszerusit(as,an);
  egyszerusit(bs,bn);
  en=lkkt(an,bn);
  es=(en/an)*as+(en/bn)*bs;
  egyszerusit(es,en);
}
    • Egészítse ki a ...-os részeket. A paraméterek sorrendje tetszőleges.
    • Pótolja a kihagyott & és * jeleket.
    • Változtat-e valamit az eredményen, ha az utolsó utasítást (egyszerusit(es,en);) kihagyjuk? A válasz csak indoklással együtt fogadható el.
  • Tekintsük az alábbi függvényt egy amőbajátékot játszó programból. Az aktuális játékállás a t változóban található. A tábla 19x19 mezőből áll.
int feladvany1(int n, int m) {
  int x, y;
  char c;
  for (y=0;y<n;y++) {
    for (x=4;x<m;x++) {
      if (0==(c=t[y][x])) {
      } else if (c==t[y][x-1] && c==t[y][x-2] && c==t[y][x-3] && c==t[y][x-4]) {
        return c;
      }
    }
  }
  return 0;
}
    • Deklarálja a t változót.
    • Mit számol ki (pontosabban: mit ad vissza) a függvény?
    • Mit tartalmaz a t változó a játék kezdetekor?
    • Miért lenne rossz, ha a kódban x=4 helyett x=0 szerepelne?
  • Tekintsük az alábbi függvényt. Minden kettőspontra végződő sorhoz adja meg, hogy mit tartalmaz a t tömb.
void feladvany2(void) {
  int t[9], *p, i;
  t[0]=0; t[1]=1;
 januar:
  for (i=2;i<9;i++) t[i]=t[i-1]+t[i-2];
 februar:
  p=&t[3];
 marcius:
  t[0]=*p++;
 aprilis:
  t[1]=*++p;
 majus:
  t[2]=(*p)++;
 junius:
  t[3]=++(*p);
 julius:
  t[4]=++*p;
 augusztus:
  *p+=*p;
 szeptember:
  ;
}
  • Tekintsük az alábbi ciklust:
for(i=0;i<=100&&t[i]!=42;i++){}
    • Deklarálja a változókat úgy, hogy a lehető legkevesebb memóriát használja.
    • Írja át a ciklust for-ből while-ba.
    • Valósítsa meg a ciklust goto-val.
    • Rajzolja le a ciklus működését folyamatábrán.
    • A ciklus befejeztével mi az i változó értékének jelentése?
    • A ciklus befejeztével az i változó milyen esetben veszi fel a maximumát?
  • Tekintsük az alábbi programrészletet:
void helyben_transzponal(int t[9][9])
int x, y
double d, *p
for (y=0;y<9;y++)
p=&t[y][0]
for (x=y+1;x<9;x++)
d=p[x]
p[x]=t[x][y]
p[x]=d
    • Pótolja a hiányzó pontosvesszőket és kapcsos zárójeleket.
    • Pótolja a tanult módon a hiányzó soreleji szóközöket (indentation).
    • Lassít vagy gyorsít a függvény futásán, ha y+1 helyett y-t írunk?
    • Változtat-e a függvény futásának eredményén, ha y+1 helyett y-t írunk?
  • Tekintsük az alábbi függvényt:
int fib(int n) {
  if (n<1) return 0;
  return fib(n-1)+fib(n-2);
}
    • A függvény az n-edik Fibonacci-számot adná vissza, ha helyesen működne. Mi a hiba?
    • Javítsa ki a hibát 2 karakter megváltoztatásával.
    • A Fibonacci-sorozatot értelmezhetjük negatív n-ekre is (a rekurzív képlet ugyanaz, mint pozitívakra). Módosítsa a programot, hogy negatív n-ekre is működjön. Háromsoros megoldást adjon.
  • Tekintsük az alábbi keres függvényt, amely az n elemből álló, nagyság szerint rendezett t tömbben keresi meg az e értéket, és tekintsük az őt hívó feladvany3 függvényt.
int keres(int t[], int n, int e) {
  int a=0, b=n-1, f;
  while (a<=b) {
    f=(a+b)/2;
    if (e==t[f]) return f;
    else if (e<t[f]) b=f-1;
    else a=f+1;
  }
  return n;
}
int feladvany3(int t[], int n, int e) {
  int a=keres(t, n, e), b=a;
  while (a>0 && t[a-1]==e) a--;
  while (b<n && t[b]==e) b++;
  return b-a;
}
    • Működik-e a keres függvény minden monoton csökkenő tömbre? A válasz csak bizonyítással együtt fogadható el.
    • Működik-e a keres függvény minden monoton növekvő tömbre? A válasz csak bizonyítással együtt fogadható el.
    • Mit ad vissza a keres függvény, ha a keresett érték szerepel a tömbben?
    • Megtalálja-e a keres függvény a keresett értéket, ha az többször is szerepel? Ha igen, melyik előfordulását találja meg?
    • Mit ad vissza a keres függvény, ha a keresett érték nem szerepel a tömbben?
    • Mit számol ki (pontosabban: mit ad vissza) a feladvany3 függvény, ha a keresett érték szerepel a tömbben?
    • Mit ad vissza a feladvany3 függvény, ha a keresett érték nem szerepel a tömbben?
  • Tekintsük az alábbi deklarációt és függvényt.
struct csucs {
  int ertek;
  struct csucs bal , jobb;
};

int feladvany4 struct csucs gyoker {
  int bal , jobb;
  if gyoker == NULL return 0;
  return feladvany4 gyoker . bal + feladvany4 gyoker . jobb + gyoker . ertek;
}
    • Pótolja a hiányzó *-okat és zárójeleket (a lehető legkevesebbet).
    • Mit számol ki (pontosabban: mit ad vissza) a függvény?
    • Hányszor hívja meg önmagát a függvény egy n csúcsból álló fa esetén? Teljesen pontos választ adjon.
  • Tekintsük az alábbi függvényt, ami 3 egész szám összesített eltérését határozza meg a középső elemtől:
int medianelteres(int a, int b, int c) {
  a=abs(a-kozepso(a, b, c));
  b=abs(b-kozepso(a, b, c));
  c=abs(c-kozepso(a, b, c));
  return a+b+c;
}
    • A függvényben van egy alapvető hiba, például a medianelteres(7, 6, 5) hívás eredménye 6, noha azt szeretnénk, hogy 2 legyen. Javítsa a hibát új változó bevezetésével.
    • Javítsa a hibát új változó bevezetése nélkül. (Át kell írni az egész kapcsos zárójelen belüli részt esetszétválasztásosra.)
  • Tekintsük az alábbi függvényt:
int feladvany5 int n {
int c = 0 int d = 2
if n < 0 n *= - 1
while n > 1{
if n % d == 0 {
n /= d c ++
} else {
++ d
}
}
return c
}
    • Pótolja a hiányzó zárójeleket és pontosvesszőket.
    • Pótolja a tanult módon a soreleji szóközöket (indentation).
    • Mit számol ki (pontosabban: mit ad vissza) a függvény?
  • Deklaráljon egy függvényt, ami kiszámolja három egész szám legnagyobb közös osztóját.
  • Deklaráljon egy függvényt, ami bővít egy törtet (számláló,nevező) egy adott számmal.
  • Deklaráljon egy függvényt, ami összehasonlít két bináris keresőfát, hogy egymás tükörképei-e. Előbb definiálja a használt struktúratípust.
  • Deklaráljon egy függvényt, ami lemásol egy bináris keresőfát, és visszaadja a másolatot. Előbb definiálja a használt struktúratípust.
  • Deklaráljon egy változót, ami egy int-ekből álló háromdimenziós tömb.
  • Deklaráljon egy változót, ami egy short-okra mutató mutatókból álló kétdimenziós tömb.

Az alábbiakhoz hasonló, tisztán elméleti feladatok nem lesznek:

  • Mi a különbség a predekrementálás és a posztdekrementálás között?
  • Mik a C nyelv kulcsszavai?
  • Hogyan kell paraméterezni a scanf függvényt?
  • Mi a strúktúratípus-definíció formális szintaxisa?
  • Hogyan lehet egy függvényből két értéket visszaadni?

Programozási feladatok

  • Írjon olyan függvényt C nyelven, ami visszadja egy bináris fában található csúcsok összegét. Deklaráció: int ertekeket_osszead(struct csucs *gyoker);
  • Írjon olyan függvényt C nyelven, ami összehasonlít két bináris fát, és 0-t ad vissza, ha megegyeznek, és 1-et, ha különböznek. Az egyezéshez nem elég, hogy ugyanazokat az értékeket tartalmazzák, a gráfnak is meg kell egyeznie. Deklaráció: int osszehasonlit(struct csucs *gyoker1, struct csucs *gyoker2);
  • Írjon olyan függvényt C nyelven, ami visszadja egy 1-nél nagyobb egész szám legkisebb, 1-nél nagyobb (prím)osztóját. Deklaráció: int minoszto(int n);. Az osztó keresését 2-től négyzetgyök n-ig végezze.
  • Írjon olyan függvényt C nyelven, ami visszadja az n karakterből álló t tömbben a leghosszabb szó hosszát (ami 0 is lehet, ha egy szó sincs a tömbben). Szónak számít egy szóközt nem tartalmazó, tovább nem bővíthető, összefüggő részsorozat. Deklaráció: int maxszohossz(char t[], int n);
  • Írjon egy olyan rekurzív függvényt C nyelven, ami kiszámolja az n alatt a k binomiális együtthatót modulo m. Deklaracio: int binom(int n, int k, int m); Használja ki, hogy 0 alatt a 0 egyenlő 1-gyel, egyébként 0 alatt az n egyenlő 0-val, egyébként pedig n alatt a k egyenlő (n-1) alatt a k plusz (n-1) alatt a (k-1).
  • Írjon olyan függvényt C nyelven, ami keres a 100-szor 100-as m mátrixban két azonos sort, és visszadja azok sorszámát (0 <= i < j < 100). Ha nincs két azonos sor, akkor i=j=100-at ad vissza. Deklaráció: void azonos_sort_keres(int m[100][100], int *i, int *j);</code>
  • Írjon olyan függvényt C nyelven, ami kiszámolja három szám legnagyobb közös osztóját. Írhat segédfüggvényt is. Deklaráció: int lnko3(int a, int b, int c);
  • Írjon olyan függvényt C nyelven, ami meghatározza, hogy egy háromszög derékszögű-e, és 0-et ad vissza, ha nem, 1-et, ha az A csúcsnál van derékszög, 2-t, ha a B csúcsnál, és 3-at, ha a C csúcsnál. A háromszög 3 csúcspontjával van megadva, minden koordináta egész szám. A derékszögűséget vektorok skalárszorzatával határozza meg. Deklaráció: int derekszogu_e(int ax, int ay, int bx, int by, int cx, int cy);.

Házi feladatok

A házi feladatokat a SIO rendszer segítségével kell beadni. Minden SIO-ban kitűzött feladatot be kell adni, kivéve amelyekhez explicit módon oda van írva, hogy szorgalmi feladat.

Technikai részletek

A C fordításhoz használt szoftver a gcc (a pontos verzió: gcc 4.1.2 Debian 4.1.1-21). A házi feladatokat a következő módon fordítjuk:

$ gcc -x c -O2 -std=c99 -pedantic-errors -static -o <prog> <forrásfájl>.c -lm

A feladat megoldásakor előbb nem a fenti paranccsal, hanem az alábbival érdemes előbb kipróbálni a fordítást:

$ gcc -W -Wall -s -O2 -std=c99 -pedantic-errors -lm -o <program> <program>.c

Ez azért jó, mert a -W -Wall sok hasznos figyelmeztető üzenetet megjelenít, és ily módon a hibákra hamar felhívja a figyelmet.


A házi feladatok listája elérhető a SIO rendszerben is: https://sioweb.math.bme.hu/user.phtml?op=zadania

Típushibák a házikban

  • A Compile error oka lehet az is, hogy a beadott fájl kiterjesztése nem .c . Tipikus rossz kiterjesztések: .cc, .cpp, .cxx.
  • A runtime error-nak lehet oka, hogy a return 0; hiányzik a main függvény végéről.
  • A forrásfájl utolsó sorának végén nincs soremelés (emiatt compile error).
  • Nagy, 8 MB-nál nagyobb tömb van a main függvényen belül (emiatt runtime error és segmentation fault). Megoldás: a tömb deklarációját a függvényen kívülre tenni. Például így jobb:
char nagytomb[10000000];
int main(void) {
  ...
  return 0;
}
  • A getchar() eredménye char típusú változóba kerül. Ez azért nem jó, mert a char csak 256 különböző értéket tud tárolni, de nekünk 257 kéne (a 256 karakter, és a fájl végét jelző -1). Megoldás: int típusú változóba tenni.
  • Függvényen belül függvény van definiálva. Ez nem jó, a függvényeket csak egymás után szabad definiálni.
  • A program fölösleges szóközöket ír ki (pl. a sor végére), és emiatt wrong answer-ös a megoldás. Ha azt kell kiírni, hogy hello, majd egy soremelést, akkor jó megoldás a printf("hello\n");, rossz megoldás a printf("hello \n");
  • Az eratoszthenészi szitát while cikluson belül az összes feladványra végigszámolja, pedig elég lenne összesen egyszer. Emiatt time limit exceeded-es a megoldás.
  • Tetszőleges karaktert nem lehet beolvasni gets()-sel vagy fgets()-sel, mert elnyelik a 0-s kódú karaktereket. A helyes megoldás karakter beolvasásásra getchar().
  • A program beszélgetni próbál a felhasználóval, pl. kiírja, hogy Most kérem a mátrix sorainak számát. Épp amiatt rossz (wrong answer) a kimenet, hogy ez az üzenet is szerepel benne.
  • A program egymás alá próbálja igazítani a számokat. Épp amiatt rossz (wrong answer) a kimenet, hogy az igazítás miatt fölösleges szóközöket ír ki.
  • A program túl sok memóriát használ, például a szitáláshoz használt tömb elemeit int-ekből építi, noha char-okba is beleférne. i386 architektúrán az int 32 bites (ebből 1 előjel), a char 8 bites (ebből 1 előjel), tehát egy charban a [-128,127] zárt intervallumból lehet szám.
  • Túl nagynak veszi a tömböt (és amiatt memory limit exceeded-et kap). A feladatkiírásban pontosan meg van adva a bemeneti adatok értéktartománya. Pont akkora (vagy egy hajszálnyival nagyobb) tömböt kell deklarálni, amekkorába az adat belefér.
  • A tömb mérete nem konstans. Például hibás az int tomb[n]; deklaráció, és helyes az int tomb[500]; deklaráció, ha n értéke legfeljebb 500 lehet (az értéktartományt lásd a feladat szövegében).
Személyes eszközök