關於Karel迷宮問題的討論

關於Karel迷宮問題的討論
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

在如上圖所示的迷宮中,Karel需要從(1,1)出發前往右上方撿拾beeper,用stanford的Karel外掛在eclipse中解決這一問題
程式設計思路:
能向右轉時向右轉,在每一次移動時總是優先考慮向右行動的可能性
程式碼1:在大迴圈裡只要Karel沒有找到beeper,它將一直移動,如果右邊是clear的,則右轉前進,否則左轉零次,一次到兩次直至前方clear後再前進。
在這個if判斷裡,如果右側是clear沒有問題,如果右側有遮擋,此時優先考慮繼續沿原方向前進,再次考慮左轉再前進,再次考慮退回去,優先順序不可顛倒,否則會陷入來回走動的死迴圈。若顛倒則優先順序為優先原方向,再次右轉,再次退回去。而此時已知右側有遮擋,則其實只有兩個選擇,繼續前進和退回去,若另外一側也是相同情況則進入死迴圈。
綜上,我們可以知道,在else分支裡應該使用turnLeft而不是turnRight
  1. import stanford.karel.*;
  2. public class mazeSolverKarel extends SuperKarel {
  3. public void run() {
  4. while (noBeepersPresent()) {
  5. if (rightIsClear()) {
  6. turnRight();
  7. move();
  8. }else {
  9. while (frontIsBlocked()) {
  10. turnLeft();
  11. }
  12.                move();
  13. }
  14. }
  15. }
  16. }
程式碼2:觀察程式碼1,我們可以發現在if和else分支裡均共享了move(); 為精簡語句我們可以將move()語句提取出來,從而獲得程式碼2
  1. import stanford.karel.*;
  2. public class mazeSolverKarel extends SuperKarel {
  3. public void run() {
  4. while (noBeepersPresent()) {
  5. if (rightIsClear()) {
  6. turnRight();
  7. }else {
  8. while (frontIsBlocked()) {
  9. turnLeft();
  10. }
  11. }
  12. move();
  13. }
  14. }
  15. }
程式碼3:觀察程式碼2,我們可以發現if和while(frontIsBlocked)均含有類似的判斷,換句話說在程式碼2中,if分支裡我們先判斷了右側是clear然後執行了右轉,在else分支中,我們已知右側不可通行試圖尋找非右側的通路,也就是說這裡的if和while功能上有重複性,因此我們可以進一步簡化程式碼為程式碼3.
在程式碼3中,直接讓Karel右轉,如果可以通行那麼不進入while迴圈找其他路,如果不可以那麼右側一定被block了,frontIsClear可以給出反饋,則進入while迴圈,先左轉返回原方向以試探原方向,原路不可行再左轉試探左側,依然不可行則沿原方向的反方向退出此處。如此一來,while迴圈就實現了if分支的作用。
從程式碼功能上看,程式碼2可以讓Karel在直通路(如圖中迷宮的最左側道路)上少做轉向操作但是程式內多了分支判斷,程式碼3更為精煉但是在直通路上Karel會有多餘的轉向操作,從而影響到達時間。
  1. import stanford.karel.*;
  2. public class mazeSolverKarel extends SuperKarel {
  3. public void run() {
  4. while (noBeepersPresent()) {
  5. turnRight();
  6. while (frontIsBlocked()) {
  7. turnLeft();
  8. }
  9. move();
  10. }
  11. }
  12. }
總結:程式碼1,2,3之間的邏輯關係很明確,從實用性和可讀性上推薦程式碼1,但是就思想性程式碼3遠勝程式碼1.

相關文章

程式語言 最新文章