怎樣使用暴力算暴力美學?

02-23

比如ProjectEuler490題

Problem 490 - Project Euler

There are n stones in a pond, numbered 1 to n. Consecutive stones are spaced one unit apart.
A frog sits on stone 1. He wishes to visit each stone exactly once, stopping on stone n. However, he can only jump from one stone to another if they are at most 3 units apart. In other words, from stone i, he can reach a stone j if 1 ≤ j ≤ n and j is in the set {i-3, i-2, i-1, i+1, i+2, i+3}.

Let f(n) be the number of ways he can do this. For example, f(6) = 14, as shown below:
1 → 2 → 3 → 4 → 5 → 6
1 → 2 → 3 → 5 → 4 → 6
1 → 2 → 4 → 3 → 5 → 6
1 → 2 → 4 → 5 → 3 → 6
1 → 2 → 5 → 3 → 4 → 6
1 → 2 → 5 → 4 → 3 → 6
1 → 3 → 2 → 4 → 5 → 6
1 → 3 → 2 → 5 → 4 → 6
1 → 3 → 4 → 2 → 5 → 6

1 → 3 → 5 → 2 → 4 → 6
1 → 4 → 2 → 3 → 5 → 6
1 → 4 → 2 → 5 → 3 → 6
1 → 4 → 3 → 2 → 5 → 6
1 → 4 → 5 → 2 → 3 → 6
Other examples are f(10) = 254 and f(40) = 1439682432976.
Let S(L) = ∑ f(n)^3 for 1 ≤ n ≤ L.
Examples:
S(10) = 18230635
S(20) = 104207881192114219

S(1 000) mod 10^9 = 225031475
S(1 000 000) mod 10^9 = 363486179
Find S(10^14) mod 10^9.

題目大概是這樣：有一隻青蛙要過河，河上有一列石頭。他（原文如此）要從第一塊跳到最後一塊(n)石頭。他只能跳到相鄰三個單位以內的石頭，並且要求每塊石頭剛好經過一次。大概情況如圖所示：

（圖片來自網路，僅供參考）

f(n)表示對於n塊石頭不同跳法的個數，S(n)為f(n)的立方和。

所求值很大，顯然需要找遞推或者通向。觀察可知，應當從序列的開頭進行分類。對於一個長度為m的開頭[1..k]，如果剛好包含1...k，則剩餘部分化為f(n-m)的情況。比如12，132，13425... 。雖然用這種方法可以分類得到通項公式，但是比較麻煩並且容易出錯。某外站論壇上還有如下提示：

於是聯想到329題，應該先按照暴力的方法，去產生一些比較小的值。

def excited(n, cur_node, remain, visited): if remain == 1 and cur_node == n: return 1 visited[cur_node] = 1 res = 0 for i in range(cur_node - 3, cur_node + 4): if i &<= 0 or i &> n or visited[i] == 1: continue else: res += excited(n, i, remain - 1, visited) visited[cur_node] = 0 return res def frog(n): return excited(n, 1, n, [0]*(n+1)) if __name__ == __main__: print([frog(i) for i in range(1,20)])

time ./pypy ~/git/euler/python/490/frog.py [1, 1, 1, 2, 6, 14, 28, 56, 118, 254, 541, 1140, 2401, 5074, 10738, 22711, 48001, 101447, 214446] real 0m4.506s user 0m4.438s sys 0m0.058s

根據之前的分析可知，遞推應該是線性的，於是可以用mma進行猜測。

coef = FindLinearRecurrence[{1, 1, 1, 2, 6, 14, 28, 56, 118, 254, 541, 1140, 2401, 5074, 10738, 22711, 48001, 101447, 214446}] (*{2, -1, 2, 1, 1, 0, -1, -1}*)

20項確定8階應該是比較可靠的。現已知f(n)的遞推關係，求 $g(n)=f(n)^3$ 。f(n)的特徵多項式的三次方展開形式為 $8^3=512$ 次多項式，且 $g(n)$ 仍然可以表示為不超過512階線性遞推。於是繼續利用mma求遞推。

fvals = LinearRecurrence[coef, {1, 1, 1, 2, 6, 14, 28, 56}, 513]; (fpow3coef = FindLinearRecurrence[fvals^3])//Short (*{6,9,119,776,2928,&<&<111&>&>,-1,-2,0,-1}*)

再利用 $f(n)^3=S(n)-S(n-1)$ 換掉遞推中的所有 $f(n)$ ，可得 $S(n)$ 遞推。

sumcoef = Append[fpow3coef, 0] + Prepend[-fpow3coef, 1] sumcoef//Short (*{7,3,110,657,2152,-3069,-52635,-261302,&<&<105&>&>,-2359,285,-1,-7,-1,2,-1,1}*)

最終將遞推寫為矩陣形式，然後利用快速冪即可求出答案。

