最近看到一道樂視的筆記題，比較有意思。大意如下：

一個螞蚱,第一跳的距離是1,第二跳的距離是2,...,第N跳的距離是N.

?編程求要跳到Ｍ位置，最少的跳的次數(shù)是多少。

首先要保證Ｍ位置，可以通過這種方式跑到。

我第一反應想到另一道小明?折返跑的??題目。

小明在400米的圈的跑道上，折返跑，第一?段跑10米，第二?段跑20米,...,第N段跑N*10米，問小明要跑多少米，可以回到起點。

這里面每跑兩次相當于?前進/后退了10米。所以以這種折返跑的方式，肯定可以跳到任意位置。對應的跳的次數(shù)就是2*Ｍ。當然這種跳法肯定不是最???優(yōu)解。（Ａ方法）

最簡單的優(yōu)化，一直跳到距離最接近M的位置，再用?兩?步加1（或者兩??步減1）的方式跳到Ｍ點。需要注意，這里面有兩種情況，一種是跳到Ｍ之前，再?兩?步加1，一種是跳到Ｍ之后，再兩步減1,需要根據(jù)哪一頭的距離更?短來判斷。（Ｂ方法）

到這?一步，我本來認為已經(jīng)找到最?優(yōu)解。不過還是被同事逼問，會不會還有更少次數(shù)的?跳法。細想來，第N步時，可能跳到位置，就是對一個數(shù)組[1,2,...,N]，隨機?附上正負，再累加。而每在一處?x位置正變負，就相當于把累加和減了2*x,對于上面方法中，假定一直往前跳，第?x?跳的?位置是d(x).跳過了Ｍ位置?，到d(n+1)，再回頭逼近的情況，如果d(n+1)-M為偶數(shù)，那么只需要把這個?距離?除2的?跳步反向，就可以得到Ｍ。

舉例為：如果要跳到53，第10?跳，一?直向前跳，會跳到55

(55-53)/2=1

所以只要把這10跳中第1跳，由向前跳，改為向后跳，即可得到53。

如果d(n+1)-M為奇數(shù)要怎么算？也可以?選跳到最接近到的偶數(shù)位置，也就是M＋1的位置，再通過兩步減1的方法，到Ｍ位置，這種跳法，最多就是n+1+2次跳。?還有一些特殊情況，比如

如果M等于d(n)+1，且d(n+1)-M為奇數(shù)的情況，那么就只用跳到d(n)，再用兩?步加1的方法到Ｍ，先到M+1再兩?步減1的?方式，要少一跳。（特殊情況S）

說到這里，這個算法就比較麻煩了，情況判斷很多。(Ｃ方法)

好吧，我也覺得看著有點暈，寫起代碼也好?寫。?難道最??精減的解法，就一定要這么麻煩。然后我?又想到一種特??殊情況。

?對于(d(n+1)-M)為奇數(shù)的情況，如果我們直接跳到d(n+2),而且d(n+2)-M為???偶數(shù)的話，通過反向(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)為奇數(shù)，(d(n+2)-M)也為奇數(shù)的情況，這?時候，可以再多?跳一?步，這時(d(n+3)-M)肯定?是偶數(shù)了。這種情況(d(n+3)-M)/2會大于n+3,需要反轉(zhuǎn)兩個數(shù)才能得到M,這兩?個?數(shù)，可以是任意兩個相加和為(d(n+3)-M)/2的兩個步數(shù)，其實方法Ｃ中對這種情況解法，次數(shù)也是n+3,而且是必反轉(zhuǎn)n+3的那種解法。

所以最終版是，先?找到在M所在的d(n)和d(n+1)區(qū)間。再通過依次??判斷d(n+1)-M,d(n+2)-M,d(n+3)-M的奇偶，來判斷所需要的步數(shù)。

其實，我就想??吐?槽這TM根本就是一道數(shù)學題??！

（代碼就不寫了吧。。。。