[[oktatas:programozás:algoritmusok|< Algoritmusok]] ====== Apróbb algoritmusok ====== * **Szerző:** Sallai András * Copyright (c) 2013, Sallai András * Szerkesztve: 2013, 2014, 2015 * Licenc: [[https://creativecommons.org/licenses/by-sa/4.0/|CC BY-SA 4.0]] * Web: https://szit.hu ===== Bevezetés ===== Itt olyan algoritmusok vannak, amelyeket nem szoktunk a programozási tételek között felsorolni, mert vagy nagyon ritkán használjuk vagy nagyon triviális, vagy nagyon összetett, esetleg speciális. ===== Faktoriális számítása ===== Egy n nemnegatív egész szám faktoriálisának az n-nél kisebb vagy egyenlő pozitív egész számok szorzatát nevezzük. Jelölése: n! Néhány szám kibontva: 0! = 1 1! = 1 2! = 1 * 2 = 2 3! = 1 * 2 * 3 = 6 4! = 1 * 2 * 3 * 4 = 24 5! = 1 * 2 * 3 * 4 * 5 = 120 A sorozat eleje: ^ 0! ^ 1! ^ 2! ^ 3! ^ 4! ^ 5! ^ 6! ^ 7! ^ 8! ^ 9! ^ 10! ^ 11! ^ 12! ^ | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5040 | 40320 | 362880 | 3628800 | 39916800 | 479001600 | Algoritmus: fakt = 1 ciklus i = 2 .. n fakt = fakt * i Rekurzívan:


függvény fak(szam){
  ha szam == 0 akkor
     visszatér 1
  else 
     visszatér fak(szam-1)*szam
}


public class Program01 {
	public static long fakt(int szam) {
		if (szam == 0) {
			return 1;
		}else {
			return fakt(szam-1)*szam;
		}
	}

	public static void main (String[] args) {
		for(int i=1; i<10; i++) {
			System.out.println(fakt(i));
		}
	}
}

===== Fibonacci számok ===== Fibonacci egy itáliai matematikus volt. Több néven ismert: Leonardo di Pisa, Leonardo Pisano, Leonardo Bonacci, Leonardo Fibonacci. Születése és halála pontosan nem ismert: (kb. 1170 – kb. 1250). Az arab számokat ő terjesztette el.A róla elnevezett számsorozatot nem ő találta ki, de az ő írásai után lett híres. Az adott elem mindig az előtte lévő két elem összege. A Fibonacci-sorozat 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987


függvény fib(szám) {
    ha ( szam <= 1 ) {
        visszatér szám;
    } ellenben {
        visszatér fib(szám-1) + fib(szám-2);
    }
}

ciklus i= 1..30 
    fib(i)
ciklus vége


public class Program26 {
	public static int fib(int szam) {
		if(szam <= 1) {
			return szam;
		}else {			
			return fib(szam -1) + fib(szam-2);
		}
	}	
	public static void main (String[] args) {
		for(int i=1;i<23;i++) {
			System.out.println(fib(i));
		}
	}
}

===== Csere ===== Csere esetén egyszerűen fel kell venni egy segédváltozót, amiben eltároljuk az egyik cserélendő értéket. Legyen például egy "a" és egy "b" nevű változó, amelyben számokat tárolunk és ezen változók tartalmát szeretnénk cserélni:


c = a
a = b
b = c

A segédváltozó a "c" lett (szokásos elnevezés például a "swap"). Először elteszem "a" értékét. Ezek után felülírhatom az "a" változót. A végén "b" változó értéke "c"-ben lesz. ===== Végrehajtás végjelig ===== Valamilyen külső körülménytől várjuk a végjelet. Ez lehet egy felhasználói beavatkozás, de lehet adatbázisból állományból vett adat.


be adat
ismétel amíg adat <> végjel
    az adat feldolgozása
    be adat
ismétlés vége

===== Átlag ===== Az átlag az elemek összegének és az elemek darabszámának hányadosa. ==== JavaScript megvalósítás ====


function selectAverage(inArray){
    var n = inArray.length;
    var sum = 0;
    for(i=0;i


===== Lottószámok =====

Klasszikus probléma a lottó számok generálása. 1 és 90 között véletlenszerűen 
választanunk kell egy számot. Ez után megint 1 és 90 között kell véletlenszerűen
választani egy számot, de az nem egyezhet meg a már kiválasztottal.

Az első gondolat az lehet, hogy generáljunk egy véletlen számot, tegyük egy listába,
majd a következő szám generálásánál nézzük meg, hogy az új szám szerepel-e
már a listában. Ha igen, kérjünk újat. Kicsi az esélye, hogy sokáig kell
futnia az algoritmusnak, de elegánsabb a következő algoritmus. 

Készítsünk egy listát amelyben az összes kihúzható szám szerepel 1-90-ig. 
Generáljunk egy véletlen számot például 1 és 90 között. A szám az első szám 
indexe a listában. Első körben az index és a listában szereplő szám egyezik.
Ez után vegyük ki listából az előbb kiválasztott számot, jegyezzük fel 
lottószámként. Kezdjük újra a véletlen szám generálást, de most már egyel
kevesebb számsorból. Ismételjük a fentieket, ötször.


===== Módusz =====

A módusz a leggyakrabban előforduló elem. 

Legyen a következő sorozat:

|  3  |  2  |  8  |  3  |  2  |  1  |  4  |  2  |  2  |  1  |

A leggyakrabban előforduló elem a 2.


==== Mondatszerűen ====



start
maxValue=0
maxCount=0

ciklus i = 0 .. a.Hossz 
	count = 0;
	ciklus j = 0 .. a.Hossz
		ha a[j] == a[i] akkor count = count + 1

	ha count>maxCount akkor			
		maxCount = count
		maxValue = a[i];
	ha vége
ciklus vége
vége



A végén a maxValue változó tartalmazza a leggyakrabban előforduló elemet.


==== JavaScript megvalósítás ====


function modusz(atvettTomb){
    var maxValue=0;
    var maxCount=0;
    var n = atvettTomb.length;
    for(i=0; imaxCount){
            maxCount = count;
            maxValue = atvettTomb[i];
        }
    }
    return maxValue;
}


==== Java megvalósítás ====

Java megvalósítás egészeket tároló ArrayList osztállyal:

public static Integer selectModusz(java.util.ArrayList inList){
    Integer maxValue =0;
    Integer maxCount = 0;
    Integer n = inList.size();
    for(int i=0; imaxCount){
            maxCount = count;
            maxValue = inList.get(i);
        }
    }
    return maxValue;
}

===== Medián =====

A medián a helyzeti középérték. Páratlan elem szám esetén a középső elem a medián.
Páros elem szám esetén a két középső elem átlaga. A számoknak **rendezettnek kell
lenniük**.

^  Index: |  0  |  1  |  2  |  3  |  4  |
^  Sorozat: |  2  |  3  |  7  |  8  |  9  |


^  Index: |  0  |  1  |  2  |  3  |  4  |  5  |
^  Sorozat: |  2  |  3  |  7  |  8  |  9  |  10  |

==== Mondatszerűen ====


start
kozep = m.Hossz/2;

ha (m.Hossz % 2 == 1)
	median =  m[kozep];
ellenben

	median =  (m[kozep-1] + m[kozep]) / 2.0;
ha vége
vége



==== JavaScript megvalósítás ====


function median(atvettTomb){
    var kozep = atvettTomb.length / 2;
    var median = 0;
    if(atvettTomb.length % 2 == 1)
        median = atvettTomb[kozep];
    else
        median = (atvettTomb[kozep-1] + atvettTomb[kozep]) / 2.0;
    return median;
}

==== Java megvalósítás ====


public static Double
        selectMedian(java.util.ArrayList inList){
    Integer mid = inList.size() / 2;
    Double median = .0;
    if(inList.size() % 2 == 1)
        median = (double) inList.get(mid);
    else
        median = (inList.get(mid-1) + inList.get(mid))/2.0;
    return median;            
}


Rendező metódus ha kell:

public static ArrayList sortIntegerList(ArrayList inList){
    int n = inList.size();
	for(int i= n-1; i>0; i--)
		for(int j=0; j inList.get(j+1))
			{
				Integer tmp = inList.get(j);
				inList.set(j, inList.get(j+1));
				inList.set(j+1, tmp);                                        
			}
    return inList;
}


===== Legnagyobb közös osztó =====


  * egész euklidesz(a, b)
    * ha b == 0 akkor
      * return a
    * ellenben return euklidesz(b, a mod b)



#include 

/* Legnagyobb közös osztó az euklidészi algoritmussal
   Bemenő paraméterek nem nagatív egész számok */
int lnko(int a, int b) {
	if(b==0) {
		return a;
	}else {
		return lnko(b, a % b);
	}
	
}

int main(int argc, char **argv) {
	
	
	printf("%d\n", lnko(35, 42));
	
	return 0;
}



===== Prímtényezőkre bontás =====


public static void primtenyezosFelbontas(int szam) {
	int oszto = 2;		
	while(szam > 1) {
		if(szam % oszto == 0) {
			System.out.printf("%20d|%d\n", szam, oszto);
			szam = szam / oszto;
		}else {
			oszto++;
		}
	}
	System.out.printf("%20d|\n", 1);
}


===== Prímszámok tesztelése =====

Prímszám az, amelyiknek pontosan két osztója van a természetes számok között. 

Naiv módszer:

public static boolean prim(long szam) {
	if(szam<2) return false;
	long i=szam-1;		
	while( i>=Math.sqrt(szam) && ((szam % i) != 0) )
		i--;
	if(i < Math.sqrt(szam))
		return true;
	else
		return false;
}


Nagy számok esetén nem ad jó eredményt. 

Használják az [[w>Sieve_of_Eratosthenes|Eratoszthenész szitáját]], valószínűségi teszteket,
és még néhány determinisztikus eljárást.