TuH2 java

Aus ProgrammingWiki

Archivierte Version vom 2009-04-16T14:05:42+00:00. Aktuelle Version

// Eine Hilfe um mal schnell ein Array beliebiger Länge, zu füllen
int[] erzeugeFeld(int length) {
	int[] field = new int[length];
	for (int i = 0; i < field.length; i++) {
		field[i] = i; 
	}
	return field;
}

//Ein Array für Testzwecke

int myArray[] = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 
100, 150, 165, 180, 200, 1000, 1500, 1600, 1700, 20000};


// die Sequenzielle Suche für den Vergleich
int sequenzSuch(int[] field, int x){
		int element= -1;
		
		for(int i = 0; i < field.length; i++){
			if(field[i] == x) 
				element = i;
		}
		return element;
		
	}


// Die eigentliche Such Methode, diese Liefert die Position an der das Element zu finden ist,
// das Ergebnis -1 signalisiert das das Element nicht enthalten ist!
int binSuch(int[] field, int x){
		int start = 0;
		int ende = field.length-1;
		int mitte = (start + ende)/2;
		
		while(start <= ende && field[mitte] != x){
			if(field[mitte] < x){
				start = mitte + 1;
			}else ende = mitte - 1;
			mitte = (ende + start)/2;
		} 
		
		if(start > ende){
			return -1;
		}else return mitte;
		
	}


//Rekursive Variante
int binSuchRek(int [] field, int x, int start, int ende){
		int mitte = start + ((ende - start)/ 2);
		if(mitte >= field.length){
			return -1;
		}else if(field[mitte] == x){
			return mitte;
		}else if(field[mitte] < x ){
			return binSuchRek(field, x, mitte + 1, ende);
		}else 
			return binSuchRek(field, x, start, mitte - 1);
	}


//karatsubas Multiplikation

import java.math.*;


public class Karatsuba_class {

	
	public BigInteger karatsuba (BigInteger x, BigInteger y)
	{
		int n = Math.max(x.bitLength(),y.bitLength());
		if (n <= 1) return x.multiply(y);
		
		n=n /2;
		BigInteger xH = x.shiftRight(n);
		BigInteger xL = x.subtract (xH.shiftLeft(n));
		BigInteger yH = y.shiftRight (n);
		BigInteger yL = y.subtract (yH.shiftLeft(n));
		
		BigInteger p1 = karatsuba(xH, yH);
		BigInteger p2 = karatsuba(xL, yL);
		BigInteger p3 = karatsuba (xL.add(xH), yL.add(yH));
		
		return p1.shiftLeft(2*n).add(p3.subtract (p1).subtract (p2).shiftLeft(n)).add(p2);
	}
}

<eval> System.out.println("An welcher Stelle ist das Element zu finden? Position:" + binSuch(erzeugeFeld(10), 3)); </eval>