Coder Forum

Java Quellcode

import java.util.Date;
import java.text.SimpleDateFormat;
 
/**
 * Diese Klasse sucht für die via Startparameter angegebene Zahl ihre möglichen Partitionen
 * und ermittelt dann die Summe der Kehrwerte der einzelnen Summanden in jeder Partition.
 * Ist diese Summe = 1, wird die gefundene Zahlenmenge ausgegeben. Zusätzlich wird als
 * Statusanzeige jeweils die erste Zahl der Partition nach Abschluss aller Partitionen die
 * mit dieser Zahl beginnen ausgegeben.
 * 
 * @author Frederik Suhr
 * @version 1.01 17.01.2008
 */
 
public class Suchen {
	/**
	 * Diese Methode wird über die Kommandozeile mit zu untersuchender Zahl und ggf. einem Startwert versorgt 
     * 
     * Beispiel 1: Suchen 2008
     * Beispiel 2: Suchen 2008 1890
     * Beispiel 3: Suchen 10  
     * 
     * @param args zahl [optional Startwert)
	 */
	public static void main(String[] args) {
		// Hier wird der Suchalgorythmus gestartet, wenn Paramter übergeben wurden.		
 
		switch (args.length){
			case 1:
				if (Integer.parseInt(args[0]) != 0)
					zs1(Integer.parseInt(args[0]), Integer.parseInt(args[0]));
				break;
 
			case 2:
				if (Integer.parseInt(args[0]) != 0 && Integer.parseInt(args[1]) != 0)
					zs1(Integer.parseInt(args[0]), Integer.parseInt(args[1]));		
			break;
 
			default:
				System.out.println("Fehler. Aufruf mit Paramter: Zu untersuchende Zahl [optional startwert]");
			break;
		}
	}
 
