c++ - 使用递归的序列到达数组末尾的最小跳转次数

Question

我有一个代码“使用递归以其序列到达数组末尾的最小跳转次数”。 但我无法打印序列。 ( vector vec中没有要打印的内容)
任何帮助将不胜感激。

Explanation :
I want to reach from 1st element ( i.e. 2) to last element ( i.e. 4) of the array in minimum Jump.
How Jump will be :
1st element is 2. It means I can make upto 2 jumps in array. If I take 1st jump then I can reach 2nd element ( i.e. 3) or if I take 2nd jump then I can reach 3rd element (i.e. 1)
2nd element is 3 ,so I can make maximum 3 jumps. In 1st jump I can reach to 1 , in 2nd jump I can reach to 0 and in 3rd jump I can reach to 4
In this way I want to reach from 1st element to last element of the array in minimum number of jumps.
So output will be like , from 1st element 2, I will jump to 3. Then from 3 I will jump to 4 (last element). So 2 Jumps. ( 2 - 3 - 4 )

#include<iostream>
#include<vector>
#include<climits>
using namespace std;

int jump(int arr[], int n, int start, vector<int> &vec)
{
    if(start == n-1)  // if start is the last element in array
       return 0;

    if( arr[start] == 0)  // if array element is 0 
       return 0;

    vector<int> vec1 = vec;
    vector<int> vec2 = vec;

    int minimum = INT_MAX;
    for( int i = 1 ; i <= arr[start]; i++ )
    {
        vec1.push_back(start);

        int _jump = 1 + jump( arr, n, start+i, vec1); // considering every jump 

        vec = (_jump < minimum) ? vec1 : vec2;

        minimum = min(minimum, _jump);
    }
        return minimum;

}

int main()
{
    int arr[] = { 2, 3, 1, 0, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<int> vec;
    cout << "Number of jumps " << jump(arr, n, 0, vec) << endl;
    cout<<"Sequence is "<<endl;
    for( auto x : vec)
        cout << x <<" ";  
    return 0;
}          

输出

Number of jumps 2      
Sequence is      

预期产量

 Number of jumps 2       
 Sequence is 2 3 4

Answer 1

这是一个示例，它将设置一个 vector ，其中每个索引在访问该索引后将按顺序存储正确的下一步。我留给您使用结果 vector 按照从第一个元素到最后一个序列的顺序进行编码。我还纠正了此条件if( arr[start] == 0)以返回“无穷大”，因为如果访问此元素，则无法完成序列。

#include<iostream>
#include<vector>
#include<climits>
using namespace std;

int jump(int arr[], int n, int start, vector<int> &vec)
{
    if(start == n-1)  // if start is the last element in array
       return 0;

    if( arr[start] == 0)  // if array element is 0 
       return INT_MAX - n;

    int minimum = INT_MAX;
    int step;
    for( int i = 1 ; i <= arr[start]; i++ )
    {
        int _jump = 1 + jump( arr, n, start+i, vec); // considering every jump 

        if (_jump < minimum){
          minimum = _jump;
          step = start + i;
        }
    }

    vec.at(start) = step;

    return minimum;
}

int main()
{
    int arr[] = { 2, 3, 1, 0, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<int> vec(n, -1);
    cout << "Number of jumps " << jump(arr, n, 0, vec) << endl;
    cout<<"Vector: "<<endl;
    for( auto x : vec)
        cout << x <<" ";  
    return 0;
}