2025年3月16日 星期日 甲辰(龙)年 月十五 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q20: 受难立面魔方阵

时间:12-28来源:作者:点击数:42

1. 问题描述

西班牙有个著名景点叫圣家堂,其中“受难立面”上主要画着耶稣从“最后的晚餐”到“升天”的场景,其中还有一个如下图所示的魔方阵,因“纵、横、对角线的数字之和都是33”而闻名(据说耶稣辞世时是 33 岁)。

如果不局限于由纵、横、对角线的数字相加,那么和数为 33 的组合有 310 种之多(网上有很多“4 个数字相加……”这样的问题,如果限定只能由 4 个数字相加,则是 88 种)。

问题:使用这个魔方阵,进行满足下列条件的加法运算,求“和相同的组合”的种数最多的和。

条件:

  1. 不限于由纵、横、对角线上的数字相加
  2. 加数的个数不限于4

其实就是给定16个数中,求其中任意组合的相加和,其中得到相同的和的组合种类数最多的和。

2. 解法1--笨办法

这是基于直感想到的第一个办法(通常我会先从最naïve的方法开始着手,虽然笨拙,但是也有它的价值)。一上来就能直中靶心想到最优解毕竟不是凡人所能奢望的事情,循序渐进或许更符合普通人的步调。

针对每一个可能的和target(和的可能数为以上所有数字总和加1,把0也当作一种可能考虑,但是只考虑给定的数组中的数都为非负数的情况),扫描所有的组合,确认和为target的组合种类数。

然后比较所有可能的target对应的组合种类数。求解流程如下所示:

代码参见下面shouNanMoFang1().

3. 解法2--逆向思维

解法1太慢了,在nums数组中为16个数时就需要秒级的时间。16个数的所有可能长度的组合数是多少呢?恰好是二项式公式,如下所示:

Nums中的数为16个时不过65536种组合,如果魔方阵为5*5=25是,组合数将变为,比4*4=16的情况增大了512倍,显然按解法1是无法承受的。

解法1的问题在于,以target为着眼点,对每一个target都进行了全组合扫描,这导致巨大的浪费。如果反过来看的话,其实只需要进行一遍全组合扫描,针对每一个组合根据其和给对应target的计数器进行计数即可!这样运行时间就缩短为(1/sum(nums))了。

在以下代码中用哈希表(python dict)来记录对应各可能target的组合数计数器。

其中从字典中所存储的{key: numeric value}中寻找拥有最大value的key的处理可以参考:Python tips

代码参见下面shouNanMoFang2().

虽然解法2相比解法1有约两个数量级的效率提升,但是在5*5魔方阵(即25个数)的情况下仍然需要数十秒的时间。对于更大的魔方阵(比如说6*6)就无能为力了。

4. 解法3--动态规划

这里所说的动态规划的方法是参考原书的提示。但是原书提示就是寥寥一句话“每次设置一个数。。。”。怎么肥四啊?有点类似于数学证明中的“显而易见、易证”之类的(人与人之间的脑回路的差别有这么大嘛)。查阅了几个CSDN博客上的解也基本上就是直接上了一段代码。。。肝疼。。。(copy一段代码很简单,或者把ruby代码翻译成别的语言的代码也很简单)不过我还是希望能用自己的话把这个事情说清楚。本题的动态规划解法的要点如下:

按顺序考虑魔方阵(代码中的nums)的每个数的处理。

令targetCnt为一个2维数组(或者说一张表格—是的,动态规划的最基本的方法就是填表!),记录在使用nums不同子集时所有可能和值targetSum的组合种类数。targetCnt[k, m]代表只考虑nums中前k+1个数(即{nums[0],…, nums[k]})的条件下的和为m的组合种类数。

假设已经处理完nums[0],…, nums[k-1]了。当前targetCnt[k-1,:]的内容相当于是只考虑{nums[0],…, nums[k-1]}的所有可能组合所得到的结果。接下来追加考虑nums[k],很显然,对于targetSum=m而言,只考虑{nums[0],…, nums[k-1]}且和等于(m-nums[k])的所有组合再加上nums[k]就构成了和为m的组合了,由此可以得到递推关系式如下(为了让公式简洁一些,将第1个坐标用作下标,第2个坐标用作上标):

这样,本题的解题过程就变成了经典的动态规划填表的过程了。进一步,与一般的动态规划问题比如背包问题中不同的是,本问题中只依赖于,而且,因此我们事实上并不需要维护一张2维的表格,而只需要维护一个1维的数组就可以了。只不过需要注意,在更新tangetCnt时要按上标从大到小更新。

