【蓝桥杯省赛真题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

输出样例：

二、算法分析

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

三、程序编写

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

四、程序说明

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