Python
import math, cmath
a= input('Kérem a másodfokú egyenlet főegyütthatóját: ')
a= float(a)
while a==0:
print('Ez nem lesz másodfokú egyenlet; nem oldom meg.')
a= input('Kérem a másodfokú egyenlet főegyütthatóját: ')
a= float(a)
b= input('Kérem az elsőfokú tag együtthatóját: ')
c= input('Kérem a konstans tagot: ')
b= float(b)
c= float(c)
d= b*b-4*a*c
print('A diszkrimináns értéke', d)
if d>=0:
print('Van valós megoldás.')
x1= (-b-math.sqrt(d))/(2*a)
x2= (-b+math.sqrt(d))/(2*a)
print('Az egyik megoldás', x1)
print('A másik megoldás', x2)
else:
print('Nincs valós megoldás.')
x1= (-b-cmath.sqrt(d))/(2*a)
x2= (-b+cmath.sqrt(d))/(2*a)
print('Az egyik megoldás', x1)
print('A másik megoldás', x2)
Elmélet
Adatszerkezetek
Adatelem: Az a legkisebb adategység, melyre hivatkozni lehet
Adatszerkezet: Az adatelemek olyan véges halmaza, amelyben az adatelemek között szerkezeti összefüggések vannak. A szerkezeti összefüggések határozzák meg az alapelemek egymáshoz való viszonyát és az adatszerkezeten végezhető műveleteket.
Osztályozásuk szerkezetük szerint:
Homogén adatszerkezetek
A homogén adatszerkezetek azonos típusú adatelemekből épülnek fel.
Struktúra nélküli homogén adatszerkezetek
A struktúra nélküli adatszerkezetek esetében az egyes adatelemek függetlenek, azaz nincs közöttük semmi nemű kapcsolat, alá- illetve fölérendeltség, vagy sorrend. Így bármikor eldönthető, hogy egy kiválasztott elem az adatszerkezet komponense-e vagy sem.
Halmaz: A matematikai halmazfogalom megjelenése adatszerkezeti szinten.
Multihalmaz: Olyan speciális halmaz, amely ismétlődést is megenged, azaz lehetnek benne azonos elemek.
Seriális állomány: Olyan speciális állomány, amelyben az adatok egymást után helyezkednek el.
Asszociatív homogén adatszerkezetek
Az asszociatív adatszerkezetek esetében a rendelkezésre álló elemekből részhalmazokat tudunk képezni amelyek átfedhetik egymást. Az adatelemek között lényegi kapcsolat nincs, de az adatelemek tartalmuk alapján címezhetőek.
Tömb: Az egyik legismertebb és leggyakrabban alkalmazott adatszerkezet. Bármelyik adateleme elérhető úgynevezett indexek (azonosító koordináták) használatával. Reprezentációi:
Sor: Az adatok egy sorban helyezkednek el, egy dimenziós adatszerkezet, egy indexű. (Nap azonos a sor adatszerkezettel!)
Mátrix: Az adatok sor-oszlop egységet alkotnak, tehát két dimenziós az adatszerkezet, így az adatelemek két index segítségével címezhetők.
Tömb: Három- vagy több dimenziós megjelenési forma.
Táblázat: A táblázat két elemből áll: egy kulcsból és egy értékből. A kulcs hordozza az érték elérési helyét. Reprezentációi:
Soros: Az adatok sor-oszlop koordinátában helyezkednek el (ezek találkozásánál találhatók a cellák). Minden egyes cellában egy kulcs és egy érték foglal helyet.
Önátrendező: Azt az elvet valósítja meg, amely szerint a leggyakrabban használt elemek (és kulcsaik) a táblázat elején kapnak helyet.
Rendezett: Valamilyen kulcs alapján (például növekvő sorrendben) rendezett táblázat.
Kulcstranszformációs: Folytonos tármegjelenése van. Egy függvény felel azért, hogy a megfelelő kulcs a megfelelő címre legyen leképezve (azaz a kulcshoz adat legyen rendelve).
Direkt állomány. Olyan állománykezelési forma, amely esetében az állomány bármely adata bárhonnan elérhető.
Random állomány. Felépítése a direkt állományéhoz hasonlít, azzal a különbséggel, hogy az elérése véletlenszerű.
Indexelt állomány. Valamilyen logikailag rendezett állomány, amely esetében az adatok változatlanul a helyükön maradnak, mindössze az állomány fejében tárolódik egy rendezett lista.
Invertált állomány. Olyan állomány, amely egy másik állomány rekordjait valamely más kulcs szerint teszi közvetlenül elérhetővé.
Multilista állomány. Olyan állomány, amelyben több egymásba ágyazott és rendezett lista kap helyet.
Szekvenciális homogén adatszerkezetek
Az adatelemek egymás után következnek, minden elem két másikkal van közvetlen kapcsolatban, kivéve az első és utolsó elemet, azaz egyértelmű sorrendje van az adatelemeknek - láncolt lista, verem, sor
Lista: Ha nem üres, akkor van első és utolsó eleme, valamint minden adatelemenek van megelőző és rákövetkező eleme.
Verem: (LIFO (teljes nevén Last In First Out) szerkezet) Olyan speciális lista, ahol az utoljára betett eleme dolgozható fel először. A verem lehet folytonos és szétszórt.
Sor: (FIFO (teljes nevén First In First Out) szerkezet) Speciális lista, amely esetében az elsőként betett elem dolgozható fel először. A sor lehet fix kezdetű, vándorló vagy ciklikus.
Sztring: Olyan lista, amelynek elemeit szimbólumok alkotják. A sztring lehet folytonos vagy szétszórt ábrázolású.
Szekvenciális állomány: Olyan állomány, amely esetében a rekordok az azonosító, azaz elsődleges kulcs szerint rendezettek.
Hierarchikus szerkezetek
A hierarchikus adatszerkezetek esetében egy elemnek akárhány rákövetkezője lehet, de minden elemnek csak egyetlen megelőzője létezik, másképp alárendeltje több lehet, de fölérendeltje csak egy (1 szülő, több leszármazott)
Fa: Olyan rekurzív adatszerkezet, amely esetében minden elem elárulja a rákövetkezőjét. Minden fa csúcsa a gyökérelem, amihez közbenső elemek tartoznak. Minden fát a levélelemek zárnak. A fákon belül úgynevezett részfák is képezhetők, amelyek önálló faként képesek működni. A fa bejárása többféle módon történhet:
Preorder (vagy prefix) bejárás. Előbb a gyökér, majd a fa bal- illetve jobb ága lesz bejárva.
Inorder (vagy infix) bejárás. Előbb a fa bal ága, majd a gyökere, és végül a jobb oldali ága lesz bejárva.
Postorder (vagy postfix) bejárás. Előbb a fa bal-, majd jobb ága lesz bejárva. Ezt követi csak a gyökér.
Hierarchikus lista: (multilista, összetett lista) Olyan lista, melynek elemei lehetnek adatelemek és listák.
Hierarchikus állomány:. A hierarchikus listát megvalósító állomány.
Hálós szerkezetek
A hálós adatszerkezetek a fák általánosításai, azaz olyan megjelenési formával bírnak, amelyek esetében az elemeknek akárhány megelőzőjük és rákövetkezőjük lehet, beleértve azt is, hogy két elem között olyan kapcsolat van, amely szerint az egyik elem a másik rákövetkezője és megelőzője is egyaránt lehet.
Gráf: A hálózatok modellezésére szolgál. Reprezentálni összefüggő, irányított gráf segítségével lehet.
Heterogén adatszerkezetek
A heterogén adatszerkezetek elemei eltérő típusúak lehetnek. Egyetlen megjelenési formája van: a rekord, amely egy tárban létező statikus adatszerkezet (tárolása alapján lehet folytonos és szétszórt). Kötött számú és sorrendű mezőből áll, amely mezők más-más, tetszőleges típusú értékeket tartalmaznak. A rekordban minden mezőt megnevezünk, és hivatkozáskor közvetlenül ezen nevet használjuk.
Bizonyos értelemben a rekord adatszerkezet kibővítése az objektum, mint adatszerkezet.
A helyfoglalás időbeni változása szerint
Statikus helyfoglalású
Elemeinek száma használatuk során állandó marad. Ilyen esetekben a felhasználó feladata, hogy megadja a szükséges elemszámot, azaz az adatszerkezetet feltöltse adattal. Fordítási időben eldől, hogy mekkora méretű tárterületet kell lefoglalni az adatszerkezet számára.
Például: Turbo Pascal array vagy record adatszerkezete
Dinamikus helyfoglalású
Használatuk során elemeinek száma változhat, sőt akár nullára is csökkenhet. Programozási szempontból kezelésük jóval bonyolultabb, mint a statikus adatszerkezeteké, gondoskodni kell a tárterület lefoglalásáról és felszabadításáról.
Az adatszerkezetet rekurzívnak nevezzük, ha definíciója önmagára vanatkozó hivatkozást tartalmaz (például: lista, fa). A rekurzív adatszerkezetet lineárisnak nevezzük, ha egy ilyen hivatkozást tartalmaz csak, azaz egyértelmű az adatelemek sorrendje (így például a fa nem lineáris).
A tárolása módja szerint
Folytonos (szekvenciális vagy vektorszerű)
A memóriában tárolt elemek egy folytonos tárterületen, egymás után helyezkednek el, és az adattételek tárolási jellemzői (típus, ábrázolási mód, hossz) azonosak.
Szétszórt
Az adatelemek szétszórtan helyezkednek el a memóriában, és elemei úgynevezett listaláncolással kapcsolódnak egymáshoz. A listák kiépítése a következő lehet:
Egy irányba láncolt lista: Minden eleme tartalmaz egy adat- illetve egy mutatórészt, amely utóbbi mindig a következő elem adatrészére mutat. Az első elem adatrészére egy úgynevezett fejelem mutat, jelezvén ezzel a lista kezdetét, míg az utolsó elem mutatója NIL (teljes nevén Non In List) „értékű”.
Cirkuláris lista: Teljes mértékben megegyezik az egy irányba láncolt listával, mindössze annyi az eltérés, hogy az utolsó elem mutatója az első elem adatrészére mutat.
Két irányba láncolt lista: Nagyban hasonlít az egy irányba láncolt listához, ám itt minden elemnek két mutatója van. Az első mutat a következő elemre, míg a második az előzőre.
Multilista: Olyan lista, amely egyesíti a cirkuláris- és a két irányba láncolt listát.
Verem (Stack) (LIFO)
Mindig az utolsó elem van legfeleül, azt vehetjük ki először
pl.: eljárások futtatása memóriából
Utasításkészlet
inicializálás
elem betevés
elem kivétel
üres?
tele van? (csak statikusnál van értelme)
Sor (Buffer) (FIFO)
ami először berakunk, azt vesszük ki először
pl.: billentyűzet buffer (ha túl gyorsan gépelünk, innen olvassa ki a gép az adatokat), szekvenciális fájl olvasása
Utasításkészlet
inicializálás
elem betevés
elem kivétel
üres?
tele van? (csak statikusnál van értelme)
Megvalósítás
Verem (Statikus)
Mire van szükség?
Tömb adatszerkezet (ennek lesz egy maximális elemszáma)
Mutató - hogy hol is tartunk (DB)
Utasítások
Inicializálás: Db = 0
üres?: Db = 0 ?
tele?: Db = Db length ?
berakás: Ha tele? = false akkor Db = Db + 1 és Tömb[Db] = elem
kivétel: Ha üres? = false akkor Db = Db - 1
Sor (Statikus)
Mire van szükség?
Tömb adatszerkezet (ennek lesz egy maximális elemszáma)
Két mutató, eleje, vége
üres? boolean
--------------
Algoritmusok és programozás
Az alábbiakban egy rövid feladatgyűjteményt közlünk azok számára, akik a programozás alajaival szeretnének megismerkedni.
A feladatokhoz a legtöbb esetben C# nyelvű megvalósítást is elérhetővé tettünk, de az összeállítás célja nem egy programozási nyelv bemutatása és tanítása lenne, hanem olyan ismeretekre próbálunk rákérdezni, amelyek bármilyen választott programozási nyelv esetén szükségesek.
Rekurzió
Faktoriális
hatványozás
szó megfordítás
binomilis együttható számolsa
maximumkivlasztás
sorozat-számítás
rekurzív bináris keresés
foci csapat bevonulás
Fibonacci
Hanoi tornyai
fa bejárása
gyorsrendezés
összefésülő rendezés
visszalépéses keresés
LNKO(m,n) = n|m ? n : LNKO(n, m % n)
Descartes szorzat
k elemű részhalmazok generálása
számrendszerek közötti átváltás
Mikor használunk rekurziót?
Az eredmény rekurzív szerkezetű
ismétléses permutciók generálása (pl 2db a, 3db b és 1db c permutációi - első elem+maradék)
valamennyi részhalmaz generálsa
partíciók megadása (pozitív egész összegre bontsa)
halmaz partíciók (diszjunkt részhalmazokra bontás)
Ha a feladat szövege rekurzív szerkezetű
Ha a megoldás módszere a backtrack
Ha a megoldás módszere az „oszd meg és uralkodj” (divide et impera)
Ha a feldolgozandó adatszerkezet rekurzív (fa, lista)
Teljes indukció
Iterációvá alakítás
verem (paraméterek, lokális változók címe, program kód visszatérési címe)
rekurzív adatszerkezetek - fa (üres|pont+bal fa+jobb fa)
fraktálok
logo
növekvő négyzetek
sorminta n elemmel
spirál
Koch
Sierpinski
Fa
Pitagorasz-fa
requrzió mélysége, szélessége
doboz-pakolás „élő” rendezés más tétel fiókokkal/dobozokkal - minden lépést más csinál… Rajz/építmény elmonds alapján.
Programozási tételek
A programozási tételek egyszerű alap algoritmusok, azaz típusfeladatok minta megoldásai, melyek bizonyítottan jók és hatékonyak, így a „tétel” elnevezés jogos rájuk nézve.
Sorozathoz érték rendelése
Az alábbi tételekben minden esetben egy A tömb elemeiből indulunk ki, eredményül pedig egy értéket kapunk.
Eldöntés tétel
Adott egy N elemű A tömb. valamint egy T() tulajdonság (logikai függvény). Döntsük el, hogy van-e az A tömbnek T tulajdonságú eleme.
Állapot tér
N in bbN, A = bbR^{N}, T: bbR right delim{lbrace}{igaz, hamis}{rbrace}
azaz N természetes szám az A tömb elemszáma, a tömb tehát N darab valós számot tartalmaz, a T tulajdonság pedig a valós számokhoz rendel igaz, vagy hamis értéket.
Előfeltétel
nincs
Utófeltétel
Ki: (exists i in bbN, 1<=i<=N: T(A(i)))
azaz a visszatérési érték akkor lesz igaz, ha találtunk az A tömbben T tulajdonságú elemet, pontosabban akkor, ha van olyan érvényes (1 és N közé eső) i index, melyre igaz, hogy az A tömb i-edik eleme T tulajdonságú.
Algoritmus
i := 1
Ciklus amig (i <= N) és nem T(A(i))
i := i + 1
Ciklus vége
Ki: (i <= N)
Magyarázat:
Az elemek vizsgálatát az első elemtől kezdjük (i := 1), és lépegetünk sorba az elemeken (i := i + 1), amíg el nem érjük a tömb végét (i ⇐ N), vagy nem találunk T tulajdonságú elemet (nem T(A(i))). A visszatérési érték akkor lesz igaz, ha nem értük el tömb végét (i ⇐ N).
Feladatok
Ismerjük egy hét napjainak napi átlaghőmérsékleteit. Igaz-e, hogy folyamatosan emelkedett a hőmérséklet?
Állapítsuk meg egy szövegről, hogy eszperente szöveg-e (eszperente szöveg az, amelyben csak e és é magánhangzók szerepelnek)
Adott szövegről döntsük el, hogy több mondatból áll-e! (Mondathatár: mondatvégi írásjel, szóköz, majd nagybetű)
Egy repülőgéprő Európából Amerikába repülve rendszeres időközönként mérték a tengerszint feletti magasságot (0 tengert, pozitív érték szárazföldet jelöl). Döntsük el, hogy az út során haladt-e el sziget felett a repülőgép!
Kiválasztás tétel
Adott egy N elemű A tömb. valamint egy T() tulajdonság (logikai függvény). Tudjuk, hogy a tömbnek van T() tulajdonságú eleme. Adjunk meg egy T() tulajdonságú elemet, vagy annak indexét!
Állapot tér
N in bbN, A = bbR^{N}, T: bbR right delim{lbrace}{igaz, hamis}{rbrace}
azaz N természetes szám az A tömb elemszáma, a tömb tehát N darab elemet tartalmaz, a T tulajdonság pedig az elemekhez rendel igaz, vagy hamis értéket.
Előfeltétel
exists i in bbN, 1<=i<=N: T(A(i))
Az A tömbnek van T() tulajdonságú eleme.
Utófeltétel
Ki: i, A(i) (i in bbN, 1<=i<=N: T(A(i)))
azaz a visszatérési érték az i index, vagy a tömb i-edik eleme, melyre A(i) T() tulajdonságú.
Algoritmus
i := 1
Ciklus amig nem T(A(i))
i := i + 1
Ciklus vége
Ki: i, A(i)
Feladatok
Adjuk meg egy beolvasott 1-nél nagyobb pozitív egyész szám legkisebb 1-től különböző pozitív osztóját!
Adjuk meg egy beolvasott 1-nél nagyobb pozitív egyész szám legnagyobb önmagától különböző pozitív osztóját!
Határozzuk meg két szám legnagyobb közös osztóját!
Határozzuk meg az N természetes számhoz legközelebbi négyzetszámot (N>1)!
Határozzuk meg hány nap múlva lesz a legközelebbi vasárnap!
Keresés tétel
Adott egy N elemű A tömb. valamint egy T() tulajdonság (logikai függvény). Döntsük el, hogy van-e az A tömbnek T tulajdonságú eleme, ha van adjuk meg az elemet, vagy az elem tömbbeli indexét!
Állapot tér
N in bbN, A = bbR^{N}, T: bbR right delim{lbrace}{igaz, hamis}{rbrace}
azaz N természetes szám az A tömb elemszáma, a tömb tehát N darab valós számot tartalmaz, a T tulajdonság pedig a valós számokhoz rendel igaz, vagy hamis értéket.
Előfeltétel
nincs
Utófeltétel
Ki: (exists i in bbN, 1<=i<=N: T(A(i))) esetén delim{lbrace}{i; A(i)}{rbrace}, különben hamis
azaz a visszatérési érték akkor lesz hamis, ha nem találtunk az A tömbben T tulajdonságú elemet, egyéb esetben a T tulajdonságú elem indexég és az elemet magát adjuk vissza.
Algoritmus
i := 1
Ciklus amig (i <= N) és nem T(A(i))
i := i + 1
Ciklus vége
Ha (i <= N) akkor
Ki: i, A(i)
különben
Ki: hamis
Elágazás vége
Magyarázat:
Az elemek vizsgálatát az első elemtől kezdjük (i := 1), és lépegetünk sorba az elemeken (i := i + 1), amíg el nem érjük a tömb végét (i ⇐ N), vagy nem találunk T tulajdonságú elemet (nem T(A(i))). Ha nem értük el tömb végét (i ⇐ N), akkor találtunk T tulajdonságú elemet, így ezt, illetve ennek indexét adjuk vissza, egyéb esetben hamis logikai értékkel tér vissza.
Feladatok
Megszámolás tétel
Adott egy N elemű A tömb. valamint egy T() tulajdonság (logikai függvény). Számoljuk meg, hogy hány T tulajdonságú eleme van az A tömbnek.
Állapot tér
N in bbN, A = bbR^{N}, T: bbR right delim{lbrace}{igaz, hamis}{rbrace}, Db in bbN
azaz N természetes szám az A tömb elemszáma, a tömb tehát N darab valós számot tartalmaz, a T tulajdonság pedig a valós számokhoz rendel igaz, vagy hamis értéket.
Előfeltétel
nincs
Utófeltétel
Db = |delim{lbrace}{i in bbN | T(A(i))}{rbrace}|
azaz a Db változó az A tömb T tulajdonságú elemeinek számával egyenlő
Algoritmus
Db := 0
Ciklus i := 1-től N-ig
Ha T(A(i)) akkor Db := Db + 1
Ciklus vége
Ki: Db
Összegzés (sorozatszámítás) tétel
Adott egy N elemű, számokat tartalmazó A tömb. Határozzuk meg az A tömb elemeinek összegét!
Állapottér
N in bbN, A = bbR^{N}
Előfeltétel
nincs
Utófeltétel
S = sum{i=1}{N}{A(i)}
Algoritmus
S := 0
Ciklus i := 1-től N-ig
S := S + A(i)
Ciklus vége
Ki: S
Magyarázat: S-ben tároljuk az eddig sorra vett elemek összegét, i mutatja, hogy hányadik elemnél tartunk a feldolgozás közben.
Első lépésként - mivel még egy elemet sem vizsgáltunk meg - az S kezdőértékét 0-ra állítjuk. Ezután végig megyünk az összes elemen (ezért számlálásos ciklust használunk) és S értékét minden lépésben az A tömb soron következő elemével növeljük.
Az algoritmus gondolatmenete minden olyan esetben alkalmazható, ahol a sorozathoz rendelt érték megadható az eggyel rövidebb sorozat és az utolsó tag segítségével (rekurzív módon):
f(a_1,a_2,...,a_n) = f(a_1,a_2,...a_{n-1}) circ a_n
Ilyen a szumma függvény az összeadás művelettel párban, a produktum függvény a szorzás művelettel, de ilyen a számok átlaga, mértani közepe, szövegek egymásután fűzése és még sok egyéb függvény is.
Feladatok
Olvassunk be egy n pozitív egész számot, majd számítsuk ki az n! értéket!
Egy napon minden órában megmértük a hőmérsékletet. Számítsuk ki ezen adatok alapján a napi átlaghőmérsékletet!
Adott szavakat fűzzünk össze közéjük szóközöket helyezve!
Maximumkiválasztás
Adott egy N elemű A tömb. Válasszuk ki a tömb legnagyobb elemét.
Algoritmus
MaxIndex := 1
Ciklus i := 2-től N-ig
Ha A(i) > A(MaxIndex) akkor MaxIndex := i
Ciklus vége
Ki: MaxIndex, A(MaxIndex)
Logaritmikus keresés
Adott egy N elemű, rendezett A sorozat. Keressük meg benne az X értéket!
Algoritmus
E := 1
V := N
Ciklus
K := int((E+V) / 2)
Ha A(K) > X akkor V := K - 1
Ha A(K) < X akkor E := K + 1
Amíg A(K) <> X és E <= N
Ha E > N akkor Ki: nincs
különben Ki: K
Sorozathoz sorozat rendelése
Rendezés
Adott egy N elemű A tömb. Rendezzük a tömb elemeit emelkedő sorrendbe!
Minimumkiválasztásos rendezés
Ciklus i := 1-től N-1-ig
// minimumkiválasztás
minIndex := i
Ciklus j := i+1-től N-ig
Ha A(minIndex) > A(j) akkor
minIndex := j;
Elágazás vége
Ciklus vége
// csere
Segéd := A(i)
A(i) := A(minIndex)
A(minIndex) := Segéd
Ciklus vége
Kiválogatás
Adott egy N elemű A tömb és egy T tulajdonság. Válogassuk ki egy B tömbbe az A vektor T tulajdonságú elemeit.
Algoritmus
Db := 0
Ciklus i := 1-től N-ig
Ha T(A(i) akkor
Db := Db + 1
B(Db) := A(i)
Elágazás vége
Ciklus vége
Szétválogatás - két tömbbe
Adott egy N elemű A tömb és egy T tulajdonság. Válogassuk ki az A vektor T tulajdonságú elemeit egy B, nem T tulajdonságú elemeit egy C tömbbe.
Algoritmus
Db := 0
Ciklus i := 1-től N-ig
Ha T(A(i) akkor
Db := Db + 1
B(Db) := A(i)
különben
C(i-Db) := A(i)
Elágazás vége
Ciklus vége
https://wiki.mayor.hu/doku.php?id=oktatas:informatika:alapismeretek
Nincsenek megjegyzések:
Megjegyzés küldése