算法-猴子搬香蕉

2018年01月28日 19:59:15

阅读数：220

问题描述:  

 

 一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉。它每走1米就要吃掉一根，请问它最多能把多少根香蕉搬到家里呢？

 提示：他可以把香蕉放下往返的走，但是必须保证它每走一米都能有香蕉吃。也可以走到n米时，放下一些香蕉，拿着n根香蕉走回去重新搬50根。

 

程序实现：

 

接口：

 

1.  
   public interface MonkeysMoveBananas {
2.  
    
3.  
   /**
4.  
   *
5.  
   * @param num 总数量 如100
6.  
   * @param maxNum 每次最多搬多少个 如50个
7.  
   * @param distance 距离 如50
8.  
   * @param eatNum 每走一米吃的数量, 如1个
9.  
   *
10.  
    * @return 到家剩余的数量，或者无法再搬香蕉时剩余的数量
11.  
    *
12.  
    */
13.  
    int Move(int num, int maxNum, int distance, int eatNum);
14.  
    }

 

实现类：

 

1.  
   /**
2.  
   * @category 猴子搬香蕉问题
3.  
   * @author song
4.  
   */
5.  
   public class MonkeysMoveBananasImpl implements MonkeysMoveBananas {
6.  
    
7.  
   /**
8.  
   *
9.  
   * @param num 总数量 如100
10.  
    * @param maxNum 每次最多搬多少个 如50个
11.  
    * @param distance 距离 如50
12.  
    * @param eatNum 每走一米吃的数量, 如1个
13.  
    *
14.  
    * @return 到家剩余的数量，或者无法再搬香蕉时剩余的数量
15.  
    *
16.  
    */
17.  
    @Override
18.  
    public int Move(int num, int maxNum, int distance, int eatNum) {
19.  
     
20.  
    /* 已经搬到的位置, 即搬了几米 */
21.  
    int location = 0;
22.  
     
23.  
    /* 每次搬运起始点剩的数量 */
24.  
    int CurrentNumberS = num;
25.  
     
26.  
    /* 每次搬运终点剩的数量 */
27.  
    int CurrentNumberE = 0;
28.  
     
29.  
    /* 外层循环一次, 即把所有剩余香蕉移动一个位置 */
30.  
    while(location < distance && CurrentNumberS > eatNum) {
31.  
    System.out.println(

    "当前所在位置" + location + "有" + CurrentNumberS + "个香蕉");
32.  
     
33.  
    /* 内层循环一次， 即把剩余香蕉移动一个位置， 是移动一个位置的具体细节 */
34.  
    while (true) {
35.  
     
36.  
    if(CurrentNumberS > maxNum) {
37.  
    MoveOnePosition(location, location+

    1, maxNum, eatNum);
38.  
    CurrentNumberS -= maxNum;
39.  
    CurrentNumberE += maxNum -eatNum;
40.  
    }

    else {
41.  
    MoveOnePosition(location, location+

    1, CurrentNumberS, eatNum);
42.  
    CurrentNumberE += CurrentNumberS - eatNum;
43.  
    CurrentNumberS =

    0;
44.  
    }
45.  
     
46.  
    /* 看需不需要搬起点剩下的, 即需不需要返回 */
47.  
    if(CurrentNumberS >= eatNum * 2) {
48.  
    MoveOnePosition(location+

    1, location, -1, eatNum);
49.  
    CurrentNumberE -= eatNum;
50.  
    }

    else {
51.  
    break;
52.  
    }
53.  
    }
54.  
     
55.  
    CurrentNumberS = CurrentNumberE;
56.  
    CurrentNumberE =

    0;
57.  
    location ++;
58.  
    }
59.  
     
60.  
    System.out.println(

    "剩余" + CurrentNumberS + "个");
61.  
    return CurrentNumberS;
62.  
    }
63.  
     
64.  
    /**
65.  
    *
66.  
    * @param from 起始位置
67.  
    * @param to 目标位置
68.  
    * @param number 搬的数量
69.  
    * @param eatNum 搬一米吃的数量
70.  
    */
71.  
    private void MoveOnePosition(int from, int to, int number, int eatNum) {
72.  
    if(number != -1) {
73.  
    System.out.println(

    "从 " + from + " 位置搬 "+ number + " 个到 " + to + " 位置, 消耗" + eatNum + "个");
74.  
    }

    else {
75.  
    System.out.println(

    "从 " + from + " 位置回到 " + to + " 位置, 消耗 " + eatNum + "个");
76.  
    }
77.  
    }
78.  
    }

 

测试类：

 

1.  
   public class MonkeysMoveBananasTest {
2.  
    
3.  
   private static MonkeysMoveBananas monkeysMoveBananas = null;
4.  
    
5.  
   @BeforeClass
6.  
   public static void setUpBeforeClass() throws Exception {
7.  
   monkeysMoveBananas =

   new MonkeysMoveBananasImpl();
8.  
   }
9.  
    
10.  
    @Test
11.  
    public void moveTest() {
12.  
    int k = monkeysMoveBananas.Move(100, 50, 50, 1);
13.  
    assertEquals(k,

    16);
14.  
     
15.  
    k = monkeysMoveBananas.Move(

    1000, 50, 50, 2);
16.  
    assertEquals(k,

    20);
17.  
    }
18.  
    }

19.