首页 > 打靶算法分析

打靶算法分析

问题: 一个设计运动员打靶,靶一共10环,连开10环打中90环的可能性有多少?请用第归算法实现?



分析:

1)每次打靶可能的得分范围是什么?

靶有10个环,那么当打中时,分数可为1-10,如果未打中得分为0,所以每次打靶得分的范围为0-10,共有11中可能

2)计算有多少种可能最直接的方法:

打10次靶,分别记录这10次打靶过程,用循环来完成

for(int i1=0;i1<=10;i++)

{

      
for(int i2=0;i2<=10;i2++)

      {

           
for(int i3=0;i3<=10;i3++)

           {

                  
---

                   
for(int i10=0;i10<=10;i10++)

                   {

                           
if(i1+i2+i3+dot.gif.+i10=90)

                           {

                                 
//一种可能

                           }

                   }

                  
---

           }

      }



但是这样做有两点不足:

1)如果题目改为连打1000枪,得分为900的可能性,估计这种写法的要哭了

2)考虑不周全,如果第一次打靶得分为0,还有9次机会,这9次机会,就要求枪枪都是满分,如果第二枪,得分不是10,那第三枪不用打就知道可能没有可能性了。就比如乒乓球比赛一样,5局3胜制,如果进行了3局都是一个人胜利的话,比赛这时候就可以宣告结束。而继续下去就是浪费时间和精力

2。采用第归的方法来解决上述问题

   第归就是自己调自己,如果没有结束限制的话,第归的效果和dead loop是一样的,但是第归正常情况下都会有结束标志,而且第归的意义就在于完成循环层数不明确或者层数明确但是数值非常大的情形。使用它的注意点就是第归函数肯定要具有一个或者一个以上的形参,没有参数的第归就形成了死循环。而且第归中函数每次调用自己的时候,需要小心谨慎的控制参数。尽量防止死循环的产生,第归和栈关系密切。

要实现上述功能,第归函数要完成的功能主要有:

 1)当传入的当前打靶次数为小于1,或者大于规定次数的时候,应该退出第归函数的执行

2)当余下的打靶次数中每次都得满分,但能无法达到目标分数的时候,应该退出第归

3)如果没有上述两种情况,就应该执行第归

实现代码:

ContractedBlock.gifExpandedBlockStart.gif

 1None.gifusing System;

 2None.gif

 3None.gifnamespace Test

 4ExpandedBlockStart.gifContractedBlock.gifdot.gif{

 5ExpandedSubBlockStart.gifContractedSubBlock.gif    /**//// 

 6InBlock.gif    /// ShotScore 的摘要说明。

 7ExpandedSubBlockEnd.gif    /// 


 8InBlock.gif    public class ShotScore

 9ExpandedSubBlockStart.gifContractedSubBlock.gif    dot.gif{

10InBlock.gif        //总共有多少种可能性

11InBlock.gif        int SumRate = 0;

12InBlock.gif        //每次可能命中的几率范围

13InBlock.gif        int[] ScoreArray;

14InBlock.gif        //总共需要多少分

15InBlock.gif        int totalScore=0;

16InBlock.gif        //一共能打多少次

17InBlock.gif        int totalShot=0;

18InBlock.gif        //当前共打中环数

19InBlock.gif        public ShotScore(int[] sa,int ts,int t)

20ExpandedSubBlockStart.gifContractedSubBlock.gif        dot.gif{

21InBlock.gif            this.ScoreArray = sa;

22InBlock.gif            this.totalShot = ts;

23InBlock.gif            this.totalScore = t;

24ExpandedSubBlockEnd.gif        }


25InBlock.gif        public int GetSum()

26ExpandedSubBlockStart.gifContractedSubBlock.gif        dot.gif{

27InBlock.gif            return SumRate;

28ExpandedSubBlockEnd.gif        }


29InBlock.gif        public void Compute(int currentShot,int cNum)

30ExpandedSubBlockStart.gifContractedSubBlock.gif        dot.gif{

31InBlock.gif            //打多打少都不行

32InBlock.gif            if(currentShot<0||currentShot>totalShot)

33ExpandedSubBlockStart.gifContractedSubBlock.gif            dot.gif{

34InBlock.gif                return;

35ExpandedSubBlockEnd.gif            }


36InBlock.gif            //以后枪枪都中10都不能满足条件,game over

37InBlock.gif            if(((totalShot-currentShot+1)*10)<(totalScore-cNum))

38ExpandedSubBlockStart.gifContractedSubBlock.gif            dot.gif{

39InBlock.gif                return;

40ExpandedSubBlockEnd.gif            }


41InBlock.gif            //打够次数了并且总共达到了预期环数

42InBlock.gif            if(currentShot==totalShot)

43ExpandedSubBlockStart.gifContractedSubBlock.gif            dot.gif{                

44InBlock.gif                //这种可能性成立

45InBlock.gif                SumRate++;    

46InBlock.gif                return;    

47ExpandedSubBlockEnd.gif            }


48InBlock.gif            for(int i=0;i<ScoreArray.Length;i++)

49ExpandedSubBlockStart.gifContractedSubBlock.gif            dot.gif{

50InBlock.gif                Compute(currentShot+1,cNum+ScoreArray[i]);

51ExpandedSubBlockEnd.gif            }


52InBlock.gif            

53ExpandedSubBlockEnd.gif        }


54ExpandedSubBlockEnd.gif    }


55ExpandedBlockEnd.gif}


