Stanford程式設計方法學公開課作業 1 ----關于Karel 中點尋找問題的讨論（Midpoint finding）

問題描述：Karel需要尋找到第一行的中點位置，并在那裡放下一個beeper，具體描述請參考英文原文

Problem 3

As an exercise in solving algorithmic problems, program Karel to place a single beeper at the center of 1st Street. For example, if Karel starts in the world

it should end with Karel standing on a beeper in the following position:

Note that the final configuration of the world should have only a single beeper at the midpoint of 1st Street. Along the way, Karel is allowed to place additional beepers wherever it wants to, but must pick them all up again before it finishes.

In solving this problem, you may count on the following facts about the world:

Karel starts at 1st Avenue and 1st Street, facing east, with an infinite number of beepers in its bag.
The initial state of the world includes no interior walls or beepers.
The world need not be square, but you may assume that it is at least as tall as it is wide.

Your program, moreover, can assume the following simplifications:

If the width of the world is odd, Karel must put the beeper in the center square. If the width is even, Karel may drop the beeper on either of the two center squares.
It does not matter which direction Karel is facing at the end of the run.

There are many different algorithms you can use to solve this problem. The interesting part of this assignment is to come up with a strategy that works.

解決思路：（可以提出以下四種解題思路）

1. 先将第一行填滿，然後左右各取出一個，并在第二行放下一個，當第一行beeper取完的時候，第二行的beeper數目即為第一行長度的一半代碼如下：

  /*            
       * File: MidpointFindingKarel.java            
       * -------------------------------            
       * THe MidpointFindingKarel class will leave a beeper on the corner             
       * closest to the center of 1st Street            
       * (or either of the two central corners if 1st Street has an even            
       * number of corners).  The world may be of any size, but you are allowed to            
       * assume that it is at least as tall as it is wide.            
       */            
        
       import stanford.karel.*;            
        
       public class MidpointFindingKarel extends SuperKarel {            
        
       public void run() {            
       fillFirstRow();		            
       //midpoint finding part            
       while (beepersPresent()) {            
       collectLeftEnd();            
       secondRowAddOne();            
       collectRightEnd();	            
        
       //step forward one more to make sure there is no more beeper            
       if (frontIsClear()) { //check whether all beepers have been collected            
       move(); //if width is odd number Karel will finally arrive (1,1)            
       } //if width is even number, Karel will finally arrive mid-point            
       }            
        
       //go to the midpoint of the first row, put beeper then collect beepers            
       //on the 2nd row            
       goToMidpoint();            
       putBeeper();            
       collectSecondRow();	            
       goToOrigin();            
       moveToBeeper();            
       }            
        
       /*            
       * fillFirstRow method is defined to fill the 1st row with beepers            
       * Karel will put only one beeper at each corner            
       * precondition: facing east, at (1,1) point            
       * postcondition: facing east, (1,1) point            
       */            
       private void fillFirstRow() {            
       goToOrigin(); //go to (1,1) facing east            
       while (frontIsClear()) {            
       putBeeper();            
       move();            
       }            
       putBeeper(); //Off-By-One-Bug            
       //make sure go back to (1,1) point facing east            
       turnAround();            
       moveToWall();            
       turnAround();            
       }            
        
        
       /*            
       * Collect the most left beeper on the 1st row, if there is any            
       * Precondition: any case            
       * Postcondition: facing east, stop at the position where Karel             
       * just collected one beeper, 1st row            
       */            
       private void collectLeftEnd() {            
       goToOrigin();            
       moveToBeeper();            
       if (beepersPresent()) {            
       pickBeeper();            
       }		            
       }            
        
       /*Similar as collectLeftEnd, while in this method, Karel will start            
       from the most right end, and try to collect the beeper at the             
       most right end            
       */            
       private void collectRightEnd() {            
       goToOrigin();            
       moveToWall(); //Reach the right end of the 1st row            
       turnAround(); //To face west            
       moveToBeeper();            
       if (beepersPresent()) {            
       pickBeeper();            
       }            
       }            
        
       /*            
       * go to 2nd row, add one more beeper            
       * precondition: anywhere at 1st row facing east            
       * postcondition: on 2nd row, at the most end where no more beeper exist            
       */            
       private void secondRowAddOne() {            
       goToOrigin();            
       bigTurnLeft();            
       turnRight();            
       while( beepersPresent()) { //arrive at the end of existing beepers            
       move();            
       }            
       putBeeper();            
       }            
        
        
       /*            
       * Make sure Karel will go to the midpoint of the first row            
       * Precondition: any case            
       * Postcondition: arrive at the mid point of the 1st row, facing south            
       */            
       private void goToMidpoint() {            
       goToOrigin();            
       moveToWall(); //reach right end             
       bigTurnLeft();            
       turnLeft();            
       moveToBeeper();            
       bigTurnLeft();		            
       }            
        
       private void collectSecondRow() {            
       goToOrigin();            
       bigTurnLeft(); //facing north            
       turnRight(); //facing east            
       while (beepersPresent() || frontIsBlocked()) {            
       pickBeeper();            
       move();            
       }            
       }            
        
       /*Move Karel back to origin of map (1,1), make it facing east            
       * Precondition: can be any case            
       * Postcondition: standing on (1,1) facing east            
       */            
       private void goToOrigin() {             
       while (notFacingSouth()) {            
       turnLeft();            
       }            
       moveToWall();            
       while (notFacingWest()) {            
       turnLeft();            
       }            
       moveToWall();            
       while (notFacingEast()) {            
       turnLeft(); //Karel will face east            
       }            
       }            
        
        
       /*            
       * move Karel to first beeper on its way            
       * precondition: facing east/west            
       * postcondition: share same orientation as in precondition, standing on             
       * the corner where first beeper appears on its way            
       */            
       private void moveToBeeper() {             
       while ( noBeepersPresent() && frontIsClear() ) {            
       move();            
       }            
       }            
        
       /*            
       * go to upper/lower row above without changing column number,             
       * make a big turn left            
       * precondition: any case            
       * postcondition: same column, arrive at upper/lower row             
       * which is one above/under the row in precondition,             
       * direction will turn left            
       */            
       private void bigTurnLeft() {            
       turnLeft();            
       move();             
       }            
        
       // Similar as in bigTurnLeft, but in this case make a big            
       //turn right            
       private void bigTurnRight() {            
       turnRight();            
       move();             
       }            
        
       private void moveToWall() { //move Karel to wall            
       while (frontIsClear()) {            
       move();            
       }            
       }            
        
       }// end of public class

