基本遞歸回溯（機器人2D尋路）

我工作的一個實踐問題，被卡住。該問題要求編寫一個方法，該方法通過重複使用三個移動中的一個來在兩個整數x和y中打印用於在2D平面中行進的所有解（0,0）到（x，y）：基本遞歸回溯（機器人2D尋路）

向右移動1（E）
拉昇1（N）
向右移動1和高達1（NE）

以下是一些例子電話：

電話：旅遊（ 2，1）
輸出：EEN // // ENE該NE // // NEE NEË

我寫以下代碼：

public void travel(int x, int y) { 
    if (x == 0 && y == 0) { 
     System.out.println(); 
    } else if (x > 0 && y > 0) { 
     System.out.print("E "); 
     travel(x-1, y); 
     System.out.print("N "); 
     travel(x, y-1); 
     System.out.print("NE "); 
     travel(x-1, y-1); 
    } else if (x > 0 && y == 0) { 
     System.out.print("E "); 
     travel(x-1, y); 
    } else if (y > 0 && x == 0) { 
     System.out.print("N "); 
     travel(x, y-1); 
    } 
}

調用在上述方法的結果以下代碼：

call：travel（2,1）;
輸出：EEN // // NE NE // //東東NEË

我知道，在這個例子中所說的問題在於與E爲需要Ë因爲三種不同的情況纔剛剛打印過一次在隨後的遞歸方法被調用之前，E被打印出來。

我想解決這個（不確定性，這是正確的方法）通過與行進方法的每個調用附接是System.out.print命令。這種方式每當調用旅行方法時，結果每次都以第一個字母打印。但是，由於該方法不返回任何內容，因此我無法在print語句中插入該方法。這是我長期堅持的地方。

如何從這裏走任何意見，將不勝感激。

來源

2013-06-24 jeebface

嗯;你知道，平板筆式繪圖儀曾經有這個問題 - 你如何找到將筆從A點移動到B點的最佳解決方案？我似乎記得有一次關於這個主題的論文。 –

當遞歸構建的解決方案，這是常見的通過部分構建的解決方案作爲參數傳遞給遞歸調用。

public void travel(int x, int y, String path) { 
    if (x == 0 && y == 0) { 
     System.out.println(path); 
    } else if (x > 0 && y > 0) { 
     travel(x-1, y, path + ' E'); 
     travel(x, y-1, path + ' N'); 
     travel(x-1, y-1, path + ' NE'); 
    } else if (x > 0 && y == 0) { 
     travel(x-1, y, path + ' E'); 
    } else if (y > 0 && x == 0) { 
     travel(x, y-1, path + ' N'); 
    } 
}

看看我們如何構建路徑，因爲我們走 - 讓函數調用處理我們在搜索中，記憶的複雜性？這也有簡化我們的代碼的很好的特性，因爲我們得到一個準確調用System.out.println每個路徑。

來源

2013-06-24 19:24:59

基本遞歸回溯（機器人2D尋路）

回答

相關問題