56None.gif
最后结果为:92378

总结:这个问题主要考察了程序员的逻辑思考能力和对第归函数的应用。十分简单。但逻辑一定要清楚,分析问题的方法一定要准确。

转载于:https://www.cnblogs.com/jillzhang/archive/2007/02/01/636889.html

更多相关:

  •         Apache POI是一个开源的利用Java读写Excel,WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码:package com.xing.studyTest.poi;import java.io.FileInputSt...

  • 要取得[a,b)的随机整数,使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。 要取得a到b之间的...

  • 利用本征图像分解(Intrinsic Image Decomposition)算法,将图像分解为shading(illumination) image 和 reflectance(albedo) image,计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 题目:面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制: 1 <= 数组长度 <= 50000 解题: cl...

  • 题目:二叉搜索树的后序遍历序列 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树:      5     /    2   6   /  1   3示例 1: 输入: [1,6,3,2,5] 输出...

  • Ctrl+Shift+X 搜索AutoScssStruct4Vue   如上图直接右键-autoScssStruct(你都不需要聚焦到template节点) 直接就给你妥妥的把SCSS代码写好了,如果你还是嫌弃点右键太麻烦了太累了(泥马~这也太懒了吧,要不要AI帮你写代码?)我们还可以设置快捷键Ctrl+Alt+S,自动插入结构...

  • 性能 是rocksdb的优点,活跃的社区十分欢迎大家对各自使用rocksdb 过程中性能相关的疑惑点进行提问。提问的时候如果能够提供更多,更详细的信息 是可以增加快速得到恢复回复的概率。当然,性能是一个非常广泛且有巨量影响因素的话题,单纯从一个简单的描述是无法进行更进一步的性能问题讨论的。 社区从两方面给出了如下 性能相关issue...

  • 我们在使用vim打开一个文件的时候,经常会弹出下面的界面 为什么会出现这个界面呢 用vim编辑文件(如这里的test.txt)时,系统会自动产生一个文件叫.test.txt.swp.如果正常退出,此文件会被自动删去.如果上次非正常退出,如果再编辑它,系统会首先查.test.txt.swp 是否存在,如果存在,就会问你如何处理....

  • P80  引用自己创建的模块 如果你使用的是Linux/BSD shell,那么按Ctrl-d退出提示符。如果是在Windows命令行中,则按Ctrl-z再按Enter。   转载于:https://www.cnblogs.com/linzh104/p/4076852.html...

  • Spring不但支持自己定义的@Autowired注解,还支持几个由JSR-250规范定义的注解,它们分别是@Resource、@PostConstruct以及@PreDestroy。  @Resource的作用相当于@Autowired,只不过@Autowired按byType自动注入,而@Resource默认按 byName自动注...