2. 對于方法1中的思路進行進一步優化，其實左側取一個右側再取一個完全可以兼并成為從左側出發一次取兩個，同時放一個到第二行，這将大量節省Karel的運動過程，優化後代碼如下：

  /*            
       * File: MidpointFindingKarel.java            
       * -------------------------------            
       * THe MidpointFindingKarel class will leave a beeper on the corner             
       * closest to the center of 1st Street            
       * (or either of the two central corners if 1st Street has an even            
       * number of corners).  The world may be of any size, but you are allowed to            
       * assume that it is at least as tall as it is wide.            
       */            
        
       import stanford.karel.*;            
        
       public class MidpointFindingKarel extends SuperKarel {            
        
       public void run() {            
       fillFirstRow();		            
       //midpoint finding part            
       while (beepersPresent()) {            
       secondRowAddOne();            
       collectLeftEnd();            
       //step forward one more to make sure there is no more beeper            
       if (frontIsClear()) { //check whether all beepers have been collected            
       move(); //if width is odd number Karel will finally arrive (1,1)            
       } //if width is even number, Karel will finally arrive mid-point            
        
       }            
        
       //go to the midpoint of the first row, put beeper then collect beepers            
       //on the 2nd row            
       goToMidpoint();            
       putBeeper();            
       collectSecondRow();	            
       goToOrigin();            
       moveToBeeper();            
       }            
        
       /*            
       * fillFirstRow method is defined to fill the 1st row with beepers            
       * Karel will put only one beeper at each corner            
       * precondition: facing east, at (1,1) point            
       * postcondition: facing east, at the most right end of 1st row            
       */            
       private void fillFirstRow() {            
       goToOrigin(); //go to (1,1) facing east            
       while (frontIsClear()) {            
       putBeeper();            
       move();            
       }            
       putBeeper(); //Off-By-One-Bug            
       }            
        
        
       /*            
       * Collect the most left beeper on the 1st row, if there is any            
       * Precondition: any case            
       * Postcondition: facing east, stop at the position where Karel             
       * just collected one beeper, 1st row            
       */            
       private void collectLeftEnd() {            
       goToOrigin();            
       moveToBeeper();            
       if ( beepersPresent() ) {            
       pickBeeper();            
       }            
       if ( frontIsClear() ) {            
       move();            
       }            
       if ( beepersPresent() ) {            
       pickBeeper();            
       }            
       }            
        
        
       /*            
       * go to 2nd row, add one more beeper            
       * precondition: anywhere at 1st row facing east            
       * postcondition: on 2nd row, at the most end where no more beeper exist            
       */            
       private void secondRowAddOne() {            
       goToOrigin();            
       bigTurnLeft();            
       turnRight();            
       while( beepersPresent()) { //arrive at the end of existing beepers            
       move();            
       }            
       putBeeper();            
       }            
        
       /*            
       * Make sure Karel will go to the midpoint of the first row            
       * Precondition: any case            
       * Postcondition: arrive at the mid point of the 1st row, facing south            
       */            
       private void goToMidpoint() {            
       goToOrigin();            
       moveToWall(); //reach right end             
       bigTurnLeft();            
       turnLeft();            
       moveToBeeper();            
       bigTurnLeft();		            
       }            
        
       private void collectSecondRow() {            
       goToOrigin();            
       bigTurnLeft(); //facing north            
       turnRight(); //facing east            
       while (beepersPresent() || frontIsBlocked()) {            
       pickBeeper();            
       move();            
       }            
       }            
        
       /*Move Karel back to origin of map (1,1), make it facing east            
       * Precondition: can be any case            
       * Postcondition: standing on (1,1) facing east            
       */            
       private void goToOrigin() {             
       while (notFacingSouth()) {            
       turnLeft();            
       }            
       moveToWall();            
       while (notFacingWest()) {            
       turnLeft();            
       }            
       moveToWall();            
       while (notFacingEast()) {            
       turnLeft(); //Karel will face east            
       }            
       }            
        
        
       /*            
       * move Karel to first beeper on its way            
       * precondition: facing east/west            
       * postcondition: share same orientation as in precondition, standing on             
       * the corner where first beeper appears on its way            
       */            
       private void moveToBeeper() {             
       while ( noBeepersPresent() && frontIsClear() ) {            
       move();            
       }            
       }            
        
       /*            
       * go to upper/lower row above without changing column number,             
       * make a big turn left            
       * precondition: any case            
       * postcondition: same column, arrive at upper/lower row             
       * which is one above/under the row in precondition,             
       * direction will turn left            
       */            
       private void bigTurnLeft() {            
       turnLeft();            
       move();             
       }            
        
       private void moveToWall() { //move Karel to wall            
       while (frontIsClear()) {            
       move();            
       }            
       }            
        
       }// end of public class

