SZIMP2

A MathWikiből
A lap korábbi változatát látod, amilyen SisakAron (vitalap | szerkesztései) 2007. március 4., 14:01-kor történt szerkesztése után volt.

Ez a wikioldal a 2007 februárjától az alkalmazott matematikusok számára Informatika 2 (más néven SZIMP2) tárgy honlapja.

Tartalomjegyzék

Oktatók

  • Az előadásokat és a gyakorlatokat tartja Szabó Péter <pts+i@math.bme.hu>, beceneve pts.
  • A házi feladatokat és a ZH-kat javítja, a konzultációk egy részét tartja Sisak Áron <aron@math.bme.hu>.

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. Az H.27-es laborban 14 munkára alkalmas gép van, amiből hallgatók számára kényelmesen használható 12 db. A biztonság kedvéért az egyik gépet hagyjuk meg tartaléknak, tehát van 11 gép, 3 gyakorlati kurzus, és összesen 33 hallgató, akiket a fentiek miatt 3 egyenlő részre kell osztani. A felosztás 2007-02-16 (pénteken) 9:10-kor, az előadás előtti 5 percben fog megtörténni. Két lehetséges megvalósuás van.

  1. A hallgatók egyeztetnek, majd összeállítanak egy nekik megfelelő felosztást, és azt írásban benyújtják a jelzett időpontban. A formai követelmények: 3 lista lesz, melyeken a tárgyat felvett hallgatók felhasználónevei vannak egyértelműen szétosztva. Minden hallgató pontosan egy listán szerepel. Minden listán minimum 11, maximum 12 felhasználónév található.
  2. Ha a fenti felosztás nem kerül benyújtásra a jelzett időpontban, akkor az előzetes gyakorlati kurzusbeosztás lép életbe (lásd lent).

Indokolt esetben utólag is lehet cserélni (2 hallgató egymás között cserél). A csere módja: a hallgatók egymással egyeztetnek, majd mindketten küldenek pts-nek és a másik hallgatónak egy e-mailt legalább 24 órával a korábbi gyakorlat előtt.

A Neptunban levő hallgatói kurzus-hozzárendelés módosításának intézésével a hallgatóknak nem kell törődniük.

Aktuális gyakorlati kurzusbeosztás (közös megegyezéssel):

  • végleges kedd 14:15-re:
    • bartazsu Barta Zsuzsanna
    • btimi Borsos Katalin
    • czirakit Cziráki Tamás
    • zsero Erő Zsolt
    • farbas Fárbás Tamás
    • kristofh Hörömpöly Kristóf
    • jgabor Janecskó Gábor
    • macsakos Mácsai Ákos
    • molnarg Molnár Gábor
    • semdan Semler Dániel
    • tbarbara Tőke Barbara
    • wlaci Winkler László
  • végleges kedd 15:15-re:
    • szape Szabó Péter
    • szbence Szűcs Benedek
    • agiesze Esze Ágnes
    • daraib Darai Borbála
    • diagy Győri Klaudia
    • dsziraki Sziráki Dorottya
    • hutivi Hutvágner Ivett
    • jocika Pinczés József
  • végleges péntek 8:15-re: (a kivéve munkanapok helyett ugyanazon héten kedd 15:15-re kell jönni)
    • csizbal Csizmadia Balázs (kivéve február 23., március 2.)
    • gszj Göbölös-Szabó Julianna (kivéve március 2., március 9.)
    • vhalasz Halász Veronika (kivéve március 9., és március 23.)
    • istvanko Kolossváry István (kivéve március 23., és március 30.)
    • rkozma Kozma Róbert Thijs (kivéve március 30., április 6.)
    • nagyal Nagy Attila (kivéve április 6., április 13.)
    • pintye Pintye Norbert (kivéve április 13., április 20.)
    • sepsir Sepsi Róbert (kivéve április 20., április 27.)
    • tuzcsaba Tűz Csaba (kivéve április 27., május 4.)
    • urbane Urbán Eszter (kivéve május 4., május 11.)
    • szabov Szabó Viktor (kivéve május 11., május 18.)
    • fukoildi Fűkő Ildikó (kivéve május 18., feburár 23.)
    • csata Csata Árpád (kivéve március 2., március 9.)
    • gubeka Gubek Andrea (kivéve március 9., március 23.)
    • kbotond Koszta Botond (kivéve március 23., és március 30.)
    • mikulan Mikulán Attila (kivéve március 30., április 6.)
    • ivajda Vajda István

