C#递归算法之打靶算法分析

2024-12-10 15:00:53

问题: 一个设计运动员打靶，靶一共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+……+i10=90)
       {
         //一种可能
       }
     }
     ---
   }
  }
}

但是这样做有两点不足:

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

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

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

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

1)当传入的当前打靶次数为小于1，或者大于规定次数的时候，应该退出第归函数的执行
2)当余下的打靶次数中每次都得满分，但能无法达到目标分数的时候，应该退出第归
3)如果没有上述两种情况，就应该执行第归

实现代码:

using System;

namespace Test
{
 /// <summary>
 /// ShotScore 的摘要说明。
 /// </summary>
 public class ShotScore
 {
  //总共有多少种可能性
  int SumRate = 0;
  //每次可能命中的几率范围
  int[] ScoreArray;
  //总共需要多少分
  int totalScore=0;
  //一共能打多少次
  int totalShot=0;
  //当前共打中环数
  public ShotScore(int[] sa,int ts,int t)
  {
   this.ScoreArray = sa;
   this.totalShot = ts;
   this.totalScore = t;
  }
  public int GetSum()
  {
   return SumRate;
  }
  public void Compute(int currentShot,int cNum)
  {
   //打多打少都不行
   if(currentShot<0||currentShot>totalShot)
   {
    return;
   }
   //以后枪枪都中10都不能满足条件,game over
   if(((totalShot-currentShot+1)*10)<(totalScore-cNum))
   {
    return;
   }
   //打够次数了并且总共达到了预期环数
   if(currentShot==totalShot)
   {
    //这种可能性成立
    SumRate++;
    return;
   }
   for(int i=0;i<ScoreArray.Length;i++)
   {
    Compute(currentShot+1,cNum+ScoreArray[i]);
   }

  }
 }
}

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

以上就是本文的全部内容，希望能给大家一个参考，也希望大家多多支持我们。

C#递归算法之快速排序

上两片第归算法学习: 1)递归算法之分而治之策略 2)递归算法之归并排序上一篇学习中介绍了了递归算法在排序中的一个应用:归并排序,在排序算法中还有一种算法用到了递归,那就是快速排序,快速排序也是一种利用了分而治之策略的算法,它由C.A.R发明,它依据中心元素的值,利用一系列递归调用将数据表划分成越来越小的子表.在每一步调用中,经过多次的交换,最终为中心元素找到最终的位置.与归并算法不同,快速排序是就地排序,而归并排序需要把元素在临时向量中拷贝,下面通过对以下向量进行排序来理解和加深快速排序算法
C#用递归算法解决八皇后问题

1.引子中国有一句古话,叫做"不撞南墙不回头",生动的说明了一个人的固执,有点贬义,但是在软件编程中,这种思路确是一种解决问题最简单的算法,它通过一种类似于蛮干的思路,一步一步地往前走,每走一步都更靠近目标结果一些,直到遇到障碍物,我们才考虑往回走.然后再继续尝试向前.通过这样的波浪式前进方法,最终达到目的地.当然整个过程需要很多往返,这样的前进方式,效率比较低下. 2.适用范围适用于那些不存在简明的数学模型以阐明问题的本质,或者存在数学模型,但是难于实现的问题. 3.应用场景在
C#递归算法寻找数组中第K大的数

1.概述国人向来喜欢论资排辈的,每个人都想当老大,实在当不成,当个老二,老三,老K也不错,您一定看过这样的争论: 两个人吵架,一个人非常强势,另外一个忍受不住了便说:"你算老几呀?",下面就通过这篇文章就是要解决找出老几的问题! 2.应用场景在向量V[first,last)中查找出第K大元素的值 3.分析如果利用排序算法将向量V排好序,那么第K大元素就是索引为v.length-k的元素了,这样能解决问题,但效率不高,因为这相当于为了歼灭敌人一个小队而动用了我们全军的力量,得不偿失
c#汉诺塔的递归算法与解析

