Hilfe bei Java Programm

[Janice]

Hallo,
ich muss ein Programm in Java erstellen mit folgender Aufgabenstellung:
Gesucht sind alle zehnstelligen Zahlen, die aus zehn verschiedenen Ziffern bestehen und durch alle Zahlen von 1 bis 9 teilbar sind. Die Zahlen sind zeilenweise in eine Datei zu schreiben!
Leider hab ich keine Ahnung wie ich das machen soll!
Also, bitte helft mir!

Janice

 

[RedWing]

Also wenn ich deine Frage richtig verstanden hab ist das richtige Stichwort
für dich Permutation. Allerding muss ich noch mal nachfragen.
Meinst du wirklich alle 10 stelligen Zahlen mit 10 verschiedenen Ziffern,
den das sind gaaanz schön viele, gell?
Das folgende ist eine Klasse miut der du dir Permuationen generieren lassen kannst.
Den Source Code findest du
hier

Unter Verwendung dieser Klasse kannst du dann für jede Permutation deiner 10 stelligen
Zahl überprüfen ob sie durch 1 ... 9 teilbar (mittels modulo)ist, und diese dann ausgeben.


Gruß

RedWing

 

[squeaker]

wieviel ist 10!? Ich würde vorher ein wenig Hirnschmalz reinstecken. Sonst testest du ewig.

Damit eine Zahl durch 2 teilbar ist, muss sie hinten eine 0,2,4,8 stehen haben.
Damit sie durch 5 teilbar ist, braucht sie hinten (letzte Stelle) eine 0 oder 5.

Damit ist die letzte Stelle schon mal eine 0. Das reduziert die Anzahl der zu testenden Möglichkeiten um Faktor 10.

Die Zahl ist auf jeden Fall durch 3 und 9 teilbar, da die Quersumme 45 ist und 45 ist durch 3 und duch 9 teilbar. Durch 1 ist sie auch immer teilbar und mit der 0 am Ende auch durch 5 und 2.

Fehlen nur noch 4,6,7 und 8. 6 kannst du dir allerdings auch sparen, da die Zahl schon durch 3 und durch 2 teilbar ist, damit auch durch 6 teilbar.

Du kannst die Zahlen auch für den Test von "Hand" herstellen indem du die jeweilige Ziffer mit dem fassenden Faktor multiplizierst. Für die letzte Stelle ist er 1, für die vorletzte 10, dann 100 usw.

Dann musst do blos noch eine Methode finden wie du alle Permutationen herstellst.

 

[RedWing]

Hallo,
deine Idee ist sicherlich nicht schlecht, aber da sie eh alle Kombinationen durchgehen
muss sollte folgendes eigentlich ausreichend sein:

        for(Iterator i = new Permute(args); i.hasNext();){

                StringBuffer buffer = new StringBuffer();
                String[] tmp = (String[])i.next();    //hole dir die nächste Permuation
                String permString = "";
                long perm = 0;

                for(int x = 0; x < tmp.length; x++)    //Fülle PermString mit den Feldwerten aus tmp
                        permString = buffer.append(tmp[x]).toString(); 
                perm = Long.parseLong(permString);     //Wandle Pemutation in long um

                if((perm % 2 == 0) && (perm % 3 == 0) && (perm % 4 == 0) && (perm % 5 == 0)
                                && (perm % 6 == 0) && (perm % 7 == 0) && (perm % 8 == 0)  &&  (perm % 9 == 0))      // Teste auf Division mit Rest
                        System.out.println (perm);
                        //Schreibe in Datei
        }

Gruß

RedWing

 

[squeaker]

Original geschrieben von RedWing
Hallo,
deine Idee ist sicherlich nicht schlecht, aber da sie eh alle Kombinationen durchgehen
muss sollte folgendes eigentlich ausreichend sein:

Genau das ist ja nicht der Fall. Ich weiss ja, dass die letzte Stelle 0 ist und ich brauch nichtmal halb so viele modulos pro test. Allerdings sollte das umbauen deines Iterators machbar sein.

 

[Thomas Darimont]

Hallo!

versuchs mal damit:

public class Permutation {

	private int maxIndex;
	private char[] carray;
	private String s;
	private int anz = 0;

	public Permutation() {}

	public void ausgabe(char[] a) {

		int len = a.length;
		char c = a[len - 1];
		String str = new String(a);
		long i = Long.parseLong(str);
		
		if(i ist Teilbar durch die Zahlen die du willst....){
			System.out.println(i);
		}
	}

	public void doIt() {

		s = "1234567890";

		maxIndex = s.length() - 1;
		carray = s.toCharArray();
		permut(carray, maxIndex);

		System.out.println("\nEs sind :" + anz + " Permutationen");

	}

	public void swap(char[] a, int i, int j) {
		char temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void permut(char[] a, int endIndex) {
		if (endIndex == 0) {
			ausgabe(a);
			anz++;
		} else {
			permut(a, endIndex - 1);
			for (int i = 0; i <= endIndex - 1; i++) {
				swap(a, i, endIndex);
				permut(a, endIndex - 1);
				swap(a, i, endIndex);
			}
		}
	}

	public static void main(String[] args) {
		Permutation p = new Permutation();
		p.doIt();
	}
}

Gruß Tom

 

[squeaker]

Meine Modifikation von Thomas Code ergibt dann:

public class Permutation {

	private int maxIndex;
	private char[] carray;
	private String s;
	private int anz = 0;

	public Permutation() {}

	public void ausgabe(char[] a) {

		int len = a.length;
		char c = a[len - 1];
		String str = new String(a);
		long i = Long.parseLong(str);
                long *=10;
		
		if(i ist Teilbar durch 4,7,8){
			System.out.println(i);
		}
	}

	public void doIt() {

		s = "123456789";

		maxIndex = s.length() - 1;
		carray = s.toCharArray();
		permut(carray, maxIndex);

		System.out.println("\nEs sind :" + anz + " Permutationen");

	}

	public void swap(char[] a, int i, int j) {
		char temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void permut(char[] a, int endIndex) {
		if (endIndex == 0) {
			ausgabe(a);
			anz++;
		} else {
			permut(a, endIndex - 1);
			for (int i = 0; i <= endIndex - 1; i++) {
				swap(a, i, endIndex);
				permut(a, endIndex - 1);
				swap(a, i, endIndex);
			}
		}
	}

	public static void main(String[] args) {
		Permutation p = new Permutation();
		p.doIt();
	}
}

Reduziert die Anzahl der Permutationen auf 32k statt 320k und die Anzahl der modulo-Berechnungen auf 3 statt 9 (pro Zahl).

 

[RedWing]

@squeaker

s = "123456789";

In deinem Fall wird die 0 aber nicht mit permutiert.
Sprich 1023456789 z.B. wird nicht mit berücksichtigt, wenn ich mich da irre
bitte sagen. Sie braucht ja alle zehn Ziffern und nicht nur 9.


Gruß RedWing

 

[squeaker]

dafür wird die Zahl mit 10 Multipliziert. Ich hatte ja oben schon festgestellt, dass die letzte Ziffer eine 0 sein muß (wegen dividierbarkeit durch 5 und durch 2).

 

[RedWing]

Umd was is mit den 0en zwischen den Ziffern.
Siehe mein Beispiel?