java蓝桥杯dfs_第七届 蓝桥杯决赛 Java B组 打靶 解题报告(DFS,回溯,全排列)-Go语言中文社区...

发布时间:2021-11-30 06:54:22

题目:


打靶


小明参加X星球的打靶比赛。


比赛使用电子感应计分系统。其中有一局,小明得了96分。


这局小明共打了6发子弹,没有脱靶。


但望远镜看过去,只有3个弹孔。


显然,有些子弹准确地穿过了前边的弹孔。


不同环数得分是这样设置的:


1,2,3,5,10,20,25,50


那么小明的6发子弹得分都是多少呢?有哪些可能情况呢?


下面的程序解决了这个问题。


仔细阅读分析代码,填写划线部分缺失的内容。


public class Main


{


static void f(int[] ta, int[] da, int k, int ho, int bu, int sc)


{


if(ho<0 || bu<0 || sc<0) return;


if(k==ta.length){


if(ho>0 || bu>0 || sc>0) return;


for(int i=0; i


for(int j=0; j


System.out.print(ta[i] + " ");


}


System.out.println();


return;


}


for(int i=0; i<=bu; i++){


da[k] = i;


f(ta, da, k+1, __________________ , bu-i, sc-ta[k]*i); // 填空位置


}


da[k] = 0;


}


public static void main(String[] args)


{


int[] ta = {1,2,3,5,10,20,25,50};


int[] da = new int[8];


f(ta, da, 0, 3, 6, 96);


}


}注意:只填写划线处缺少的内容,不要填写已有的代码或符号,也不要填写任何解释说明文字等。


本题结论有待验证,证明后更改,主要纠结于3代表总共三个弹孔,还是三次重复穿过弹孔


如果代表总共三个弹孔 ?答案:i > 0 ?? ho - 1: ho


如果代表总共三次重复穿过:答案:i > 1 ? ho - (i - 1) : ho


分析:


1.main函数分析:


public static void main(String[] args) {


int[] ta = { 1, 2, 3, 5, 10, 20, 25, 50 };//记录分值


int[] da = new int[8];//记录每个分值的个数


f(ta, da, k,ho,bu, sc);


f(ta, da, 0, 3, 6, 96);//第一二个参数不用解释,从ta第0位开始枚举,3个重复弹孔,上限6个分数,共96分


}


2.递归函数分析:


static void f(int[] ta, int[] da, int k, int ho, int bu, int sc) {


if (ho < 0 || bu < 0 || sc < 0)//最后ho bu sc 都大于0 才有递归的必要(剪枝)


return;


if (k == ta.length) {// 当k枚举完ta数组(类似for循环的i),开始判断


if (ho > 0 || bu > 0 || sc > 0)// 三个参数都等于0,说明递归过程会把已经枚举的值扣除相应的ho,bu,sc值


return;


for (int i = 0; i < da.length; i++) {//输出每个分值


for (int j = 0; j < da[i]; j++)


System.out.print(ta[i] + " ");


}


System.out.println();


return;


}


for (int i = 0; i <= bu; i++) {//bu是分数个数的上限


da[k] = i;//每一个分值从0~bu(即6)进行深搜枚举


f(ta, da, k + 1, i > 1 ? ho - (i - 1) : ho, bu - i, sc - ta[k] * i); // 填空位置


}


/*刚开始直接填0,发现每个答案加起来就是96,唯一不同的就是,有的弹孔数不是3个


*可见,ho的值就是用来筛选的且要扣除有几个重复的,由da数组可知每个分值是记录每个分值个数的


*所以我推出ho,当分值的个数大于1,只要减去每个分值的个数扣掉1之后的值(即重复的数量),如da[1] = 3,那么我就ho扣掉2


*最后运行,果然,得出了三组数据且只有三个弹孔,完美解决


* */


da[k] = 0;//分值每种情况枚举完之后要回溯,清零


}


把ho填0,得出的结果:



推出代码后结果:



所以应该填入:i > 1 ? ho - (i - 1) : ho


完整代码:


public class Main {


static void f(int[] ta, int[] da, int k, int ho, int bu, int sc) {


if (ho < 0 || bu < 0 || sc < 0)


return;


if (k == ta.length) {


if (ho > 0 || bu > 0 || sc > 0)


return;


for (int i = 0; i < da.length; i++) {


for (int j = 0; j < da[i]; j++)


System.out.print(ta[i] + " ");


}


System.out.println();


return;


}


for (int i = 0; i <= bu; i++) {


da[k] = i;


f(ta, da, k + 1, i > 1 ? ho - (i - 1) : ho, bu - i, sc - ta[k] * i); // 填空位置


}


da[k] = 0;


}


public static void main(String[] args) {


int[] ta = { 1, 2, 3, 5, 10, 20, 25, 50 };


int[] da = new int[8];


f(ta, da, k,ho,bu, sc);


f(ta, da, 0, 3, 6, 96);


}


}


总结:


主要还是考深搜还有回溯,跟全排列有点像,类似全排列的进阶







相关资源:解决python3.7中opencv模块cv2安装问题

相关文档

