✔ Baum?Array?Stack? oder Liste?

Crach

Crach

Mitglied
Hallo,

Tüftel seit einiger Zeit an einem Problem und komm nur schwer voran.
Gegeben ist ein Array mit Zahlen:

Code: 
	1 2 0 0 0 0 0 0 0 0 
	2 0 0 0 0 0 0 0 0 0  
	1 4 0 0 0 0 0 0 0 0  
	2 4 0 0 0 0 0 0 0 0  
	2 3 5 0 0 0 0 0 0 0  
	4 0 0 0 0 0 0 0 0 0

Dieses muss nun so aufgelistet werden, damit es einen Sinn ergibt.
Zb steht in Zelle [0][0] die 1. Das bedeutet. er muss nun im array an Stelle 1 gehen (also Zellen [1][x]). danach schaut er, welche zahlen da so drin sind. Wenn diese schonmal vorkamen..in dieser Reihe von durchgelaufenen Zahlen, dann soll er sie ignorieren ->nur die neuen nehmen.
In dem Fall nimmt er nun die 2 ..und schaut was in zelle [2][x] ist..die 1 und 4 -> er nimmt die 4..weil die 1 schon vor kam. Jetzt soll er zu [4] und diese auslesen.

Mein Problem ist nun: Irgendwann kommt er ja ans ende, wo er nichts neues mehr finden kann. Was dann? Oder wie Implementiert man die ganze Sache am schönsten?

Ich hab die möglichen Fälle als Grafik noch da:

http://www.sabled.de/tmpUpload/beispiel_baum.PNG

Das Programm soll im grunde alle möglichen Kombinationen(alle Pfade durch den Baum) in einem Array (wenn möglich) speichern.
Hab es schon mit einer Rekursion und Iteration versucht... das wird aber viel zu kompliziert und verwirrend :confused: . Wenn möglich, wie könnte man den Baum aufbauen im Programm?


Danke schonmal für hilfreiche Ideen^^
 
Zuletzt bearbeitet:
Ich hab zwar nicht verstanden wie das mit dem Baumerstellen aus dem Array geht aber solang du das verstehst reicht es ja. Wenn du mal eine Suchmaschine benutzt findest du auch genug Beispiele wie man einen Baum in Java erstellt.

Wenn du das hast kannst du dir ja überlegen wie man das gut durchsuchen kann.
 
Danke für die antwort^^

Also nochmal:

Ich hab dieses Array:

1 2 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
1 4 0 0 0 0 0 0 0 0
2 4 0 0 0 0 0 0 0 0
2 3 5 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0

und mit einem "Zeiger" zeig ich auf die erste Zeile oben..Also Zeile 0. da drin findet er die eine zahl. nun übergibt er den Wert dem Zeiger. Also Zeiger=1 . Das bedeutet, dass dieser nun auf die Zeile 1 zeigt..mit den Zahlen 2,0,0,0,0... ..da drin findet er die 2.. nun zeigt er also auf die Zeile 2 ..mit den Zahlen 1,4,0,0,.... Da aber die 1 schonmal vorkam soll er nun die 4 nehmen ..und Zeiger=4 setzen ..in der 4. zeile sind die 2 und die 5 neu. Das soll er dann solange machen, bis er zb durch rekursion durfch jeden abschnitt durchgegangen ist (Wie in meiner Grafik).

Nebenbei soll er aber immer die Kombination speichern.

Leider klingt das ganze relativ einfach in der theorie.. aber sobald er eine nach der anderen rekursion beendet hat, "Weiß" er ja nicht mehr, welche Zahlen schon vorkamen..also -> er arbeitet dann nochmal den zweig ab..obwohl dieser schon gespeichert wurde.

Ich finds selst sehr verwirrend.
 
Auf die Gefahr hin, dass ich wegen meines Küchen-Javas nun gelyncht werde: Bis 4 Uhr heute morgen hatte ich eine lustige Zeit, ein wenig herumzutüfteln; hier das Ergebnis:

Code: 
import java.util.*;
import java.lang.Math.*;

//version 1.0 vom 16.11.2007
//@STL

