
贪心算法均分纸牌问题.doc
1页贪心算法均分纸牌问题[均分纸牌]有N堆纸牌,编号分别为1,2,…,n每堆上有若干张,但纸牌总数必为n的倍数•可以在任一堆上取若干张纸牌,然后移动移牌的规则为:在编号为1上取的纸牌,只能移到编号为2的堆上;在编号为n的堆上取的纸牌,只能移到编号为n-1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多例如:n=4,4堆纸牌分别为:①9②8③17④6移动三次可以达到目的:从③取4张牌放到④再从③区3张放到②然后从②去1张放到①输入输出样例:498176屏幕显示:3算法分析:设a[i]为第I堆纸牌的张数(0<=l<=n),v为均分后每堆纸牌的张数,s为最小移动次数我们用贪心算法,按照从左到右的顺序移动纸牌如第I堆的纸牌数不等于平均值,则移动一次(即s加1),分两种情况移动:1•若a[i]>v,则将a[i]-v张从第I堆移动到第I+1堆;2•若a[i] 如n=3,三堆指派数为1227,这时v=10,为了使第一堆为10,要从第二堆移9张到第一堆,而第二堆只有2张可以移,这是不是意味着刚才使用贪心法是错误的呢?我们继续按规则分析移牌过程,从第二堆移出9张到第一堆后,第一堆有10张,第二堆剩下-7张,在从第三堆移动17张到第二堆,刚好三堆纸牌都是10,最后结果是对的,我们在移动过程中,只是改变了移动的顺序,而移动次数不便,因此此题使用贪心法可行的。
点击阅读更多内容
相关文档
小学田径教学的现状与发展趋势分析.docx
城区集中热电联产供暖项目经济效益和社会效益分析报告(模板范文).docx
医药产业园项目经济效益和社会效益分析报告(范文模板).docx
工业机器人技术发展对社会道德规范的影响.docx
完善审计机制对财政资金使用效率的影响.docx
学生情感因素在文本误读中的作用.docx
基于大数据的财政资金流向监控与预警机制.docx
城市低效土地再开发的现状与挑战.docx
压缩机生产线项目经济效益和社会效益分析报告(范文).docx
县级预算执行审计对财政资金提升效益的必要性与挑战.docx
成人学习者特点与在线学习需求的差异化分析.docx
当前高校辅导员职能的演变与挑战.docx
当前高校课程思政实施效果的评价与反思.docx
当前高中生涯指导实施中存在的主要问题与挑战.docx
当前物流企业发展存在的问题及根源.docx
当前实验室安全事故的根源与防控对策.docx
废旧铜综合利用项目经济效益和社会效益分析报告(参考范文).docx
基础会计课程混合式教学的概念与发展趋势.docx
基于元宇宙的微课互动教学模式创新探索.docx
小微企业融资难题的现状与成因分析.docx
猜您喜欢
作物智能生产与管理技术.pptx
仓储与邮政业的绿色转型策略.pptx
桥梁伸缩缝施工汇报材料.docx
新人教版2019-2020学年八年级上学期物理期中检测试卷.doc
大班安全公开课会说话的安全标志教案反思.docx
浙江省建筑三类人员安全员C证考试内容及考试题附答案(100题)第43期.docx
高三化学一轮复习-化学反应速率和化学平衡四教学设计.doc
2022江苏省三级公共营养师专业能力考试试题.docx
仓储与邮政业的绿色包装与循环利用研究.pptx
2022年《打电话》教案范文合集8篇.doc
2023年英文感谢信的英文感谢信感谢父母(4篇).doc
班级读书工作计划.docx
日光温室无公害苋菜栽培技术.doc
宁夏重点小学一年级语文【上册】能力检测试题 附解析.doc
企业开工领导致辞.doc
2018-2019学年高一地理上学期第三次月考试题 (III).doc
小班益智区目标.doc
生物质无醛环保胶黏剂项目建议书写作模板.doc
给爸爸的一封戒烟信.doc
操作系统生产与消费者问题.docx
相似文档 更多>
正为您匹配相似的精品文档

最近下载




![河南新冠肺炎文件-豫建科[2020]63号+豫建科〔2019〕282号](http://img.jinchutou.com/static_www/Images/s.gif)






