电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

骑士球员报告

17页
  • 卖家[上传人]:bin****86
  • 文档编号:60399598
  • 上传时间:2018-11-15
  • 文档格式:DOCX
  • 文档大小:24.30KB
  • / 17 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、为了适应公司新战略的发展,保障停车场安保新项目的正常、顺利开展,特制定安保从业人员的业务技能及个人素质的培训计划骑士球员报告程序设计实践报告学号;姓名;题目来源及序号XX年25题;难度等级_级一、题目说明:由教师给出25.编写程序求解骑士巡游问题:在n行n列的棋盘上,假设一位骑士从初始坐标位置(x1,y1)出发,要遍访棋盘中的每一个位置一次。请编一个程序,为骑士求解巡游“路线图”。当n=5时,意味着要在5行5列的棋盘的25个“点”处,按骑士行走规则,依次将1至25这25个“棋子”分别摆放到棋盘上。例如,当n=5且初始坐标位置定为(1,1)即最左上角的那个点时,如下是一种巡游“路线图”。程序执行后的输出结果为:(x1,y1)?=(1=5,1=5):11二、问题分析及求解基本思路说明:给出题目的分析及初步的解题思路。要求简洁、易懂“棋盘”可用二维数组B表示。编制一个具有如下原型的递归函数solve,用于完成任务:从(i,j)点出发,做第k至第n*n次的移动将k直到n的平方这些数码按规则分别摆放到棋盘即数组B中,若成功则通过引用参数ok返回true,否则返回false。voidsolve(i

      2、nti,intj,intk,bool&ok);编制主函数,让用户输入作为巡游起点的初始坐标位置(x1,y1),在该处摆放“棋子”1,而后进行调用“solve(x1,y1,2,ok);”来完成所求任务。欲处理的初始问题为:从某点(x1,y1)出发,按所给行走规则,作24次移动,遍访棋盘中没被访问过的各点。可分解化简为如下两个子问题:由点(x1,y1)出发,按所给行走规则作1次移动到达(g,h);从(g,h)点出发,按所给行走规则,作23次移动,遍访棋盘中没被访问过的各点。solve函数具体实现时,若由(i,j)点出发已“无路可走”,则将引用参数ok置为false而递归出口;否则,先“迈一步”到达(g,h)点,而后再进行递归调用:solve(g,h,k+1,ok);以实现从新点(g,h)出发,将k+1直到25这些“棋子”分别摆放到棋盘上,若成功则通过引用参数ok返回true。主要才用了递归算法:在函数或子过程的内部,直接或者间接地调用自己的算法。其次用到了回溯算法:问题的每个解都包含N部分,先给出第一部分,再给出第二部分,直到给出第N部分,这样就得到了一个解。若尝试到某一步时发现已经无法继

      3、续,就返回到前一步,修改已经求出的上一部分,然后再继续向后求解。这样,直到回溯到第一步,并且已经将第一步的所有可能情况都尝试过之后,即可得出问题的全部解。三、问题求解的整体框架结构说明:围绕求解目标给出具体的模块。要求简洁、易懂Main()流程Solve()流程四、主要算法说明:要求用自然语言描述算法。要求简洁、易懂首先定义setw()的头文件,setw(n)设域宽为n个字符,并定义一个宏并赋初值,定义全局性的二维数组intb55;保存步数,boola55记录某一点是否已经走过,num记录方案数intdx=0,1,1,-1,-1,2,2,-2,-2;intdy=0,2,-2,2,-2,1,-1,1,-1;提供每一步的走法,把每种走法的可能写出来,并且把数组中的数全部按“日”的走法一共种可能输入到给定的棋盘。#include#include#defineN12usingnamespacestd;intb55;intnum=-255;intdx=0,1,1,-1,-1,2,2,-2,-2;intdy=0,2,-2,2,-2,1,-1,1,-1;编写solve(inti,intj,intk,

      4、bool&ok,intn)函数,定义变量参数,通过循环判断x是否在棋盘内,判断y是否在棋盘内,通过ax1y1=false;记录该点是否已经走过,并重复调用solve(x1,y1,k+1,ok,n)递归调用该函数,将数组全部数输写到棋内,并且把棋盘从而形成不同方案。voidsolve(inti,intj,intk,bool&ok,intn)intm,x1,y1,n1,n2;boolt1,t2;for(m=1;m=0)&(x1=0)&(y1rowcol;brow-1col-1=1;/设置起始点arow-1col-1=false;solve(row-1,col-1,2,ok,n);/调用函数计算结果if(!ok)coutinput;cout难在有限的时间内找到解。然后尝试贪心、动态规划、图论等硬做的算法,但这些算法都在预料之中以失败告终。最后,看来只有必经之路数学方法才能可以解决这个问题。【确定总算法和研究对象】用数学方法解决等价转化等题目的方法还是不胜枚举的。例如有归纳法,有总体法,有解方程法,有数形结合。对于这个题目,我们应选取什么数学方法好呢?注意到,如果任意的三个向量都可以与某两个向

      5、量等价,那么便可以从n(n2)个向量中任选三个向量出来,用与它们等价的两个向量代替它们,从而变成n-1个向量。不断重复上述的过程,直到只剩下两个向量为止,这时剩下的两个向量便是一个可行解。而由问题描述可以知道:对于任意三个向量都存在两个向量与它们等价。这便意味这种方法是可行的。于是,就可以确定下总算法不断化三为二,同时也产生了我们的研究对象如何把三个向量等价替换为两个向量?【分析研究对象】因为满足条件的解是无限多个的,解的范围没有多少限制,而我们仅仅需要这样一个解,所以这时确定下来的研究对象虽然看起来简洁明了,可是要解决该问题的难度依然相当大。【“约制”思想确定新任务】既然研究对象的条件、限制还是那么宽松,因而可先且放下研究对象,而尝试做些更“细”的工作把两个向量等价转化为具有某些性质的两个向量新任务。【寻找两个向量的规律】为了更加容易地找到两个向量的一般性质,可以先从一些小数据着手,试着找出有用的规律。比如当两个向量分别为,时,在直角坐标系中能被这两个向量表示的点的位置如下图:由此我们可以观察很多重要的性质:1、所有的点都在且只在直线x?2k?k?Z?和直线y?k?k?Z?上;2、在

      6、Y轴上,所有的点都出现且只出现在(0,4k)?k?Z?上;3、直线x?2k?k?Z?上的点都可通过平移Y轴而得到。于是我们归纳出任意两个不在Y轴上的向量(a1,b1)和(a2,b2)能表示的点的一般性质:所有的点分布在且只在直线x?gcd(a1,a2)?k(k?Z)和直线y?gcdb1(,b2)?k(k?Z)上;在Y轴上,所有的点都出现且只出现在(0,a1b2?a2b1gcd(a1,a2)k)?k?Z?上;直线x?gcd(a1,a2)?k(k?Z)上的点都可通过平移Y轴而得到。性质的证明:1、充分性(0,a1b2?a2b1gcd(a1,a2)k)?k?Z?位置上都有点的证明:对于任意的k?Z,令t1?a2gcd(a1,a2)k,t2?a1gcd(a1,a2)k,则(a1,b1)t1?(a2,b2)t2=(0,b1t1?b2t2)=(0,a1b2?a2b1gcd(a1,a2)a1b2?a2b1gcd(a1,a2)k)所以(0,证毕。k)?k?Z?位置上都有点。2、必要性在Y轴上,所有的点都只出现在(0,明:a1b2?a2b1gcd(a1,a2)k)?k?Z?上的证设在Y轴上能用这两个向量

      7、表示的任意一点为(0,y)?y?Z?,则必存在两个整数t1和t2,使得由式得t1a1?t2a2?t1a1a2?t2因为?t2为整数,所以a2|t1a1?a2gcd(a1,a2)a2gcd(a1,a2)|t1a1gcd(a1,a2)因为与a1gcd(a1,a2)互质,所以a2gcd(a1,a2)|t1令t1?a2gcd(a1,a2)k?k?Z?,则可以推出t2?a1gcd(a1,a2)k,所以y?t1b1?t2b2?a1b2?a2b1gcd(a1,a2)k所以必定存在一个整数k使得y?a1b2?a2b1gcd(a1,a2)k,也就是说在Y轴上,所有的点都只出现在(0,证毕。a1b2?a2b1gcd(a1,a2)k)?k?Z?上。综上所述,可以得出性质。证毕。【“约制”思想解决新任务】有了上面富有价值的性质之后,摆在眼前的问题便是,如何利用性质恰当地约束转化后的两个向量?虽然约束的方式不可胜数,但是绝大数对解题并没有什么任何作用。此时就要取其精华了。注意到在每一条有点的坚直直线上,一个显眼的性质是,上面的点都是相隔定长出现的。这催人从直觉上觉得,转化后的一个向量可以是一个坚直向量。这种感觉

      8、正确吗?正确!更重要的是,正因为这种“约制”思想,使解题的思路开始走出模糊、步入明晰。下面给出转化后其中一个向量是坚直向量的转化方法:设须要等价转化的两个向量分别为(a1,b1)和(a2,b2)。1、如果a1?0或者a2?0,则可令转化后的两个向量为(a1,b1)和(a2,b2);2、如果a1?0或者a2?0,综合性质和性质,可以大胆地约制其中一个向量为(0,a1b2?a2b1gcd(a1,a2),因为每一条直线x?gcd(a1,a2)?k(k?Z)上的点都是相隔|a1b2?a2b1gcd(a1,a2)|个单位出现的。此时,另一个向量应该是什么呢?由性质可以推测,如果能找到一个向量,只用这个向量能且只能表示每一条直线x?gcad1,a(2)?k(k?Z)上一个骑士能到达的点,那么问题就解决了。要找的这个向量的横坐标无疑可以是gcd(a1,a2),于是顺理成章地想到用扩展的欧几里德算法快速地找出两个整数p和q使得a1p?a2q?gcd(a1,a2)则向量(a1,b1)p?(a2,b2)q?(gcd(a1,a2),b1p?b2q)就是我们要找的另一个向量了。下面证明(gcd(a1,a2),b1p?b2q)和(a2,b2)。价于(a1,b1)和证明:1、对于任意的整数t1和t2,总存在两个整数T1和T2使得(a1,b1)t1?(a2,b2)t2?(gcd(a1,a2),b1p?b2q)T1?(0,的证明:对于任意的整数t1和t2,令整数T1?a1t1?a2t2gcd(a1,a2)a1b2?a2b1gcda(1,a2)T2。因为骑士通过向量(a1,b1)和(a2,b2)能够到达位置(a1,b1)t1?(a2,b2)t2?(a1t1?a2t2,b1t2?b2t2)和位置(gcd

      《骑士球员报告》由会员bin****86分享,可在线阅读,更多相关《骑士球员报告》请在金锄头文库上搜索。

      点击阅读更多内容
    TA的资源
  • 高考语文第一轮总复习 同步测试卷(五)实用类文本阅读课件

    高考语文第一轮总复习 同步测试卷(五)实用类文本阅读课件

  • 高考语文第一轮总复习 写作总论课件

    高考语文第一轮总复习 写作总论课件

  • 高考语文大一轮复习 第5部分 论述类文本阅读 第一节 理解文中重要词句含意2大考点课件

    高考语文大一轮复习 第5部分 论述类文本阅读 第一节 理解文中重要词句含意2大考点课件

  • 高考语文大一轮复习 第3部分 古代诗文阅读 专题三 默写常见的名句名篇课件

    高考语文大一轮复习 第3部分 古代诗文阅读 专题三 默写常见的名句名篇课件

  • 高考语文大一轮复习 第3部分 古代诗文阅读 专题二 第四节 鉴赏诗歌的艺术技巧课件

    高考语文大一轮复习 第3部分 古代诗文阅读 专题二 第四节 鉴赏诗歌的艺术技巧课件

  • 高中物理 第四章 力与运动 第一节 伽利略的理想实验与牛顿第一定律课件 粤教版必修1

    高中物理 第四章 力与运动 第一节 伽利略的理想实验与牛顿第一定律课件 粤教版必修1

  • 高中物理 第三章 研究物体间的相互作用 第三节 力的等效和替代课件 粤教版必修1

    高中物理 第三章 研究物体间的相互作用 第三节 力的等效和替代课件 粤教版必修1

  • 高中物理 第一章 运动的描述 第五节 速度变化的快慢 加速度课件 粤教版必修1

    高中物理 第一章 运动的描述 第五节 速度变化的快慢 加速度课件 粤教版必修1

  • 高中物理 第2章 能的转化与守恒章末复习方案与全优评估课件 鲁科版必修2

    高中物理 第2章 能的转化与守恒章末复习方案与全优评估课件 鲁科版必修2

  • 高中物理 42 实验:探究加速度与力、质量的关系课件 新人教版必修1

    高中物理 42 实验:探究加速度与力、质量的关系课件 新人教版必修1

  • 高中物理 31《受力分析》课件 新人教版必修1

    高中物理 31《受力分析》课件 新人教版必修1

  • 高中物理 22 匀变速直线运动的速度与时间的关系课件 新人教版必修1

    高中物理 22 匀变速直线运动的速度与时间的关系课件 新人教版必修1

  • 高中物理 14 用打点计时器测速度课件 新人教版必修1

    高中物理 14 用打点计时器测速度课件 新人教版必修1

  • 高中数学第一章导数及其应用1_5_1曲边梯形的面积课件新人教a版选修2_2

    高中数学第一章导数及其应用1_5_1曲边梯形的面积课件新人教a版选修2_2

  • 高中数学 第二章 随机变量及其分布 24 正态分布课件 新人教a版选修2-31

    高中数学 第二章 随机变量及其分布 24 正态分布课件 新人教a版选修2-31

  • 高中数学 第四章 圆与方程 42_1 直线与圆的位置关系课件 新人教a版必修21

    高中数学 第四章 圆与方程 42_1 直线与圆的位置关系课件 新人教a版必修21

  • 高中数学 第二章 随机变量及其分布 21_2 离散型随机变量的分布列(2)课件 新人教a版选修2-31

    高中数学 第二章 随机变量及其分布 21_2 离散型随机变量的分布列(2)课件 新人教a版选修2-31

  • 高中数学 第二章 统计 23_2 两个变量的线性相关课件 新人教a版必修3

    高中数学 第二章 统计 23_2 两个变量的线性相关课件 新人教a版必修3

  • 高中数学 第二章 统计 22_1 用样本的频率分布估计总体分布课件 新人教a版必修3

    高中数学 第二章 统计 22_1 用样本的频率分布估计总体分布课件 新人教a版必修3

  • 高中数学 第二章 统计 21_3 分层抽样课件2 新人教a版必修31

    高中数学 第二章 统计 21_3 分层抽样课件2 新人教a版必修31

  • 点击查看更多
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.