好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

贪心算法均分纸牌问题.doc

1页
  • 卖家[上传人]:公****
  • 文档编号:395170025
  • 上传时间:2023-05-01
  • 文档格式:DOC
  • 文档大小:26KB
  • / 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,最后结果是对的,我们在移动过程中,只是改变了移动的顺序,而移动次数不便,因此此题使用贪心法可行的。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.