Programozási tételek

[Calyd]

Szükségét éreztem egy olyan témának, ahol a programozási tételek szerepelnek. Itt igyekszem mindegyiket bemutatni, mi a lényege és nagyjából példával illusztrálni, hogy milyen problémákra alkalmazhatóak. A nehézsége a dolognak, hogy többen több nyelvet használunk, így forráskód használata nem biztos, hogy célszerû már ezen okból sem. A miatt is tartózkodnék a használatától, mert programozni tényleg nyelvfüggetlenül érdemes. Hiszen ha a gondolkodásmódot elsajátítjuk, akkor az egyes programozási környezetekkel is jobban boldogulunk, ugyanis csak az adott nyelv elemeivel, lehetõségeivel kell megismerkednünk. Algoritmust azonban – szerintem – célszerû lenne írnom. Itt viszont az a gondom, hogy több eszköz kínálkozna erre a célra, viszont bizonyosak itt nem megvalósíthatók, mások pedig túlzottan formálisak. Ezért azt hiszem a legjobb lesz, ha a szöveges megfogalmazásnál maradok. Akkor vágjunk is bele!

 

Mik is a programozási tételek? Talán megtévesztõ lehet az elnevezés. Itt nem axiómákról, vagy bizonyított matematikai állításokról van szó (bár megjegyzem, a hatékonyságuk bizonyított), hanem alapvetõ problémák legjobb algoritmusairól. A legjobb persze relatív fogalom és programozási szempontból is több aspektusból meg lehet vizsgálni, de most nem ez a célom. A lényeg, hogy ezeket az algoritmusokat úgymond építõkövekként használhatjuk, sok problémára megoldást adhatnak. Nyilván bonyolultabbak esetén ezeket kombinálni kell. Fontos megjegyeznem, hogy az itt leírtak a Neumann-elvû nyelvekhez használhatóak!

 

Megadom a tételek specifikációit is, mert így érzem teljesnek a leírást. Ezt négy részre lehet bonatni:

- Bemenet: a program olyan adatai, amit a feladat meghatároz, vagy a feladatoból következik.

- Kimenet: a program futása során a bemeneti adatokból keletkezõ eredmény(ek).

- Elõfeltétel: a bemenõ adatokkal szemben megfogalmazandó szigorítások, kritériumok, elvárások.

- Utófeltétel: itt kéne megfogalmazni, hogy a bemenetbõl miként is lesz a kimenet. Pontosabban, hogy mi teljesül a kimenetre.

 

A másolás tétele:

Ennek lényege, hogy egy sorozat elemeit lemásoljuk. Még nem mondtam meg, hogy mit is értek másolás alatt. Másolás alatt értem azt, hogy még egy példányt létrehozunk az adott struktúrájú sorozatból (lehet, hogy kéne egy téma az adatszerkezeteknek is…). Azaz az adott sorozat még egyszer szerepelni fog a memóriában. Ha szükséges, esetleg idõ közben az elemeken változtathatok. Például, ha van egy papírlapom, amin szerepelnek emberek adatai: név, nem, cím, telefonszám és e-mail cím. Szükségem lehet az adatokra mondjuk otthon is, de a munkahelyemen kell hagyjam az eredetit. Ilyenkor másolatra van szükségünk. Azonban lehet, hogy ennyi minden nem fontos már az emberekrõl, elég csak a nevük és az e-mail címük. Ilyenkor változtatok az adatokon a másolás során, hiszen nem másolok át mindent. Lehet, hogy nem életszerû a példa teljesen, de lényeg ez.

Specifikáció:

- Bemenet: a sorozat elemszáma és a sorozat elemei;

- Kimenet: egy sorozat;

- Elõfeltétel: a választott szerkezet elemeihez hozzá tudjunk férni (pl. egy halmaz elemeihez nem tudunk);

- Utófeltétel: a kimenõ sorozat elemei rendre a bemenõ elemeit tartalmazzák, és a két sorozat hossza egyenlõ.

Algoritmus: egyesével végigmegyünk a sorozat elemein, majd (esetlegesen megváltoztatva) egyesével elhelyezzük a másolatnak választott struktúrában.

 

Az eldöntés tétele:

Gyakori feladat, hogy megmondjuk van-e egy sorozatnak egy bizonyos tulajdonságú eleme. Talán érezhetõ, hogy a tétel általánosságát ez a „bizonyos tulajdonság” adja, hiszen ezt többféleképpen meghatározhatjuk. Például, ha adott száz szám, akkor van-e köztük prím? Van-e páros? Van-e páros prím? Ha emberekrõl van szó, akkor van-e „X Y”? Van-e olyan, aki magasabb, mint 190 cm és nincs gyereke? Szóval sokféle lehet ez a tulajdonság. Csupán annyi kritérium van, hogy értelmezhetõ legyen a sorozat elemeire. Nyilván nem értelmes például az kérdés, hogy a 2-nek van-e gyereke? 