Tárgykövetelmények

A szorgalmi időszakban teljesítendő:

  • A kiadott házi feladatok megoldása és beadása a SIO rendszerbe. 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.
  • A második ZH megírása. A ZH valószínűleg számítógéppel megoldandó lesz. 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 fentieket összesítve kerül meghatározásra.

Katalógus

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

Az előadások látogatása nem kötelező.

A hallgatók munkája

Előadáson a hallgatók figyelnek és jegyzetelnek. Legalább annyit leírnak, amennyi a táblára kerül.

Gyakorlaton a gyakorlat ideje alatt a hallgatók megcsinálják a kitűzött feladatot. Minden hallgatónak saját számítógépe van, amivel a feladatot megoldja. A gyakorlatvezető segít, és ellenőrzi is a megoldást. Amelyik hallgató kész van, és unatkozik, plusz feladatot kér vagy talál ki magának, és azt is megoldja. Gyakorlaton általában nem kell jegyzetelni. Füzetbe jegyzetelés helyett ajánlott tömören, de egyértelműen fájlba írni. A begépelendő kódrészleteket a hallgatók megkapják fájlban.

Gyakorlaton 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 hobbi-szintű ismerete, tetszőleges programozási nyelv munkaerőpiacon versenyképes 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 otthon tanulnak, például az ajánlott irodalomból, esetleg az órai jegyzetükből. A ZH-kra való felkészülés legjobb eszköze a gyakorlás: az elmélet bebiflázása helyett sokkal eredményesebb (a ZH és a jövő szempontjából is) egy adott feladatot adott módon megoldó program elkészítése, vagy ilyen példaprogramok tanulmányozása.

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.

A hallgatók megírják a ZH-kat.

A hallgatók a félév végén beiratják a jegyet.

Ajánlott szoftverek

C nyelvhez Linux alatt ajánlott:

  • sima szövegszerkesztő: kate
  • fordítóprogram: gcc
  • fejlesztőkörnyezet: Kdevelop
  • egyéb segédprogramok: strace, valgrind

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ít, amin a fenti linuxos szoftverek megtalálhatók, és hosszadalmas telepítés nélkül kipróbálhatók.

Tananyag

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

Ajánlott irodalom:

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 ~/szimp2 mappába helyezze.
  • Minden fájlnév és mappanév kisbetűs.
  • A fájlnevek é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és még a fájl tartalmának módosítása előtt történik.
  • 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:

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

1. gyakorlat (2007-02-13 és 2007-02-16)

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.

Az szimp2 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.

~/szimp2/hello.c:

#include <stdio.h>
int main(void) {
  printf("Hello, World!\n");
  return 0;
}

A sor elején levő szóközök (ún 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 ~/szimp2
$ cd ~/szimp2
$ kate hello.c
$ gcc -W -Wall -s -O2 -o hello hello.c
$ ./hello
Hello, World!

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

~/szimp2/hello100.c:

#include <stdio.h>
int main(void) {
  int c;
  for (c=0;c<100;c++) {
    printf("Hello, World!\n");
  }
  return 0;
}

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. Inkább kapcsoljuk ki, mint hogy figyelnünk kelljen a hibázásaira, és folyamatosan küzdenünk kelljen vele.

Hasznos parancsok:

$ cd ~/szimp2
$ 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

~/szimp2/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;
}

~/szimp2/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, és visszaadja az eredményt. Hasonlóa 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 miatt vannak.

1. előadás (2007-02-16)

Megtanultuk:

  • bemenet
  • kimenet
  • processzor
  • memória
  • program
  • bájt: 1 bájt == 8 bit; 0..255
  • folyamatábra
  • *
  • +
  • <<
  • < <= == > >=
  • a=b=0
  • if
  • for
  • while
  • goto
  • printf-ből a %d és a \n
  • getchar: while (0<=(c=getchar()))
  • putchar
  • else: csak érintettük. Példa: if (a<0) b=-1; else b=1;

~/szimp2/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

~/szimp2/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

2. gyakorlat (2007-02-20)