class Proj1 {
  static int MaxNumber;
  static int[][] InitialArray = {
            {1,2,0,0,0,0,0,0,0,0},
            {2,0,0,0,0,0,0,0,0,0},
            {1,4,0,0,0,0,0,0,0,0},
            {2,4,0,0,0,0,0,0,0,0},
            {2,3,5,0,0,0,0,0,0,0},
            {4,0,0,0,0,0,0,0,0,0}};
  static Vector returnArray = new Vector();

  public static void main(String[] args) {
    MaxNumber = 0;
    int i;
    for(i=0;i<InitialArray.length;i++){
      for(int j=0;j<InitialArray[i].length;j++){
        if (MaxNumber<InitialArray[i][j]) MaxNumber=InitialArray[i][j];
      }
    }

    for(i=0;i<InitialArray[0].length;i++){
      if (InitialArray[0][i]>0) step(0,i,0,0);
    }
    
    String str="Solutions to this problem:\n";
    for(i=0;i<returnArray.size();i++) {
      //Bei Bedarf können hier Nullen weggekürzt, int in ein Array umgewandelt etc. werden.
      //Momentan wird hier einfach der Pfad aus dem Vektor ausgelesen und als String abgeschrieben.
      str = str+" "+returnArray.get(i).toString()+"\n";
    }
    System.out.println(str);
  }

  public static void step(int line, int entry, int s, int path){
    int news=s+1,i,j;
    int number=InitialArray[line][entry];
    int newpath=number*(int)Math.pow(10,MaxNumber-news)+path;

    //System.out.println("path: "+path+" line: "+line+" entry: "+entry+" dest: "+InitialArray[line][entry]+" step: "+s+" newpath: "+newpath);

    boolean EndOfBranch=true,LinkWorks;
    for(i=0;i<InitialArray[line].length;i++){ //go through line for new callups
      LinkWorks=true;

      if(InitialArray[number][i]==0) LinkWorks=false; //Number is zero
      for(j=0;j<MaxNumber;j++){ //number has been seen before
        if(((path%Math.pow(10,j+1))-(path%Math.pow(10,j)))/Math.pow(10,j)==InitialArray[number][i]) LinkWorks=false;
      }
      if(LinkWorks){//Number is a working link; next instance can be called. This also means that here is not the end of branch.
        step(number,i,news,newpath);
        EndOfBranch=false;
      }
    }
    if (EndOfBranch) returnArray.add(newpath);
  }
}
 
Zuletzt bearbeitet:
Okay, nach 6 Tagen und 19 Versuchen hab ichs dann doch hinbekommen.
Hab das ganze mit einer Rekursion gelöst und einer Hand voll von Variablen,welche als Zeiger für die Arrays dienen.

Schreibt mich an, wer sich auch in sowas versuchen will^^.
 
*lol* ich versuch grad in deinem quelltext durchzusehen^^.. aber meiner ist ziemlich lang..und sicher auch extrem uneffizient(hauptsache es klappt^^°°°).

Zur erklärung nochmal:

vorhanden sind dei arrays zb:

0 [1,2]
1 [2]
2 [1,3,4]
3 [2,4]
4 [2,3,5]
5 [4]

er fängt bei 0 oben an..findet die 1..geht in array 1..usw. ..meine Lösung dazu:

