【蓝桥杯省赛真题36】python最佳排列方式 中小学青少年组蓝桥杯比赛 算法思维python编程省赛真题解析

本文主要是介绍【蓝桥杯省赛真题36】python最佳排列方式 中小学青少年组蓝桥杯比赛 算法思维python编程省赛真题解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

python最佳排列方式

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、程序说明

五、运行结果

六、考点分析

七、 推荐资料

1、蓝桥杯比赛

2、考级资料

3、其它资料

---

python最佳排列方式

第十三届蓝桥杯青少年组python比赛省赛真题

一、题目要求

（注：input（）输入函数的括号中不允许添加任何信息）

1、编程实现

有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*2=24；乘积相加：12+24=36这种排序方式是所有乘积相加的数值最大，为36。

2、输入输出

输入描述：输入N个正整数(3≤N)，正整数之间一个英文逗号隔开

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

1，2，3，4

输出样例：

36

二、算法分析

1. 题目相对而言具有一定的难度，需要用到一定的算法知识
2. 小兔子老师这里采用深度优先算法进行实现
3. 思路就是每一个数字进行按要求的排列组合，同时标记使用过的数字，然后将每种组合的数字保存到另外一个列表，计算出每种排序后的组合乘积和值
4. 最后返回求和中最大的那个组合的和值

三、程序编写

def dfs(t,f,a):sum = 0if(t == len(ls)):res = 0for i in range(0,len(ls)-2):res += (a[i] * a[i+1] * a[i+2])return resfor i in range(len(ls)):if(f[i] == 0):a[t] = ls[i]f[i] = 1sum = max(sum,dfs(t+1,f,a))f[i] = 0return sum
ls = list(map(int,input().split(',')))
ls_f = [0]*len(ls)
ls_res = [0]*len(ls)
print(dfs(0,ls_f,ls_res))

四、程序说明

1. 定义递归函数 dfs，也就是深度算法的实现过程
2. dfs包含三个参数：t 表示当前递归深度，f 是一个和 ls 等长的数组，用于标记 ls 中的元素是否已经使用过，a 是一个和 ls 等长的数组，用于保存当前排列
3. 定义一个变量 sum 用于保存最大乘积和的结果
4. 如果 t 的值等于 ls 的长度，说明已经得到了一个完整的排列，此时计算该排列的乘积和，并返回
5. 否则，遍历 ls，对于每个未被使用过的元素，将其加入当前排列 a 中，并将对应的标记 f 设为 1
6. 然后，递归调用 dfs 函数，将递归深度加一，并更新 sum 的值为当前 sum 和递归调用的返回值中的较大者
7. 之后，回溯对应的标记 f 为 0，以便在下一轮遍历中该元素可以被使用
8. 最后，返回 sum 作为整个函数的结果
9. 在主程序中，利用split函数以及map函数将输入的数字转换成整数对象，并结合list函数将多个对象转换成列表
10. 然后，分别定义了与 ls 等长的两个数组 ls_f 和 ls_res，用于标记和保存结果
11. 接着，调用 dfs 函数，将初始递归深度设为 0，并传入初始的标记数组和结果数组
12. 最后通过print函数输出即可

五、运行结果

1,2,3,436

六、考点分析

难度级别：难，这题相对而言还是有一点小难度，难在算法的实现，具体主要考查如下：

1. 学会分析题目，找到解题思路
2. 学会深度优先算法知识的应用
3. input函数：Python 中 input() 函数接受一个标准输入数据，返回为 string 类型。
4. int函数：强制将传入对象转换成整数类型
5. split函数：按照指定的分隔符进行分割
6. map函数：将指定的对象按照指定的函数进行迭代，在这里是将时分秒字符串类型数据按int整数类型数字返回输出（相当于多个变量强制类型转化）
7. list函数：强制将参数转化成列表对象
8. 学会列表的相关操作：列表声明、取数、遍历等等
9. 学会for循环的使用：for循环可以遍历任何有序的项及列表元素等等。
10. range函数：rang（a,b），循环的时候是不包括b的，所以我们这个案例中要转变一下，要想包含b，就应该写成range(a,b+1)
11. 学会if...条件判断语句的使用：满足条件才执行相应的程序
12. 学会if...else双分支语句的使用：满足条件执行一种处理程序，不满足执行另一种处理程序
13. print函数：用于打印输出，最常见的一个函数。
14. 充分掌握for循环，深度搜索算法和列表相关操作函数的使用

PS：方式方法有多种，小朋友们只要能够达到题目要求即可！

七、 推荐资料

• 所有考级比赛学习相关资料合集【推荐收藏】

1、蓝桥杯比赛

• 蓝桥杯python选拔赛真题详解

• 蓝桥杯python省赛真题详解

• 蓝桥杯python国赛真题详解

• 历届蓝桥杯科技素养计算思维真题解析

2、考级资料

• python等级一级真题解析【电子学会】

• python等级二级真题解析【电子学会】

• python等级三级真题解析【电子学会】

• python等级四级真题解析【电子学会】

3、其它资料

• 初学python100例

• 历届蓝桥杯scratch国赛真题解析
• 历届蓝桥杯scratch省赛真题解析
• 历届蓝桥杯scratch STEMA选拔赛真题解析
• 历届蓝桥杯科技素养计算思维真题解析
• 画图-scratch编程考级99图
• 电子学会历年scratch等级考试一级真题解析
• 电子学会历年scratch等级考试二级真题解析
• 电子学会历年scratch等级考试三级真题解析
• 电子学会历年scratch等级考试四级真题解析
• 零基础学习scratch3.0【入门教学 免费】
• 零基础学习scratch3.0【视频教程 114节 免费】

这篇关于【蓝桥杯省赛真题36】python最佳排列方式 中小学青少年组蓝桥杯比赛 算法思维python编程省赛真题解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---