Specifikáció:

- Bemenet: a sorozat elemszáma, a sorozat elemei és a tulajdonság-függvény, mely a sorozat egy elemérõl képez logikai értékre. Magyarul: egy elem megfelel-e a tulajdonságnak?

- Kimenet: egy logikai érték: igaz vagy hamis (igen van, vagy nem nincs a keresett elem);

- Elõfeltétel: nincs;

- Utófeltétel: ha van keresett elem, akkor van olyan eleme a sorozatnak, melyre teljesül a tulajdonság.

Algoritmus: egyesével vizsgáljuk meg a sorozat elemeit. A vizsgálat addig tart, amíg nem értünk a sorozat végére és nem „jó” tulajdonságú a vizsgált elem. Csak akkor van a sorozatnak az adott tulajdonságnak megfelelõ eleme, ha még nem vizsgáltunk meg minden elemet, de a vizsgálat már véget ért, egyébként nincs. Ez kicsit biztos furán hangzik, de gondoljuk csak végig! Ha nincs vége a sorozatnak, akkor (az „és” kapcsolat miatt) csak amiatt hagytuk abba a vizsgálatot, mert az éppen vizsgált elem megfelelõ volt.

A tételnek van egy másik változata, amikor is azt kell megmondani, hogy minden elem megfelel-e a tulajdonságnak. Ekkor a vizsgálat addig tart, amíg nem értünk az elemek végére és „jó” tulajdonságú elemet vizsgáltunk. Könnyen láthatjuk, hogy a sorozat minden eleme csak akkor volt megfelelõ tulajdonságú, ha a vizsgálat véget ért, és minden elemet megvizsgáltunk.

 

Folyt. köv.

[Gereby]

Nagyon jó ötlet. Örülök, hogy van egy ember, aki nagyon építõjellegû dolgokat ír ide a programozáshoz. Szerintem én is tanulok majd belõle, illetve szándékomban áll hozzá tenni jól bevállt módszereimet. Szerintem ide gyûjtsük a tudást, aztán ha valamelyikkel kapcsolatban valami fajta kérdés van, azt az adott nyelv topicjában tegyük fel. Ez legyen egy tudásbázis. Ki is emelem.

[Calyd]

Akkor folytatnám amit elkezdtem...

 

[/u]A kiválasztás tétele:

Vannak olyan esetek, amikor az adatainkról tudunk valamilyen előzetes tényt, és ezt kihasználjuk. Ez a tétel kicsit hasonló lesz az eldöntéshez. A sorozatunk elemein szintén értelmezni tudunk egy bizonyos tulajdonságot, hogy megfelelnek-e neki, avagy sem. Valamint az is tudjuk, hogy legalább egy elemre biztosan teljesül, csak épp nem tudjuk melyikre. Ezt az elemet szeretnénk meghatározni, vagyis kiválasztani. Lehetne egy kérdés, hogy miért nem az összest adjuk meg. A válasz egyrészt az, hogy az egy másik tétel, másrész az, hogy nem véletlenül másik, az ugyanis egy kicsit bonyolultabb. Visszatérve a kiválasztáshoz, mondok egy példát: a ruhásszekrényből a ruhák (ezek a sorozat elemi) szeretnénk kivenni a tavaszi dzsekit. Tudjuk, hogy van ilyen, csak nem, hogy melyik az. Ez talán buta példának tűnhet, de a számítógép szempontjából nem az. Nekünk van szemünk, így elég ránézni a ruhatárra, de gép nem így működik, neki szépen végig kell mindent pásztáznia.

Specifikáció:

- Bemenet: a sorozat elemszáma, a sorozat elemei és a tulajdonság-függvény, mely a sorozat egy eleméről képez logikai értékre. Magyarul: egy elem megfelel-e a tulajdonságnak?

- Kimenet: a keresett elem sorszáma (esetleg maga az elem, vagy mindkettő);

- Előfeltétel: létezik a sorozatnak olyan eleme, melyre a tulajdonság-függvény igaz értékű;

- Utófeltétel: egy sorszám, melyre teljesül, hogy a sorozat „sorszámadik” eleme a megfelelő tulajdonágú.

Algoritmus: egyesével vizsgáljuk meg a sorozat elemeit. A vizsgálat addig tart, amíg nem „jó” tulajdonságú a vizsgált elem (nézzük meg, mi a különbség az eldöntéssel szemben, és jusson eszünkbe az előfeltétel). A keresett sorszám épp az utolsóként vizsgált elem helye a sorozatban.

 

A lineáris keresés tétele:

