农夫追牛问题

　　问题描述：农夫John和一头逃跑的牛在同一坐标轴上，John的初始位置为N(0<N<=100,000),牛的位置为K(0<K<=100,00),假定John在追逐过程中，牛不会移动，John有两种追逐方式：1）走路，从位置X移动X-1或者X+1需要一分钟时间；2）意念传输，一分钟内，可以从位置X移动到位置2*X。问，John最少需要多少时间追到牛。设John的位置为5，牛的位置为17，请输出结果。

　　分析：初始位置N,K并没有规定其大小，所以N可能大于K，也可能是小于K。农夫可以从X移动到2*X，但没有说明从位置2*X移动到X，所以可以认为不允许这样移动。问题关键点是如何判断采用哪一种移动方式更好。

　　在这里只分析N<K的情况。虽然这是从N移动到K的问题，但在实现的过程中，也可以逆向思考，从K返回到N，同样可以得出正确的最小时间和经过的位置。我是实现了从K到N的过程，因为我觉得对于一个大数来说，尽可能地以双倍的方式来接近它，效率会比较高，而对于一个小数来说，尽可能地以双倍的方式去增长，并不一定可以得到最优结果，如移动顺序5，10，20，19，18，17比5，4，8，16，17多花一分钟。这种贪婪思想就是，如果位置X折半后可以更接近N，那就采用折半的方式，当然这需要考虑奇偶情况的，伪码如下：

　　(1)minTime=N-K,executeTime=0；

　　(2)当N==K时，如果exeuteTime<MinTime,minTime=executeTime;否则返回；

　　　　如果N!=K，执行（3）；

　　(3)如果N为奇数，需要考虑两种情况，第一种情况，newPosition = (N-1)/2，adjustment=2，执行(4)；第二种情况，newPosition = (N+1)/2，adjustment=2，执行(4)；如果N为偶数，newPosition = N/2，adjustment=1，执行(4)；

　　(4)如果 |newPosition-N|+adjustment < N-K,则N=newPosition，executeTime=executeTime+adjustment，执行(2),否则如果executeTime+|N-K|<minTime,则minTime=execute+|N-K|；

　　使用了不同数据进行测试，结果没有问题。采用这种逆向的方法去求解的过程，其中也蕴含了采用这种方式可以得到最优结的证明过程。有时候采用贪婪思想不能得到最优解，但可以得到最优近似解，但在有些情况下，采用贪婪思想可以得到最优解，前提是算法思想合理。

　　采用gdb调试代码真是痛苦，与它的关系还需要进一步磨合。