最大乘积和-第13届蓝桥杯省赛Python真题精选

[导读]：超平老师的Scratch蓝桥杯真题解读系列在推出之后，受到了广大老师和家长的好评，非常感谢各位的认可和厚爱。作为回馈，超平老师计划推出《Python蓝桥杯真题解析100讲》，这是解读系列的第85讲。

最大乘积和，本题是2022年4月17日举办的第13届蓝桥杯青少组Python编程省赛真题编程部分第5题，13届一共举办了两次省赛，这是第一次省赛。题目要求对于N个正整数，编程计算出所有乘积相加的数值最大的排列方式，并输出数值。

先来看看题目的要求吧。

一.题目说明

编程实现：

有N个正整数，现对N个正整数进行不同方式的排列，每次排列后都会按照以下规则进行一次计算，聪明的小蓝发现，排列方式不同，最后计算出的结果也不相同。

计算规则：

第一次：第一个数乘以第二个数乘以第三个数，结果记录为M(1) ；

第二次：第二个数乘以第三个数乘以第四个数，结果记录为M(2) ;

第三次：第三个数乘以第四个数乘以第五个数，结果记录为M(3) ;

…

第N − 2次：第N − 2个数乘以第N − 1个数乘以第N个数，结果记录为M ( N − 2 ) 。

最后计算M(1) + M(2) + M(3) . . … . M(N − 2)的数值。找出一种排列方式使这个数值最大。

例如：N = 4，4个正整数分别为1，2，3，4，那么排列方式就会有24种，其中排列方式为1，3，4，2时，按照规则计算2次：1 × 3 × 4 = 12，3 × 4 x 2 = 24，乘积相加：12 + 24 = 36 这种排序方式是所有乘积相加的数值最大，为36。

输入描述：

输入N个正整数，正整教之间一个英文逗号隔开。

输出描述：

找出所有乘积相加的数值最大的排列方式，并输出数值。

输入样例：

1,2,3,4

输出样例：

36

二.思路分析

这是一道和排列组合相关的算法题，涉及的知识点包括循环、列表、排列函数、枚举算法和贪心算法等。

乍一看，这不就是典型的组合排列问题嘛。

将N个正整数的全排列都列举出来，逐个计算M(1) + M(2) + … . M(N − 2)的值，就可以得到最大值。

针对本题，我给出两种解决方案：

• 枚举算法 + 排列函数

• 贪心算法

1. 枚举算法 + 排列函数

这个比较好理解，就是先使用permutations()函数获取所有的排列，然后使用循环分别计算每一种排列的乘积和，通过比较找到最大值。

计算排列比较简单，关键是针对每一种排列都要计算乘积和。为了方便，可以使用自定义函数来处理，从而简化代码结构。

2.贪心算法

从理解的角度来看，使用排列函数是最佳方案，但是随着数字规模的增加，其缺点也越来越明显，那就是算法的时间复杂度越来越高，算法效率将大打折扣。

实际上，还有一种更高效的方法，这就是贪心算法。

假定有5个数字，自左至右分别是abcde，如图所示：

它一共有3个乘法算式，如下：

M(1) = a * b * cM(2) = b * c * dM(3) = c * d * e

很容易，发现如下3条规律：

• 两端的a和e，都只参与了一次运算；

• 左2的b和右2的d，参与了两次运算；

• 中间位置的c，参与了3次运算；

随着数字个数的增加，中间位置的数字可以有多个，它们都需要参与3次运算。

很显然，将最大的数字放在中间，接下来每一次都找到当前最大的数字，并和之前已经存放的最大数字紧挨着，最小的数字放在两端，这样就可以得到更大的乘积，这不就是贪心算法的思想嘛。

接下来我们举例说明，如果有4个数字，分别是1、2、3、4，那么肯定要将3和4放在中间，1和2放在两端。

不过，放在两端时，需要考虑2的位置，它既可以放在4的旁边，也可以放在3的旁边，肯定找最大的呀，也就是2和4挨在一起，可以得到更大的乘积，即1、3、4、2，如图：

此时，对于原列表[1, 2, 3, 4]来说，处在奇数位的[1, 3]正序排列，处在偶数位的[2, 4]逆序排列。

当然，也可以排列成2、4、3、1，效果一样，如图：