3. 對于方法2中的思路進行進一步優化，其實karel完全可以将用于中點位置計數的beeper直接放在第一行，這樣Karel的運動過程将會得到進一步的簡化，換言之，Karel将從（1,1）出發，一次取兩個beeper，然後折回（1,1），放下一個beeper，之後再去取兩個beeper，折回在（1,2）放下一個beeper，以此類推，直至開始時放置的beeper全部取完。具體代碼如下：

  /*            
       * File: MidpointFindingKarel.java            
       * -------------------------------            
       * THe MidpointFindingKarel class will leave a beeper on the corner             
       * closest to the center of 1st Street            
       * (or either of the two central corners if 1st Street has an even            
       * number of corners).  The world may be of any size, but you are allowed to            
       * assume that it is at least as tall as it is wide.            
       */            
        
       import stanford.karel.*;            
        
       public class MidpointFindingKarel extends SuperKarel {            
        
       public void run() {            
       fillFirstRow();	            
       goToOrigin();            
       //midpoint finding part            
       while (beepersPresent()) {            
       collectLeftEnd();            
       firstRowAddOne();            
       move(); //go to blank place without any beeper            
       moveToBeeper();            
       }            
        
       //go to the midpoint of the first row, put beeper then collect beepers            
       //on the 2nd row            
       goToMidpoint();            
       }            
        
       /*            
       * fillFirstRow method is defined to fill the 1st row with beepers            
       * Karel will put only one beeper at each corner            
       * precondition: facing east, at (1,1) point            
       * postcondition: facing east, at the most right end of 1st row            
       */            
       private void fillFirstRow() {            
       goToOrigin(); //go to (1,1) facing east            
       while (frontIsClear()) {            
       putBeeper();            
       move();            
       }            
       putBeeper(); //Off-By-One-Bug            
       }            
        
        
       /*            
       * Collect the most left beeper on the 1st row, if there is any            
       * Precondition: any case            
       * Postcondition: facing east, stop at the position where Karel             
       * just collected one beeper, 1st row            
       */            
       private void collectLeftEnd() {            
       if ( beepersPresent() ) {            
       pickBeeper();            
       }            
       if ( frontIsClear() ) {            
       move();            
       }            
       if ( beepersPresent() ) {            
       pickBeeper();            
       }            
       }            
        
        
       /*            
       * go to 2nd row, add one more beeper            
       * precondition: anywhere at 1st row facing east            
       * postcondition: on 2nd row, at the most end where no more beeper exist            
       */            
       private void firstRowAddOne() {            
       goToOrigin();            
       while( beepersPresent()) { //arrive at the end of existing beepers            
       move();            
       }            
       putBeeper();            
       }            
        
       /*            
       * Make sure Karel will go to the midpoint of the first row            
       * Precondition: any case            
       * Postcondition: arrive at the mid point of the 1st row, facing west            
       */            
       private void goToMidpoint() {            
       goToOrigin();            
       while ( beepersPresent() ) {			            
       pickBeeper();            
       move();            
       }             
       turnAround(); //OBOB, Karel will move one more step             
       move(); //at the end of this part            
       putBeeper();            
       }            
        
       /*Move Karel back to origin of map (1,1), make it facing east            
       * Precondition: can be any case            
       * Postcondition: standing on (1,1) facing east            
       */            
       private void goToOrigin() {             
       while (notFacingSouth()) {            
       turnLeft();            
       }            
       moveToWall();            
       while (notFacingWest()) {            
       turnLeft();            
       }            
       moveToWall();            
       while (notFacingEast()) {            
       turnLeft(); //Karel will face east            
       }            
       }            
        
        
       /*            
       * move Karel to first beeper on its way            
       * precondition: facing east/west            
       * postcondition: share same orientation as in precondition, standing on             
       * the corner where first beeper appears on its way            
       */            
       private void moveToBeeper() {             
       while ( noBeepersPresent() && frontIsClear() ) {            
       move();            
       }            
       }            
        
       /*            
       * go to upper/lower row above without changing column number,             
       * make a big turn left            
       * precondition: any case            
       * postcondition: same column, arrive at upper/lower row             
       * which is one above/under the row in precondition,             
       * direction will turn left            
       */            
       private void bigTurnLeft() {            
       turnLeft();            
       move();             
       }            
        
       private void moveToWall() { //move Karel to wall            
       while (frontIsClear()) {            
       move();            
       }            
       }            
        
       }// end of public class