从左到右 A B C 柱大盘子在下, 小盘子在上, 借助B柱将所有盘子从A柱移动到C柱, 期间只有一个原则: 大盘子只能在小盘子的下面. 如果有3个盘子, 大中小号, 越小的越在上面, 从上面给盘子按顺序编号 1(小),2(中),3(大), 后面的原理解析引用这里的编号. 小时候玩过这个游戏, 基本上玩到第7个,第8个就很没有耐心玩了,并且操作的动作都几乎相同觉得无聊. 后来学习编程, 认识到递归, 用递归解决汉诺塔的算法也是我除了简单的排序算法后学习到的第一种算法. 至于递归,简单来说
C#用递归算法解决经典背包问题

1.引子我们人类是一种贪婪的动物,如果给您一个容量一定的背包和一些大小不一的物品,裝到背包里面的物品就归您,遇到这种好事大家一定不会错过,用力塞不一定是最好的办法,用脑子才行,下面就教您如何解决这样的问题,以获得更多的奖品. 2.应用场景在一个物品向量中找到一个子集满足条件如下 : 1)这个子集加起来的体积大小不能大于指定阀值 2)这个物品子集加起来价值大小是向量V中所有满足条件1的子集中最大的 3.分析背包问题有好多版本,本文只研究0/1版本,即对一个物体要么选用,要么就抛弃,不能将一个
C#递归算法之归并排序

归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为: 1)划分子表 2)合并半子表首先我们来讨论归并算法,归并算法将一系列数据放到一个向量中,索引范围为[first,last],这个序列由两个排好序的子表构成,以索引终点(mid)为分界线,以下面一个序列为例 7,10,19,25,12,17,21,30,48 这样的一个序列中,分为两个子序列 7,10,19,25 和
c#斐波那契数列(Fibonacci)(递归,非递归)实现代码

//Main 复制代码代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Fibonacci{ class Program { static void Main(string[] args) { Console.WriteLine("Would you like to know which
C#用递归算法实现：一列数的规则如下: 1、1、2、3、5、8、13、21、34，求第30位数是多少

方法一:递归算法 /// <summary> /// 一列数的规则如下: 1.1.2.3.5.8.13.21.34求第30位数是多少, 用递归算法实现.(C#语言) /// </summary> /// <param name="pos"></param> /// <returns></returns> public int GetNumberAtPos(int pos) { if(pos==0||pos==1)
C# 递归函数详细介绍及使用方法

什么是递归函数/方法? 任何一个方法既可以调用其他方法也可以调用自己,而当这个方法调用自己时,我们就叫它递归函数或递归方法. 通常递归有两个特点: 1. 递归方法一直会调用自己直到某些条件被满足 2. 递归方法会有一些参数,而它会把一些新的参数值传递给自己. 那什么是递归函数?函数和方法没有本质区别,但函数仅在类的内部使用.以前C#中只有方法,从.NET 3.5开始才有了匿名函数. 所以,我们最好叫递归方法,而非递归函数,本文中将统一称之为递归. 在应用程序中为什么要使用递归?何时使用递归?如何
c#递归遍历文件夹示例

代码很简单,指定需要递归遍历的文件夹和遍历规则就要可以运行了复制代码代码如下: /// <summary>/// 递归获取文件夹目录下文件/// </summary>/// <param name="pathName">需要递归遍历的文件夹</param>/// <param name="fileRule">遍历规则『委托』</param>public static void LoopFol
C# 递归查找树状目录实现方法

1.递归查找树状目录复制代码代码如下: public partial class Form1 : Form { string path = @"F:\学习文件";//递归查找树状目录 public Form1() {递归查找树状目录 InitializeComponent(); } private void Form1_Load(object sender, EventArgs e)
C#递归算法之分而治之策略

1.分而治之的概念分而治之是一种使用递归解决问题的算法,主要的技巧是将一个大的复杂的问题划分为多个子问题,而这些子问题可以作为终止条件,或者在一个递归步骤中得到解决,所有子问题的解决结合起来就构成了对原问题的解决 2.分而治之的优点和缺点分而治之算法通常包括一个或者多个递归方法的调用,当这些调用将数据分隔成为独立的集合从而处理较小集合的时候,分而治之的策略将会有很高的效率,而在数据进行分解的时候,分而治之的策略可能会产生大量的重复计算,从而导致性能的降低. 3.画标尺程序的分析讲解画标

C#递归算法之打靶算法分析

相关推荐

随机推荐