当前位置:   article > 正文

蓝桥杯算法训练:数字游戏(python)_试题 算法训练 数字游戏

试题 算法训练 数字游戏

问题描述

  给定一个1~N的排列a[i],每次将相邻两个数相加,得到新序列,再对新序列重复这样的操作,显然每次得到的序列都比上一次的序列长度少1,最终只剩一个数字。
  例如:
  3 1 2 4
  4 3 6
  7 9
  16
  现在如果知道N和最后得到的数字sum,请求出最初序列a[i],为1~N的一个排列。若有多种答案,则输出字典序最小的那一个。数据保证有解。

输入格式

  第1行为两个正整数n,sum

输出格式

  一个1~N的一个排列

样例输入

4 16

样例输出

3 1 2 4

数据规模和约定

  0<n<=10

 参考代码:

  1. import itertools
  2. n,m=map(int,input().split())
  3. dp=[i+1 for i in range(n)]#生成一行n列的数组,初始值为i+1
  4. sp=[]
  5. for x in itertools.permutations(dp,n):
  6. dp=list(x) #因为itertools.permutations出来的结果是以元组的形式,这里要把他们转换成列表的形式,方便在后面使用下标进行访问
  7. sp=dp.copy()#数组的深拷贝和浅拷贝。将排列好的数组复制给sp,用sp进行计算,保留原始的dp,如果最后sp算的结果满足要求,则输出dp里的内容
  8. for j in range(n-1):
  9. for i in range(n-1):
  10. sp[i]=sp[i]+sp[i+1]
  11. #print(dp)
  12. #print("此时的sp为:",dp)#可以用这句话进行测试,观看效果
  13. if sp[0]==m:#每将一种情况算完就进行比较一次,如果发现是想要的值,就输出并且结束循环
  14. for f in dp:#直接遍历并输出数组,也就是列表里的内容
  15. print(f,end=' ')
  16. break

代码解释:

执着于自己的思路:

3 1 2 4
4 3 6
7 9
16

因为下面每一行的数据是由上一行的数据相加得到的,这么看示例直观的看可以以二维数组的形式存储,但是考虑到要有不同的序列,每一种情况都要算的话容易超时,所以方便计算就采取一维数组计算覆盖的方法,用计算的新的数值覆盖掉以前的值:sp[i]=sp[i]+sp[i+1],另外发现计算的次数是n-1次,所以j的取值为0~n-2。其他可结合代码注释理解。

知识补充:

字典序,也就是全排列:

介绍什么是全排列:

经典算法:字典序排列_Espresso Macchiato的博客-CSDN博客杂谈:经典算法之字典序排列0. 引言1. 字典序排序2. 获取字典序排列的邻接元素1. 获取字典序排序的次小字符串2. 获取字典序排序的次大字符串3. 参考链接0. 引言最近连着两周打比赛都遇到了字符串字典序的相关问题,然后还连着两周都在这个坑里面摔死,简直了……因此,就趁着这个假期来整理一下字典序相关的内容,省的后面再在同一个问题上摔倒了……1. 字典序排序我们首先来看一下字典序排序的定义。考察两个字符串s以及s',s字典序在s'之前的判断条件为:def is..https://blog.csdn.net/codename_cys/article/details/116721756介绍可以用来求全排列的函数:itertools库里的permutations函数

Python学习:itertools库 combinations() 和 permutations()_combinations 库_Carol.Carol的博客-CSDN博客@[TOC](itertools库 combinations() 和 permutations())欢迎使用Markdown编辑器你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。新的改变我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,帮助你用它写博客:全新的界面设计 ,将会带来全新的写作体验;在创https://blog.csdn.net/sinat_37960022/article/details/110434470数组定义并初始化:

一维数组:dp=[i+1 for i in range(n)]#生成一行n列的数组,初始值为i+1

二维数组:dp=[[0 for i in range(n)]for j in range(m)]#生成m行n列的二维数组,初始值全为0

最后得分为90,有待改进......

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/64181
推荐阅读
相关标签
  

闽ICP备14008679号