Ez a tétel is sokban hasonlít az előző kettőre, sőt mit több, azok összeépítéséből kaphatjuk a megoldást. Szintén sorozatból indulunk ki, de semmi előzetes ismeretünk nincs az elemekről. Továbbra is szükségünk van a már megszokott „bizonyos tulajdonságú elem” fogalomra. A tétel lényege, hogy megnézi, van-e számunkra kedvező eleme a sorozatnak (eldöntés), és ha van, akkor meg is adja, hogy az hol található (kiválasztás). Például, hogy megint a ruhatáras példát vegyem elő: nem tudjuk, hogy ott van-e dzseki a szekrényben. Így előzetes tudás nélkül állunk neki, viszont ha ott van, akkor ki szeretnénk venni. Tehát keresünk.

Specifikáció:

- Bemenet: a sorozat elemszáma, a sorozat elemei és a tulajdonság-függvény, mely a sorozat egy eleméről képez logikai értékre. Magyarul: egy elem megfelel-e a tulajdonságnak?

- Kimenet: egy logikai érték: igaz vagy hamis (igen van, vagy nem nincs a keresett elem). Valamint a keresett elem sorszáma (esetleg maga az elem, vagy mindkettő);

- Előfeltétel: nincs;

- Utófeltétel: ha van keresett elem, akkor van olyan eleme a sorozatnak, melyre teljesül a tulajdonság, és ennek az elemnek a sorszámát adjuk vissza eredményül.

Algoritmus:

A feladatot meg lehetne oldani az eldöntés és a kiválasztás teljesen különálló megvalósításával, de nem ezt fogjuk tenni, hanem mint korábban említettem: a két tételt összeépítjük. Ezt könnyen megtehetjük, hiszen az algoritmusuk nagyon hasonló volt. Vizsgáljuk egyesével a sorozat elemeit. A vizsgálat addig tart, amíg nem értünk a sorozat végére és nem „jó” tulajdonságú elemet vizsgáltunk. Csak akkor van a sorozatnak az adott tulajdonságnak megfelelő eleme, ha még nem vizsgáltunk meg minden elemet, de a vizsgálat már véget ért, egyébként nincs (eddig volt az eldöntés). Ha van ilyen elem, akkor éppen őt vizsgáltuk meg utoljára, így a keresett elem sorozatbeli helye is rögtön megvan (kiválasztás).

 

A megszámolás tétele:

Szintén gyakori feladat, hogy a „bizonyos tulajdonság”-nak eleget tevő elemekből megtudjuk, hogy mennyi van. Például, a nagy leltárt készít a lekvárokról és kíváncsi, hogy hány baracklekvár van. Vagy egy számsorozat hány prímszámot tartalmaz? Esetleg hány bőrcipőnk van? Ismét közös fajtájú elemek között értelmezünk egy tulajdonság-függvényt, ez alapján fogunk dolgozni, így általánosítva a megoldást.

Specifikáció:

- Bemenet: a sorozat elemszáma, a sorozat elemei és a tulajdonság-függvény, mely a sorozat egy eleméről képez logikai értékre. Magyarul: egy elem megfelel-e a tulajdonságnak?

- Kimenet: darabszám, azaz egy természetes szám (nincs 2,357 darab lekvár például);

- Előfeltétel: nincs;

- Utófeltétel: a darabszám egy 1-től a sorozat elemszámáig tartó összeg eredményeképp kapható, ahol a tagok 0-k vagy 1-ek lehetnek. Ezt úgy tesszük meg, hogy a sorozat elemeinek megfeleltetünk 1-et, illetve 0-t attól függően, hogy teljesült, avagy nem teljesült rá az adott tulajdonság. Megjegyzem, hogy ez az ötlet sok egyéb helyen is előfordul.

Algoritmus:

A darabszámot nullára állítjuk, majd egyesével végigmegyünk a sorozat elemein, és minden egyes lépésben megvizsgáljuk, hogy az adott elem kielégíti-e az adott tulajdonságot (pl. nagymama, minden lekvárt megvizsgál, hogy micsoda). Ha megfelel az elem, akkor eggyel megnöveljük a darabszámot, különben nem kell tennünk semmit (hozzáadhatunk 0-t, de minek?)

 

Folyt. köv.

 

 

@Gereby:

Igen, én is így gondoltam, hogy ha nyelvfüggő kérdés van, akkor majd az oda kerül, ahova kell.

[Calyd]

A maximum (minimum) kiválasztás tétele:

Gyakori feladat, hogy meghatározzuk egy sorozat maximális vagy minimális elemét. A két probléma megvalósításban nem különbözik nagymértékben, pusztán csak az elemek között a „kisebb” relációt kell alkalmazni és így módosítani a tételt. A probléma megvalósításához szükséges, hogy a sorozat elemei között értelmezni tudjuk a „nagyobb” relációt, hiszen a maximum az, aki mindenkinél nagyobb. Ami szabadságot nyújt, hogy miként értelmezzük azt, hogy egy elem nagyobb a másiknál. Például, emberek között lehet a magasság alapján, vagy az életkor alapján, esetleg mindkettõ.

