Összegzés
Általában egy tömb elemeinek összegzését jelenti. Általánosan: összeg=összeg+aktuális elem, vagyis új összeg=régi összeg+aktuális elem
Példa: Állítsunk elő 10db 1-100 közötti véletlen számot, töltsünk fel velük egy tömböt. Számoljuk ki a számok összegét! Ha ez megvan, akkor ennek felhasználásával számoljuk ki az átlagukat is!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Console.WriteLine("Tömb elemei:"); int[] a = new int[10]; //tömb, 10 elem int osszeg = 0; double atlag = 0; Random vsz = new Random(); for (int i = 0; i < 8; i++) { a[i] = vsz.Next(101); osszeg += a[i]; //osszeg=osszeg+a[i]; Console.Write("{0,5}", a[i]); //5 karakternyi hely mindegyik számnak } Console.WriteLine(); atlag = Convert.ToDouble(osszeg) / a.Length; //összeg osztva tömb elemszám Console.WriteLine("A számok összege: {0}", osszeg); Console.WriteLine(" A számok átlaga: {0:0.000}", atlag); //3 tizedesjegy Console.ReadKey(); |
Megszámlálás
Megszámoljuk, hogy hány olyan elem van, ami egy megadott feltételnek megfelel.
Példa: Számoljuk meg, hány negatív és hány pozitív szám van egy 10 elemű, -100 100 közötti véletlen számokkal feltöltött tömbben!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Console.WriteLine("Megszámlálás"); int[] a = new int[10]; //10 elemű tömb int pozitivak = 0, negativak = 0; Random vsz = new Random(); Console.WriteLine("Tömb elemei:"); for (int i = 0; i<10; i++) { a[i] = vsz.Next(-100, 101); if (a[i] > 0) pozitivak++; if (a[i] < 0) negativak++; Console.Write("{0,5}", a[i]); } Console.WriteLine(); Console.WriteLine(" {0} db pozitív szám van.", pozitivak); Console.WriteLine(" {0} db negatív szám van.", negativak); Console.ReadKey(); |
Eldöntés
Ez az algoritmus eldönti, hogy van-e a tömbben adott tulajdonságú elem. Ha van, a ciklus leáll, break utasítással kilépünk a do while ciklusból. Természetesen meg lehet oldani for ciklussal is.
Példa: Állítsunk elő 5 egész számot, egy 0-100 közötti véletlenszámokból, és döntsük el, van-e közöttük 3-mal osztható!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Console.WriteLine("Eldöntés"); int[] a = new int[5]; //5 elemú tömb bool van = false; Random vsz = new Random(); for (int i = 0; i < 5; i++) { a[i] = vsz.Next(101); Console.Write("{0,5}", a[i]); } int j = 0; do { if (a[j] % 3 == 0) { van = true; break; } j++; } while (van == false && j < 5); Console.WriteLine(); if (van) { Console.WriteLine("Van hárommal osztható szám!"); } else { Console.WriteLine("Nincs hárommal osztható szám."); } Console.ReadKey(); |
Kiválasztás
Az adatok közül kiválasztunk egy, vagy több olyan elemet, ami a megadott feltételeknek megfelel. Az algoritmus megadja, hogy az adott elem a tömbben hol helyezkedik el.
Példa: Állítsunk elő 10 véletlen számot -100 és 100 között! Írjuk ki az első pozitív szám indexét és értékét! (plusz az tömb összes elemét, hogy ellenőrizni tudjuk)
Ebben az esetben akár ki is léphetünk a ciklusból, ha megtaláltuk a keresett elemet. A tömb indexelése 0-val kezdődik. Ha -1 kezdőelemet adunk az index változónak, akkor ennek segítségével eldönthető, hogy találtunk–e a feltételnek megfelelő elemet. Ha végigmentünk a tömbön, és -1 maradt az index változónk értéke, akkor nem volt megfelelő szám. Ha -1-nél nagyobb, akkor találtunk megfelelő elemet. FOR és DO .. WHILE ciklussal is:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
Console.WriteLine("Kiválasztás"); int[] a = new int[10]; int index = -1; //keresett elem indexe. Ha -1 marad, akkor nem találtunk megfelelőt! Random vsz = new Random(); for (int i = 0; i < 10; i++) { a[i] = vsz.Next(-100, 100); Console.Write("{0,5}", a[i]); } /* int j = 0; do { if (a[j] > 0) { index = j; }; j++; } while (index == -1 && j < a.Length);*/ for(int j=0; j<a.Length; j++) { if (a[j] > 0) { index = j; break; } } Console.WriteLine(); if (index > -1) Console.WriteLine("Az 1. pozitív szám: {0} indexe: {1}", a[index], index); else Console.WriteLine("Nincs pozitív szám!"); Console.ReadKey(); |
Maximum/minimum kiválasztás
Rendezetlen elemek közül keressük meg a legnagyobbat/legkisebbet. Karakter és szöveg típusú változókra is érvényes. A for ciklus előtt az első elemet (0.index) tekintjük a legnagyobbnak, majd a for ciklus során végignézzük az elemeket, hogy van-e ennél nagyobb/kisebb elem. Ha az aktuálisan vizsgált elem nagyobb, akkor az lesz az új maximum.
Példa: Állítsunk elő 10db 0-500 közötti véletlen számot, és keressük meg, melyik a legnagyobb!
(keressük meg a legkisebbet is!)
Ellenőrzésként írjuk ki a 10db számot is a képernyőre!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Console.WriteLine("Maximum, minimum kiválasztás"); int[] a = new int[10]; //10 elemű tömb int min = 0, max = 0; Random vsz = new Random(); for (int i = 0; i < a.Length; i++) { a[i] = vsz.Next(501); Console.Write("{0,5}", a[i]); } min = a[0]; max = a[0]; for (int i = 1; i < a.Length; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } Console.WriteLine(); Console.WriteLine("A legkisebb szám: {0}", min); Console.WriteLine("A legnagyobb szám: {0}", max); Console.ReadKey(); |
Kérjünk be 5db karaktert, és írjuk ki az abc sorrend szerint elsőt! (ASCII karaktekkód szerint rendez)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Console.WriteLine("Minimum kiválasztás"); char[] a = new char[5]; char min = ' '; for (int i = 0; i < 5; i++) { Console.WriteLine("Kérem a(z) {0} karaktert: ",i+1); a[i] = Convert.ToChar(Console.ReadLine()); } min = a[0]; for (int i = 1; i < 5; i++) { if (a[i] < min) min = a[i]; } Console.WriteLine(); Console.WriteLine("Az első karakter: {0}", min); Console.ReadKey(); |
Állítson elő véletlenszerűen 28 db számot a [-10, 10] tartományból!
- Állapítsa meg pozitív vagy negatív számból van-e több? A választ
és a darabszámokat írja a képernyőre! - Hányszor fordult elő a 7-es szám?
- Van-e a számok között 0, hanyadik indexe van az elsőnek?
- Adja meg a negatív számok átlagát!
- Adja meg melyik a legkisebb, és a legnagyobb szám!
- Melyik volt a pozitív számok közül a legkisebb?
- Melyik volt a negatív számok közül a legnagyobb?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
Console.WriteLine("Gyakorlás"); int[] tomb = new int[28]; int db_nulla = 0, db_poz = 0, db_neg = 0, keresett = 7, db_keresett = 0, nulla_indexe = 0, osszeg = 0; int min, poz_min = 0; int max, neg_max = 0; double atlag = 0; bool nulla = false; Random vsz = new Random(); for (int i = 0; i < 28; i++) { tomb[i] = vsz.Next(-10, 11); if (tomb[i] == keresett) { db_keresett++; } if (tomb[i] == 0) { db_nulla++; if (db_nulla == 1) nulla_indexe = i; } if (tomb[i] > 0) db_poz++; if (tomb[i] < 0) { db_neg++; osszeg += tomb[i]; } Console.Write("{0} ", tomb[i]); } Console.WriteLine(); Console.WriteLine("Negatív szám: {0} db, pozitív szám: {1} db", db_neg, db_poz); if (db_poz > db_neg) Console.WriteLine("Több a pozitív szám!"); else if (db_neg > db_poz) Console.WriteLine("Több a negatív szám!"); else Console.WriteLine("A + és - számok száma egyenlő"); //van-e 7-es szám? if (db_keresett > 0) Console.WriteLine("A számok között van 7-es! {0} db", db_keresett); else Console.WriteLine("A számok között nincs 7-es!"); //Van 0, indexe if (db_nulla > 0) Console.WriteLine("A számok között van {0} db 0, az első indexe: {1}", db_nulla, nulla_indexe); atlag = Convert.ToDouble(osszeg) / db_neg; Console.WriteLine("A negatív számok átlaga: összeg:{0} / darab {1} = {2}", osszeg, db_neg, atlag); max = tomb[0]; min = tomb[0]; poz_min = max; neg_max = min; for (int i = 0; i < 28; i++) { if (tomb[i] > max) max = tomb[i]; if (tomb[i] < min) min = tomb[i]; // legnagyobb negatív szám if ((tomb[i] < 0) && (tomb[i] > neg_max)) neg_max = tomb[i]; // legkisebb pozitív szám if ((tomb[i] > 0) && (tomb[i] < poz_min)) poz_min = tomb[i]; } Console.WriteLine(); Console.WriteLine("A legnagyobb szám: {0}, a legkisebb szám: {1}", max, min); Console.WriteLine("A legnagyobb negatív szám: {0}, a legkisebb pozitív szám: {1}", neg_max, poz_min); Console.ReadKey(); |
Kiválogatás
Kiválogatás során egy tömb elemei közül kiválogatjuk azokat, amelyek a megadott feltétel(ek)nek megfelelnek. Ezeket akár egy másik tömbbe is tárolhatjuk.
Generáljunk 20db véletlenszámot 1-100 közötti számokból. Az öttel osztható számokat írassuk ki, és tároljuk egy másik tömbben! Ilyen esetben a másik tömb méretének is célszerű az eredeti tömb méretét megadni, mert akár az is elképzelhető, hogy minden generált szám osztható öttel.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Console.WriteLine("Kiválogatás"); int[] a = new int[20]; int[] b = new int[20]; int db = 0; Random vsz = new Random(); for (int i = 0; i < 20; i++) { a[i] = vsz.Next(101); Console.Write("{0} ", a[i]); if (a[i] % 5 == 0) { b[db] = a[i]; db++; } } Console.WriteLine(); Console.WriteLine("Az öttel osztható számok:"); for (int j = 0; j < db; j++) { Console.Write("{0} ", b[j]); } Console.ReadKey(); |
Szétválogatás
Szétválogatás esetén egy tömb minden elemét elhelyezzük a megadott feltételek szerint másik tömbben. A szétválogatás utáni tömbök elemszáma megegyezik az eredeti tömb elemszámával.
Állítsunk elő 20db 1-100 közötti véletlen számot! Válogassuk szét a számokat 3 tömbbe: legyenek a ‘ketto’ tömbben a kettővel osztható számok, a ‘harom’-ban a kettővel nem de hárommal oszthatóak, az ‘egyeb’ tömbben az összes többi. Írassuk ki a tömbök tartalmát!
namespace szetvalogatas
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Szétválogatás");
int[] a = new int[20];
int[] ketto = new int[20];
int[] harom = new int[20];
int[] egyeb = new int[20];
int i = 0, j = 0, dbketto = 0, dbharom = 0, dbegyeb = 0;
Random vsz = new Random();
for (i=0; i<20; i++)
{
a[i] = vsz.Next(101);
Console.Write("{0} ", a[i]);
if (a[i]%2==0)
{
ketto[dbketto] = a[i];
dbketto++;
}
else if (a[i]%3==0)
{
harom[dbharom] = a[i];
dbharom++;
}
else
{
egyeb[dbegyeb] = a[i];
dbegyeb++;
}
}
Console.WriteLine();
Console.WriteLine("A kettővel osztható számok: ");
for (j = 0; j < dbketto; j++)
Console.Write("{0} ", ketto[j]);
Console.WriteLine();
Console.WriteLine("A kettővel nem de hárommal oszthtó számok: ");
for (j = 0; j < dbharom; j++)
Console.Write("{0} ", harom[j]);
Console.WriteLine();
Console.WriteLine("Egyéb számok");
for (j = 0; j < dbegyeb; j++)
Console.Write("{0} ", egyeb[j]);
Console.ReadKey();
}
}
}
Lineáris keresés
A lineáris keresés nagyon hasonlít az eldöntésre: egy n elemű sorozatban keresünk adott feltételnek megfelelő elemet. Az algoritmusnak el kell döntenie, van-e az adott feltételnek megfelelő elem. Ha igen, akkor ennek az elemnek a sorszámát keressük.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Console.WriteLine("Lineáris keresés"); int[] tomb = new int[15]; Random vsz = new Random(); int n = tomb.Length; for (int s = 0; s < n; s++) { tomb[s] = vsz.Next(21); Console.Write("{0} ", tomb[s]); } int keresettSzam = 1; int i = 0; while (i < n && tomb[i] != keresettSzam) i++; if (i < n) Console.WriteLine("A keresett szám indexe: {0} ", i); else Console.WriteLine("A keresett szám nincs benne a tömbben"); Console.ReadKey(); |
RENDEZÉSI ALGORITMUSOK
BUBORÉK RENDEZÉS
Nevét onnan kapta, hogy hasonlóan ahhoz, ahogy a pezsgőspohárban szállnak felfelé a buborékok, a rendezés során is minden egyes menetben a fennmaradó elemek közül a legnagyobbat helyezzük át a tömbszelet végére, tetejére. A rendezés során a tömb fennmaradó – még nem rendezett – részén végighaladva az egymás utáni szomszédos elemeket összehasonlítjuk, és ha szükséges megcseréljük őket, hogy közülük mindig a nagyobb helyezkedjen el feljebb; ezt a műveletet aztán a tömbön feljebb lépve addig ismételjük, amíg a fennmaradó rész végéhez nem érünk. A műveletsor végén a rendezetlen rész tetejére mindig a legnagyobb érték kerül majd fel, amelyet a következő menetben már nem veszünk figyelembe. A ciklust egészen addig ismételjük a fennmaradó – egyre kisebb – halmazon, amíg már csak egyetlen elem marad ebben, amely ebben az esetben a halmaz legkisebb eleme lesz, miközben a tömb fennmaradó része az összes nála nagyobb elemet fogja tartalmazni, növekvő sorrendben.
Az algoritmus műveletigénye a tömb méretének négyzetével arányos, ezért nagy tömböknél nem javasolt a használata, mert rendkívül lassú futáshoz vezet. Ilyen esetekre a gyorsrendezés vagy az összefésülő rendezés használata ajánlott. A minimumkiválasztásos és a beszúrásos rendezések általában hatékonyabbak a buborékrendezésnél.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Console.WriteLine("Buborék rendezés"); int[] tomb = new int[] { 10, 2, 9, 8, 5, 6, 1, 4, 3, 7 }; int n = tomb.Length; //Kiíratás rendezés előtt for (int i = 0; i < n; i++) Console.Write("{0} ", tomb[i]); Console.WriteLine(); //Buborék rendezés for (int i = n - 1; i > 0; i--) for (int j = 0; j < i; j++) if (tomb[j] > tomb[j + 1]) { int temp = tomb[j + 1]; tomb[j + 1] = tomb[j]; tomb[j] = temp; } //Kiíratás rendezés után for (int i = 0; i < n; i++) Console.Write("{0} ", tomb[i]); Console.WriteLine(); Console.ReadLine(); |
Egy szemléletes video a YouTube-ról, és egy másik.
Beszúrásos rendezés
Működése leginkább a kártyalapok egyenként való kézbe vételéhez és a helyükre igazításához hasonlítható. Van a kezünkben 10,9,K,A és felveszünk egy J-t, akkor a 10-es után fogjuk beszúrni, de az előtte levő elemeket is rendezi, tehát 9, 10, J, K, A lesz az eredmény. Ezzel persze nincs ki a sorunk pókernél…
Vesszük a soron következő elemet, és megkeressük a helyét a tőle balra lévő, már rendezett részben, majd a kereséssel párhuzamosan a nagyobb elemeket rendre eggyel jobbra mozgatjuk. Az aktuális elemet egy segédváltozóban tároljuk, mert a mozgatások során értéke felülíródhat egy nagyobb elemmel.
Ezen algoritmus használata akkor igazán előnyös, ha az adatsorunk már részben rendezett. Továbbá akkor igen hatékony, ha egy rendezett sorozatot bővítünk és a bővítés után is szeretnénk, hogy a sorozat rendezett maradjon. Az algoritmus futási ideje legjobb esetben konstans, vagyis a gép sebességétől függ, az elemektől nem. Legrosszabb esetben pedig négyzetes.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Console.WriteLine("Beszúrásos rendezés!"); int[] tomb = { 10, 2, 9, 8, 5, 6, 1, 4, 3, 7 }; for (int i = 0; i < tomb.Length; i++) Console.Write("{0} ", tomb[i]); Console.WriteLine(); //beszúrásos rendezés for (int i = 1; i < tomb.Length; i++) { int kulcs = tomb[i]; int j = i - 1; while (j >= 0 && tomb[j] > kulcs) { tomb[j + 1] = tomb[j]; j = j - 1; } tomb[j + 1] = kulcs; } for (int i = 0; i < tomb.Length; i++) Console.Write(tomb[i] + " "); Console.WriteLine(); Console.ReadLine(); |
Frissítve: 2024.05.01.