Tartalomjegyzék

< Programozási tételek

Programozási tételek Java megvalósításban

Tételek

Összegzés

Program.java
class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
 
		int osszeg = 0;
		for(int i=0; i<7; i++)
			osszeg = osszeg + tomb[i];
 
		System.out.println(osszeg);
	}
}

Megszámolás

Program.java
class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7;
		int szamlalo = 0;
		for(int i=0; i<n; i++)
			if(tomb[i] > 5)
				szamlalo++;
 
		System.out.println(szamlalo);
	}
}

Eldöntés tétel

Program.java
class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		int ker = 2; //Amiről el szeretnénk dönteni, hogy van-e ilyen
 
		int i = 0;
		while(i<n && tomb[i] != ker)
			i++;
 
		if(i<n)
			System.out.println("Van ilyen szám.");
		else
			System.out.println("Nincs ilyen szám.");
	}
}

Kiválasztás tétel

Program.java
class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		int ker = 2; //Amiről szeretnénk tudni, hogy hányadik helyen van
 
		int i = 0;
		while(tomb[i] != ker)
			i++;
 
		System.out.printf("%d\n", i + 1);
	}
}

Keresés tétel

Program.java
class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		int ker = 2; //Amit keresünk
 
		int i = 0;
		while(i<n && tomb[i] != ker)
			i++;
 
		if(i<n) {
                        //Ha a kérdés az, hogy hányadik akkor i + 1 a vége
                        //ha a kérdés az, hogy mi az indexe, akkor csak i
			System.out.printf("Van ilyen a következő helyen: %d\n", i + 1); 
 
		}else {
			System.out.println("Nincs ilyen elem");
                }
	}
}

Kiválogatás tétel

Program.java
class Program
{
	public static void main(String[] argv)
	{		
		int[] a = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		int[] b = new int[n];
		int j=0;
		for(int i=0; i<n;i++)
			if(a[i] > 5)
				b[j++] = a[i];
 
		int m = j; //A "b" tömb elemeinek száma
 
		//Első tömb kiíratva:
		for(int i=0; i<n;i++)
			System.out.print(a[i] + " ");
		System.out.println();
 
		//Második tömb kiíratva:
		for(int i=0; i<m;i++)
			System.out.print(b[i] + " ");
		System.out.println();
 
	}
}

Szétválogatás tétel

Program.java
class Program
{
	public static void main(String[] argv)
	{		
		int[] a = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
		int[] b = new int[n];
		int[] c = new int[n];
 
		int j=0;
		int k=0;
		for(int i=0; i<n;i++)
			if(a[i] > 5)
				b[j++] = a[i];
			else
				c[k++] = a[i];
 
		int m = j; //A "b" tömb elemeinek száma
		int l = k; //A "c" tömb elemeinek száma
 
		//Első tömb kiíratva:
		for(int i=0; i<n;i++)
			System.out.print(a[i] + " ");
		System.out.println();
 
		//Második tömb kiíratva:
		for(int i=0; i<m;i++)
			System.out.print(b[i] + " ");
		System.out.println();
 
		//Harmadik tömb kiíratva:
		for(int i=0; i<l;i++)
			System.out.print(c[i] + " ");
		System.out.println();
 
	}
}

Metszet tétel

Program.java
class Program
{
	public static void main(String[] argv)
	{		
		int[] a = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // Az első tömb elemeinek száma
		int[] b = {4, 7, 9, 8, 2};
		int m = 5; //A második tömb elemeinek száma
		int[] c = new int[n+m]; //A harmadik tömb
 
		int j;
		int k = 0;
		for(int i=0; i<n;i++)
		{
			j = 0;
			while(j<m && b[j] != a[i])
				j++;
			if(j<m)
			{
				c[k] = a[i];
				k++;
			}
		}
 
		int l = k; //A "c" tömb elemeinek száma
 
		//Első tömb kiíratva:
		for(int i=0; i<n;i++)
			System.out.print(a[i] + " ");
		System.out.println();
 
		//Második tömb kiíratva:
		for(int i=0; i<m;i++)
			System.out.print(b[i] + " ");
		System.out.println();
 
		//Harmadik tömb kiíratva:
		for(int i=0; i<l;i++)
			System.out.print(c[i] + " ");
		System.out.println();
 
	}
}

Unió tétel

Program.java
/* Unió tétel */
class Program7
{
	public static void main(String[] argv)
	{		
		int[] a = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // Az első tömb elemeinek száma
		int[] b = {4, 7, 9, 8, 2};
		int m = 5; //A második tömb elemeinek száma
		int[] c = new int[n+m]; //A harmadik tömb
 
		for(int i=0; i<n; i++)
			c[i] = a[i];
 
		int k = n-1;
 
		for(int j=0; j<m;j++)
		{
			int i = 0;
			while(i<n && a[i] != b[j])
				i++;
			if(i>=n)
			{
				k++;
				c[k] = b[j];	
			}
		}
 
		int l = k + 1; //A "c" tömb elemeinek száma
 
		//Első tömb kiíratva:
		for(int i=0; i<n;i++)
			System.out.print(a[i] + " ");
		System.out.println();
 
		//Második tömb kiíratva:
		for(int i=0; i<m;i++)
			System.out.print(b[i] + " ");
		System.out.println();
 
		//Harmadik tömb kiíratva:
		for(int i=0; i<l;i++)
			System.out.print(c[i] + " ");
		System.out.println();
 
	}
}

