TU Wien:Einführung in die Programmierung 1 VU (Podlipnig)/Übungen zur Rekursion

From VoWi
Jump to navigation Jump to search
 1 public class RecursionTraining {
 2 
 3     // ABCD -> DCBA
 4     public static String reverse(String s){
 5         return null;
 6     }
 7 
 8     // Sollte wie s.equals(t) funktionieren.
 9     public static boolean equalStrings(String s, String t){
10         return false;
11     }
12 
13     // Der gegebene String enthält genau eine öffnende und eine schließende
14     // runde Klammer. Schreibe eine rekursive Funktion, welche den Text
15     // zwischen den Klammern (inklusive der Klammern) retourniert.
16     public static String betweenParen(String s){
17         return null;
18     }
19 
20     // Lösche jedes zweite Zeichen eines Strings
21     // ABCD -> AC
22     public static String del2ndChars(String s){
23        return null;
24     }
25 
26     // Lösche die ersten n Vorkommen des Zeichens x
27     // ABABAB, B, 2 -> AAAB
28     public String deleteNOccurrences(String text, char x, int n){
29         return null;
30     }
31 
32     // Verschiebe alle 'x' in einem String an das Ende
33     // xaxbx -> abxxx
34     public static String mvToEnd(String text) {
35         return null;
36     }
37 
38     // Verschiebe das kleinste Zeichen an den Anfang
39     // Vorbedingungen:
40     // * s != null
41     // * kleinstes Zeichen kommt nur einmal vor
42     // z.B. klein -> eklin
43     public static String shiftMinCharLeft(String s) {
44         return null;
45     }
46 
47     // Gebe alle Permutationen eines Strings aus
48     public static void permutate(String text, int pos){
49     }
50 
51     // Enthält n die Ziffer digit?
52     // z.B. 13, 3 -> true
53     //      13, 4 -> false
54     public static boolean containsDigit(int n, int digit){
55         return false;
56     }
57 
58     // Index vom größten Wert eines Integer Arrays
59     public static int indexOfMaxValue(int[] arr){
60         return 0;
61     }
62 
63     // Gebe eine Zahl in 3er-Blöcken aus, getrennt mit Beistrichen
64     // z.B. 234 -> 234
65     //      12005 -> 12,005
66     public static void formatNum(Long l){
67     }
68 
69     //Gibt true zurück, wenn char m genau count-Mal im String sequence vorkommt, sonst false.
70     //isPresentNTimes("ABBAACBA", 'A', 4) -> true
71     //isPresentNTimes("ABBAACBA", 'Z', 0) -> true
72     //isPresentNTimes("ABBAACBA", 'A', 3) -> false
73     public static boolean isPresentNTimes(String sequence, char m, int count) {
74     }
75 
76     public static void main(String[] args) {
77     }
78 }

Implementierungen von Gittenburg[edit]

  1 public static String reverse(String s){
  2     if (s.length() < 2)
  3         return s;
  4     return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));
  5 }
  6 
  7 public static boolean equalStrings(String s, String t) {
  8     return s.length() == t.length() && (s.length() == 0 ||
  9             s.charAt(0) == t.charAt(0) && equalStrings(s.substring(1), t.substring(1)));
 10 }
 11 
 12 public static String betweenParen(String s){
 13     if (s.charAt(0) != '(')
 14         return betweenParen(s.substring(1));
 15     else if (s.charAt(s.length() - 1) != ')')
 16         return betweenParen(s.substring(0, s.length()-1));
 17     else
 18         return s;
 19 }
 20 
 21 public static String del2ndChars(String s){
 22     if (s.length() < 2)
 23         return s;
 24     return s.charAt(0) + del2ndChars(s.substring(2));
 25 }
 26 
 27 public static String deleteNOccurrences(String text, char x, int n){
 28     if (n > 0){
 29         int idx = text.indexOf(x);
 30         if (idx > 0)
 31             return deleteNOccurrences(text.substring(0,idx) + text.substring(idx+1), x, n-1);
 32     }
 33     return text;
 34 }
 35 
 36 public static String mvToEnd(String text){
 37     if (text.length() == 1)
 38         return text;
 39     else if (text.charAt(0) == 'x')
 40         return mvToEnd(text.substring(1)) + 'x';
 41     else
 42         return text.charAt(0) + mvToEnd(text.substring(1));
 43 }
 44 
 45 public static String shiftMinCharLeft(String s) {
 46     if (s.length() < 2)
 47         return s;
 48 
 49     String r = shiftMinCharLeft(s.substring(1));
 50 
 51     if (r.charAt(0) < s.charAt(0))
 52         return r.charAt(0) + "" + s.charAt(0) + r.substring(1);
 53     else
 54         return s;
 55 }
 56 
 57 public static void permutate(String text, int pos) {
 58     if (pos == text.length() - 1)
 59         System.out.println(text);
 60     else
 61         for (int i = pos; i < text.length(); i++) {
 62             permutate(text.charAt(i) + text.substring(0, i) + text.substring(i+1), pos+1);
 63         }
 64 }
 65 
 66 public static boolean containsDigit(int n, int digit){
 67     if (n < 10)
 68         return n == digit;
 69 
 70     return (n % 10 == digit) || contains(n / 10, digit);
 71 }
 72 
 73 public static int indexOfMaxValue(int[] arr) {
 74     if (arr.length == 1)
 75         return 0;
 76     int max = indexOfMaxValue(Arrays.copyOf(arr, arr.length - 1));
 77     return max < arr[arr.length - 1] ? arr.length - 1 : max;
 78 }
 79 
 80 public static void formatNum(Long l){
 81     String s = String.valueOf(l);
 82     int count = s.length() % 3;
 83     if (count == 0)
 84         count = 3;
 85     System.out.print(s.substring(0, count));
 86 
 87     if (s.length() > count){
 88         System.out.print(',');
 89         if(s.charAt(count) == '0')
 90             System.out.print('0');
 91         if(s.charAt(count+1) == '0')
 92             System.out.print('0');
 93         formatNum(Long.valueOf(s.substring(count)));
 94     }
 95 }
 96 
 97 public static boolean isPresentNTimes(String sequence, char marker, int count) {
 98         if (sequence.isEmpty()) return false;
 99         boolean charIn = (sequence.charAt(0) == marker);
100         if (sequence.length() == 1) return charIn
101                 ? count - 1 == 0
102                 : count == 0;
103         return charIn
104                 ? isPresentNTimes(sequence.substring(1), marker, count - 1)
105                 : isPresentNTimes(sequence.substring(1), marker, count);
106     }

Externe Links[edit]