Specifikáció:

- Bemenet: a sorozat elemei, a sorozat elemszáma és a nagyobb-függvény;

- Kimenet: a maximális elem sorszáma, azaz egy természetes szám (esetleg maga az elem, vagy mindkettõ);

- Elõfeltétel: nincs;

- Utófeltétel: a maximális elem sorszámára teljesül, hogy nincs olyan eleme a sorozatnak, mely nagyobb lenne az ennek a sorszámnak megfelelõ elemnél.

Algoritmus: jelöljük meg a sorozat elsõ elemét, mintha õ lenne a maximum. A második elemtõl kezdve egyesével haladjunk végig az egész sorozat, majd minden lépésben az aktuális elemet hasonlítsuk össze a maximumnak kinevezett elemmel. Ha ez az elem nagyobb, akkor õt jegyezzük meg, mint maximumot.

 

A kiválogatás tétele:

A kiválasztásnál említést tettem, hogy ha egy „bizonyos tulajdonság”-nak megfelelõ elembõl nem csak egyet, hanem az összest ki szeretnénk választani, akkor az már egy másik probléma. Ezt kiválogatásnak hívják. Azon kívül, hogy ez az algoritmus több elemet is megad(hat), még eltérés az is, hogy nem tételezzük fel, hogy van a sorozat elemei közt ilyen „bizonyos tulajdonság”-ú. Például, ilyen feladat az, hogy a szõke lányokat válogassuk ki, vagy a baracklekvárokat, vagy az „A” betûvel kezdõ rendszámú autókat. Mint látható, ezt a feladatot is a tulajdonság-függvény használatával tudjuk általánosítani.

Specifikáció:

- Bemenet: a sorozat elemszáma, a sorozat elemei és a tulajdonság-függvény;

- Kimenet: egy darabszám (ez továbbra is természetes szám), valamint egy indexsorozat. Ez azt jelenti, hogy elemei természetes számok és csak olyanok lehetnek, melyek az eredeti sorozatban értelmes sorszámot jelentenek. Azaz nem az elemeket válogatjuk ki, hanem csak a sorszámukat, így kevesebb memóriát használunk (általában egy index kisebb memóriaterületen elfér, mint maga az adat);

- Elõfeltétel: nincs;

- Utófeltétel: a darabszám a megszámolásnál említett módon fog történni. A kimeneti sorozatra igaz lesz, hogy elemszáma éppen darabszámnyi, elemei olyan egész számok, hogy az eredeti sorozat „annyiadik” elemére igaz értékû a tulajdonság-függvény.

Algoritmus: állítsuk 0-ra a darabszámot, majd egyesével menjünk végig a sorozat összes elemén. Minden elemnél vizsgáljuk meg, hogy teljesül-e rá a tulajdonság. Ha igen, akkor növeljük meg a darabszámot eggyel, majd „darabszámadik” helyre írjuk le az aktuális sorszámot. Például, legyen egy számsorozatunk: 5, 2, 0, 3. Válogassuk ki a 2-nél nagyobb számokat. Az 5 nagyobb, mint a 2, ezért a darabszám 1-re növekszik, az elsõ helyre pedig leírjuk az 1-et, hiszen ez az 5 sorszáma. A 2 nem nagyobb, mint a 2, így lépünk tovább egészen a négyesig. A 3 nagyobb, mint a 2, ezért a darabszámot megnöveljük 2-re, és a második helyre leírjuk a 4-et, hiszen ez a 3 sorszáma.

 

 

Most érketünk egy olyan részhez, ahol is már a szöveges megfogalmazás lehetõségei nem elegendõek. Még maradt néhány tétel, de ezek már túl bonyolultak ahhoz, hogy konkrét algoritmus nélkül érthetõek legyenek - szerintem legalábbis. Itt jönnének olyan tételek, mint a szétválogatás, egyesítés, metszet és összefuttatás. Ezekrõl csak néhány szót említenék itt:

- Szétválogatás: hasonlít a kiválogatáshoz, tulajdonképpen fel is használja valamiképp azt. A lényege, hogy nem egy tulajdonságunk van, mint korábban, hanem több, és ezek alapján többfele dobáljuk szét az elemeket.

- Egyesítés: aki ismeri a halmazmûveleteket, annak ez nem lesz újdonság, pontosan azt jelenti itt is. Mit is? Két sorozat elemeit egyesítjük egy harmadikba de úgy, hogy az elemek csak egyszer szerepeljenek. Fontos, hogy halmaz-tulajdonságú sorozatokból indul ki. Tehát az eredeti két sorozatban egy elem, csak egyszer szerepel.

