目錄
1. 問題描述
2. 解題分析
3. 代碼及測試
1. 問題描述
輪盤遊戲被稱為“賭場女王”。流傳較廣的輪盤數字排布和設計有“歐式規則”和“美式規則”兩種。兩種輪盤上的數字序列分别如下所示：
歐式規則:
0,32,15,19,4,21,2,25,17,34,6,27,13,36,11,30,8,23,10,5,24,16,33,1,20,14,31,9,22,18,29,7,28,12,35,3,26
美式規則：
0,28,9,26,30,11,7,20,32,17,5,22,34,15,3,24,36,13,1,00,27,10,25,29,12,8,19,31,18,6,21,33,16,4,23,35,14,2
下圖是歐式規則的輪盤示意圖（侵删）。
下面我們找到這些規則下“連續n個數字之和”最大的位置。舉個例子，當n=3時，按照歐式規則得到的最大的組合是36,11,30這個組合，和為77；而美式規則下則是24,36,13這個組合，得到的和為73.（圖中所示輪盤為歐式規則的輪盤，注意輪盤是圓形的）
問題：當 2 ≤ n ≤ 36時，求連續n個數之和最大的情況，并找出滿足條件“歐式規則下的最大和小于美式規則下的最大和”的n的個數。
2. 解題分析
求連續n個數字的平均（本題是求和，但是求和與求平均隻差一個平均系數，求平均也是也先求和再除以參與求和的資料的個數）在信号處理領域中稱為求移動平均（moving average, or running average），其計算方式有一個小小的trick。令資料序列用x[k]表示，則從第m數開始的連續n個數的累加和的計算可以表示如下：
這樣就得到了一個遞推關系，從上一個連續和sum[m-1]開始，隻要把減去最前面一個數，加上後面一個數就可以得到新的sum[m]。這樣可以極大地降低運算複雜度，在信号處理領域是常用技巧。
本題還有另外一個需要注意的要點就是輪盤是圓形的，用線性數組表示輪盤上的數字排列數組的話，一部分的連續和涉及到頭上一部分數字和尾巴上一部分數字的求和。最基本的做法就是用位址對數字長度進行求模運算。也可以用對數組進行線性擴充的方法以避免位址求模的處理。由于這個問題比較簡單，本題解就用“簡單粗暴”的前者對付一下了。
3. 代碼及測試
# -*- coding: utf-8 -*-
"""
Created on Sun Aug 29 07:14:15 2021
@author: chenxy
"""
import sys
import time
import datetime
# import random
from typing import List
# from queue import Queue
# from collections import deque
class Solution:
euroRule= [0,32,15,19,4,21,2,25,17,34,6,27,13,36,11,30,8,23,10,5,24,16,33,1,20,14,31,9,22,18,29,7,28,12,35,3,26]
usaRule = [0,28,9,26,30,11,7,20,32,17,5,22,34,15,3,24,36,13,1,0,27,10,25,29,12,8,19,31,18,6,21,33,16,4,23,35,14,2]
def maxSum(self, nums:List, n:int) -> int:
runningSum = sum(nums[0:n]) # The sum of the first n numbers as initial value
sumMax = runningSum
M = len(nums)
for k in range(1,len(nums)):
runningSum += nums[(k+n-1)%M] - nums[k-1]
if sumMax < runningSum:
sumMax = runningSum
# print('k ={0},runningSum={1},sumMax={2}'.format(k,runningSum,sumMax))
return sumMax
def maxCoronaSum(self, nMin:int, nMax:int) -> List:
"""
:
:ret: The list of numbers satisfying the condition.
"""
ans = []
for n in range(nMin, nMax+1):
euroMax = self.maxSum(self.euroRule,n)
usaMax = self.maxSum(self.usaRule,n)
# print('n ={0},euroMax={1},usaMax={2}'.format(n,euroMax,usaMax))
if euroMax < usaMax:
print('n={0}, euroMax={1}, usaSum={2}'.format(n,euroMax,usaMax))
ans.append(n)
return ans
if __name__ == '__main__':
sln = Solution()
tStart = time.time()
ans = sln.maxCoronaSum(2,36)
tCost = time.time() - tStart
print('nums ={0}, tCost = {1:6.3f}(sec)'.format(len(ans),tCost))
print('ans ={0}'.format(ans))
運作結果：
上一篇：Q08: 優秀的機器人
下一篇：
本系列總目錄參見：程式員的算法趣題：詳細分析和Python全解