A gyakorlat megkezdése előtt ezt az útmutatót mindenki figyelmesen olvassa el, a gyakorlaton pedig figyelmesen kövesse. A figyelmes követésnek része, hogy a bemásolandókat pontosan másoljuk be, a fájlnevet pontosan úgy adjuk meg, ahogy le van írva, minden karakter számít (tehát nem inputrc, hanem ~/.inputrc).

Ugyanazt a parancsot sosem írjuk be kétszer, hanem a korábbi beírást hasznosítjuk újra.

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    

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: ember gondol, gép talál ki):

#include <stdio.h>
int main(void) {
  int a=1, b=100;
  printf("Gondolj egy szamot %d es %d kozott (zart)!\n", a, b);
  ...
  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.

Az alábbira már nem jutott kedden idő, pedig jóval egyszerűbb, mint az embergondol.

Számkitalálós program (gepgondol.c: gep gondol, ember talál ki):

#include <stdio.h>
#include <math.h>
#include <time.h>
int main(void) {
  int a=1, b=100;
  int gondolt, tipp;
  srand(time());
  gondolt=rand()%(b-a)+a;
  printf("Gondoltam egy szamot %d es %d kozott (zart), talald ki!\n", a, b);
  while (1) {
    printf("Mit tippelsz?\n");
    scanf("%d",&tipp);
    if (gondolt>tipp) {
      printf("A gondolt szam nagyobb, mint %d\n", tipp);
    } else {
      printf("A gondolt szam nem nagyobb, mint %d\n", tipp);
    }
    ...
  }
  return 0;
}

2. előadás (2007-02-23)

Megtanultuk:

  • egydimenziós tömbök definiálása és 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
    • gyakorlaton lesz még szó ezek felderítéséről
  • 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
    • működik láncolt listákra is
      • az elemhozzáférés tömbnél konstans, listánál O(n) időigényű
      • az elem beszúrása listánál O(1), tömbnél O(n) időigényű
    • #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

~/szimp2/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] > x) {
      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 58 2 64 40 7 14 31 50 96 54 18 76 61 
$ 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 
# é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

~/szimp2/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;
}

Ez nem volt előadáson, de érdekes:

~/szimp2/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 (2007-02-27, 2007-03-02)

A feladat az egymilliónál kisebb prímszámok kiírása volt Eratoszthenészi szita segítségével, ~/szimp2/erszita1.c néven.

~/szimp2/erszita1.c:

/* Esze Ágnes megoldása alapján */
#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;
}

Kipróbálás:

$ cd ~/szimp2
$ 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ítani kellett 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 már kihúzta. Ehhez az alábbi módosítások voltak szükségesek:

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

~/szimp2/erszita2.c:

/* Esze Ágnes megoldása alapján */
#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 (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;
}

Kipróbálás ugyanúgy, mint erszita1 esetén, de erszita1 helyett erszita2-vel.

Harmadik, szorgalmi feladatként azt kellett megoldani, hogy a páros számokkal nem is foglalkozunk (kivéve a 2-t), a páros indexeket a tömbből is kihagyjuk. 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 kell írni, és kettesével kell ugrálni.

~/szimp2/erszita3.c

/* Esze Ágnes megoldásából indulva */
#include <stdio.h>
int main (void) {
  int i,j;
  char tomb[500000];
  for(i=0;i<500000;i++) {
    tomb[i]=0;
  }
  printf("2\n");
  for(i=2;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+=i) {
        tomb[j/2]=1;
      }
    }
  }
 hoppa:
  for(;i<1000000;i+=2) {
    if (tomb[i/2]!=1)
      printf("%d\n", i);
  }
  return 0;
}

Érdemes egymás mellett összevetni az erszita2.c-t és az erszita3.c-t.

3. előadás (2007-03-02)

A függvényekről és a rekurzióról volt szó. Ezeket a fogalmakat vettük:

  • függvény
  • visszatérési érték
  • paraméter
  • lokális változó
  • érték szerinti paraméterátadás
  • cím szerinti paraméterátadás
  • mellékhatás
  • rekurzió

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:

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;
}

Példa cím szerinti paraméterátadásra (~/szimp2/csere.c; ez már jó, és szerepelt is a táblán):

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;
}

