Apróbb algoritmusok

• Szerző: Sallai András
• Copyright © 2013, Sallai András
• Szerkesztve: 2013, 2014, 2015
• Licenc: CC BY-SA 4.0
• Web: https://szit.hu

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.

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:

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 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 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.

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

Az átlag az elemek összegének és az elemek darabszámának hányadosa.

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;    
}

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.

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

Legyen a következő sorozat:

A leggyakrabban előforduló elem a 2.

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.

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 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;
}

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.

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

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;
}

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;
}

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

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;
}

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á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.