Ungültige Wörter filtern

[hanswürstchen]

Hi! Ich hab folgendes Problem: Ich muss Binärwörter erstellen die als Kriterium haben, dass wenn ein Wort zwei aufeinander folgende 11 im Wort hat, noch mindestens eine weitere 1 daran sein muss. Z.B. ist 1010 gültig, 1110 auch aber 1100 nicht. Der Algo. um die Anzahl an gültigen Wörtern zu erlangen lautet "2a(n-1)) - a(n-3) + a(n-4)"

Mein Code gibt nun die maximale Anzahl gültiger Wörter, alle möglichen Kombinationen aber auch die ungültigen wieder.

Kann mir jmd helfen? Wäre echt super!
Hier mal der Code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Sanscouple {
	
	public static void main(String[] args)throws NumberFormatException, IOException { 
	
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
	
		System.out.println("Bitte einen Wert für x eingeben.");
		int x = Integer.parseInt(br.readLine());
		System.out.println("Maximale Anzahl an gueltigen Woertern: "+wordCounter(x));
		allWords(x);

	} 
	
	//Anzahl der maximal gueltigen Woerter berechnen
	public static int wordCounter(int n) { 
		if (n == 1) { 
		return 2; 
		} 
		else if (n == 0) { 
		return 1; 
		} 
		else if (n == 2) { 
		return 3; 
		} 
		else if (n == 3) { 
		return 6; 
		} 
		else { 
		return (2*wordCounter(n-1)) - wordCounter(n-3) + wordCounter(n-4); 
		} 
	} 
	
	//Anzahl aller Woerter berechnen und ausgeben
	public static void allWords(int n) {
		System.out.println("Alle Binaerwoerter mit der Laenge " + n + ":");

		String x;
		int counter = 0;
		int i = 0;

		do {
			x = Integer.toString(i, 2);
			if (x.length() < n) {
				int maxBits = n - x.length();
				for (int j = 1; j <= maxBits; j++) {
					x = "0" + x;
				}
			}
			if (x.length() == n) {
				System.out.println(x);
				counter++;
			}
			i++;
		} while (x.length() <= n);
		
		System.out.println("Anzahl der Binaerwoerter mit der Laenge " + n
				+ ": " + counter + " Woerter");
	}
}

 

[FerdiP]

Also ich hab mich mal dran versucht und bin auf folgenden Code gekommen:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Sanscouple {

  public static void main(String[] args) throws IOException{
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);

    System.out.println("Bitte einen Wert für x eingeben.");
    int x = Integer.parseInt(br.readLine());
    System.out.println("Maximale Anzahl an gueltigen Woertern: "+wordCounter(x));
    allWords(x);
  }
  
  public static int wordCounter(int n){
    if (n == 1) {
      return 2;
    }
    else if (n == 0) {
      return 1;
    }
    else if (n == 2) {
      return 3;
    }
    else if (n == 3) {
      return 6;
    }
    else {
      return (2*wordCounter(n-1)) - wordCounter(n-3) + wordCounter(n-4);
    }
  }
  
  public static void allWords(int n)throws IOException{
    String bin="",end="";
    int last;
    
    for(int i=0;i<n;i++){
      end += "1";
    }
    last = getDez(end);
    System.out.println("0");
    for(int i=1;i<=last;i++){
      bin = getDual(i);
      if( canUse(bin) ){
        System.out.println( bin );
      }
    }
  }
  
  public static boolean canUse(String bin){
    if( bin.length() <= 2 ){
      if( bin.equals("11") ){
        return false;
      }else{
        return true;
      }
    }
    boolean canUse = true;
    char c1=bin.charAt(0),c2=bin.charAt(1);
    for(int i=2;i<bin.length();i++){
      if( c1=='1' && c2=='1' && bin.charAt(i)!='1' ){
        if( bin.length() > 3 && i >= 3){
          if( bin.charAt(i-3)!='1' ){
            canUse = false;
            break;
          }
        }else{
          canUse = false;
          break;
        }
      }
      c1 = c2;
      c2 = bin.charAt(i);
    }
    if( canUse == true ){
      c1=bin.charAt(bin.length()-1);
      c2=bin.charAt(bin.length()-2);
      for(int i=bin.length()-3;i>0;i--){
        if( c1=='1' && c2=='1' && bin.charAt(i)!='1' ){
          if( bin.length() > 3 && i < bin.length()-3){
            if( bin.charAt(i+3)!='1' ){
              canUse = false;
              break;
            }
          }else{
            canUse = false;
            break;
          }
        }

        c1 = c2;
        c2 = bin.charAt(i);
      }
    }
    return canUse;
  }
  
  public static String getDual(int n){
    StringBuilder dual = new StringBuilder();
    int rest;
    while( n != 0 ){
      rest = n % 2;
      dual.append(rest);
      n = n / 2;
    }
    return turnString( dual.toString() );
  }
  
  public static String turnString(String str){
    StringBuilder ant = new StringBuilder();
    char[] strArray = str.toCharArray();
    for(int i=strArray.length-1;i>=0;i--){
      ant.append(strArray[i]);
    }
    return ant.toString();
  }
  
  public static int getDez(String dual){
    int zahl=0,tmp=1;
    for(int i=dual.length()-1;i>=0;i--){
      if(dual.charAt(i) == '1'){
        zahl += tmp;
      }
      tmp *= 2;
    }
    return zahl;
  }
  
}

Es geht sicherlich noch etwas besser und kürzer, da aber viele Überprüfungen und Ausnahmen erledigt werden müssen, sowohl auch Umrechnung, hat es sich etwas in die Länge gezogen. Ich hoffe du kannst trotzdem etwas damit anfangen. Sollte aber eigenltich seine Arbeit tun. Die letzten drei Methoden dienen nur zum umrechnen der Zahlensysteme. In der Methode canUse(String bin) wird eine Dualzahl als String übergeben und es wird überprüft ob man sie verwenden kann. Es wird einmal vorwerts und rückwerts überprüft, da es sich herrausstellte, dass bei zum Beispiel 1011 oder 10111011 als richtig erkannt werden, was aber nicht der Fall sein darf.