最近看到一道乐视的笔记题，比较有意思。大意如下：
一个蚂蚱,第一跳的距离是1,第二跳的距离是2,...,第N跳的距离是N.
�编程求要跳到Ｍ位置，最少的跳的次数是多少。
首先要保证Ｍ位置，可以通过这种方式跑到。
我第一反应想到另一道小明�折返跑的��题目。
小明在400米的圈的跑道上，折返跑，第一�段跑10米，第二�段跑20米,...,第N段跑N*10米，问小明要跑多少米，可以回到起点。
这里面每跑两次相当于�前进/后退了10米。所以以这种折返跑的方式，肯定可以跳到任意位置。对应的跳的次数就是2*Ｍ。当然这种跳法肯定不是最���优解。（Ａ方法）
最简单的优化，一直跳到距离最接近M的位置，再用�两�步加1（或者两��步减1）的方式跳到Ｍ点。需要注意，这里面有两种情况，一种是跳到Ｍ之前，再�两�步加1，一种是跳到Ｍ之后，再两步减1,需要根据哪一头的距离更�短来判断。（Ｂ方法）
到这�一步，我本来认为已经找到最�优解。不过还是被同事逼问，会不会还有更少次数的�跳法。细想来，第N步时，可能跳到位置，就是对一个数组[1,2,...,N]，随机�附上正负，再累加。而每在一处�x位置正变负，就相当于把累加和减了2*x,对于上面方法中，假定一直往前跳，第�x�跳的�位置是d(x).跳过了Ｍ位置�，到d(n+1)，再回头逼近的情况，如果d(n+1)-M为偶数，那么只需要把这个�距离�除2的�跳步反向，就可以得到Ｍ。
举例为：如果要跳到53，第10�跳，一�直向前跳，会跳到55
(55-53)/2=1
所以只要把这10跳中第1跳，由向前跳，改为向后跳，即可得到53。
如果d(n+1)-M为奇数要怎么算？也可以�选跳到最接近到的偶数位置，也就是M＋1的位置，再通过两步减1的方法，到Ｍ位置，这种跳法，最多就是n+1+2次跳。�还有一些特殊情况，比如
如果M等于d(n)+1，且d(n+1)-M为奇数的情况，那么就只用跳到d(n)，再用两�步加1的方法到Ｍ，先到M+1再两�步减1的�方式，要少一跳。（特殊情况S）
说到这里，这个算法就比较麻烦了，情况判断很多。(Ｃ方法)
好吧，我也觉得看着有点晕，写起代码也好�写。�难道最��精减的解法，就一定要这么麻烦。然后我�又想到一种特��殊情况。
�对于(d(n+1)-M)为奇数的情况，如果我们直接跳到d(n+2),而且d(n+2)-M为���偶数的话，通过反向(d(n+2)-M)/2也可以得到Ｍ，这种就只需要n+2��步。比如，跳到52按�照方法C,需要选跳10步，第1步反向，到53，�再+11,-12到52。需要12步。按照新�方法，d(11)=66, （66-52）/2=7,反向第7步即可得到52，只需要用11步。
按照，当然也有(d(n+1)-M)为奇数，(d(n+2)-M)也为奇数的情况，这�时候，可以再多�跳一�步，这时(d(n+3)-M)肯定�是偶数了。这种情况(d(n+3)-M)/2会大于n+3,需要反转两个数才能得到M,这两�个�数，可以是任意两个相加和为(d(n+3)-M)/2的两个步数，其实方法Ｃ中对这种情况解法，次数也是n+3,而且是必反转n+3的那种解法。
所以最终版是，先�找到在M所在的d(n)和d(n+1)区间。再通过依次��判断d(n+1)-M,d(n+2)-M,d(n+3)-M的奇偶，来判断所需要的步数。
其实，我就想��吐�槽这TM根本就是一道数学题！！
（代码就不写了吧。。。。
网友评论