C ++ - Может ли кто-нибудь помочь мне перевести это цикл для функции рекурсии? - PullRequest
Новая
       36

C ++ - Может ли кто-нибудь помочь мне перевести это цикл для функции рекурсии?

0 голосов
/ 30 октября 2019

У меня есть массив, таблица, с некоторыми символами, а и б. Я хочу найти и заменить 'b' на 'a', а затем посчитать, сколько их заменить. Как написать рекурсивную функцию, эквивалентную вложенному циклу? 

    const int length = 4;
    char table[length][length] = {
        {'a','b','a','a'},
        {'a','a','a','b'},
        {'a','a','b','a'},
        {'b','b','a','a'}
    };

    int count = 0;
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length; j++) {
            if (table[i][j] == 'b') {
                count++;
                table[i][j] = 'a';
            }
        }
    }
    cout << "Count: " << count << endl;

Это то, что я пытался: 

int replace_char(char array[][length], int row, int col) {
    // base cases and recursive
    if (row+1 != length - 1)
        replace_char(array, row+1, col);
    if (col+1 != length - 1)
        replace_char(array, row, col+1);

    // do this
    if (array[row][col] == 'b') {
        array[row][col] = 'a';
        return 1 + replace_char(array, row, col);
    }
    return 0;
}

Моя идея, если это не конец столбца илистрока, затем проверьте следующий столбец или строку. При проверке, если char равен b, верните 1 и начните проверку с того места, где он останавливается. Но это не работает.

Ответы [ 2 ]

0 голосов
/ 30 октября 2019

Очень близко: 

int replace_char(char array[][length], int row, int col) {
    if (col == length) {
        return replace_char(array, row + 1, 0); // reach the end of a col increment the
                                                // row by 1 and reset the col.
                                                // We are over the end so return
    }
    if (row == length) {
        // Then we have passed the last row simply return.
        return 0;
    }

    // Now do the work.
    int count = 0;
    if (array[row][col] == 'b') {
        array[row][col] = 'a';
        count = 1;
    }
    // Once you have done the work
    // Make the recursive call.
    return count + replace_char(array, row, col + 1);
}
0 голосов
/ 30 октября 2019

Функция может быть определена следующим образом, как показано в демонстрационной программе 

#include <iostream>

size_t replace_count( char *s, size_t n, char c1 = 'b', char c2 = 'a' )
{
    return n == 0 ? 0 
                  : ( ( *s == c1 ? ( *s = c2, 1 ) : 0 ) + replace_count( s + 1, n - 1, c1, c2 ) );
}

int main() 
{
    const int length = 4;
    char table[length][length] = {
        {'a','b','a','a'},
        {'a','a','a','b'},
        {'a','a','b','a'},
        {'b','b','a','a'}
    };

    std::cout << replace_count( reinterpret_cast<char *>( table ), length * length )
              << '\n';

    return 0;
}

Ее вывод 

5
...