最后,作为动态规划解法,当然必须要定义初始条件或者边界条件。本题的边界条件可以定义为,在空组合(或者说从nums中选择0个数)时,targetSum=0时的组合数为1,targetSum>0时的组合数为0,即:

代码参见以下shouNanMoFang3().

5. 代码及测试

  • # -*- coding: utf-8 -*-
  • """
  • Created on Thu Sep 9 17:45:33 2021
  • @author: chenxy
  • """
  • import sys
  • import time
  • import datetime
  • import math
  • # import random
  • from typing import List
  • # from queue import Queue
  • # from collections import deque
  • import itertools as it
  • class Solution:
  • def shouNanMoFang1(self, nums: List):
  • totalSum = sum(nums)
  • # cnts = []
  • targetSum = 0 # The target sum which has the greatest number of combination sum
  • targetCnt = 0 # The number combination sum of the target sum
  • for target in range(1,totalSum+1):
  • cnt = 0
  • # ansLst = []
  • for k in range(1,len(nums)+1):
  • # print('k = ',k)
  • for p in it.combinations(nums,k):
  • p_sum = sum(p)
  • if p_sum == target:
  • cnt += 1
  • # ansLst.append(p)
  • if cnt > targetCnt:
  • targetCnt = cnt
  • targetSum = target
  • # cnts.append(cnt)
  • return targetSum,targetCnt
  • def shouNanMoFang2(self, nums: List):
  • numCombSum = dict()
  • for k in range(1,len(nums)+1):
  • for p in it.combinations(nums,k):
  • p_sum = sum(p)
  • if sum(p) in numCombSum:
  • numCombSum[sum(p)] += 1
  • else:
  • numCombSum[sum(p)] = 1
  • targetSum = max(numCombSum, key=numCombSum.get)
  • targetCnt = numCombSum[targetSum]
  • return targetSum,targetCnt
  • def shouNanMoFang3(self, nums: List):
  • totalSum = sum(nums)
  • targetCnt = [0] * (totalSum + 1)
  • targetCnt[0] = 1
  • for n in nums:
  • for i in range(totalSum - n, -1, -1):
  • targetCnt[i + n] += targetCnt[i]
  • maxtargetCnt = max(targetCnt)
  • return targetCnt.index(maxtargetCnt),maxtargetCnt
  • if __name__ == '__main__':
  • sln = Solution()
  • nums = [1,14,14,4,11,7,6,9,8,10,10,5,13,2,3,15]
  • tStart = time.perf_counter()
  • targetSum, targetCnt = sln.shouNanMoFang1(nums)
  • tCost = time.perf_counter() - tStart
  • print('Solution1: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
  • .format(len(nums),targetSum,targetCnt,tCost))
  • tStart = time.perf_counter()
  • targetSum, targetCnt = sln.shouNanMoFang2(nums)
  • tCost = time.perf_counter() - tStart
  • print('Solution2: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
  • .format(len(nums),targetSum,targetCnt,tCost))
  • tStart = time.perf_counter()
  • targetSum, targetCnt = sln.shouNanMoFang3(nums)
  • tCost = time.perf_counter() - tStart
  • print('Solution2: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
  • .format(len(nums),targetSum,targetCnt,tCost))
  • nums = [1,14,14,4,11,7,6,9,8,10,10,5,13,2,3,15,34,19,21,44,12,31,47,13,41]
  • tStart = time.perf_counter()
  • targetSum, targetCnt = sln.shouNanMoFang2(nums)
  • tCost = time.perf_counter() - tStart
  • print('Solution2: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
  • .format(len(nums),targetSum,targetCnt,tCost))
  • tStart = time.perf_counter()
  • targetSum, targetCnt = sln.shouNanMoFang3(nums)
  • tCost = time.perf_counter() - tStart
  • print('Solution2: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
  • .format(len(nums),targetSum,targetCnt,tCost))
  • nums = [1,14,14,4,11,7,6,9,8,10,10,5,13,2,3,15,34,19,21,44,12,31,47,13,41,\
  • 2,15,17,5,12,37,26,19,28,20,30]
  • tStart = time.perf_counter()
  • targetSum, targetCnt = sln.shouNanMoFang3(nums)
  • tCost = time.perf_counter() - tStart
  • print('Solution2: len(nums)={0}, targetSum = {1}, targetCnt = {2}, tCost = {3:5.3f}(sec)'\
  • .format(len(nums),targetSum,targetCnt,tCost))

运行结果如下:

从运行结果可以看出,解法2相比解法1有2个数量级的提升,解法3相比解法2进一步提升了4个数量级!合理的算法设计的威力是如此巨大!

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门