Was soll dieses Programm genau machen ?

[F1sch]

Path.java
Wir betrachten ein rechteckiges Spielfeld aus n x m Punkten, wobei ca. 10% der
Punkte mit einem Bonus belegt sind. Ziel ist es, einen Weg von (0;0) nach (n-1;m-1)
zu finden, auf dem möglichst viele Boni eingesammelt werden können. Dabei darf man nur
nach rechts oder unten laufen, nicht nach links oder rechts. Schreiben Sie eine rekursive Java-
Methode, welche die Anzahl der Boni ermittelt, die maximal eingesammelt werden können.
Schreiben Sie außerdem ein geeignetes Rahmenprogramm.

Beispiel:
Anzahl Punkte horizontal: 5
Anzahl Punkte vertikal: 7
00001
00010
00110
00100
00000
00000
00010
Es koennen maximal 3 Boni eingesammelt werden.

Ich versteh nicht genau was das Programm machen soll...

Soll ich eine nxm Matrix programmieren in der zufällig ca. 10% der gesamt Punkte (im Bsp 10% von 35 Punkten) mit einem Bonus belegt sind?
Ich versteh die Aufgabenstellung nicht wirklich... Wie kommt man bei dem Beispiel auf 3 Boni?
Kann es mir jemand erklären ? 😀

 

[asdasdjk]

verschiedene wege aufstellen und einen geeigneten wählen.

man startet immer bei einem bestimmten feld, und kann jeweils nur nach unten oder rechts unten gehen. es gibt also immer eine alternative. wie würde man den weg speichern und was würde man bei einer alternative machen?

es ist ja schon der hinweis auf eine rekursive methode gegeben...

 

[darekkay]

Ich musste das auch zwei mal lesen ^^
Der wichtigste Punkt ist: Dabei darf man nur nach rechts oder unten laufen, nicht nach links oder oben.

Schau dir dein Beispiel an, und überlege, warum höchstens 3 Boni möglich sind 😉

Deine Aufgabe ist es, einen Algorithmus zu schreiben, der bei einem gegebenen Feld (also sollst du keine Felder programmieren, höchstens um deinen Algorithmus zu testen) die höchste Anzahl an Boni ausgibt, die gesammelt werden können.

 

[F1sch]

public class Path {
	public static void main(String[] args) {		             
		System.out.print("Anzahl Punkte horizontal: ");
		int n=In.readInt();
		System.out.print("Anzahl Punkte vertikal: ");
		int m=In.readInt();
		int[][] a;
		a= new int[n][m];
		for (int i=0; i<a.length; ++i) {
		for (int j=0; j<a[i].length; ++j) {
		System.out.print(a[i][j]);
		}
      Out.println();
    }
	
}
}

so den Block hab ich schon^^
wie mach ich es nun damit die 10% Boni (die 1en) zufällig in der Matrix verteilt werden ? (im Bsp. oben sind es viel mehr als 10% oder seh ich das falsch ?)😀
und wie kann ich es auslesen lassen wieviele Boni ich max sammeln kann ?

 

[asdasdjk]

auf zählerische lösungen musst du schon selbst kommen ^^

für das befüllen mit zufallswerten gibt es zwei ansätze:

solange eine zufällige zahl wählen, deren zugehöriges element noch nicht 1 ist, bis etwa 10% erreicht sind.

oder alle elmente in eine liste packen, dann wiederholt ein zufälliges listenelement wählen und aus der liste entfernen. dabei wird der zur auswahl stehende bereich der zufallszahl immer kleiner.


ein weg würde einer folge von werten entsprechen, die für indices der jeweiligen elemente des arrays stehen. die dabei vorkommende einsen müssen gezählt werden. will nicht alles verraten, aber wie weit seid ihr denn schon bei der programmierung?

int x = 0;
int y = 0;

int sum = 0;

while (x != xmax && y != ymax) {
 if (Math.random() < 0.5) {
  if (x == xmax) {
   y++;
  } else {
   x++;
  }
 } else {
  if (y == ymax) {
   x++;
  } else {
   y++;
  }
 }
 if (array[x][y] == 1) {
  sum++;
 }
}

so sollte ihr es nicht machen!!! aber es ist gut, das zu verstehen.

 

[F1sch]

public class Path {
	private static java.util.Random generator;
	public static void main(String[] args) {
		System.out.print("Anzahl Punkte horizontal: ");
		int n=In.readInt();
		System.out.print("Anzahl Punkte vertikal: ");
		int m=In.readInt();
		int[][] a= new int[n][m];

		generator = new java.util.Random();
    		for (int x = 0; x < n; ++x) {
    		for (int z = 0; z < m; ++z) {
    		a[x][z] = generator.nextInt(2);
		}
       }
       	    for (int i=0; i<a.length; ++i) {
		for (int j=0; j<a[i].length; ++j) {
		System.out.print(a[i][j]);
		}
		Out.println();
		}
	}

     
    }

hmm hab jetzt die zufallszahlen, allerdings deutlich über 10% 🙁

hast du vielleicht icq oder sowas ? 😀

 

[G3]

Und wie kann man die Bonis sammeln?

 

[darekkay]

hmm hab jetzt die zufallszahlen, allerdings deutlich über 10% 🙁

Lass mich raten - es sind etwa 50%? ^^
Du berechnest für jeden Eintrag in der Matrix eine Zufallszahl aus dem Bereich [0,1] (mit nextInt(x) wird eine Zahl aus dem bereich 0 bis x-1 ermittelt). Das heißt, zu 50% wird es eine eins.

Was du machen könntest: eine Zahl aus dem Bereich [0,9] berechnen lassen (nextInt(10)), und beispielsweise bei 0 (oder jeder beliebigen anderen Zahl) das Element auf "Bonus" setzen. In etwa:

for (int x = 0; x < n; ++x) {
	for (int z = 0; z < m; ++z) {
		int zahl = generator.nextInt(9);
		if (zahl == 0){
			a[x][z] = "1";
		}
		else {
			a[x][z] = "0"; // oder was auch immer das zeichen für ein leeres feld ist
		}

	}
}

 

[asdasdjk]

oben muss ein ||, statt dem &&-Operator.
erst wenn beide werte x und y gleich xmax und ymax sind, soll aufgehört werden - das entspräche der position unten rechts.
das programm wählt immer zufällig einen schritt nach rechts oder unten und zählt dabei, auf welchen feldern sich eine eins befindet.

das programm, um den besten weg zu wählen, könnte so aussehen:

import java.io.*;

public class Clazz {

public static void main(String[] args) throws IOException {
	BufferedReader in = new BufferedReader(
							new InputStreamReader(System.in)); // gepufferter reader
	
	System.out.print("Größe des Feldes, separiert durch Kommata, eingeben: ");
	String sizestr = in.readLine();
	String[] size = sizestr.split("\\D");
	int x = Integer.parseInt(size[0]);
	int y = Integer.parseInt(size[1]);
	
	int[][] field = new int[x][y];
	
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < y; j++) {
			if (Math.random() < 0.10) { // circa 10 Prozent
				field[i][j] = 1;
			} else {
				field[i][j] = 0;
			}
		}
	}
	
	printField(field);
	
	int maxSum = maxSum(field, 0, 0, 0);
	System.out.println("maxSum: " + maxSum);
}

public static void printField(int[][] field) {
	for (int i = 0; i < field.length; i++) {
		for (int j = 0; j < field[i].length; j++) {
			System.out.print(field[i][j]);
		}
		System.out.println();
	}
}

public static int maxSum(int[][] ia, int x, int y, int sum) {
	if (x == ia.length || y == ia[0].length) // abbruch
		return sum;
		
	sum += ia[x][y];
	
	// erst rechts, dann unten weitergehen
	int sum1 = maxSum(ia, x + 1, y, sum);
	int sum2 = maxSum(ia, x, y + 1, sum);
	
	return sum1 > sum2 ? sum1 : sum2;
}

}

eigentlich sollte man den eingabe-code wegen der womöglich auftretenden ausnahmen (NumberFormatException, ArrayIndexOutOfBoundsException) so nicht schreiben, aber da es nur ein mini-programm ist, geht es auch so.

versuche die rekursive methode zu verstehen 🙂

 

[asdasdjk]

um verschiedene Probleme zu vermeiden, könnte Abbruch auch so geschrieben werden:

public static int maxSum(int[][] ia, int x, int y, int sum) {
	if (x >= ia.length || y >= ia[x].length) // abbruch
		return sum;

auftretend, wenn array.length == 0 ist, wenn x oder y ungültig ist, wenn 2D-Array nicht quadratisch aufgebaut ist usw.

eigentlich dann keine solche Methode öffentlich deklarieren/definieren, sondern eine öffentliche Methode, die an die dann Private delegiert, schreiben.