C\#재 귀 알고리즘 의 사격 알고리즘 분석

문제:한 설계 선수 가 과녁 을 쏘 았 는데 과녁 은 모두 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 이다.
요약:이 문 제 는 주로 프로그래머 의 논리 적 사고력 과 제 귀 함수 에 대한 응용 을 고찰 했다.매우 간단 하 다.그러나 논 리 는 반드시 명확 해 야 하고 문 제 를 분석 하 는 방법 은 반드시 정확 해 야 한다.
이상 이 바로 본문의 전체 내용 입 니 다.여러분 께 참고 가 될 수 있 기 를 바 랍 니 다.여러분 들 도 저 희 를 많이 응원 해 주시 기 바 랍 니 다.