Code: 
public int RekursivAufbau(int[][] aktuellesArray,int bushsPointer)
{
	System.out.println(" (Starte rekursion) ");
	
	if(RekTiefe<Suchtiefe)
	{
		int[] temp=new int[groesse];
		
		int tempzahl=0;
		int ursprungsPos=-1;

		temp=vergleichZweiArray(tmparray,buhs,0,bushsPointer,groesse); //gib zahlen zurück, die er weiterhin nutzen kann/darf
		
		int q=-1;
		int e=-1;
		
		while(temp[q+1]>0)
		{
			q++;
		}
		
		int w=q+1;
		if(w>0)
		{
			

			tempzahl=0;
			for(e=0;e<w;e++)
			{
				
				int r=-1;
			
				if(ursprungsPos==-1) ursprungsPos=feldarrayPointer;
				
				if(w>1) //wenn mehr als 1 gefundene neue Zahl vorhanden ist
				{
					int bl=feldarrayPointer+1;
					feldarray=kopieren(feldarray,ursprungsPos,feldarrayPointer+1); //macht eine Kopie im feldarry(hilfsArray) ,damit später wieder auf die alte position zurück gegriffen werden kann...für die anderen neuen Zahlen
					feldarrayPointer++;
				}
				
				while(temp[r+1]>0)
				{
					r++;
				}

				einfuegen(temp[e],feldarray,feldarrayPointer); //fügt eine zahl am ende des Arrays an zb die 5 ... 1,2,3,4,0,0,0,0 -> 1,2,3,4,5,0,0,0
				einfuegen(temp[e],tmparray,0);

				tmparray=kopiereZeile(feldarray, tmparray, 0, groesse, feldarrayPointer);

				bushsPointer=temp[e];
				
				RekTiefe++;
				
				tempzahl=RekursivAufbau(feldarray,bushsPointer);
				
				RekTiefe--;

			}
		}
		else
		{
			entfernen(tmparray,0);
		}
		
		return q;
	}
	else
	{
		return 0;
	}
}

.....
// buhs wird vorher initialisiert..mit den ganzen werten die er durchlaufen soll(wie oben in dem beispiel)

Ich weiß..mit arrays arbeiten ist eig. nicht so toll..es müsst dynamischer sein das ganze. Nur aus Zeitmangel lass ichs so..bin aber bereit für vorschläge zur optimierung ;)
 
Ich habe mal eine Lösung erstellt:

Java: 
import java.util.*;
public class Main{
    public Main() {
        int[][] matrix = {
             {1,2,0,0,0,0,0,0,0,0}, 
             {2,0,0,0,0,0,0,0,0,0},  
             {1,4,0,0,0,0,0,0,0,0}, 
             {2,4,0,0,0,0,0,0,0,0},
             {2,3,5,0,0,0,0,0,0,0},
             {4,0,0,0,0,0,0,0,0,0},       
        };
        for(int zeile=0; zeile<matrix.length; zeile++) {
            ArrayList<Integer> zahlen = new ArrayList<Integer>();
            for(int zelle=0; zelle <matrix[zeile].length; zelle++) {
                if(!zahlen.contains(matrix[zeile][zelle])) {
                    zahlen.add(matrix[zeile][zelle]);
                }
            }
            System.out.print("Zahlen in Reihe " + zeile + ":");
            Iterator<Integer> it = zahlen.iterator();
            while(it.hasNext()) {
                System.out.print(" " + it.next());
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        new Main();
    }  
}
 
@Schnacki: Irgendwie denke ich, dass unsere Lösungen 2 verschiedene Probleme behandeln.

Bei dir ist die "Lösung" (der Output), wenn ich das Programm ablaufen lasse:
Zahlen in Reihe 0: 1 2 0
Zahlen in Reihe 1: 2 0
Zahlen in Reihe 2: 1 4 0
Zahlen in Reihe 3: 2 4 0
Zahlen in Reihe 4: 2 3 5 0
Zahlen in Reihe 5: 4 0
(Was im Übrigen der eingegebenen Matrix entspricht, außer dass hinten die 0'en fehlen).

Mein Programm gibt (sinngemäß) aus:
Mögliche Wege durch das Feld:
1-2-4-3
1-2-4-5
2-1
2-4-3
2-4-5

Mittlerweile bin ich mir selbst auch nicht mehr sicher, was eigentlich die Frage war. Vielleicht könnte Crach noch einmal bestätigen, ob eines dieser Programme in seiner Lösung der Musterlösung entspricht, oder ob gar beide Programme das falsche ausgeben.
 
Danke für Eure Mühe erstmal.

Hab bei meiner Grafik am Anfang bisschen was vergessen gehabt - wobei mein prog. mich dann drauf aufmerksam machte.

Von SymTec die Lösung ist sehr nah dran. Es scheinen nur noch 1-2-3-4-5 und 2-3-4-5 zu fehlen.
Gibt dein Programm es genau so aus? wenn ja, dann würde mir das extrem viel arbeit sparen.

-------- EDIT --------
Bei meinem Beispiel oben fehlte ne 3. Also die Lösung von SymTec müsst richtig sein
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück