✔ Baum?Array?Stack? oder Liste?

[Crach]

So, nun Teil 2 der ganzen Sache:

Problem ist, dass es nicht nur so wenig Werte sind, die in das Programm geladen werden müssen. Auf deutsch: es können bis zu 30 zeilen untereinander reingeladen werden, nicht nur die 6. Und das ganze auf eine Länge von auch max. 30 (naja 29).

Da dann ziemlich viele kombinationen raus kommen..und extrem lange. Kann eine Beschränkung eingebaut werden. Also nur Zeichenketten mit max. 10 Elementen

 

[SymTec]

Diese Version spricht auch weitere Knackpunkte des Problems an. Natürlich sollten dann noch "MaximumWay" und auch "InitialArray" als Argumente übergeben werden; das ist aber am besten bei der Implementierung in den Kontext möglich.

import java.util.*;

//version 2.0
//date 17.11.2007
//author SymTec

public class Proj1 {
  //static variable declaration (vars will be accessible throughout the program)
  static byte MaximumWay=5;
  static byte[][] 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 returnVector = new Vector();

  public static void main(String[] args) {
    //variable declaration for the main method
    byte i;

    //go through first line and find the different paths from there
    for(i=0;i<InitialArray[0].length;i++){
      if (InitialArray[0][i]>0) {
        new Proj1((byte)0,i,(byte)0,"");
      }
    }
    
    //declaration of the return variable (makes more sense here than in the
    //normal declaration part)
    int[][] returnArray = new int[returnVector.size()][];

    //in this loop, the path that had been stored as String is converted back
    //to integers. The var "MaximumWay" has got another meaning now than before.
    for(i=0;i<returnVector.size();i++) {
      String s=returnVector.get(i).toString();
      int[] sArray = new int[s.length()];
      for(MaximumWay=0;MaximumWay<s.length();MaximumWay++){
        sArray[MaximumWay]=(int)s.charAt(MaximumWay);
      }
      returnArray[i]=sArray;
    }

    //Debug output:
    String str="Solutions to this problem:\n";
    for(i=0;i<returnArray.length;i++){
      for(byte j=0;j<returnArray[i].length;j++){
        str=str+returnArray[i][j]+" ";
      }
      str=str+"\n";
    }
    System.out.println(str);
    //End Debug
  }

  public Proj1(byte line, byte entry, byte s, String path){
    //variable declaration for this instance of method Proj1
    byte news=(byte)(s+1),i,j;
    byte number=InitialArray[line][entry];
    String newpath=path+(char)number;
    boolean EndOfBranch=true,LinkWorks;

    //go through line, look for working links
    for(i=0;i<InitialArray[line].length;i++){
      LinkWorks=true;

      //if link is zero, it does not work
      if(InitialArray[number][i]==0) LinkWorks=false;
      //if link is already somewhere in the path, it does not work
      for(j=0;j<InitialArray.length;j++){
        if(path.indexOf((char)InitialArray[number][i])>=0) LinkWorks=false;
      }
      
      //if link works, call next instance of Proj1.
      //if there is a next instance, this obviously is not the end of this branch.
      if((LinkWorks)&&(news<MaximumWay)){
        new Proj1(number,i,news,newpath);
        EndOfBranch=false;
      }
    }
    
    //if no further instance has been called, add the path you took to get here
    //to the list of possible solutions for this problem.
    if (EndOfBranch) returnVector.add(newpath);
  }
}

 

[SymTec]

Scheinbar ist in der geplanten Umgebung die Klasse java.util.* nicht vorrätig. Version 3.0 spart sich die Verwendung des Datentyps "vector" und verzichtet daher auf diese Klasse, braucht dann aber ein wenig mehr Aufwand, um die Pfade aus dem Datenwust zu extrahieren:

//version 3.0
//date 18.11.2007
//author SymTec

public class Proj1 {
  //static variable declaration (vars will be accessible throughout the program)
  static byte MaximumWay=5;
  static byte[][] InitialArray = {
            {1,2,0,0,0,0,0,0,0,0},
            {2,0,0,0,0,0,0,0,0,0},
            {1,4,3,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 String returnPath = "";
  static int numWays=0;

  public static void main(String[] args) {
    //variable declaration for the main method
    byte i;

    //go through first line and find the different paths from there
    for(i=0;i<InitialArray[0].length;i++){
      if (InitialArray[0][i]>0) {
        new Proj1((byte)0,i,(byte)0,"");
      }
    }
    
    
    //declaration of the return variable (makes more sense here than in the
    //normal declaration part)
    int[][] returnArray = new int[numWays][];
      
    //in this loop, the path that had been stored as String is converted back
    //to integers.
    int start=0,stop;
    String s;
    for(int j=0;j<numWays;j++) {
      stop=returnPath.indexOf((char)127,start);
      s=returnPath.substring(start,stop);
      int[] sArray = new int[s.length()];
      for(i=0;i<s.length();i++){
        sArray[i]=(int)s.charAt(i);
      }
      returnArray[j]=sArray;
      start=stop+1;
    }

    //Debug output:
    String str="Solutions to this problem:\n";
    for(int k=0;k<returnArray.length;k++){
      for(byte j=0;j<returnArray[k].length;j++){
        str=str+returnArray[k][j]+" ";
      }
      str=str+"\n";
    }
    System.out.println(str);
    //End Debug
  }

  public Proj1(byte line, byte entry, byte s, String path){
    //variable declaration for this instance of method Proj1
    byte news=(byte)(s+1),i,j;
    byte number=InitialArray[line][entry];
    String newpath=path+(char)number;
    boolean EndOfBranch=true,LinkWorks;

    //go through line, look for working links
    for(i=0;i<InitialArray[line].length;i++){
      LinkWorks=true;

      //if link is zero, it does not work
      if(InitialArray[number][i]==0) LinkWorks=false;
      //if link is already somewhere in the path, it does not work
      for(j=0;j<InitialArray.length;j++){
        if(path.indexOf((char)InitialArray[number][i])>=0) LinkWorks=false;
      }
      
      //if link works, call next instance of Proj1.
      //if there is a next instance, this obviously is not the end of this branch.
      if((LinkWorks)&&(news<MaximumWay)){
        new Proj1(number,i,news,newpath);
        EndOfBranch=false;
      }
    }
    
    //if no further instance has been called, add the path you took to get here
    //to the list of possible solutions for this problem.
    if (EndOfBranch) {
      returnPath=returnPath+newpath+(char)127;
      numWays++;
    }
  }
}