最近看到一道樂視的筆記題，比較有意思扳埂。大意如下：
一個螞蚱,第一跳的距離是1,第二跳的距離是2,...,第N跳的距離是N.
?編程求要跳到Ｍ位置业簿，最少的跳的次數(shù)是多少。
首先要保證Ｍ位置阳懂，可以通過這種方式跑到梅尤。
我第一反應(yīng)想到另一道小明?折返跑的??題目柜思。
小明在400米的圈的跑道上，折返跑巷燥，第一?段跑10米赡盘，第二?段跑20米,...,第N段跑N*10米，問小明要跑多少米缰揪，可以回到起點陨享。
這里面每跑兩次相當(dāng)于?前進(jìn)/后退了10米邀跃。所以以這種折返跑的方式霉咨，肯定可以跳到任意位置。對應(yīng)的跳的次數(shù)就是2*Ｍ拍屑。當(dāng)然這種跳法肯定不是最???優(yōu)解途戒。（Ａ方法）
最簡單的優(yōu)化，一直跳到距離最接近M的位置僵驰，再用?兩?步加1（或者兩??步減1）的方式跳到Ｍ點喷斋。需要注意，這里面有兩種情況蒜茴，一種是跳到Ｍ之前星爪，再?兩?步加1，一種是跳到Ｍ之后粉私，再兩步減1,需要根據(jù)哪一頭的距離更?短來判斷顽腾。（Ｂ方法）
到這?一步，我本來認(rèn)為已經(jīng)找到最?優(yōu)解诺核。不過還是被同事逼問抄肖，會不會還有更少次數(shù)的?跳法。細(xì)想來窖杀，第N步時漓摩，可能跳到位置，就是對一個數(shù)組[1,2,...,N]入客，隨機?附上正負(fù)管毙，再累加。而每在一處?x位置正變負(fù)桌硫，就相當(dāng)于把累加和減了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āng)然也有(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ù)學(xué)題Ａ形整陌！
（代碼就不寫了吧。瞎领。泌辫。。
