快捷導(dǎo)航

C#遞歸算法之打靶算法分析

更新時間：2016年06月16日 10:55:15 作者：Robin

這篇文章是對打靶算法分析，比較簡單，但邏輯一定要清楚，分析問題的方法一定要準確，有需要的朋友可以參考一下。

問題: 一個設(shè)計運動員打靶，靶一共10環(huán)，連開10環(huán)打中90環(huán)的可能性有多少？請用第歸算法實現(xiàn)？

分析：

1）每次打靶可能的得分范圍是什么？
靶有10個環(huán)，那么當打中時，分數(shù)可為1-10，如果未打中得分為0，所以每次打靶得分的范圍為0-10，共有11中可能
2）計算有多少種可能最直接的方法：

打10次靶，分別記錄這10次打靶過程，用循環(huán)來完成

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局都是一個人勝利的話，比賽這時候就可以宣告結(jié)束。而繼續(xù)下去就是浪費時間和精力

采用第歸的方法來解決上述問題

　　第歸就是自己調(diào)自己，如果沒有結(jié)束限制的話，第歸的效果和dead loop是一樣的，但是第歸正常情況下都會有結(jié)束標志，而且第歸的意義就在于完成循環(huán)層數(shù)不明確或者層數(shù)明確但是數(shù)值非常大的情形。使用它的注意點就是第歸函數(shù)肯定要具有一個或者一個以上的形參，沒有參數(shù)的第歸就形成了死循環(huán)。而且第歸中函數(shù)每次調(diào)用自己的時候，需要小心謹慎的控制參數(shù)。盡量防止死循環(huán)的產(chǎn)生，第歸和棧關(guān)系密切。

要實現(xiàn)上述功能，第歸函數(shù)要完成的功能主要有:

1)當傳入的當前打靶次數(shù)為小于1，或者大于規(guī)定次數(shù)的時候，應(yīng)該退出第歸函數(shù)的執(zhí)行
2)當余下的打靶次數(shù)中每次都得滿分，但能無法達到目標分數(shù)的時候，應(yīng)該退出第歸
3)如果沒有上述兩種情況，就應(yīng)該執(zhí)行第歸

實現(xiàn)代碼:

using System;

namespace Test
{
 /// <summary>
 /// ShotScore 的摘要說明。
 /// </summary>
 public class ShotScore
 {
  //總共有多少種可能性
  int SumRate = 0;
  //每次可能命中的幾率范圍
  int[] ScoreArray;
  //總共需要多少分
  int totalScore=0;
  //一共能打多少次
  int totalShot=0;
  //當前共打中環(huán)數(shù)
  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;
   }
   //打夠次數(shù)了并且總共達到了預(yù)期環(huán)數(shù)
   if(currentShot==totalShot)
   {    
    //這種可能性成立
    SumRate++; 
    return; 
   }
   for(int i=0;i<ScoreArray.Length;i++)
   {
    Compute(currentShot+1,cNum+ScoreArray[i]);
   }
   
  }
 }
}

最后結(jié)果為:92378
總結(jié)：這個問題主要考察了程序員的邏輯思考能力和對第歸函數(shù)的應(yīng)用。十分簡單。但邏輯一定要清楚，分析問題的方法一定要準確。

以上就是本文的全部內(nèi)容，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: