Veröffentlicht 14. April 200916 j Hi Leute, Ich häng an einer Übungsaufgabe zu Rekursion. Ich soll da nix abgeben und mach's aus freien Stücken, weil ich das kapieren will und muss. Die berühmte Aufgabe mit den Fibonacci Zahlen krieg ich hin, der Algorithmus lässt sich auch leicht begreifen. Hier mein Problem: A prime number is an integer that cannot be divided by any integer other than one and itself. For example, 7 is prime because its only divisors are 1 and 7. The integer 8 is not prime because its divisors are 1, 2, 4, and 8. Another way to define prime is: prime(N) = prime(N, N-1) prime(N, 1) = true prime(N, D) = if D divides N, false else prime(N, D-1) For example, prime(4) = prime(4,3) prime(4,3) = prime(4,2) prime(4,2) = false Another example, prime(7) = prime(7,6) prime(7,6) = prime(7,5) prime(7,5) = prime(7,4) prime(7,4) = prime(7,3) prime(7,3) = prime(7,2) prime(7,1) = true Translate the math-like definition of prime into two Java methods that return boolean. Use the % operator to test divisibility. Put your method into a class, write a testing class, and test your program. Aufgabenstellung ist also, eine Zahl n zu überprüfen, ob sie eine Primzahl ist - und zwar rekursiv auf Teilbarkeit durch alle ihre Vorgänger. Bisher hab ich das hier: public class Recursion { public boolean prime( int n) { if (n == 1) return true; if((n % n-1) != 0 ) return prime(n-1); else return false; } } public class RecursionTest { public static void main(String args[]) { Recursion prm = new Recursion(); boolean isDivisible = prm.prime(4); System.out.print("Primzahl: " ); if (isDivisible == true) System.out.print("ja"); else System.out.print("nein"); } } Dass es so nicht funktioniert, ist mir klar, nur ich hab keine Ahnung wie ich die prime() Methode richtig schreiben soll. Kann mir wer weiter helfen? Vielen Dank schonmal.
14. April 200916 j Autor So ungefähr dann?! Damit bekomm ich aber n StackOverFlow. Aber is die Richtung richtig? public boolean prime( int n) { if(n > 2) return prime(n, n-1); else if (n == 2) return true; else return false; } public boolean prime(int n, int d) { if(n % d == 0) return prime(1); else return prime(n, n-1); }
14. April 200916 j public class Prime { public Prime() {} private long divisor = 0; public static void main(String[] args) { Prime p = new Prime(); long start = System.currentTimeMillis(); boolean isDivisible = p.testPrime(151); System.out.print("Primzahl: "); if (isDivisible == true) System.out.println("Ja"); else System.out.println("Nein, Erste Teilbarkeit durch "+p.getDivisor()); System.out.println(System.currentTimeMillis()-start+" ms"); } public boolean testPrime(long n) { return testPrime(n, n-1); } public boolean testPrime(long n,long d) { if (d == 1) return true; if ((n % d) != 0) return testPrime(n, d-1); else setDivisor(d); return false; } public long getDivisor() { return divisor; } public void setDivisor(long divisor) { this.divisor = divisor; } } So in etwa. Edit: Kannst das ganze natürlich auch Iterativ machen. Is glaub ich sogar sinnvoller und nicht so Fehleranfällig Edit 2: Wollte grad Iterativ posten, aber war ja zum lernen hier. Dann lass ich das lieber Bearbeitet 14. April 200916 j von DominikJ Iterativ
14. April 200916 j Autor Ja vielen Dank für die Hilfe, hat mich auch weiter gebracht. Meine Lösung is allerdings noch um einiges kürzer und verständlicher geworden: public class Recursion { public boolean prime(long n) { if(n == 1) return false; return prime(n, n - 1); } private boolean prime(long n, long m) { if (m == 1) { return true; } else if (n % m == 0) { return false; } else { return prime(n, m - 1); } } } public class RecursionTest { public static void main(String args[]) { Recursion prm = new Recursion(); boolean isDivisible = prm.prime(4); System.out.print("Primzahl: " ); if (isDivisible == true) System.out.print("ja"); else System.out.print("nein"); } } Und na klar wäre es mit ner herkömmlichen Schleife einfacher, aber es ging ja grad um Rekursion. Danke nochmal.
Archiv
Dieses Thema wurde archiviert und kann nicht mehr beantwortet werden.