天天看點

天下歸心——一道關于三國殺的數組遞推公式

天下歸心——一道關于三國殺的數組遞推公式

如圖所示,場上角色為一個陸遜與N個神曹操。開局時,隻有陸遜隻有一張手牌【南蠻入侵】(圖中有三張,因為不大會設定系統,在本問題中,以陸遜一張手牌為準),N個神曹操都沒有手牌,然後陸遜開局先使用【南蠻入侵】,陸遜的技能【聯營】和神曹操的技能【歸心】都是每次必須發動的。

問該【南蠻入侵】結算完畢後,每個神曹操手中各有幾張牌?

結算完畢後,我們對每個神曹操手牌數命名為a[1],a[2],……,a[N],我們就是要求 a[1],a[2],……,a[N]的值。

以下懂陸遜和神曹操技能的請無視之。 ================================================================= 說明,神曹操的技能【歸心】是,沒收到一點傷害,會對場上沒人摸一張手牌,當然如果某人沒有手牌則不摸。陸遜的技能【聯營】是,如果手中沒有手牌,則從牌堆中摸一張手牌。也就是每個神曹操在自己的歸心階段能從陸遜手中摸一張牌,開始第一個神曹操受傷,然後摸陸遜一張牌,第二個神曹操受傷,然後從陸遜手中以及第一個神曹操手中摸一張牌,以此類推。。。 ================================================================

如果這個問題是來程式設計的話,我們大家立馬想到【模拟法】,也就是将整個過程模拟一遍,最終算法的複雜度為O(N^2)。

但是對這個問題,讓我們從數學角度對其進行分析。

對于這類開始找不到頭緒的問題,有一種通用的解決思路,就是先寫出幾個來看看,看這幾個有沒有什麼可以直接看出來的規律,然後再分析歸納。

那我們也按照這個思路來解決:  

天下歸心——一道關于三國殺的數組遞推公式

  然後看第i次的時候第i個神曹操的手牌數,發現貌似有如下規律,1, 2,2, 3,3,3, 4,4,4,4,……

也就是,1連續出現1次,2連續出現2次,3連續出現3次,4連續出現4次,……出現一次就是一行

也就是說,1在第一行出現,2在第(1,1+2]行之間出現,3在第(1+2,1+2+3]行之間出現,4在第(1+2+3,1+2+3+4]之間出現。一直推下去,k在第(1+2+……(k-1), 1+2+3+……+k]之間出現,也就是k在第

天下歸心——一道關于三國殺的數組遞推公式

行之間出現,

那麼如果第i次的時候第i個神曹操的手牌數為k,則   然後我們就求出了第i次時第i個神曹操的手牌數的計算公式了。

天下歸心——一道關于三國殺的數組遞推公式

令i=N,則可以求出第N個神曹操的手牌數。

如果求N-1個神曹操的手牌數,可以做如下考慮:根據上面的公式,我們能算出第N-1次時神曹操的手牌數k',第N次的時候,第N-1個神曹操的手牌數比第N-1次,少了一張(被第N個神曹操摸走了)

第N-i個神曹操的手牌數可以如下計算,先計算第N-i次時的手牌數,然後之後i次,每次被摸走一張牌,直到為0為止。

于是,第N次的時候,第i個神曹操的手牌數為

天下歸心——一道關于三國殺的數組遞推公式

  i為[1,N]之間的整數。

經驗證,i對1~N之間的任何數都成立,是以,這個就是這個問題的解。

注:該問題還有一個取下整的答案,取下整的那個答案形式和這個很相似,隻有一點差别是根号裡面為8i-7,這兩個答案可以分析發現是等價的。

==============================================

然後這個問題可以算是解答了,但是其中還有幾個問題, 為什麼第i次的時候第i個神曹操的手牌數 1連續出現1次,2連續出現2次,3連續出現3次,4連續出現4次,……?這個是我們看出來的,其機理還沒有弄明白。

研究了很長時間,這個規律出現的原理仍然沒搞明白,如果有人對這個機理了解了,請留言,不勝感謝。

========================問題擴充=======================================

這個問題還可以有擴充,這個問題是要求神曹操開局手牌數均為0,那如果手牌數不為0呢?這個規律肯定不能很好滿足了,計算過程肯定要修改了。有興趣的可以考慮兩種情況: 第一:第一個神曹操有K張手牌,其他的神曹操手牌數為0. 第二:每個神曹操都有K張手牌。 第三,考慮第一或者第二的情況下,陸遜在某次之後決定不發動【聯營】了,特别是陸遜一開始就不發動聯營。 第四,某個神曹操,比如第3個,決定不發動【歸心】,其餘照辦。 第五:先給定一個神曹操的手牌數組b[N],然後給定一個是否發動【歸心】的二進制數組c[N],再給一個陸遜決定不發動【聯營】的次序号。