- Metszet: két (halmaz-tulajdonságú) sorozat elemeibõl készítünk egy harmadikat úgy, hogy csak a közös elemeket vesszük be.

- Összefuttatás: az egyesítés egy hatékonyítása abban az esetben, ha két sorozat nem csak halmaz-tulajdonságú, hanem rendezett is.

 

Azt hiszem holnap néhány alapvetõ rendezési módszert írok le. Úgyhogy folyt. köv.

[Calyd]

Akkor ahogy ígértem, leírok néhány rendező algoritmust. Igaz tartom magam a "jobb később, mint soha" mondáshoz is

 

Amit elsőként meg kell jegyeznem, hogy az itt leírtak úgynevezett belső rendezések. Ez azt jelenti, hogy az adat maga elfér a memóriában, vagy a rendezés során sem lesz memóriabeli akadályunk. Nyilván, ha vannak belső, akkor léteznek külső rendezési algoritmusok is. Akkor szükséges ilyeneket használnunk, ha az előbb említett problémákkal találkozunk. Ilyenkor valamilyen más tárolóeszközt (pl. merevlemezt) kell használnunk. Ezek azonban már nem mondhatók alapvető problémáknak, így nem ejtek szót róluk, kizárólag a belsőkre hagyatkozom.

 

Fontos megemlíteni még, hogy a rendezések esetében sem mindig egyértelmű, hogy mi alapján (milyen szempont szerint) rendezünk. Gondoljunk csak arra, hogy például embereket rendezhetünk név, de akár magasság szerint is. Azt mondhatjuk, hogy a rendezéseket általában valamilyen "kulcs" alapján végezzük, amely általában az elemek részét képezik.

A rendezéseknél egy bemenő sorozat elemeit permutáljuk (vagyis más sorrendbe helyezzük). A rendezetlenből rendezettig többféleképp juthatunk el, így több megoldás is született a rendezés problémájára. A rendezések során összehasonlításokat végzünk, így tudjuk eldönteni, hogy szükség van-e esetleg cserére az elemek között. Természetesen igaz az, hogy egy elem önmagában rendezett!

Meg tudunk különböztetni - az alapelv alapján - háromféle elgondolást:

- transzpozíciós: ha az összehasonlításban szereplő elempárok egymáshoz képesti sorrendje (transzpozíció) rossz, akkor megcseréljük őket. Például: (4,3,2,5,1) -> (3,4,2,5,1) -> (3,2,4,5,1) -> (3,2,4,5,1) -> (3,2,4,1,5) -> (2,3,4,1,5) [itt jó a sorrend!] -> (2,3,4,1,5) -> (2,3,1,4,5) -> (2,3,1,4,5) -> (2,1,3,4,5) -> (1,2,3,4,5)

- szelekciós: itt mindig a rendezettség szerinti következő elemet választjuk ki (szelekció), majd cserével a helyére tesszük. Például: (4,3,2,5,1) -> MinimumKiválasztás(4,3,2,5,1): 1 -> (1,3,2,5,4) -> MinimumKiválasztás(3,2,5,4): 2 -> (1,2,3,5,4)...

- beszúrásos: a következő elem a rendezettségnek megfelelő helyre kerül (beszúrás) a már rendezett részsorozatban. Például: (4,3,2,5,1) -> (3,4,2,5,1) -> (2,3,4,5,1) -> (2,3,4,5,1) -> (1,2,3,4,5). A vastagított a már rendezett részsorozatot jelöli, a dőlt pedig azt az elemet, melyet be szeretnénk szúrni a megfelelő helyre.

 

Mindhárom módszerre adok példát az alábbiakban. Előtte azonban a specifikáció. Ez mindegyik változatnál ugyan az nyilvánvaló módon, hiszen csak a módszer változik, azt pedig nem a specifikáció tartalmazza.

Specifikáció:

- Bemenet: a sorozat elemei, a sorozat elemszáma. A sorozat elemi pedig "kulcs" és "egyéb" részekből tevődnek össze. Továbbá létezik a kulcsok között a "nagyobb" reláció;

- Kimenet: egy sorozat;

- Előfeltétel: elég a memória a rendezéshez (úgy is mondhatjuk, ohogy közvetlenül el tudjuk érni az adatokat);

- Utófeltétel: a kimenő sorozat a bemenő sorozat permutációhalmazának egy eleme (magyarul: az eredeti egy esetleges sorrendbeli változata)

 

Az egyszerű cserés rendezés:

A filozófiáját tekintve ez egy transzpozíciós rendezés. Tehát akkor fogunk cserélni az elemek közt, ha rossz a sorrendjük egymáshoz képest.