buildRMatrix[ker_] := With[{dim = Length[ker]}, Append[Drop[IdentityMatrix[dim], 1], Reverse@ker]]; mod = 10^9; mo = Mod[#, mod] ; mo[Algebra`MatrixPowerMod[mo@buildRMatrix[sumcoef], 10^14 - 1, mod].mo@Accumulate[Take[fvals^3, 121]]] // First

為了防止嚴重違反pe社區管理規範，答案就不貼了。一道本來難度較高的題目，利用暴力的辦法，意外的繞過了所有的分析過程，減少了很多時間消耗。因此雖然暴力是不可取的，但偶爾也可以展現一種簡單的美。

比如雞兔同籠問題

今有雉兔同籠，上有三十五頭，下有九十四足，問雉兔各幾何？

暴力解法：把籠子里每隻雞和兔子都砍掉兩條腿，總計砍掉35X2=70條腿，還剩下94-70=24條腿

此時雞都沒有腿了，每隻兔子還有兩條腿，那麼這24條腿都是兔子腿，而且屬於12隻兔子

所以雞的數量就是35-12=23

又比如：

福爾摩斯同志退休後當上了養蜂人，但他這種人，你知道，是絕對無法忍受這種平靜的田園生活的。終於有一天他實在忍不住了，把華生醫生給招來，他說：「我多麼渴望智力上的刺激！

華生滿足了他的要求，他給福爾摩斯出了這樣一道題:

一個人收到一封匿名信，這封信讓他午夜去當地的墓地。

通常他不會理會這種事情，但是出於好奇，他還是去了。

夜晚一片死寂，僅有一彎新月照明。

這個人在自己的祖墳前站住了。

就買在他準備回去時，他聽到腳步聲。

他高聲呼叫，但沒有人回答他。

次日清晨，管理員發現他的屍體，

臉上帶著猙獰的笑容。

問題是：此人在1904年的美國總統選舉中是否投了西奧多-羅斯福的票？

暴力解法：

福爾摩斯：「呵呵，naive，如果我說這人死於1903年，是不是題目中沒有任何證據可以推翻我的論斷？1903年的時候可能在晚上看到新月，人類也早就發明了墓葬，有的墓地也有管理員了。」

華生：「對。」

福爾摩斯：「所以題目中無法證偽這個人死於1903年，或者1902年，或者這個人不是美國人……沒投羅斯福票的可能性太大了，所以我都不要去論證什麼，直接就可以猜測：此人沒有投羅斯福的票。」

又比如五點共圓老給大家鞍山市都放假哦不不Joan二胺愛好V佛愛乾淨哦按飛龍鳳奇偶比哈按我的

用解析法強行證明Miquel-Clifford定理的n=5情形。

使用猝不及防的暴力。

比如討論諸葛亮事迹的時候，舌戰群儒這個詞就非常的猝不及防。

又如辰東《聖墟》，猝不及防地出現被詛咒的神獸和跑得比誰都快的問題少女。

還有就是知乎有很多猝不及防的回答，比如說：

為什麼覺得矢澤妮可形象很好看？ - 知乎

當日本人說「大丈夫」的時候是真的完全不知道這幾個字在中國漢語裡面的內涵的嗎？ - 知乎

這類回答實在太多，我就不一一列舉了。

謝謝大家。

是時候祭出這張圖了

比如ProjectEuler329題

Prime Frog
Susan has a prime frog.

Her frog is jumping around over 500 squares numbered 1 to 500. He can only jump one square to the left or to the right, with equal probability, and he cannot jump outside the range [1;500].
(if it lands at either end, it automatically jumps to the only available square on the next move.)
When he is on a square with a prime number on it, he croaks P (PRIME) with probability 2/3 or N (NOT PRIME) with probability 1/3 just before jumping to the next square.
When he is on a square with a number on it that is not a prime he croaks P with probability 1/3 or N with probability 2/3 just before jumping to the next square.
Given that the frogs starting position is random with the same probability for every square, and given that she listens to his first 15 croaks, what is the probability that she hears the sequence PPPPNNPPPNPPNPN?
Give your answer as a fraction p/q in reduced form.

題目大意是這樣：有一個青蛙在標記為1-500格子上跳，每次向左或者向右跳一格，所有跳躍產生的概率都是平等的（如果到邊界只有一種跳法）。每當他處於一個格子上時，都會對這個數字是不是質數進行表態。然而消息可靠的概率只有2/3，也就是說出現偏差的概率是1/3。

現在S女士聽到這個青蛙說跳十五步對應序列「PPPPNNPPPNPPNP」（P表示質數，N表示不是）。求她聽到這種說法的概率。

一般來說project euler上的問題都是需要一些數學或者編程技巧才可以解決，然而此題與眾不同。青蛙15步內只有最多2^15種跳法，初始狀態也只有500種可能，所以只需把所有可能性暴力枚舉，計算相應概率求和即可。由於演算法非常簡單，在某些語言中幾行就可以寫出解法，讓人感到一種簡單，淺顯的美。然而使用暴力演算法是由於這個題目的特殊性決定的，在一般情況下，直接使用暴力演算法所消耗的時間是不可以預料的，並且有的時候電腦會一下子就死機了，然後就得重新開機，並且有丟失資料的風險。

當你發現oj的數據規模並不大的時候

順手來一個：

當你用最笨的方法算出高考數學壓軸題的時候。

有的問題特別是圓錐曲線問題都有幾何背景，有的有很巧妙的解法。當你用暴力計算證出它們來時，你就體會到了暴力美學。

背景音樂。

最好是古典樂，交響樂，比如貝多芬第九交響曲

「A——MEN————!!!」

其實我個人是反對暴力m學的，顯得知識水平很低，但是適當的場合暴力一下也不是不行