4. 對于方案1還有另一種優化的思路，那就是擺脫計數器的限制，左右各取出一個，一直這樣取下去，直至取完，那麼Karel此時必然自然位于中點位置進而無需計數，其運動過程将更為簡單快捷。程式設計的要點在于要保證Karel始終執行往複運動直至beeper被全部取盡，代碼如下：

  /*            
       * File: MidpointFindingKarel.java            
       * -------------------------------            
       * THe MidpointFindingKarel class will leave a beeper on the corner             
       * closest to the center of 1st Street            
       * (or either of the two central corners if 1st Street has an even            
       * number of corners).  The world may be of any size, but you are allowed to            
       * assume that it is at least as tall as it is wide.            
       */            
       import stanford.karel.*;            
        
       public class MidpointFindingKarel extends SuperKarel {            
       public void run() {            
       fillFirstRow();	            
       goToOrigin();            
       //midpoint finding part            
       while (beepersPresent()) {		            
       pickBeeper();						            
       move();            
       moveToEnd();					            
       }		            
       putBeeper();            
       }            
        
       /*            
       * fillFirstRow method is defined to fill the 1st row with beepers            
       * Karel will put only one beeper at each corner            
       * precondition: facing east, at (1,1) point            
       * postcondition: facing east, at the end of 1st row            
       */            
       private void fillFirstRow() {            
       goToOrigin(); //go to (1,1) facing east            
       while (frontIsClear()) {            
       putBeeper();            
       move();            
       }            
       putBeeper(); //Off-By-One-Bug            
       }            
        
       /*            
       * Karel will move to the last beeper of the beeper chain            
       * Precondition: standing at one end facing that chain            
       * Postcondition: standing at another end facing that chain             
       * which means the orientation is changed oppositely             
       */            
       private void moveToEnd() {		            
       while ( beepersPresent() && frontIsClear() ) {            
       move();            
       }            
       if ( frontIsBlocked() && beepersPresent() ) { //for the case arrive at the wall            
       turnAround();            
       } else {            
       turnAround();            
       move();            
       }            
        
       }            
        
       /*Move Karel back to origin of map (1,1), make it facing east            
       * Precondition: can be any case            
       * Postcondition: standing on (1,1) facing east            
       */            
       private void goToOrigin() {             
       while (notFacingSouth()) {            
       turnLeft();            
       }            
       moveToWall();            
       while (notFacingWest()) {            
       turnLeft();            
       }            
       moveToWall();            
       while (notFacingEast()) {            
       turnLeft(); //Karel will face east            
       }            
       }            
        
       private void moveToWall() { //move Karel to wall            
       while (frontIsClear()) {            
       move();            
       }            
       }            
        
       }// end of public class

讨論：從思想性上，方案4遠優于其他方案，而且實作過程簡潔漂亮；但就擴充簡易性而言不如方案2、3，方案2，3稍作修改就可以實作在1/3，1/4... 處放置一個beeper，而方案4的擴充性相對而言不是特别明顯（以1/3為例，需要左側取一個，右側取兩個）

Stanford程式設計方法學公開課作業 1 ----關于Karel 中點尋找問題的讨論（Midpoint finding）

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

Stanford程式設計方法學公開課作業 1 ----關于Karel 中點尋找問題的讨論 （Midpoint finding）

繼續閱讀

Stanford程式設計方法學公開課作業 1 ----關于Karel 中點尋找問題的讨論（Midpoint finding）