盐城seo网站优化软件做外贸现在一般都通过哪些网站

当前位置： 首页 > news >正文

盐城seo网站优化软件,做外贸现在一般都通过哪些网站,南京手机网站制作,众创空间网站建设方案[导读]#xff1a;超平老师计划推出《全国青少年信息素养大赛Python编程真题解析》50讲#xff0c;这是超平老师解读Python编程挑战赛真题系列的第15讲。 全国青少年信息素养大赛#xff08;原全国青少年电子信息智能创新大赛#xff09;是“世界机器人大会青少年机器人设… [导读]超平老师计划推出《全国青少年信息素养大赛Python编程真题解析》50讲这是超平老师解读Python编程挑战赛真题系列的第15讲。 全国青少年信息素养大赛原全国青少年电子信息智能创新大赛是“世界机器人大会青少年机器人设计与信息素养大赛”赛事之一由中国电子学会主办包含很多赛项大赛自2013年举办已连续成功举办八届已正式入围“2022-2025学年面向中小学生的全国性竞赛活动名单”。  大赛旨在激发广大青少年的科学兴趣和想象力培养钻研探究、创新创造的科学精神和实践能力促进青少年科技创新活动的广泛开展发现和培养一批具有科研潜质和创新精神的青少年科技创新后备人才。 大赛主要竞赛类别包括电子科技、智能机器人、软件编程三类全国青少年Python编程挑战赛就属于其中的软件编程类。 一.赛事说明 2023年第9届Python挑战赛赛程分为初赛、复赛和总决赛三个阶段。初赛是资格赛复赛是地方选拔赛总决赛是全国各地选拔的精英汇聚在一起进行PK。 本届Python挑战赛是在线上举行参赛选手登录大赛官网在指定页面完成答题并提交答案。评定成绩的依据是同时考虑得分和用时两个方面首先是得分高者名次靠前如果得分一样则用时少者名次靠前。 2023年全国青少年Python编程挑战赛华北赛区北京初中组复赛于2023年7月15日正式举行。一共有6道题全是编程题考试时间是90分钟。 今天超平老师分享的是第6题也是最后一题错排问题。 二.题目描述 题目背景 圣诞节快到了公司为每个员工都准备了礼物每个礼物都有一个精美的盒子。如果所有的礼物都不小心装错了盒子求所有礼物都装错盒子共有多少种不同情况。 输入描述 输入一个正整数n表示公司人数保证n  ≤  20。 输出描述 输出一个整数代表有多少种情况。 样例1 输入 2 输出 1 三.思路分析 这是一个典型的错排问题那什么是错排问题呢我们来看两个大家都熟悉的生活场景。 10本不同的书放在书架现重新摆放使得每本书都不在原来的位置上有几种摆法 1个人给10个同学写信但他把所有的信都装错了信封问共有多少种错误的方式 这些都是生活中的错排问题推而广之一个n个元素的排列若一个排列中所有的元素都不在自己原来的位置上那么这样的一个排列就称为原排列的一个错排。而研究一个排列的错排个数的问题就称为错排问题。 错排问题也叫做伯努利-欧拉错装信封问题它是数学史上著名的数论问题。最早研究这个问题的是丹尼尔·伯努利。后来欧拉对此产生了兴趣并独立解决了这个难题并称其为“组合理论的一个妙题”。因此历史上也将错排问题叫做“伯努利-欧拉装错信封问题”。 很明显错位问题涉及到排列组合知识首先能想到的自然是枚举算法我们使用函数f(n)来表示n个数的错排总数。 当n 1时只有一个数字不可能出现错排情况所以f(1) 0 当n 2时全排列只有两种分别是12和21其中后者是错排所以f(2) 1 当n 3时全排列有6种分别是123、132、213、231、312、321其中231和312是错排所以f(3) 2 当n 4时全排列有24种其中错排有9种分别是2143、2341、 2413、3142、 3412、3421、 4123、4312、 4321所以f(4) 9 …… 枚举算法的编程实现是需要使用循环的并且还是嵌套循环嵌套的层数取决于nn 3时使用3层循环n 4时则为4层循环以此类推。 随着n的增大循环的次数越来越多由于n是变化的 直接使用枚举算法是无法编写代码的。 我们不妨换一个思路对于n个元素的错排问题可以将转化为 n - 1个元素的错排问题它们只是规模大小不同排列的算法其实是一样的。 因此我们可以使用递推的思想来推导f(n)和f(n-1)之间的关系。 假定n - 1个元素是错排的在增加第n个元素时它是不能放在第n个位置n的正确位置那么它放在哪儿呢 我们可以分两步来进行推导。 第一步选择n的位置。 前面n - 1个元素任何一个位置都是可以的假设放在第m位上1 m n -1。很显然n的可选位置有n - 1种方案。 第二步选择m的位置。 由于m被挤出来了 需要考虑m的放置问题m可以放哪些地方呢此时又可以分两种情况 放在n的位置此时m和n的位置是固定的错排就转化为除了m和n之外其它n -2位的错排问题即f(n - 2) 不放在n的位置此时m的位置是固定的错排就转化为除了m之外其它n - 1位的错排问题即f(n - 1)
因此我们可以得出如下公式 熟悉斐波那契数列的同学应该对这个推导公式比较熟悉。 实际上伟大的数学家欧拉早在200多年前就已经给出了这个递推公式并解决了此题然后将此题誉为“组合理论的一个妙题”。 有了递推公式我们很容易就可以想到使用递归算法或者动态规划算法来编程实现。 接下来我们进入具体的编程实现环节。 四.编程实现 根据上面的思路分析我们使用两种方式来编写代码 递归算法 动态规划
1.递归算法 根据前面的思路分析和递归算法的实现方式需要先定义好递归函数代码如下 需要注意这里的两个if语句这也是递归的出口由于涉及到n - 1和n - 2所以n 1和n 2时是不能直接使用推导公式的。 然后就可以调用递归函数计算出总的组合情况代码如下 递归的好处就是代码简洁理解起来相对比较容易缺点就是当递归层数较多时执行时间太长考试时有可能出现超时的情况。 2.动态规划 动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。 对于动态规划通常可以分成如下5个步骤 确定dp数组以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组
首先dp数组在本题中dp是一个一维列表dp[i]表示i个盒子错排的方案数量。 递推公式在思路分析部分已经确定好了。 然后就是初始化了我们只需要考虑dp[1]和dp[2]的情况即可。根据前面的分析dp[1] 0dp[2] 1。 我们先定义一个函数用于计算错排数量代码如下 简单说明两点 1). 为了方便计算对于n个盒子将列表长度设置为n 1其中dp[0]可以不用管或者理解为n为0的情况 2). 由于dp[1]和dp[2]是不能使用推导公式所以循环需要在从n 3开始直到第n个元素结束包括第n个元素。 接下来获取用户输入调用函数即可代码如下 如果我们将dp数组打印出来可以看到如下结果 这是n 20的情况测试程序可以发现随着n的增大仍然可以在很短的时间内输出结果这就是动态规划算法的强大之处了。 五.总结与思考 本题难度较大考查的知识点主要包括 处理输入数据 函数的定义及使用 列表的运算及操作 递归算法 动态规划算法
作为初中组复赛压轴题本题还是非常有难度的这里的排列组合已经涉及到高中数学知识了。 虽然我们并不需要使用数学方法来解决但要想完美的解决这个问题需要理解并掌握动态规划算法。 给你留一个小小的思考题除了上面提到的递归算法和动态规划算法实际上还有两种算法可以解决一是使用itertools中的permutations函数二是使用迭代算法赶紧动手尝试一下吧。 类似的错排问题还有不少超平老师再给你来两题吧。 教室里有10个座位(1 ~ 10)10位同学分别坐在一个不同的位置上(1 ~ 10)现要求打乱所有同学的位置打乱规则如下所有的同学都不能出现在原来的位置上问有多少种打乱的方法 家中阳台有10盆不同的花为保持新鲜感希望每天重新摆放使得每盆花都不在第一天放的位置。那么最多可以保持多少天每天摆法都不同 你还有什么巧妙的解决方案吗欢迎和超平老师交流。 如果你觉得文章对你有帮助别忘了点赞和转发予人玫瑰手有余香 更多教程请移步至“超平的编程课”gzh。