AuK/Näherungsverfahren 1 SS10/Java1

Wiki-Quelltext dieser Seite.

<language>Java</language>
<code id="4c0ccf71e9a15" hidden>

/*breite und länge = 6
 *xe = 3;
 *ye = 1;
 * --->geschlossene Springertour 
 */
	boolean imSchachbrett(int x, int y, int breite, int länge) {
		return ((0 <= x && x < breite) && (0 <= y && y < länge));
	}

	int möglicheSchritte(int[][] a, int breite, int länge, int x, int y) {
		int anzahl = 0;
		int xn, yn;
		for (int i = 0; i < 8; i++) {
			xn = x + nx[i];
			yn = y + ny[i];
			if (imSchachbrett(xn, yn, breite, länge) && a[xn][yn] == 0)
				anzahl++;
		}
		return anzahl;
	}

	boolean findeBestenWeg(int[][] a, int breite, int länge, int[] xy) {
		int aux = Integer.MAX_VALUE;
		int xn, yn, xx = 0, yy = 0;
		for (int i = 0; i < 8; i++) {
			xn = xy[0] + nx[i];
			yn = xy[1] + ny[i];
			if (imSchachbrett(xn, yn, breite, länge) && a[xn][yn] == 0) {
				int schritte = möglicheSchritte(a, breite, länge, xn, yn);
				if (schritte < aux) {
					aux = schritte;
					xx = xn;
					yy = yn;
				}
			}
		}
		if (aux < Integer.MAX_VALUE) {
			xy[0] = xx;
			xy[1] = yy;
			return true;
		}
		return false;
	}

	/*
	 * boolean mitSprungErreichbar(int[][] a,int[] nx,int[] ny,int breite,int
	 * länge,int UrsprungX,int UrsprungY){ for(int i=0;i<nx.length;i++){
	 * if(a[UrsprungY+ny[i]][UrsprungX+nx[i]]==breite*länge){ return true; }else
	 * return false;
	 * 
	 * } }/*mitSprungErreichbar(a,breite,länge,ursprungX,ursprungY)
	 * 
	 * void wegBerechnung(int[][] a,int breite,int länge,int[] xy, int ctr ){
	 * while (findeBestenWeg(a, breite, länge, xy)) { a[xy[0]][xy[1]] = ++ctr; }
	 * }
	 */


		int[] nx = { -2, -2, -1, -1, 1, 1, 2, 2 };
		int[] ny = { -1, 1, -2, 2, -2, 2, -1, 1 };
		int breite = 0;
		int länge = 0;
		int ye = 0;
		int xe = 0;
		int xn, yn;
		länge = Integer.parseInt(JOptionPane.showInputDialog(null,
				"Geben Sie die Breite eines n*m Schachbretts an : ", "6"));
		breite = Integer.parseInt(JOptionPane.showInputDialog(null,
				"Geben Sie die Länge eines n*m Schachbretts an : ", "6"));
		xe = Integer.parseInt(JOptionPane.showInputDialog(null,
				"Geben Sie die x-Koordinate des Springers an (zwischen 1 und "
						+ breite + "): ", "2"));
		while (xe > breite)
			xe = Integer.parseInt(JOptionPane.showInputDialog(null,
					"Geben Sie die x-Koordinate des Springers an(zwischen 1 und "
							+ breite + "): ", "2"));
		ye = Integer.parseInt(JOptionPane.showInputDialog(null,
				"Geben Sie die y-Koordinate des Springers an (zwischen 1 und "
						+ länge + "): ", "2"));
		while (ye > länge)
			ye = Integer.parseInt(JOptionPane.showInputDialog(null,
					"Geben Sie die y-Koordinate des Springers an (zwischen 1 und "
							+ länge + "): ", "2"));
		ye--;
		xe--;
		int[][] a = new int[breite][länge];
		int ursprungX = xe, ursprungY = xe;
		a[ye][xe] = 1;
		int ctr = 1;
		int[] xy = new int[2];
		xy[0] = ye;
		xy[1] = xe;
		while (findeBestenWeg(a, breite, länge, xy)) {
			a[xy[0]][xy[1]] = ++ctr;
		}
		if (ctr == breite * länge) {
			for (int i = 0; i < breite; i++) {
				System.out.println();
				System.out.println();
				for (int j = 0; j < länge; j++) {
					System.out.print(a[i][j] + "\t");
				}
			}

			for (int i = 0; i < 8; i++) {
				xn = ursprungX + nx[i];
				yn = ursprungY + ny[i];
				if (imSchachbrett(xn, yn, breite, länge)) {
					if (a[ursprungY + ny[i]][ursprungX + nx[i]] == breite* länge){
						gTour = true;
					} else
						gTour = false;
				}
			}System.out.println();
                        System.out.println();
                        if (gTour == true)
				System.out.println("Es ist eine geschlossene Springertour!");
                        else System.out.println("Es ist keine geschlossene Springertour!");
		} else
			System.out.println("Es gibt keine Lösung für diese Startposition!!");
</code>
<eval id="4c0680bb30e86"></eval>