Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
4.0k views
in Technique[技术] by (71.8m points)

recursion - Recursive function always returning same value

I am trying to solve the so-called "Hopper tower problem" with a recursive approach. This problem consists of:

  • Array given as input. (ex: towers = [2,2,4,0,2]).
  • You start at tower[0]
  • Maximum distance you can travel corresponds to your current position in the array. Example: if you are at towers[1], you can go to either towers[2] or towers[3], as the height of your tower is 2.
  • The function should return false if there is no possible configuration that allows you to reach the end of the array.

This exercise can be found better explained here "https://www.youtube.com/watch?v=kHWy5nEfRIQ". However, I want to practice the recursive/DP approach. My current solution must be close, but I have one problem. My helper function always returns a few falses (from those nodes that could not reach the end of the array). Due to this, my final function always returns false, and I do not know how to solve it despite I have searched for the solutions in other sites. Is it common that these functions return different boolean to be interpreted? Or do I have to avoid it (although I do not know how)? Thank you

My code is here:

#include <stdio.h>
#include <iostream>
using namespace std;

//Tower = array of towers
//ptr = current position (pointer)
//n = size of array tower
bool helper(int* tower, int ptr, const int n){

    if ((ptr + tower[ptr]) >= n) { //Stop condition
        return true;
    }
    else{
        if (tower[ptr] != 0){
            for (int i = 1; i <= tower[ptr]; i++) 
                helper(tower, ptr + i, n);
        }
    }
    return false;
}   

bool dpTower(int* tower, int const n) {
    return helper(tower, 0, n);
}

int main()
{
    int tower[] = { 2,2,0,4,2,0 };
    int length = sizeof(tower) / sizeof(tower[0]);

    bool hoppable = dpTower(tower, length);

    if (hoppable == true)
        cout << "It is hoppable";
    else
        cout << "It is not hoppable";

    return 0;
}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)
等待大神解答

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...