Maximum kiválasztás tétele

Program.java
class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
 
		int max = tomb[0];
 
		for(int i=0; i<n;i++)
			if(tomb[i] > max)
				max = tomb[i];
 
		System.out.println("Legnagyobb: " + max);
 
	}
}

Minimumkiválasztás tétele

Program.java
class Program
{
	public static void main(String[] argv)
	{		
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
 
		int min = tomb[0];
 
		for(int i=0; i<n;i++)
			if(tomb[i] < min)
				min = tomb[i];
 
		System.out.println("Legkisebb: " + min);
 
	}
}

Rendezések

Buborék rendezés

Program.java
/* Buborék rendezés */
class Program
{
	public static void main(String args[])
	{
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
 
		for(int i= n-1; i>0; i--)
			for(int j=0; j<i; j++)
				if(tomb[j] > tomb[j+1])
				{
					int tmp = tomb[j];
					tomb[j] = tomb[j+1];
					tomb[j+1] = tmp;
				}
 
		for(int i=0; i<n; i++)
			System.out.print(tomb[i] + " ");
		System.out.println();
	}
}

Vagy:

Program.java
/* Buborék rendezés */
class Program
{
	public static void main(String args[])
	{
		int[] tomb = {3, 8, 2, 4, 5, 1, 6};
		int n = 7; // A tömb elemeinek száma
 
		for(int i= n-2; i>0; i--)
			for(int j=0; j<=i; j++)
				if(tomb[j] > tomb[j+1])
				{
					int tmp = tomb[j];
					tomb[j] = tomb[j+1];
					tomb[j+1] = tmp;
				}
 
		for(int i=0; i<n; i++)
			System.out.print(tomb[i] + " ");
		System.out.println();
	}
}

Utóbbi különbsége: mettől-meddig megyünk a ciklusban.

Beszúrásos rendezés

Rekurzív megvalósítás:

Program01.java
package rendezesbeszurassal;
 
public class RendezesBeszurassal {
 
    static void rendezesBeszurassalR(int[] t, int n) {        
        if(n>0) { // eredeti: n>1
            rendezesBeszurassal(t, n-1);
            int x = t[n-1]; // eredeti: t[n]
            int j = n-2; // eredeti: n-1
            while(j>= 0 && t[j]>x) {
                t[j+1] = t[j];
                j = j-1;
            }
            t[j+1] = x;
        }
    }
    static void kiir(int[] t) {
        for (int i = 0; i < t.length; i++) {
            System.out.print(t[i]+" ");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        int[] t = {35, 24, 83, 12, 7, 23};
        rendezesBeszurassalR(t, t.length);
        kiir(t);
    }
 
}

Normál megvalósítás: 

    static void rendezesBeszurassal(int[] t) {
        for (int i = 0; i < t.length; i++) {  //eredeti: i=1
            int x = t[i];
            int j = i - 1;
            while(j>=0 && t[j]>x) {
                t[j+1] = t[j];
                j = j - 1;
            }
            t[j+1] = x;
        }
    }

A megjegyzések azokra a tömbökre utalnak, ahol a kezdőérték 1.

Gyorsrendezés

Különböző változatokat látunk itt a gyorsrendezésre.

A tömböt felosztjuk három részre. Egy kisebb, egy egyenlő és egy nagyobb részre, a pivot elem alapján. Ezt követően rekurzívan hívja önmagát az egyes részekre.

Program01.java
import java.util.ArrayList;
import java.util.Arrays;
 
 
public class Program01 {
    static ArrayList<Integer> quicksort(ArrayList<Integer> list) {
        if (list.size() <= 1) {
            return list;
        }
        ArrayList<Integer> less = new ArrayList<>();
        ArrayList<Integer> equal = new ArrayList<>();
        ArrayList<Integer> greater = new ArrayList<>();
        int pivot = list.get(list.size()-1);
        for (Integer x : list) {
            if (x < pivot) less.add(x);
            if (x == pivot) equal.add(x);
            if (x > pivot) greater.add(x);
        }        
        ArrayList<Integer> sumList = new ArrayList<Integer>();
        sumList.addAll(quicksort(less));
        sumList.addAll(equal);
        sumList.addAll(quicksort(greater));        
        return sumList;
    }
 
    static void kiirLista(ArrayList<Integer> list) {
        for(Integer x : list) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        Integer[] t = {8, 2, 7, 9, 5, 4, 3};
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(t));
        list = quicksort(list);
        kiirLista(list);
    }
}

A következő helyben rendező változat hatékonyabb lehet nagyobb méretű elem számnál, mivel nem készít újabb tömböket, helyette a bemeneti tömbön dolgozik.