  • OC中的MRC与ARC机制
  • 2017最新婚礼策划方案及流程
  • 一道让你拍案叫绝的算法题
  • 星晴
  • shapenet网络_CVPR 2019 | GeoNet:基于测地距离的点云分析深度网络
  • 初二开学反思作文
  • 域名和网址有什么不同
  • 关于洛克的故事
  • 关于秋天好词好句
  • Mybatis使用TypeHandler实现数据的加解密转换
  • 猪蹄怎么做好吃?猪蹄的做法大全(4)
  • 《长安晓望,寄崔补阙》原文注释
  • 黑马程序员--Java IO流
  • 精选新学期学习计划范文汇总8篇
  • 巴诺巴奇果冻面膜哪个颜色好?巴诺巴奇果冻面膜不同颜色功效
  • 太晚睡觉等于自杀,你晚上一般什么时候睡觉?
  • 炸面窝的方法
  • 员工五一劳动节演讲稿范文
  • Linux:CentOS 7 解压 7zip 压缩的文件
  • 苹果11pro激活步骤
  • Hive和hbase的区别
  • 阴虚内热要怎么调理
  • 牛初乳的营养价值与功效
  • 乐划锁屏有什么用
  • 腾讯云视频加密
  • 新手学车起步的技巧有哪些
  • 某村“不忘初心、牢记使命”主题教育学习工作方案
  • 数据建模应用
  • 丁姓高分男孩名字
  • 骏捷汽车保养常识
  • 猜你喜欢

  • 不同的蔬菜喷不同的叶面肥
  • 极简待办怎么设置壁纸-极简待办设置壁纸方法
  • 发动机排气管项目立项备案申请报告
  • 庐山的导游词
  • 工程部门年度总结
  • 覃雄油画作品欣赏
  • 管建刚作文指导之——第一节说话力研究
  • 实验5 FTP和WWW服务器的配置
  • 上海斐优投资管理有限公司企业信用报告-天眼查
  • C++中的前置声明(Forward Declaration)
  • 2014年中山大学公共管理硕士MPA土地资源管理行政管理社会保障考研真题考研参考书,考研复试线-育明广州分校
  • 【推荐】写给同桌的你优秀作文-范文word版 (5页)
  • 第四季度工作总结2000字
  • 对比4G和5G的MIMO多天线传输的基本过程(加扰、层映射、预编码)
  • 中华文化的勃兴(二)ppt1 人教版
  • 提高预应力张拉施工质量的控制方法
  • 天津市蓟县福农鑫源农作物种植专业合作社企业信用报告-天眼查
  • 关于加强惩防体系建设的几点思考(精)
  • 博美犬小时候的图片大全欣赏
  • 精选循环系统病理生理学PP课件资料
  • 最新人美版美术五年级下册第19课《昨天、今天和明天》教案.doc
  • 第1节 抗生素的合理使用
  • 高二化学复习知识点
  • 人教版高中化学选修四高二化学期末复*盐类的水解巩固练*
  • 【扫盲】Multitarget-tracker多目标跟踪
  • 青少年逆反心理透析及对策
  • TOD SOD AOD三大规划模式
  • 学*k12精品新版高中数学北师大版必修1*题:第二章函数 检测
  • 【感谢信】给朋友的感谢信3篇
  • eAAA桥涵水文课件第四章
  • 7月去云南旅游必备物品
  • 山西省2012届高考政治复* 第2单元第5课第2课时 新时代的劳动者课件 新人教版必修1
  • 遗失的美好
  • 2015年天津科技大学082203发酵工程考研参考书专业课考研真题考录比复试线
  • 复旦大学微观经济学2004真题及答案
  • 中美物流成本比较分析及启示_索沪生
  • 2019年兼并合同公证书-优秀word范文 (1页)
  • 钢筋制安,混凝土浇筑,模板制安劳务分包合同
  • 【部编】最新2018年春部编人教版小学一年级语文下册:《吃水不忘挖井人》练习-精品试卷
  • 最新 初中语文阅读教学中设疑提问的方法-精品
  • 王衍识石勒是什么典故
  • 小学数学北师大2011课标版四年级《比大小》教学设计
  • 电脑版