C#递归算法之打靶算法分析
|
问题: 一个设计运动员打靶，靶一共10环，连开10环打中90环的可能性有多少？请用第归算法实现？
分析： 1）每次打靶可能的得分范围是什么？ 打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的可能性，估计这种写法的要哭了 采用第归的方法来解决上述问题 第归就是自己调自己，如果没有结束限制的话，第归的效果和dead loop是一样的，但是第归正常情况下都会有结束标志，而且第归的意义就在于完成循环层数不明确或者层数明确但是数值非常大的情形。使用它的注意点就是第归函数肯定要具有一个或者一个以上的形参，没有参数的第归就形成了死循环。而且第归中函数每次调用自己的时候，需要小心谨慎的控制参数。尽量防止死循环的产生，第归和栈关系密切。 要实现上述功能，第归函数要完成的功能主要有: 1)当传入的当前打靶次数为小于1，或者大于规定次数的时候，应该退出第归函数的执行 实现代码:
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 以上就是本文的全部内容，希望能给大家一个参考，也希望大家多多支持编程小技巧。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
