遞歸難題C++代碼

Question

遞歸難題您已給出由含有一個整數時，每個正方形的一排的一個難題，這樣

初始正方形的圓是能夠沿着移動到其他的正方形標記該行。在拼圖的每個步驟中，您可以將標記移動到當前佔據的平方中由整數指示的平方數。標記可能沿着該行向左或向右移動，但可能不會移過任何一端。例如，唯一合法的第一步是將標記向右移動三個方格，因爲沒有空間向左移動三個空格。謎題的目標是將標記移動到行的最遠端的0處。在這種配置中，你可以通過下面的一組動作解謎：

https://i.stack.imgur.com/yUz3P.png

一個。寫一個算法void SolvePuzzle（int start，int squares [1..n]），它將標記的起始位置和正方形數組一起使用。該算法應該解決起始配置中的難題，並顯示在序列結尾達到0所需的所有移動。你可以假設數組中的所有整數都是正數，除了最後一個條目，即目標方格，它總是爲零。數組中的元素的值必須是調用你的函數，因爲它們是事先經過相同的，（這是，如果你在處理過程中改變他們說，你需要改變他們回來！）

void SolvePuzzle(int start, int squares[]){ 

if(squares[start]==0) 
return; 
else{ 
    cout<<squares[start]<<" "; 
if(squares[start]%2==0) 
SolvePuzzle(start+squares[start],squares); 
else 
SolvePuzzle(start-squares[start],squares); 
} 


} 


int main(){ 
    int arraytest[] = { 3, 6, 4, 1, 3, 4, 2, 5, 3, 0 }; 
SolvePuzzle(arraytest[0],arraytest); 

    return 0; 
} 

我解決像這樣但我需要If語句中的正確錯誤

Answer 1

即使從描述中無法真正瞭解，您所面臨的問題是您並不知道是否必須向左或向右移動來解決難題。

最簡單的方法就是試着向左走，如果它起作用，你解決它，否則你走對了。這意味着你必須改變你的功能，否則你不能真正返回正確的道路或答案。

它可能會出現這樣的：

#include <vector> 
#include <iostream> 

bool SolvePuzzle(int squares[], int size, int position, 
       std::vector<bool>& go_right_sol){ 
    if(squares[position]==0){ 
     return true; 
    } 
    int leftPos = position - squares[position]; 
    int rightPos = position + squares[position]; 
    if(rightPos < size && SolvePuzzle(squares, size, rightPos, go_right_sol)){ 
     go_right_sol.insert(go_right_sol.begin(), true); 
     return true; 
    } 
    if(leftPos > 0 && SolvePuzzle(squares, size, leftPos, go_right_sol)){ 
     go_right_sol.insert(go_right_sol.begin(), false); 
     return true; 
    } 
    return false; 

} 


int main(){ 
    int arraytest[] = { 3, 6, 4, 1, 3, 4, 2, 5, 3, 0 }; 
    int arraysize = 10; 
    std::vector<bool> solution; 
    SolvePuzzle(arraytest, arraysize, 0, solution); 
    for(int i = 0; i < solution.size(); i++){ 
     std::cout << ((solution[i]) ? "right" : "left") << " - "; 
    } 
    std::cout << std::endl; 
    return 0; 
}