Példa a hatványozás rekurzív számolására (~/szimp2/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 (~/szimp2/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 (~/szimp2/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;

Csemegeként (nem kerül számonkérésre) következzen a powmod2 olyan változata, ami a lokális változók értékét nem módosítja (~/szimp2/powmod3.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 powmod3(int alap, int kitevo, int modulus) {
  int ret;
  if (kitevo<=0) return 1;
  return powmod3b(alap%modulus, kitevo, modulus);
}
/** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
 * kitevo>=0.
 */
int powmod3b(int alap, int kitevo, int modulus) {
  return powmod3c(alap, kitevo, modulus, powmod3b(alap, kitevo/2, modulus));
}
/** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
 * kitevo>=0.
 */
int powmod3c(int alap, int kitevo, int modulus, int fele) {
  if (fele==0) return 0;
  return powmod3d(alap, kitvo, modulus, (fele*fele)%modulus);
}
/** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
 * kitevo>=0.
 */
int powmod3d(int alap, int kitevo, int modulus, int felnegyzet) {
  if (kitevo%2==0) return felnegyzet;
  return (alap*felnegyzet)%modulus;
}

Megjegyzés: a powmod3 függvény Cékla nyelven is működik. A Cékla nyelvet majd a Deklaratív programozás tárgy keretében fogjuk tanulni.

Példa a faktoriális rekurzív számolására (~/szimp2/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 (~/szimp2/fakt2.c; nem kell érteni, hogy miért jobb a fakt2, mint a fakt):

int fakt2(int n) {
  return fakt2b(n, 1);
}
/** n!*szorzo -t adja vissza. */
int fakt2b(int n, int szorzo) {
  if (n<2) return szorzo;
  return fakt2b(n-1, szorzo*n);
}

Példa a Fibonacci-sorozat rekurzív számolására (~/szimp2/fib.c; ez szerepelt is a táblán előadáson):

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 (~/szimp2/fib2.c; ez is szerepelt a táblán):

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 legrövidebb közös részstring hosszának rekurzív meghatározására (~/szimp2/lkrh.c). Ezt még nem kell érteni.

int max(int a, int b) {
  return a>b ? a : b;
}
int lkrh(char *s, char *t) {
  if (*s=='\0') return 0; /* ha az s üres, akkor lkrh==0 */
  if (*s=='\0') return 0; /* ha a  t üres, akkor lkrh==0 */
  if (*s==*t) { /* az első karakter azonos */
    return 1+lkrh(s+1, t+1);
  } else {
    return max(lkrh(s+1, t), lkrh(s, t+1));
  }
}

A fenti lkrh függvény túl lassú, mert rekurzív hívásakor ugyanarra az s--t párra többször is meghívódik (és tovább hívja magát rekurzívan). Jó lenne az első hívás után letárolni az eredményt.

Házi feladatok

A házi feladatokat a SIO rendszer segítségével kell beadni. Csak azokat kell beadni, amelyeknek a beadási határideje itt fel van tüntetve.

A többi SIO-beli feladatot szorgalmi feladatként lehet beadni. A szorgalmi feladatok megoldása elmélyíti a hallgató tudását, növeli a hallgató gyakorlati rátermettségét, és nagyban segíti a ZH-ra való felkészülést.

Technikai részletek

A C fordításhoz használt szoftver a gcc, verziószám gcc (GCC) 3.4.6 (Debian 3.4.6-4), a házi feladatokat a következő módon fordítjuk:

$ gcc -x c -O2 -std=c99 -static -o <forrásfájl>.o <forrásfájl> -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 -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.

Fontos, hogy a beadott C forrásfájlok .c-re végződjenek, ellenkező esetben a rendszer fordítási hibát jelez (Compile error).

A main függvénynek return 0;-ra kell végződnie.

Kiírt házi feladatok

kód leírás beadási határidő
uc https://sioweb.math.bme.hu/user.phtml?op=inc&id=6 2007. március 31., 24:00 CET
lcuc https://sioweb.math.bme.hu/user.phtml?op=inc&id=7 2007. március 31., 24:00 CET
pow2count https://sioweb.math.bme.hu/user.phtml?op=inc&id=38 2007. március 31., 24:00 CET
primecount https://sioweb.math.bme.hu/user.phtml?op=inc&id=205 2007. március 31., 24:00 CET

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

Személyes eszközök