	/**
	 * Diese Methode überprüft für ein Array von Zahlen ob die Summe der Kehrwerte vom Element sAnzahlZuPruefen
	 * bis zum Element 1 gleich 1 ist. Wird 1 überschritten, bricht die Analyse ab.
	 * 
	 * Die Rückwärtssuche bietet sich an, da das Array absteigend sortiert ist, d.h. die grössten
	 * Brüche entstehen hinten. (Genial *g*)
	 * 
	 * @param iZahl Array von zu untersuchenden Zahlen
	 * @param sAnzahlZuPruefen selbst definierte obere Grenze des Arrays
	 */
	private static void fktCheckZahl(int iZahl[], int sAnzahlZuPruefen) {
 
		// hier doch etwas fusch aber ohne die Erweiterung auf die grösste Zahl, die ja die meißten
		// Primfaktoren enthält, habe ich zuviele Lösungen durch Rundungsfehler verloren
		// und einfach das epsilon für einen vergleich runtersetzen ist mir auch irgendwie schwammig,
		// könnte man aber evtl machen, dann die möglichen kandidaten genau prüfen ... hmmm						
		// analyse mit Epsilon durchführen, mögliche Lösungen dann genauer untersuchen (Hauptnenner)
 
		double hauptNenner =  iZahl[1]; 	 	
 
		double summeZaehler = 1.0; // iZahl[1] auf hauptNenner  			 	
	 	int k; //Zählvariable für zu prüfende Zahl	 	 	 		 	 			 	
 
 
	 	if (iZahl[sAnzahlZuPruefen]==1) // wenn nich der triviale Fall {1} vorliegt, wird der bruch immer grösser 1
	 		return;
 
	 	for (k=sAnzahlZuPruefen;k>1;k--) {	 			 			 		
	 		summeZaehler = summeZaehler + hauptNenner / (double)iZahl[k]; 	 		
	 		if (summeZaehler > hauptNenner) 
	 			return;	 				 		
	 	}
 
		// Prüfe ob Summe der Kehrwerte gleich 1
	 	if (summeZaehler == hauptNenner) {
			System.out.println("found " + arrayPrint(iZahl,sAnzahlZuPruefen));
		}	 	
 
	}
 
 
	/**
	 * Partitionen erzeugen und auf gewünschte Eigenschaften überprüfen
	 * 	
	 * Algorithmus zs1 nach ANTOINE ZOGHBIU und IVAN STOJMENOVIC
	 * (siehe http://www.site.uottawa.ca/~ivan/F49-int-part.pdf )
	 * 
	 * @param n zu partitionierende Zahl
	 * @param startWert bilde erste Partition anhand Startwert
	 */
	private static void zs1(int n, int startWert) {
 
		SimpleDateFormat dateFormatter  = new SimpleDateFormat("(dd.MM. HH:mm:ss)"); // Anzeigeformat festlegen                  
 
		System.out.println("Beginne Analyse von " + Integer.toString(n) +  " absteigend ab "+ Integer.toString(startWert) +" " + dateFormatter.format(new Date()));		
 
		if (n==1) {
			System.out.println("Trivialer Fall, Summe von {1} = 1 und der Kehrwert auch 1");
			System.exit(0);
		}
 
 
		int oldN; // Speicher für letzten Wert an Position 1 der Menge --> Ausgabe bei Änderung
     	oldN = startWert;              
 
     	int xi[]=new int[n+1]; // hier finden alle Berechnungen statt, xi enthält die jeweils aktuelle Partition, +1 weil es sonst zu nem überlauf kaum, die letzte speicherstelle wird aber nicht wirklich benutzt!
 
		int m; // Anzahl Partitionen
		int h; // Index der letzten Zahl in der Partition grösser 1
		int r,t; // Variablen für Iteration ...
 
		int i; // Laufvariable Erstbefüllung mit 1en				     		
        for (i=1;i<n+1;i++) {
        	xi[i]=1;
        }	    
 
 
        xi[1] = startWert; // Startwert setzen
 
		if (startWert != n)	{
			// erzeuge Partition der Form
			// {startWert,n-startWert}
			xi[2] = n - xi[1];
			m = 2;
			h = 2;												
 
			// wenn xi[h] grösser als der Vorgänger, ausgleichen
	        while (xi[h] > xi[h-1]) {
	        	r = xi[h] - xi[h-1];
	        	xi[h]-= r;
	        	h++;
        		xi[h]= r;
	        	m++;	            	            
	        }
 
	        // neues h bestimmen: weil letzte stelle evtl gleich 1, vgl def von h
	        while (xi[h] <= 1) {
	        	h--;
	        }	        	        
 
	        r=0;
		}
		else {
			// Partition gleich die Zahl selbst --> ermittle alle Partitionen
			m = 1;
			h = 1;
		}		
 
		// hier beginnt der eigentliche Algorithmus zs1
        while (xi[1]!=1) {  // da der zs1 absteigend iteriert, endet er, wenn die erste Zahl = 1 ist        	
 
        	if (xi[h]==2) {
    	        m++;
    	        xi[h] = 1;
    	        h--;
        	}
        	else {
    	        r = xi[h] - 1;    	        
    	        t = (m - h + 1);    	        
    	        xi[h] = r;
 
    	        while (t >= r) {
    	            h++;
    	            xi[h] = r;
    	            t = t - r;
    	        }
    	        if (t == 0) {
    	        	m = h;
    	        }    	            
    	        else {
    	        	m = h + 1;
    	            if (t > 1) {
    	                h++;
    	                xi[h] = t;    	            	
    	            }	            
    	        }        		
        	}        	
 
        	// zs1 hat eine neue Partition in xi erzeugt:
 
        	if (oldN > xi[1]) { // erster Wert hat sich geändert, Lebenszeichen geben        		        		
        		System.out.println("Alle Partitionen mit " + Integer.toString(oldN) +  " als grösster Zahl überprüft. " + dateFormatter.format(new Date()));
        		oldN = xi[1];
        	}
        	fktCheckZahl (xi, m); // Frage: Ist der Methodenaufruf langsam oder schnell, ggf. Überprüfung hier einfügen?        	
        }	    	    	     
 
        // Vollzug melden
        System.out.println("Alle Partitionen mit " + Integer.toString(oldN) +  " als grösster Zahl überprüft. Fertig. " + dateFormatter.format(new Date()));        
		fktCheckZahl (xi, m);
	}
 
 
	/**
	 * Gibt das Array als Mengenklammer von seinen Elementen zurück
	 * 
	 * @param arr Array von Zahlen
	 * @param ub selbst definierte obere Grenze des Arrays
	 * @return String der Form "{A1,A2,...,Aub}"
	 */
	private static String arrayPrint(int arr[], int ub) {
		String str = "{";
		short i;		
		for (i = 1;i <= ub; i++) {			
			str = str + String.valueOf(arr[i]);
			if (i<ub) str = str + ",";
		}
		str = str + "}";
 
		return str;
	}	
}

Source code

zs1(2008,2008);