如果有5个数字，分别是1、3、5、7、9，其中9最大，肯定放在正中间，9旁边依次是7和5，两端则分别是3和1，如图所示：

此时，对于原列表[1, 3, 5, 7, 9]来说，处在奇数位的[1, 5, 9]正序排列，处在偶数位的[3, 7]逆序排列。

如果有6个数字，分别是2、3、5、7、8、10，最大的两个数8和10要放在中间，紧接着7和10挨着，5则和8挨着，3和2分列两端，如图：

此时，对于原列表[2, 3, 5, 7, 8, 10]来说，处在奇数位的[2, 5, 8]正序排列，处在偶数位的[3, 7, 10]逆序排列。

如果有7个数字，分别是3、5、5、6、7、9、12，则其排列如图所示：

此时，对于原列表[3, 5, 5, 6, 7, 9, 12]来说，处在奇数位的[3, 5, 7, 12]正序排列，处在偶数位的[5, 6, 9]逆序排列。

讲到这里，相信聪明的你，已经发现这其中的规律和奥妙了。

对于一个有序的序列，先将处在奇数位的数字找出来顺序排列，然后再将处在偶数位的数字找出来逆序排列，构成一个新的列表，就可以得到最大乘积和了。

所以，对于输入的N个正整数，我们可以通过如下4步进行处理：

• 将列表进行排序

• 分别获取奇数位的数字和获取偶数位的数字

• 奇数位数字正序，偶数位数字逆序，构成一个新列表

• 分别计算M(1)、M(2)、...、M(n- 2)，并求和

思路有了，接下来，我们就进入具体的编程实现环节。

三.编程实现

根据上面的思路分析，我们分别使用两种方法来实现：

• 枚举算法 + 排列函数

• 贪心算法

1. 枚举算法 + 排列函数

根据前面的思路分析，编写代码如下：

代码不多，说明3点：

1). 对n个数字获取全排列，第一个参数为列表，第二个参数是n；

2). permutations()函数得到的是可迭代对象，使用for循环来获取每一个对象，该对象是元组；

3). 在获取最大值的时候，直接使用了max()函数。

2. 贪心算法

根据前面的思路分析，编写代码如下：

代码不多，强调3点：

1). 在获取奇数和偶数列表的时候，使用了带条件的列表推导式，非常方便；

2). 列表逆序，直接使用切片运算[::-1]，方便快捷；

3). 在Python编程中，可以直接将两个列表相加，得到新的列表。

至此，整个程序就全部完成了，你可以输入不同的数据来测试效果啦。

四.总结与思考

本题代码在12行左右，涉及到的知识点包括：

• 循环语句；

• 列表推导式；

• 排列函数；

• 枚举算法；

• 贪心算法；

本题代码不算多，但是难度不小，关键点有两个，一是灵活运用Python自带的排列函数快速解决问题，二是分析乘法算式的特点，找到数字排列的规律，从而找到更高效的算法。

本题给出了两个解决方案，方案一相对比较简单，但并不是最优的方案，大概率会出现超时情况，因为它的时间复杂度太高了。

permutations()函数的时间复杂度取决于输入的数据大小，对于包含n个元素的列表，它会生成n的阶乘个排列，因此，其时间复杂度可以表示为O(n!)。

当n值很大时，阶乘的增长非常快，导致permutations()函数的性能会随着输入大小的增加而急剧下降。

你可以输入1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13，来测试一下方法一的效果。

因此，在数据较多的时候，必须要考虑使用其他更高效的方法来避免计算所有排列。

而方案二则使用了贪心算法的思想，找出数字排列的规律，最后通过一次循环就可以计算出最大乘积和。

由于使用了排序函数，因此其时间复杂度主要取决于sort()函数。在Python编程中，sort()方法使用的是Timsort算法，其时间复杂度为O(n log n)，其中n是列表的长度。

Timsort算法由Tim Peters在2002年为Python编程语言提出的，并已成为Python sort()方法和sorted()函数的默认排序算法。

Timsort算法是一种混合了归并排序和插入排序思想的排序算法，针对不同情况下的数据集均具有较好的性能表现。

你还有什么好的想法和创意吗，也非常欢迎和超平老师分享探讨。

如果你觉得文章对你有帮助，别忘了点赞和转发，予人玫瑰，手有余香😄

需要源码的，可以移步至“超平的编程课”gzh。