Aufgabensammlung Programmierung/ Zeckendorf-Sequenz/ Lösung (Java)/ Zeckendorf.java

/**
 * Programm zur Lösung der Programmieraufgabe Zeckendorf-Sequenz.
 * Benutzung:
 *     java Zeckendorf.class [Zahl]
 *
 * Für die Repräsentation der Zahlen werden BigInteger-Objekte verwendet. Diese
 * können beliebig große Ganzzahlen darstellen. Für die Indizes hingegen normale
 * int-Werte, weil ein Überlauf völlig unrealistisch ist.
 */

import java.math.BigInteger;

public class Zeckendorf {

	//Liste der Fibonaccizahlen, so wie wir sie brauchen.
	protected static Fibonacci fibs = new Fibonacci(BigInteger.ONE,new BigInteger("2"));

/**
 * Diese Funktion berechnet zu einer übergebenen Zahl den Index der
 * nächstgrößeren Fibonaccizahl.
 * @param number Die Zahl, zu welcher der nächstgrößee Index berechnet wird.
 */
public static int nextFib(BigInteger number) {
	int i = -1;
	//solange getFib(i) < number, die Iteration besteht aus dem i++.
	while (fibs.getFib(++i).compareTo(number) < 0);

	return i;
}

/**
 * Diese Funktion berechnet die Zeckendorf-Zerlegung zu einer gegebenen Zahl x.
 * @param x Die zu zerlegende Zahl
 */
public static boolean[] zeck(BigInteger x) {
	int limit = nextFib(x);
	//Liste für die Ausgabe
	boolean[] ausgabe = new boolean[limit];

	for (int i = limit - 1;i >= 0;i--) {
		ausgabe[i] = fibs.getFib(i).compareTo(x) <= 0;
		if (ausgabe[i]) x = x.subtract(fibs.getFib(i));
	}

	return ausgabe;
}

/**
 * Hauptfunktion
 * @args args Kommandozeilenargumente
 */

public static void main(String[] args) {
	//Brauche ein Argument
	if (args.length < 1) System.exit(1);

	BigInteger zahl = new BigInteger(args[0]);
	boolean[] zerlegung = zeck(zahl);

	//Ausgabe
	System.out.print("{");
	for (int i = 0;i < zerlegung.length;i++)
		System.out.print((zerlegung[i] ? "true" : "false") +
			(i + 1 < zerlegung.length ? "," : ""));
	System.out.println("}");
}
}