Algoritmus: a sorozat elemein végigmegyünk az utolsó előtti elemig, majd minden egyes elemnél a rákövetkezőtől végigmegyünk az utolsóig. Azaz az egyik végighaladás (első sorszámú!) eleme a második végighaladás során végig fix. Azt is megfigyelhetjük, hogy az első végigmenés csak egyszer történik meg, míg a második többször (pontosan sorozat elemszáma-1-szer). Ha a fix sorszámú elemnél nagyobbat találunk a második végighaladás során, akkor megcseréljük. Ennek az lesz a következménye, hogy a legkisebb elem mindig a legelejére kerül.

Példa: (4,2,1,3) -> (2,4,1,3) -> (1,4,2,3) -> (1,4,2,3). Itt értünk végig először a második végighaladáson, ahol az első elem volt a fix. Az utolsó összehasonlítás nem eredményezett cserét.

(1,4,2,3) -> (1,2,4,3) -> (1,2,4,3). Itt ért véget másodszor a második végighaladás. Az csak véletlen, hogy itt is az utolsó összehasonlítás nem eredményezett cserét.

(1,2,4,3) -> (1,2,3,4). Itt ért véget a rendezés algoritmusa.

Megjegyezném, hogy amennyire tudom ez a leghatékonyabb rendezés abban az esetben, ha semmit nem tudunk a sorozatról. Úgy tűnhet, hogy buta az algoritmus és ez nem teljesen rossz gondolat. Néha sokat hasonlít össze feleslegesen, sőt azt sem veszi észre elég korán, ha rendezett a sorozat. Ezalatt azt értem, hogy van olyan rendezés, ami az első lefutás után ezt "felfogja"

 

A minimum kiválasztásos rendezés:

Ez egy szelekciós fajta rendezés, az én egyik kedvencem, mert szerintem nagyon logikus, ezért könnyen érthető. Az ember bármikor fejből megírja az algoritmust.

Algoritmus: a sorozat elemein egyesével végigmegyünk egészen az utolsó előtti elemig. Minden egyes lépésnél azonban elvégzünk egy minimum kiválasztást a maradék sorozat elemein úgy, hogy a végighaladás aktuális elemét tekintjük először minimumnak (lásd: minimum kiválasztás). Majd ezzel a minimummal megcseréljük az aktuális elemet. Fontos, hogy itt a minimum kiválasztásánál sorszámokkal dolgozzunk!

Példa: a vastagított a végighaladás aktuális eleme, a dőlt pedig a sorozat, melyből minimumot választunk ki. (4,2,1,3) -> MinKiv: 3 (az 1-es sorszáma!) -> (1,2,4,3) -> MinKiv: 2 (a 2-es sorszáma!) -> (1,2,4,3) -> MinKiv: 4 (a 3-as sorszáma!) -> (1,2,3,4).

 

Sajnálom! Ismét a szöveges leírásom akadályaiba ütköztem, amikor megpróbáltam szövegesíteni egy beszúrásos elvű rendezést, úgyhogy ezt most kihagynám Még gondolkozom rajta, hogy mindenféle "csúnya" szavak és jelölések használata nélkül miként tudnám leírni. Ha kitalálok jót, akkor pótolom.

[netacademia]

Szeva!

 

Algortmusok-hoz szeretnék segítséget kérni. AAO tantárgyhoz. C#-ban tanulunk programozni, de mindegy hogy miben készûl el az algoritmus, azt talán át tudom irni. Bele tudok kezdeni, de aztán összevisszaság lesz belõle

 

Feladat

1. Írjunk programot, amely egytıl n-ig a következı sorozat értékét kiszámítja, majd kiírja:

1*(2 + 3*(4 + 5*(Kn)K))

 

2. Olvassunk be nemnegatív egész számokat, és írjuk ki a szám 16-os számrendszerbeli

alakját. A 0 (nulla) beolvasására álljon le a program.

 

3. Írjuk ki két beolvasott pozitív egész szám közötti prímek összegét!

 

 

4. Olyan durva hogy le se merem irni.

 

5. Olvassunk be nemnegatív, maximum 5 jegyõ egész számokat 0 végjelig. Állapítsuk meg,

hány 1, 2, 3, 4 vagy 5 jegyõ szám volt közöttük, és azon belül hány végzıdött 0-ra, 1-re, …,

9-re!.

 

 

 

 

[Calyd]

Hali!

 

1: egyelõre nem teljesen világos a K szerepe, ezért feltételezem, hogy egy elõre megadott konstans. Ezt úgy tudnád megvalósítani, hogy felveszel egy segédváltozót, melynek értékét nullára állítod (azért nullára, mert ez az összeadás egységeleme). Egy számlálós ciklussal mész végig a sorozat elemein n-ig, és ehhez a segédváltozóhoz mindig hozzáadod az aktuális lépésben kiszámolt értéket. Az aktuális lépésben kiszámolt értéket pedig úgy kapod, hogy a megadott képletbe n helyére a ciklusváltozót írod.

