程序员的算法趣题Q10: 轮盘的最大值

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))   

运行结果：