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

Download

public class RecursionTraining {

    // ABCD -> DCBA
    public static String reverse(String s){
        return null;
    }

    // Sollte wie s.equals(t) funktionieren.
    public static boolean equalStrings(String s, String t){
        return false;
    }

    // Der gegebene String enthält genau eine öffnende und eine schließende
    // runde Klammer. Schreibe eine rekursive Funktion, welche den Text
    // zwischen den Klammern (inklusive der Klammern) retourniert.
    public static String betweenParen(String s){
        return null;
    }

    // Lösche jedes zweite Zeichen eines Strings
    // ABCD -> AC
    public static String del2ndChars(String s){
       return null;
    }

    // Lösche die ersten n Vorkommen des Zeichens x
    // ABABAB, B, 2 -> AAAB
    public String deleteNOccurrences(String text, char x, int n){
        return null;
    }

    // Verschiebe alle 'x' in einem String an das Ende
    // xaxbx -> abxxx
    public static String mvToEnd(String text) {
        return null;
    }

    // Verschiebe das kleinste Zeichen an den Anfang
    // Vorbedingungen:
    // * s != null
    // * kleinstes Zeichen kommt nur einmal vor
    // z.B. klein -> eklin
    public static String shiftMinCharLeft(String s) {
        return null;
    }

    // Gebe alle Permutationen eines Strings aus
    public static void permutate(String text, int pos){
    }

    // Enthält n die Ziffer digit?
    // z.B. 13, 3 -> true
    //      13, 4 -> false
    public static boolean containsDigit(int n, int digit){
        return false;
    }

    // Index vom größten Wert eines Integer Arrays
    public static int indexOfMaxValue(int[] arr){
        return 0;
    }

    // Gebe eine Zahl in 3er-Blöcken aus, getrennt mit Beistrichen
    // z.B. 234 -> 234
    //      12005 -> 12,005
    public static void formatNum(Long l){
    }

    //Gibt true zurück, wenn char m genau count-Mal im String sequence vorkommt, sonst false.
    //isPresentNTimes("ABBAACBA", 'A', 4) -> true
    //isPresentNTimes("ABBAACBA", 'Z', 0) -> true
    //isPresentNTimes("ABBAACBA", 'A', 3) -> false
    public static boolean isPresentNTimes(String sequence, char m, int count) {
    }

    public static void main(String[] args) {
    }
}

Implementierungen von Gittenburg

public static String reverse(String s){
    if (s.length() < 2)
        return s;
    return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));
}

public static boolean equalStrings(String s, String t) {
    return s.length() == t.length() && (s.length() == 0 ||
            s.charAt(0) == t.charAt(0) && equalStrings(s.substring(1), t.substring(1)));
}

public static String betweenParen(String s){
    if (s.charAt(0) != '(')
        return betweenParen(s.substring(1));
    else if (s.charAt(s.length() - 1) != ')')
        return betweenParen(s.substring(0, s.length()-1));
    else
        return s;
}

public static String del2ndChars(String s){
    if (s.length() < 2)
        return s;
    return s.charAt(0) + del2ndChars(s.substring(2));
}

public static String deleteNOccurrences(String text, char x, int n){
    if (n > 0){
        int idx = text.indexOf(x);
        if (idx > 0)
            return deleteNOccurrences(text.substring(0,idx) + text.substring(idx+1), x, n-1);
    }
    return text;
}

public static String mvToEnd(String text){
    if (text.length() == 1)
        return text;
    else if (text.charAt(0) == 'x')
        return mvToEnd(text.substring(1)) + 'x';
    else
        return text.charAt(0) + mvToEnd(text.substring(1));
}

public static String shiftMinCharLeft(String s) {
    if (s.length() < 2)
        return s;

    String r = shiftMinCharLeft(s.substring(1));

    if (r.charAt(0) < s.charAt(0))
        return r.charAt(0) + "" + s.charAt(0) + r.substring(1);
    else
        return s;
}

public static void permutate(String text, int pos) {
    if (pos == text.length() - 1)
        System.out.println(text);
    else
        for (int i = pos; i < text.length(); i++) {
            permutate(text.charAt(i) + text.substring(0, i) + text.substring(i+1), pos+1);
        }
}

public static boolean containsDigit(int n, int digit){
    if (n < 10)
        return n == digit;

    return (n % 10 == digit) || contains(n / 10, digit);
}

public static int indexOfMaxValue(int[] arr) {
    if (arr.length == 1)
        return 0;
    int max = indexOfMaxValue(Arrays.copyOf(arr, arr.length - 1));
    return max < arr[arr.length - 1] ? arr.length - 1 : max;
}

public static void formatNum(Long l){
    String s = String.valueOf(l);
    int count = s.length() % 3;
    if (count == 0)
        count = 3;
    System.out.print(s.substring(0, count));

    if (s.length() > count){
        System.out.print(',');
        if(s.charAt(count) == '0')
            System.out.print('0');
        if(s.charAt(count+1) == '0')
            System.out.print('0');
        formatNum(Long.valueOf(s.substring(count)));
    }
}

public static boolean isPresentNTimes(String sequence, char marker, int count) {
        if (sequence.isEmpty()) return false;
        boolean charIn = (sequence.charAt(0) == marker);
        if (sequence.length() == 1) return charIn
                ? count - 1 == 0
                : count == 0;
        return charIn
                ? isPresentNTimes(sequence.substring(1), marker, count - 1)
                : isPresentNTimes(sequence.substring(1), marker, count);
    }

Externe Links

• https://codingbat.com/java/Recursion-1