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

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數目即為第一行長度的一半

1. /*
2. * File: MidpointFindingKarel.java
3. * -------------------------------
4. * THe MidpointFindingKarel class will leave a beeper on the corner
5. * closest to the center of 1st Street
6. * (or either of the two central corners if 1st Street has an even
7. * number of corners). The world may be of any size, but you are allowed to
8. * assume that it is at least as tall as it is wide.
9. */
10. import stanford.karel.*;
11. public class MidpointFindingKarel extends SuperKarel {
12. public void run() {
13. fillFirstRow();
14. //midpoint finding part
15. while (beepersPresent()) {
16. collectLeftEnd();
18. collectRightEnd();
19. //step forward one more to make sure there is no more beeper
20. if (frontIsClear()) { //check whether all beepers have been collected
21. move(); //if width is odd number Karel will finally arrive (1,1)
22. } //if width is even number, Karel will finally arrive mid-point
23. }
24. //go to the midpoint of the first row, put beeper then collect beepers
25. //on the 2nd row
26. goToMidpoint();
27. putBeeper();
28. collectSecondRow();
29. goToOrigin();
30. moveToBeeper();
31. }
32. /*
33. * fillFirstRow method is defined to fill the 1st row with beepers
34. * Karel will put only one beeper at each corner
35. * precondition: facing east, at (1,1) point
36. * postcondition: facing east, (1,1) point
37. */
38. private void fillFirstRow() {
39. goToOrigin(); //go to (1,1) facing east
40. while (frontIsClear()) {
41. putBeeper();
42. move();
43. }
44. putBeeper(); //Off-By-One-Bug
45. //make sure go back to (1,1) point facing east
46. turnAround();
47. moveToWall();
48. turnAround();
49. }
50. /*
51. * Collect the most left beeper on the 1st row, if there is any
52. * Precondition: any case
53. * Postcondition: facing east, stop at the position where Karel
54. * just collected one beeper, 1st row
55. */
56. private void collectLeftEnd() {
57. goToOrigin();
58. moveToBeeper();
59. if (beepersPresent()) {
60. pickBeeper();
61. }
62. }
63. /*Similar as collectLeftEnd, while in this method, Karel will start
64. from the most right end, and try to collect the beeper at the
65. most right end
66. */
67. private void collectRightEnd() {
68. goToOrigin();
69. moveToWall(); //Reach the right end of the 1st row
70. turnAround(); //To face west
71. moveToBeeper();
72. if (beepersPresent()) {
73. pickBeeper();
74. }
75. }
76. /*
77. * go to 2nd row, add one more beeper
78. * precondition: anywhere at 1st row facing east
79. * postcondition: on 2nd row, at the most end where no more beeper exist
80. */
82. goToOrigin();
83. bigTurnLeft();
84. turnRight();
85. while( beepersPresent()) { //arrive at the end of existing beepers
86. move();
87. }
88. putBeeper();
89. }
90. /*
91. * Make sure Karel will go to the midpoint of the first row
92. * Precondition: any case
93. * Postcondition: arrive at the mid point of the 1st row, facing south
94. */
95. private void goToMidpoint() {
96. goToOrigin();
97. moveToWall(); //reach right end
98. bigTurnLeft();
99. turnLeft();
100. moveToBeeper();
101. bigTurnLeft();
102. }
103. private void collectSecondRow() {
104. goToOrigin();
105. bigTurnLeft(); //facing north
106. turnRight(); //facing east
107. while (beepersPresent() || frontIsBlocked()) {
108. pickBeeper();
109. move();
110. }
111. }
112. /*Move Karel back to origin of map (1,1), make it facing east
113. * Precondition: can be any case
114. * Postcondition: standing on (1,1) facing east
115. */
116. private void goToOrigin() {
117. while (notFacingSouth()) {
118. turnLeft();
119. }
120. moveToWall();
121. while (notFacingWest()) {
122. turnLeft();
123. }
124. moveToWall();
125. while (notFacingEast()) {
126. turnLeft(); //Karel will face east
127. }
128. }
129. /*
130. * move Karel to first beeper on its way
131. * precondition: facing east/west
132. * postcondition: share same orientation as in precondition, standing on
133. * the corner where first beeper appears on its way
134. */
135. private void moveToBeeper() {
136. while ( noBeepersPresent() && frontIsClear() ) {
137. move();
138. }
139. }
140. /*
141. * go to upper/lower row above without changing column number,
142. * make a big turn left
143. * precondition: any case
144. * postcondition: same column, arrive at upper/lower row
145. * which is one above/under the row in precondition,
146. * direction will turn left
147. */
148. private void bigTurnLeft() {
149. turnLeft();
150. move();
151. }
152. // Similar as in bigTurnLeft, but in this case make a big
153. //turn right
154. private void bigTurnRight() {
155. turnRight();
156. move();
157. }
158. private void moveToWall() { //move Karel to wall
159. while (frontIsClear()) {
160. move();
161. }
162. }
163. }// end of public class
2. 對於方法1中的思路進行進一步優化，其實左側取一個右側再取一個完全可以兼併成為從左側出發一次取兩個，同時放一個到第二行，這將大量節省Karel的運動過程，優化後程式碼如下：
1. /*
2. * File: MidpointFindingKarel.java
3. * -------------------------------
4. * THe MidpointFindingKarel class will leave a beeper on the corner
5. * closest to the center of 1st Street
6. * (or either of the two central corners if 1st Street has an even
7. * number of corners). The world may be of any size, but you are allowed to
8. * assume that it is at least as tall as it is wide.
9. */
10. import stanford.karel.*;
11. public class MidpointFindingKarel extends SuperKarel {
12. public void run() {
13. fillFirstRow();
14. //midpoint finding part
15. while (beepersPresent()) {
17. collectLeftEnd();
18. //step forward one more to make sure there is no more beeper
19. if (frontIsClear()) { //check whether all beepers have been collected
20. move(); //if width is odd number Karel will finally arrive (1,1)
21. } //if width is even number, Karel will finally arrive mid-point
22. }
23. //go to the midpoint of the first row, put beeper then collect beepers
24. //on the 2nd row
25. goToMidpoint();
26. putBeeper();
27. collectSecondRow();
28. goToOrigin();
29. moveToBeeper();
30. }
31. /*
32. * fillFirstRow method is defined to fill the 1st row with beepers
33. * Karel will put only one beeper at each corner
34. * precondition: facing east, at (1,1) point
35. * postcondition: facing east, at the most right end of 1st row
36. */
37. private void fillFirstRow() {
38. goToOrigin(); //go to (1,1) facing east
39. while (frontIsClear()) {
40. putBeeper();
41. move();
42. }
43. putBeeper(); //Off-By-One-Bug
44. }
45. /*
46. * Collect the most left beeper on the 1st row, if there is any
47. * Precondition: any case
48. * Postcondition: facing east, stop at the position where Karel
49. * just collected one beeper, 1st row
50. */
51. private void collectLeftEnd() {
52. goToOrigin();
53. moveToBeeper();
54. if ( beepersPresent() ) {
55. pickBeeper();
56. }
57. if ( frontIsClear() ) {
58. move();
59. }
60. if ( beepersPresent() ) {
61. pickBeeper();
62. }
63. }
64. /*
65. * go to 2nd row, add one more beeper
66. * precondition: anywhere at 1st row facing east
67. * postcondition: on 2nd row, at the most end where no more beeper exist
68. */
70. goToOrigin();
71. bigTurnLeft();
72. turnRight();
73. while( beepersPresent()) { //arrive at the end of existing beepers
74. move();
75. }
76. putBeeper();
77. }
78. /*
79. * Make sure Karel will go to the midpoint of the first row
80. * Precondition: any case
81. * Postcondition: arrive at the mid point of the 1st row, facing south
82. */
83. private void goToMidpoint() {
84. goToOrigin();
85. moveToWall(); //reach right end
86. bigTurnLeft();
87. turnLeft();
88. moveToBeeper();
89. bigTurnLeft();
90. }
91. private void collectSecondRow() {
92. goToOrigin();
93. bigTurnLeft(); //facing north
94. turnRight(); //facing east
95. while (beepersPresent() || frontIsBlocked()) {
96. pickBeeper();
97. move();
98. }
99. }
100. /*Move Karel back to origin of map (1,1), make it facing east
101. * Precondition: can be any case
102. * Postcondition: standing on (1,1) facing east
103. */
104. private void goToOrigin() {
105. while (notFacingSouth()) {
106. turnLeft();
107. }
108. moveToWall();
109. while (notFacingWest()) {
110. turnLeft();
111. }
112. moveToWall();
113. while (notFacingEast()) {
114. turnLeft(); //Karel will face east
115. }
116. }
117. /*
118. * move Karel to first beeper on its way
119. * precondition: facing east/west
120. * postcondition: share same orientation as in precondition, standing on
121. * the corner where first beeper appears on its way
122. */
123. private void moveToBeeper() {
124. while ( noBeepersPresent() && frontIsClear() ) {
125. move();
126. }
127. }
128. /*
129. * go to upper/lower row above without changing column number,
130. * make a big turn left
131. * precondition: any case
132. * postcondition: same column, arrive at upper/lower row
133. * which is one above/under the row in precondition,
134. * direction will turn left
135. */
136. private void bigTurnLeft() {
137. turnLeft();
138. move();
139. }
140. private void moveToWall() { //move Karel to wall
141. while (frontIsClear()) {
142. move();
143. }
144. }
145. }// end of public class
3. 對於方法2中的思路進行進一步優化，其實karel完全可以將用於中點位置計數的beeper直接放在第一行，這樣Karel的運動過程將會得到進一步的簡化，換言之，Karel將從（1,1）出發，一次取兩個beeper，然後折回（1,1），放下一個beeper，之後再去取兩個beeper，折回在（1,2）放下一個beeper，以此類推，直至開始時放置的beeper全部取完。具體程式碼如下：
1. /*
2. * File: MidpointFindingKarel.java
3. * -------------------------------
4. * THe MidpointFindingKarel class will leave a beeper on the corner
5. * closest to the center of 1st Street
6. * (or either of the two central corners if 1st Street has an even
7. * number of corners). The world may be of any size, but you are allowed to
8. * assume that it is at least as tall as it is wide.
9. */
10. import stanford.karel.*;
11. public class MidpointFindingKarel extends SuperKarel {
12. public void run() {
13. fillFirstRow();
14. goToOrigin();
15. //midpoint finding part
16. while (beepersPresent()) {
17. collectLeftEnd();
19. move(); //go to blank place without any beeper
20. moveToBeeper();
21. }
22. //go to the midpoint of the first row, put beeper then collect beepers
23. //on the 2nd row
24. goToMidpoint();
25. }
26. /*
27. * fillFirstRow method is defined to fill the 1st row with beepers
28. * Karel will put only one beeper at each corner
29. * precondition: facing east, at (1,1) point
30. * postcondition: facing east, at the most right end of 1st row
31. */
32. private void fillFirstRow() {
33. goToOrigin(); //go to (1,1) facing east
34. while (frontIsClear()) {
35. putBeeper();
36. move();
37. }
38. putBeeper(); //Off-By-One-Bug
39. }
40. /*
41. * Collect the most left beeper on the 1st row, if there is any
42. * Precondition: any case
43. * Postcondition: facing east, stop at the position where Karel
44. * just collected one beeper, 1st row
45. */
46. private void collectLeftEnd() {
47. if ( beepersPresent() ) {
48. pickBeeper();
49. }
50. if ( frontIsClear() ) {
51. move();
52. }
53. if ( beepersPresent() ) {
54. pickBeeper();
55. }
56. }
57. /*
58. * go to 2nd row, add one more beeper
59. * precondition: anywhere at 1st row facing east
60. * postcondition: on 2nd row, at the most end where no more beeper exist
61. */
63. goToOrigin();
64. while( beepersPresent()) { //arrive at the end of existing beepers
65. move();
66. }
67. putBeeper();
68. }
69. /*
70. * Make sure Karel will go to the midpoint of the first row
71. * Precondition: any case
72. * Postcondition: arrive at the mid point of the 1st row, facing west
73. */
74. private void goToMidpoint() {
75. goToOrigin();
76. while ( beepersPresent() ) {
77. pickBeeper();
78. move();
79. }
80. turnAround(); //OBOB, Karel will move one more step
81. move(); //at the end of this part
82. putBeeper();
83. }
84. /*Move Karel back to origin of map (1,1), make it facing east
85. * Precondition: can be any case
86. * Postcondition: standing on (1,1) facing east
87. */
88. private void goToOrigin() {
89. while (notFacingSouth()) {
90. turnLeft();
91. }
92. moveToWall();
93. while (notFacingWest()) {
94. turnLeft();
95. }
96. moveToWall();
97. while (notFacingEast()) {
98. turnLeft(); //Karel will face east
99. }
100. }
101. /*
102. * move Karel to first beeper on its way
103. * precondition: facing east/west
104. * postcondition: share same orientation as in precondition, standing on
105. * the corner where first beeper appears on its way
106. */
107. private void moveToBeeper() {
108. while ( noBeepersPresent() && frontIsClear() ) {
109. move();
110. }
111. }
112. /*
113. * go to upper/lower row above without changing column number,
114. * make a big turn left
115. * precondition: any case
116. * postcondition: same column, arrive at upper/lower row
117. * which is one above/under the row in precondition,
118. * direction will turn left
119. */
120. private void bigTurnLeft() {
121. turnLeft();
122. move();
123. }
124. private void moveToWall() { //move Karel to wall
125. while (frontIsClear()) {
126. move();
127. }
128. }
129. }// end of public class
4. 對於方案1還有另一種優化的思路，那就是擺脫計數器的限制，左右各取出一個，一直這樣取下去，直至取完，那麼Karel此時必然自然位於中點位置從而無需計數，其運動過程將更為簡單快捷。程式設計的要點在於要保證Karel始終執行往復運動直至beeper被全部取盡，程式碼如下：
1. /*
2. * File: MidpointFindingKarel.java
3. * -------------------------------
4. * THe MidpointFindingKarel class will leave a beeper on the corner
5. * closest to the center of 1st Street
6. * (or either of the two central corners if 1st Street has an even
7. * number of corners). The world may be of any size, but you are allowed to
8. * assume that it is at least as tall as it is wide.
9. */
10. import stanford.karel.*;
11. public class MidpointFindingKarel extends SuperKarel {
12. public void run() {
13. fillFirstRow();
14. goToOrigin();
15. //midpoint finding part
16. while (beepersPresent()) {
17. pickBeeper();
18. move();
19. moveToEnd();
20. }
21. putBeeper();
22. }
23. /*
24. * fillFirstRow method is defined to fill the 1st row with beepers
25. * Karel will put only one beeper at each corner
26. * precondition: facing east, at (1,1) point
27. * postcondition: facing east, at the end of 1st row
28. */
29. private void fillFirstRow() {
30. goToOrigin(); //go to (1,1) facing east
31. while (frontIsClear()) {
32. putBeeper();
33. move();
34. }
35. putBeeper(); //Off-By-One-Bug
36. }
37. /*
38. * Karel will move to the last beeper of the beeper chain
39. * Precondition: standing at one end facing that chain
40. * Postcondition: standing at another end facing that chain
41. * which means the orientation is changed oppositely
42. */
43. private void moveToEnd() {
44. while ( beepersPresent() && frontIsClear() ) {
45. move();
46. }
47. if ( frontIsBlocked() && beepersPresent() ) { //for the case arrive at the wall
48. turnAround();
49. } else {
50. turnAround();
51. move();
52. }
53. }
54. /*Move Karel back to origin of map (1,1), make it facing east
55. * Precondition: can be any case
56. * Postcondition: standing on (1,1) facing east
57. */
58. private void goToOrigin() {
59. while (notFacingSouth()) {
60. turnLeft();
61. }
62. moveToWall();
63. while (notFacingWest()) {
64. turnLeft();
65. }
66. moveToWall();
67. while (notFacingEast()) {
68. turnLeft(); //Karel will face east
69. }
70. }
71. private void moveToWall() { //move Karel to wall
72. while (frontIsClear()) {
73. move();
74. }
75. }
76. }// end of public class