A bal és jobb széleket azért kell megadni, mert rekurzióban így egyre kisebb tömböket kell átnéznie az algoritmusnak. Így a tömb rendezésekor a második paraméter mindig 0, a harmadik paraméter mindig n-1, ahol n a tömb elemeinek száma.

A következő példa tömbön dolgozik:

Program.java
class Program
{
	static void gyors(int[] tomb, int bal, int jobb)
	{
		if(bal < jobb)
		{
			int also = bal, felso = jobb + 1, kulcs = tomb[bal];
			for( ; ; )
			{
				while(++also < felso && tomb[also] < kulcs)
					;
				while(tomb[--felso] > kulcs)
					;
				if(also >= felso)
					break;
				csere(tomb, also, felso);
			}	
			csere(tomb, felso, bal);
			gyors(tomb, bal, felso -1);
			gyors(tomb, felso+1, jobb);			
		}
	}
 
	static void csere(int[] tomb, int i, int j)
	{
		int seged = tomb[i];
		tomb[i] = tomb[j];
		tomb[j] = seged;
	}
 
	public static void main(String args[])
	{
		int[] tomb = {8, 5, 2, 9, 4, 3, 1, 6};
		int meret = 8;
 
		gyors(tomb, 0, 7);
 
		for(int i=0; i<meret; i++)
			System.out.print(tomb[i] + " ");
		System.out.println();
	}
}

Ez is helyben rendező, de listán dolgozik.

Program01.java
import java.util.ArrayList;
import java.util.Arrays;
 
public class Program01 {
 
    static void quicksort(ArrayList<Integer> list, int lo, int hi) {
        if(lo < hi) {
            int p = partition(list, lo, hi);
            quicksort(list, lo, p-1);
            quicksort(list, p+1, hi);
        }
    }
    static int partition(ArrayList<Integer> list, int lo, int hi) {
        int pivot = list.get(hi);
        int i = lo -1;
        for (int j = lo; j < hi; j++) {
            if(list.get(j)<= pivot) {
                i++;
                swap(list, i, j);
            }
        }
        swap(list, i+1, hi);
        return i + 1;
    }
    static void swap(ArrayList<Integer> list, int i, int j) {
        int tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }
    static void kiir(ArrayList<Integer> list) {
        for(Integer x : list) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Integer[] t = {8, 2, 7, 3, 4, 9};
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(t));
        quicksort(list, 0, list.size()-1);
        kiir(list);
    }
 
}

Ne felejtsük el, hogy a listáknak vannak saját rendező metódusaik is.

Shell rendezés

Program.java
class Program
{
	public static void main(String args[])
	{
		int[] tomb = {8, 5, 2, 9, 4, 3, 1, 6};
		int[] leptomb = {5, 3, 1};
 
		int meret = 8;
 
		for(int k = 0; k< 3; k++)
		{
			int lepeskoz = leptomb[k];
			for(int j = lepeskoz; j < meret; j++)
			{
				int i = j - lepeskoz;
				int kulcs = tomb[j];
				while(i>=0 && tomb[i] > kulcs)
				{
					tomb[i + lepeskoz] = tomb[i];
					i = i - lepeskoz;
				}
				tomb[i + lepeskoz] = kulcs;
			}
		}
 
		for(int i=0; i<meret; i++)
			System.out.print(tomb[i] + " ");
		System.out.println();
	}
}

Összefuttatás

Összefuttatás, összefésülés

Program01.java
class Program01{
	public static void main(String[] args) {
		int[] a = { 1, 3, 5, 7, 9};
		int[] b = {2, 4, 6, 8 };
 
		int[] c = new int[a.length+b.length];
 
		int n = a.length;
		int m = b.length;
 
		int i = 0;
		int j = 0;
		int k = -1;
		while(i<n && j<m) {
			k++;
			if(a[i]<b[j]) {
				c[k] = a[i];
				i++;
			}else if(a[i] == b[j]) {
				c[k] = a[i];
				i++;
				j++;				
			}else if(a[i] > b[j]) {
				c[k] = b[j];
				j++;
			}
		}
		while(i<n) {
			k++;
			c[k] = a[i];
			i++;
		}
		while(j<m) {
			k++;
			c[k] = b[j];
			j++;
		}
 
		kiir(c, k);
 
	}
	public static void kiir(int[] tomb, int meret) {		
		for (int i = 0; i < meret + 1; i++) {			
			System.out.println(tomb[i]);
		}		
	}

Keresés rendezett tömbben

Logaritmikus keresés

Program01.java
public class Program01 {
	public static void main(String[] args) {
 
		int[] t={3, 4, 6, 8, 18, 50, 52, 61, 68, 70};	
 
		int n = t.length;		
 
		int e = 0;
		int u = n-1;
		int k;
		int ker = 52;
		do {
			k = (e+u) / 2;
			if(ker<t[k]) u = k-1;
			if(ker>t[k]) e = k+1;
		}while(e<=u && t[k]!=ker);
		boolean van = e<=u;
		int index = 0;
 
		if(van) {			
			index = k;
		}
		System.out.printf("%s %d\n", van, index);
 
	}
}