C\#알고리즘 의 큰 소 가 새끼 소 를 낳 는 문제 의 효율 적 인 해결 방법

질문:
갓 태 어 난 송아지 한 마리 가 4 년 뒤에 송아지 한 마 리 를 낳 고 이후 매년 한 마 리 를 낳는다.현재 갓 태 어 난 송아지 한 마리 가 있 는데,20 년 후 에는 모두 몇 마리 가 있 느 냐 고 물 었 다.
생각:
이런 자식 은 손 자 를 낳 고,손 자 는 아들 을 낳 고,자손 의 문 제 는 순환 안에 순환 하 는 내장 순환 이 있어 서,한눈 에 보면 첫 번 째 문제 라 는 것 을 알 수 있다.
그래서 첫 번 째 버 전이 나 왔 다.

public long Compute1(uint years)
{
  //    1  
  long count = 1;
  if (years <= 3)
  {
    return count;
  }
  int i = 4;
  while (i <= years)
  {
    int subYears = i - 3;
    count += Compute1((uint)(subYears));
    i++;
  }
  return (long)count;
}

그러나 이런 순환 하 는 방법 은 cpu 형 을 지치 게 해 야 합 니 다.당신 은 100 년 동안 위의 방법 을 테스트 하 는 것 을 믿 지 않 습 니 다.저 는 한참 을 기 다 렸 지만 결과 가 없습니다.개선 하 세 요.늙 은 소(소 마왕)와 송아지(빨 간 아이,할머니 의 꼬치)는 똑 같은 출산 능력 을 가지 고 있 습 니 다.그들의 출산 곡선 은 같 습 니 다.그래서 소 는 늙 은 소의 출산 경험 을 재 활용 할 수 있 습 니 다.그러면 소 한 마리 가 n 년 째 에 몇 마리 가 공생 하 는 지 반복 적 으로 계산 하 는 문 제 를 해결 할 수 있 습 니 다.나이 가 많 을 때 cpu 의 연산 횟수 를 현저히 낮 출 수 있 습 니 다.다음은 이러한 사고방식 을 바탕 으로 하 는 알고리즘 입 니 다.

Hashtable table = new Hashtable();
public long Compute(uint years)
{
  //    1  
  long count = 1;
  if (years <= 3)
  {
    return count;
  }
  int i = 4;
  while (i <= years)
  {
    int subYears = i - 3;
    if (table.ContainsKey(subYears))
    {
      count = (long)table[subYears];
    }
    else
    {
      count += Compute((uint)(subYears));
    }
    if (!table.ContainsKey(subYears))
    {
      table.Add(subYears, count);
    }
    i++;
  }
  return (long)count;
}

테스트 프로그램 으로 위의 추론 을 테스트 해 보 세 요.결 과 는 다음 과 같 습 니 다.
1)years 를 입력 하 는 것 이 비교적 어 릴 때 첫 번 째 방법 은 시간 이 짧 지만 이들 의 시간 은 기본적으로 하나의 수량 급 에 있다.
2)years 를 입력 하 는 것 이 비교적 클 때 예 를 들 어 40 이상 의 경우 두 번 째 알고리즘 은 첫 번 째 성능 보다 100 이상 이 고 years 를 입력 할 수록 성능 이 현격 하 다.
테스트 결과 캡 처:
20 년

50 년

원본 프로그램 및 테스트 프로그램:http://xiazai.jb51.net/201606/yuanma/HowMoneyCows(jb51.net).rar
이상 이 바로 본문의 전체 내용 입 니 다.여러분 께 참고 가 될 수 있 기 를 바 랍 니 다.여러분 들 도 저 희 를 많이 응원 해 주시 기 바 랍 니 다.