Egész SorozatÖsszead(Egész N,K){
Egész i,összeg;

összeg:=0;
Ciklus (i=1,i<N,i++){
   összeg:=összeg+1*(2 + 3*(4 + 5*(K*i)*K));
}
Visszaad összeg;
}

 

2: a nulla kezelése egyszerû elágazás, ez gondolom nem jelentene gondot. Ha nem nulla a szám, akkor mit is lehetne kezdeni? A végeredményt tárolni szerintem nehézkes lehet és nem volt feladat, hogy szükséges. Eért azt ötlötem ki, hogy folyamatosan kiírjuk az aktuális eredményt. Érdemes felvenni egy konstans, karakterekbõl álló tömböt, ami a 0,...9,A,...,F értékekbõl áll. Beolvassuk a számot, majd egy elöltesztelõs ciklussal megyünk addig, amíg a számot 16-tal osztva 16-nál kisebb maradékot nem kapunk. Erre c#-ban azt hiszem a % operátor szolgál, algebrában ezt modulónak hívják. A ciklusban pedig a következõt tesszük: megnézzük, hogy 16 hányszor van meg a számban. Egész érdekel, tehát div (ezt nem tudom fejbõl, hogy mi C#-ban). A konstans tömbünknek pedig kiírjuk az ennyi-1-ik elemét (mert nullától indexelõdik a tömb), majd a számot csökkentjük ennyiszer 16-tal. Végül pedig, amikor már a cikluson kívül vagyunk megnézzük, hogy a maradék szám nulla-e, vagy sem. Ha nem nulla, akkor még egy értéket kiírunk. Pl. 123-at 16-os számrendszerbelivé alakítjuk. 123 div 16 = 7, tehát kiírjuk a konstans tömb 6-ik elemét, vagyis a 7-et, majd 123-ból kivonunk 7*16-ot. Így marad 11. Ekkor a ciklusból már kilépünk, és mivel a 11 nem nulla, ezért még kiírjuk a konstans tömb 11-1-ik elemét, vagyis B-t.

 

3: egy nem hatékony, de egyszerû megoldás kínálkozik erre. Érdemes elkészíteni egy PrimE logikai függvényt. Tudtommal nincs logikai típus a C-s nyelvekben, ezért ezt megoldhatjuk úgy, hogy egész értékû függvényt írunk, és 0 jelöli mondjuk a hamist és 1 az igaz értéket. Ez a függvény úgy mûködne, hogy egy paramétere van, a szám amirõl vizsgáljuk, hogy prím-e. Kettõtõl elmegyünk egy elöltesztelõs ciklussal a szám gyökéig (vagy amíg nem találunk osztót) egyesével és megnézzük, hogy osztója-e a számnak. Ha elértünk a szám gyökéig és nem léptünk ki a ciklusból, akkor nem találtunk osztót, tehát prímszám. Miért a gyökéig? Ez egy kis számelméleti megfontolást igényel, de legyen elég annyi, hogy ha addig nincs osztó, akkor nincs osztó. Egyébként a PrimE függvény az eldöntés tétel Mind-e változata. Ha ez megvan, akkor már nem olyan nehéz az eredeti probléma, ezért ezt rádbízom, hogy kicsit te is törd a fejed!

 

5: elsõ körben szétválogathatjuk a számokat a számjegyek alapján. Ehhez öt tömbre van szükségünk, ha nem helyben szeretnénk megcsinálni. A feltétel, hogy mondjuk 4-jegyû-e a szám lehetne az, hogy 999<szám<10000. A szétválogatáskor érdemes számolni a darabszámokat, így az, hogy mibõl mennyi van már kész is. Azt, hogy hány 0-ra, 1-re stb végzõdõ szám van úgy lehet meghatározni, hogy levonod az aktuális számból a végzõdést, és ha osztható a különbség 10-zel, akkor a szám a végzõdésre végzõdik. 947 7-re végzõdik, mert 947-7 osztható 10-zel.

 

Itt találsz algoritmusokat is.

[don_dody]

Összegzés tétele:

 

•Egy tömb elemeinek összegzése

•Könnyen átírható szorzatra vagy más mûveletre

 

s:=0

Ciklus i:=1...N

s:=s+T

Ciklus vége

Ki: s

 

 

Megszámolás tétele:

 

•Megszámolja, hogy a tömbben hány, adott tulajdonságú elem van

–Például, negatív számok

 

s:=0

Ciklus i:=1..N

Ha T<0 akkor s:=s+1

Ciklus vége

Ki: s

 

Eldöntés tétele:

 

