Отладка рекурсивной проблемы; неверный вывод

Question

Я пытаюсь написать программу на основе инструкций, которые мне дали:

Найти длину самой длинной (смежной) возрастающей подпоследовательности в векторе с n элементами. В качестве примера рассмотрим следующий вектор, который содержит 12 элементов:

5, 8, 10, 5, 2, 1, 12, 12, 83, 30, 40, 65

Элементы которые образуют увеличивающиеся последовательности (подпоследовательности всего массива) в этом массиве:

5, 8, 10 (количество элементов равно 3)
5 (1)
2 (1)
1, 12, 12, 83 (4)
30, 40, 65 (3)

Следовательно, длина самой длинной увеличивающейся подпоследовательности равна 4. Обратите внимание, что равные значения считаются как растущие значения.

Мой код должен быть написан с рекурсией для упражнения по пониманию предмета. При попытке скомпилировать программу раньше, вместо 4, мой вывод был 12. Мне нужна помощь, чтобы получить правильный вывод. Я подозреваю, что мои счетчики не увеличиваются правильно. Моя функция "наибольший элемент" работает правильно, но мои проблемы l ie в моей функции последовательности. Помощь будет оценена. Я все еще изучаю, как работает рекурсия.

Вот мой код (в файле .hpp только два моих прототипа):

#include <iostream>
#include <vector>
#include "increasing_sequences_recursive.hpp"

int main() {
    std::vector<int> numbers;
    int input;
    int startIdx = 0;

    std::cout << "Enter a set of numbers (0 to stop): " << std::endl;

    while (true) {
        std::cin >> input;

        if (input != 0) {
            numbers.push_back(input);
        }
        else {
            break;
        }
    } 

    startIdx = numbers.size();
    std::cout << "Length of longest sequence: " <<
           increasing_sequences_recursive(numbers, startIdx);

    return 0;
}

// Recursively find the largest sequence
int increasing_sequences_recursive(std::vector<int> &numbers, int startIdx) {
    int counter = 0;
    int maxCounter = 0;

    if (startIdx == 1) {
        return 1;
    }
    int largeElmt = largestElement(numbers, startIdx);
    counter += increasing_sequences_recursive(numbers, startIdx - 1);
    if (numbers[startIdx - 1] <= largeElmt) {//numbers[startIdx]) {
        counter++;
        if (counter >= maxCounter) {
            maxCounter = counter;
        }
    }
    else {
        if (counter >= maxCounter) {
            maxCounter = counter;
        }
    }

    return maxCounter;
}

// Recursively find the largest element.
int largestElement(std::vector<int> &numbers, int n) {
    // Assume n >= 1; Find largest element in the first
    // n elements of n "numbers"
    if (n == 1)
        return numbers[n - 1];

    int res = largestElement(numbers, n - 1);
    if (res > numbers[n - 1])
        return res;

    return numbers[n - 1];
}

Answer 1

Это звучит как домашнее задание , поэтому я не собираюсь находить ошибку в вашем коде, поскольку она не будет вам полезна в любом смысле. Вместо этого я дам несколько советов, которые, я надеюсь, приведут вас в правильном направлении.

Во-первых, в вашем коде нет ничего странного C ++ - специфицируя c. Таким образом, это, по сути, не вопрос C ++, а скорее вопрос c алгоритма.

Суть рекурсии состоит в том, чтобы сформулировать параметризованную задачу F(N) в терминах задачи более низких значений параметра, например, в терминах F(N-1) и для определения тривиального случая, например F(0). В вашем случае F(N) может означать «длину самой длинной увеличивающейся подпоследовательности без первых N + 1 элементов всей последовательности» (здесь я использую «N + 1» для поддержки индексации на основе нуля). Как мы можем express F(N) в терминах F(N-1)?

Давайте назовем последовательность A, и это N-й элемент A[N] (начиная с нуля). Тогда мы можем сказать, что F(N) равно F(N-1)+1 в случае A[N] >= A[N-1] и 1 в противном случае. Проверьте сами. И, конечно, F(0) - это 1. Теперь ваша задача - перевести это определение на C ++. Код должен выглядеть НАМНОГО проще, чем тот, который вы придумали. Но опять же, я не собираюсь предоставлять это здесь, так как вы должны сделать это самостоятельно.

HTH

Answer 2

Первые алгоритмы c недостаток:

Здесь есть недостаток алгоритми c:

int largeElmt = largestElement(numbers, startIdx);    // (1)<========= 
counter += increasing_sequences_recursive(numbers, startIdx - 1);
if (numbers[startIdx - 1] <= largeElmt) {             // (2)<=========  
    counter++;

В (1) вы ищете самый большой элемент в startIdx первые цифры. Поскольку largestElmt является наибольшим в подмассиве, условие в (2) всегда выполняется. Таким образом, вы всегда добавляете 1 к рекурсивному результату, который начинается с 1. Таким образом, в конце вы только подсчитываете количество элементов в массиве (хотя и сложным образом).

Второй алгоритм c недостаток:

Теперь вы можете исправить это, просто проверив, что последние цифры уменьшаются:

 if (numbers[startIdx-2]<=numbers[startIdx - 1] )    // no need for largest

Это нормально с точки зрения индекса , поскольку startIdx гарантированно будет как минимум 2. К сожалению, ваша рекурсия не учитывает смежность. Таким образом, вы просто будете считать последующие пары, которые увеличиваются, без перезапуска счета в случае сбоя. Итак, здесь вы найдете 8.

Выход?

Вам нужно выделить guish в своей рекурсии в случае, когда вы продлеваете последовательность (просто добавляя одну к текущая длина), а также случай, когда у вас есть сбой (и придется перезапустить с 1). В обоих случаях вы должны следить за самой длинной последовательностью. Поэтому вам нужно как минимум передать что-то большее в качестве параметра рекурсии, если вы хотите рекурсию элемент за элементом.

Но так ли это должно быть? Если нет, вы могли бы oop найти последовательность возрастающих чисел и использовать рекурсию, чтобы найти наибольшую такую ​​последовательность в остальной части массива, как только вы обнаружите нарушение. Это было бы намного проще!