Задача рекурсии поможет C ++

Question

Я пытаюсь написать код для проверки, можете ли вы достичь конца массива, следуя определенному правилу.Вы начинаете с первого элемента массива целых чисел, и число, хранящееся в этой позиции, - это количество прыжков, которые вы можете сделать вперед или назад.Цель состоит в том, чтобы достичь конца вектора, который представлен значением 0.

 bool Solvable(int start, Vector<int> & squares) {
        int steps = squares[start];
        int prev = start - steps;
        int forward = start + steps;
        if (prev >= 0) {
            if (squares[prev] != squares[start]) {
                return Solvable(prev, squares);
            }
        }
        if (forward < squares.size()) {
            if (squares[forward] == 0) return true;
            if (squares[forward] != squares[start]) {
                return Solvable(forward, squares);
            }
        }
        return false;
    } 

Код не работает, потому что я думаю, что мне не хватает базового варианта, но я не могу понять, какой другой базовый вариант мне нужен.

Спасибо!

Answer 1

Есть пара проблем.Во-первых, ваш код будет только выбирать движение вперед или назад, вы никогда не выбираете оба варианта.Причина в том, что вы всегда говорите return Solvable.Вместо этого вам нужно что-то вроде этого

// try backwards
bool found = Solvable(prev, squares);
// did it work?
if (found)
  return true;
// oh well try forwards
return Solvable(forward, squares);

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

Вторая проблема - это вашаsquares[forward] != squares[start] и squares[prev] != squares[start] тесты.Они не кажутся мне частью проблемы, как вы ее описали.Я бы бросил их.

Хорошая проблема, чтобы проиллюстрировать рекурсию Кстати.

Answer 2

Вот версия, которая обнаруживает циклы и отслеживает, пытались ли вы двигаться вперед или назад от определенного квадрата.Пример использования рекурсивной вспомогательной функции с нерекурсивным внешним интерфейсом для установки переменных (здесь векторов fwd и bck) для отслеживания того, что вы делаете, очень распространен.

#include <iostream>
#include <vector>

using namespace std;

bool helper(int cur, const vector<int> &squares,
            vector<bool> &fwd, vector<bool> &bck)
{
  cout << "cur=" << cur << "  sq=" << squares[cur] << endl;
  if (squares[cur] == 0) return true;     // Found.
  if (fwd[cur] && bck[cur]) return false; // Cycle.
  if (!fwd[cur]) {                        // Try forwards.
    fwd[cur] = true;
    int up = cur + squares[cur];
    if (up < squares.size()) {
      cout << "Forwards" << endl;
      bool found = helper(up, squares, fwd, bck);
      if (found) return true;
    }
  }
  if (!bck[cur]) {                        // Try backwards.
    bck[cur] = true;
    int dn = cur - squares[cur];
    if (dn >= 0) {
      cout << "Backwards" << endl;
      bool found = helper(dn, squares, fwd, bck);
      if (found) return true;
    }
  }
  return false;
}

bool solvable(const vector<int> &squares)
{
  vector<bool> fwd(squares.size(), false);
  vector<bool> bck(squares.size(), false);
  return helper(0, squares, fwd, bck);
}

int sqs[] = { 2, 3, 1, 1, 4, 3, 4, 0, 1, 3, 1 };

int main(void)
{
  vector<int> sq(sqs, sqs + sizeof(sqs) / sizeof(int));
  cout << solvable(sq) << endl;
}