Tartalomjegyzék

< Algoritmusok

Apróbb algoritmusok

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
}
Program01.java
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
Program01.java
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<n; i++)
        sum += inArray[i];
    var average = sum / n;
    return average;    
}

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; i<n; i++) {
        var count = 0;
        for(j=0;j<n; j++)
            if(atvettTomb[j] == atvettTomb[i])
                count++;
        if(count>maxCount){
            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<Integer> inList){
    Integer maxValue =0;
    Integer maxCount = 0;
    Integer n = inList.size();
    for(int i=0; i<n; i++){
        Integer count = 0;
        for(int j=0; j<n;j++){
            if(inList.get(i)==inList.get(j)){
                count++;
            }
        }
        if(count>maxCount){
            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<Integer> 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<Integer> sortIntegerList(ArrayList<Integer> inList){
    int n = inList.size();
	for(int i= n-1; i>0; i--)
		for(int j=0; j<i; j++)
			if(inList.get(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ó

prg01.c
#include <stdio.h>
 
/* 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 Eratoszthenész szitáját, valószínűségi teszteket, és még néhány determinisztikus eljárást.