喝汽水问题的两种算法实现

我顺便记录了一下循环执行的次数。

可能明显看到，第二种办法在算法上的优势。

所以，最重要的还是人脑对在计算机外算法的改进，而不只是依据最快的硬件，搞最坏的时间空间复杂度。

~~~~~~~~~~~~~~~~~~~

喝了三个空瓶就兑换一次的策略。

 1 public class hello {
 2
 3     /**
 4      * @param args
 5      */
 6     public static void main(String[] args) {
 7         int num =  1000;
 8         int emptynum = 0;
 9         int drinknum = 0;
10         int cpunum = 0;
11         while( num > 0){
12             System.out.println("===============");
13             cpunum++;
14             System.out.println("cpunum = " + cpunum);
15             num--;
16             drinknum++;
17             emptynum++;
18             if (emptynum == 3)
19             {
20                 cpunum++;
21                 num++;
22                 emptynum = 0;
23             }
24             System.out.println("drinknum = " + drinknum);
25             System.out.println("num = " + num);
26             System.out.println("emptynum = " + emptynum);
27
28         }
29
30     }
31
32 }

第二种，每次全喝完，集中兑换空瓶策略。

 1 public class hello {
 2
 3     /**
 4      * @param args
 5      */
 6     public static void main(String[] args) {
 7         int num =  1000;
 8         int emptynum = 0;
 9         int drinknum = 0;
10         int cpunum = 0;
11         while( num > 0){
12             System.out.println("===============");
13             cpunum++;
14             System.out.println("cpunum = " + cpunum);
15             drinknum += num;
16             System.out.println("drinknum = " + drinknum);
17             emptynum += num;
18             num = emptynum / 3;
19             System.out.println("num = " + num);
20             emptynum -= (num*3);
21             System.out.println("emptynum = " + emptynum);
22
23         }
24
25
26
27     }
28
29 }

输出：

===============
cpunum = 1
drinknum = 1000
num = 333
emptynum = 1
===============
cpunum = 2
drinknum = 1333
num = 111
emptynum = 1
===============
cpunum = 3
drinknum = 1444
num = 37
emptynum = 1
===============
cpunum = 4
drinknum = 1481
num = 12
emptynum = 2
===============
cpunum = 5
drinknum = 1493
num = 4
emptynum = 2
===============
cpunum = 6
drinknum = 1497
num = 2
emptynum = 0
===============
cpunum = 7
drinknum = 1499
num = 0
emptynum = 2