•Az algoritmus eldönti, hogy van-e a tömbben adott tulajdonságú elem. Amint talál egyet, a ciklus leáll.

•Ha a ciklus azért állt le, mert túlléptünk a tömb utolsó, vizsgált elemén is, akkor nem volt benne keresett elem

•Van-e 50 az elemek között

 

i:=1

Ciklus amíg i<=N és T<>50

i:=i+1

Ciklus vége

Ha i<=N akkor

ki: "volt 50"

 

Kiválasztás tétele:

•Az algoritmus megadja, hogy a tömbben egy bizonyos elem hol (hányadik helyen) van.

•Csak akkor mûködik, ha biztosan van ilyen elem

 

i:=1

Ciklus amíg T<>50

i:=i+1

Ciklus vége

ki: i

 

Keresés tétele:

 

•Az elõzõnél biztonságosabb algoritmus: megadja, hogy van-e olyan elem, és ha igen, hányadik.

 

i:=1

Ciklus amíg i<=N és T<>50

i:=i+1

Ciklus vége

Ha i<=N akkor

ki: i

különben

ki: -1 /* bármilyen más érvénytelen index */

 

Kiválogatás tétele:

 

•Ez az algoritmus egy tömb bizonyos tulajdonságú elemeit teszi egy másik tömbbe.

•db változó számolja, hogy a másik tömbbe hány elem került

•válogassuk ki a negatív számokat.

•Az eredmény a B tömbben lesz

•deklarációnál a B tömböt N elemûre kell választani, hacsak nem tudjuk elõre, hány negatív szám van T-ben

 

db:=0

Ciklus i:=1..N

Ha T<0 akkor

db:=db+1

B[db]:=T

Ha vége

Ciklus vége

 

Szétválogatás tétele:

 

•Kiválogatáshoz hasonló, de a nem megfelelõ elemeket is tömbbe tesszük

 

Szétválogatás két tömbbe

 

dbb:=0

dbc:=0

Ciklus i:=1..N

Ha T<0akkor

dbb:=dbb+1, B[dbb]:=T

különben

dbc:=dbc+1, C[dbc]:=T

Ciklus vége

 

Metszet tétele:

 

•két tömb (A[1..N] és B [1..M]) azonos elemeinek kiválogatása C tömbbe

•Az algoritmus lényege: menjünk végik A tömb elemein, és válogassuk ki azokat (kiválogatás), melyek szerepelnek B-ben (eldöntés).

•Visszavezethetõ a korábbi feladatokra

•C maximális elemszáma N és M közül a kisebbik

 

db:=0

Ciklus i:=1..N

j:=1

Ciklus amíg j<=M és B[j]<>A

j:=j+1

Ciklus vége

Ha j<=M akkor db:=db+1, C[db]:=A

Ciklus vége

 

Unió tétele:

 

•A és B tömb összes elemét C tömbbe tenni

•Tegyük be C-be A összes elemét, majd B-bõl azokat, melyek nem szerepelnek A-ban.

•C elemszáma legfeljebb N+M.

 

Ciklus i:=1..N

C:=A

Ciklus vége

db:=N

Ciklus j:=1..M

i:=1

Ciklus amíg i<=N és B[j]<>A

i:=i+1

Ciklus vége

Ha i>N akkor db:=db+1, C[db]:=B[j]

Ciklus vége

 

Maximum kiválasztás tétele:

 

•T tömb maximális elemének megkeresése

 

m:=1

Ciklus i:=2..N

Ha T>T[m] akkor m:=I

Ciklus vége

Ki: m, T[m]

 

•m:a pillanatnyilag talált legnagyobb elem helyét mutatja

 

Rendezés tétele:

 

Rendezés maximum kiválasztással

 

•Az elv: kiválasztjuk a tömb legnagyobb elemét, és berakjuk a tömb végére (vagyis kicseréljük az utolsó elemmel)

•Ezt az eljárást ismételjük a maradék tömbre

•i változó adja meg, hogy hányadik elem fog a helyére kerülni

•A Csere(i,m) eljárás kicseréli a tömb i. és m. elemét

 

Ciklus i:=N..2

m:=1

Ciklus j:=2..I

Ha T[j]>T[m] akkor m:=j

Ciklus vége

Csere(i,m)

Ciklus vége

 

Buborékos rendezés

 

•Végigmegy a tömbön, és ha szomszédos elemeknél rossz a sorrend, megcseréli õket.

•Ez a csere, mint egy buborék, végighalad a tömbön, és a legnagyobb elemet biztosan a tömb végére teszi.

•i változó ismét azt jelzi, hányadik elem kerül a helyére.

 

Ciklus i:=N..2

Ciklus j:=1..i-1

Ha T[J]>T[J+1] akkor Csere(j,j+1)

Ciklus vége

Ciklus vége