Паритет - Рекурсия Java - PullRequest
Новая
       26

Паритет - Рекурсия Java

0 голосов
/ 09 декабря 2018

У меня проблема с проверкой четности: двоичная строка - это строка, содержащая только символы «0» и «1».Четность двоичной строки определяется следующим образом.Если число раз, когда символ «1» появляется в этой строке, является четным, то четность равна 0;если это нечетно, четность равна 1. Например, четность «101» равна 0, четность «10110» равна 1, а четность «001001101» равна 0. Напишите функцию, используя сигнатуру 

public static int parity(String binaryStr)
//no changes are allowed & only use recursive solution, no loops allowed

Мне удалось написать это итеративно, однако моя рекурсия вне outOfboundries: 

  public static int parity(String binaryStr) {
    int counter = 0;
    for (int i = 0; i < binaryStr.length () ; i++) {
        if (binaryStr.charAt (i) == 49) {
            counter++;
        }
    }
    if ( counter % 2 == 0 ) {
        return 0;
    }
    else {
        return 1;
    }
}

recursive: 

private static int index = 0;
private static int ans = 0;

private static int parity(String binaryStr) {
    if ( index == binaryStr.length ()-1 ) {
        if ( ans % 2 == 0 ) {
            return 0;
        }
        else {
            return 1;
        }
    }
    else if ( binaryStr.charAt (index) == '1' ) {
        ans++;
        return parity (binaryStr.substring (index++));
    }
    return  parity (binaryStr.substring (index++));
}

пожалуйста, помогите мне исправить это

1 Ответ

0 голосов
/ 09 декабря 2018

Основная проблема с вашим кодом заключается в передаче binaryStr.substring (index++) рекурсивному вызову, который передает исходную String вместо подстроки.Следовательно, вы получаете бесконечную рекурсию.Вы можете использовать ++index.

Вместо использования static переменных, я предлагаю следующее: 

private static int parity(String binaryStr) {
    if (binaryStr.length() == 0) {
        return 0;
    } else {
        return ((binaryStr.charAt(0) == '0') ? 0 : 1) ^ parity(binaryStr.substring(1));
    }
}

Объяснение:

Если два операнда бита -если XOR (^) равны, он возвращает 0. Если один операнд равен 0, а другой равен 1, он возвращает 1.

Это именно та логика, которая вам нужна:

Если первый символравен '1', а остаток String имеет четность 1 (т. е. нечетное число '1'), четность всего String равна 0.

Если первый символ равен '1' ирезультат String имеет четность 0 (т. е. четное число '1' s, the whole String` четность равно 1.

Если первый символ равен '0', четность всего String равен паритету остальных String.

...